-
基于二阶矩阵的优化问题(一)线搜索策略(附matlab代码)
2020-06-01 16:54:14优化算法的问题在于如何从XkX_kXk更新到Xk+1X_{k+1}Xk+1、确定步长公式(详见 基于二阶矩阵的优化问题(二))和判定迭代终止的条件(详见 于二阶矩阵的优化问题(三))是我们需要在不精确搜索中解决的问题。...非精确线搜索更新
优化算法的问题在于如何从更新到、确定步长公式详见 基于二阶矩阵的优化问题(二)和判定迭代终止的条件(详见 于二阶矩阵的优化问题(三))是我们需要在不精确搜索中解决的问题。
我们有两种方法来解决这个问题:
1.线搜索策略
2.信任域策略线搜索策略
我们选择一个下降方向来使得lost function慢慢迭代至最小值。
这是的更新公式,可以看到,我们需要知道其和的值才能进行迭代(代表了步长、代表下降方向),第一种方法就是走一个最速下降方向(负梯度),而走一个极其猥琐的距离,但这种方法在函数比较诡异时效果较差(如rosenbrock函数),但在某些复杂问题时,我们还是使用最速下降来解决问题,详见 大规模的优化问题(一)。
最速下降+牛顿法
让我们来列一下牛顿方向的式子:
在这里,我们要假设这里的二次型()是正定的,这是函数的局部二次型构型就是碗状的,我们可以求出这里的pk(下降方向):
;
这边的就是这里的局部二次型的顶点,在牛顿法中,我们可以一步就走到这个点。
ok,这个问题的理论情况是这样的,但在实际问题中,我们不可能去求一个hessian矩阵的逆矩阵,所以,我们把移到等式的左边,变成:,
这个等式实际上就等于Ax=b的形式,这边我们只需要求解一个线性方程组即可。
以上为牛顿法的基础理论,下面看一下牛顿法的实现步骤:可以看到,牛顿法的意义在于足够靠近真解时的快速收敛,我们先走几部最速下降法,使得足够靠近阈值,后再启动牛顿法,会有较好的效果,即保证了算法的效率,有保证了算法的鲁棒性。
下面是最速下降法+牛顿法matlab实现的代码:
function [x1] = min_hybrid(func, dfunc, d2func ,x, MAX_IT ,eps, threshold) err = 10.0; steps = 0; alpha = 1.0; //最速下降法 while (err > threshold)//此处阈值需要调参 f = func(x); g = dfunc(x); p = -g; step=step+1; alpha = backtracking(@func, x, f, g, p, 1e-4, 0.8, alpha * 2.0); x = x + alpha * p; if (steps > MAX_IT) break; end error = norm(g); end //牛顿法 while (error > eps) f = func(x); g = dfunc(x); G = d2func(x); p = -G\g; x = x + p; step=step+1; if (steps > MAX_IT) break; end error = norm(g); end x1=x; end function alpha = backtracking(func, x, f, df, p, c, rho, alpha0) alpha = alpha0; while (func(x(1) + alpha * p(1), x(2) + alpha * p(2)) > f + c * alpha * df' * p) alpha = alpha * rho; end end
其中func、gfunc和hess需要自行解析计算,func的接口只有x,gfunc和hess没有输入参数。(这边要注意,使用wolfe条件时,alpha可以恒取1)
启发
牛顿法实际上是在改进真解,用少量次数的迭代即可实现一阶方法上千次的迭代效果,首先系数矩阵必须要正定,否则牛顿法不能保证收敛。
修正牛顿法
牛顿法最大的问题在于,系数矩阵必须要正定,那么如果系数矩阵不正定,则将改成正定(modification),下面是修改系数矩阵的算法框架:
初值
for k=0,1,2,…
令 ,其中为修正项,使得充分正定。
求解
(其中在wolfe条件时可以取1)
end好了,现在我们需要解决四件事,就可以实现修正牛顿法的运用:
1.判定是否正定;
2.解方程组;
3.如何构建;
4.如何使得最小;特征值修正(eigenvalue modification)
谱分解
首先我们先对对称矩阵做正交分解(householder等),得到正交阵Q,和对角阵V,然后就可以得到的所有特征值,我们知道,正定矩阵所有的特征值都是充分大的正数,即,当出现负的特征值时,我们添加一个修正项使得特征值大于等于δ。此时的的Frobenius范数最小。
即用Matlab中的eig()函数求出特征值后,直接对特征值修改即可。单位增量法
谱分解的问题在于,其真正改变的是特征值,所以对的改动是比较大的,当我们不希望发生很大的变动时,我们就使用单位增量法。单位增量法直接对添加一个修正项,使得其正定。
首先,我们对进行cholesky分解:L是对角线均为1的下三角阵,D为对角阵,若不定,D的对角元会过大。
下面是单位增量法的Matlab代码:function[L,D]=modification(A,delta,beta) if(norm(A-A')>eps return; end n=size(A,1); d=zero(n,1); L=zero(n); C=zero(n); theta=zeros(n,1); for j = 1:n C(j,j) = A(j,j)-sum(d(1:j-1)'.*L(j,1:j-1).^2); for i = j+1:n C(i,j) = A(i,j)-sum(d(1:j-1)'.*L(i,1:j-1).*L(j,1:j-1)); absjj=abs(C(i,j)); if theta < abs(C(i,j)) theta = abs(C(i,j)); end end d(j) = max([abs(C(j,j)), (theta/beta)^2, \delta]); for i = j+1:n L(i,j) = C(i,j)/d(j); end L(j,j) = 1.0; end D=diag(d); end
单位增量法得到的和在形式上很接近,但其特征值完全不同,所以两种方法各有优势,可根据情况自行选择。
拟牛顿法
如果你的数据维数过大或者无法承受计算二阶矩阵的消耗,这边也可以使用拟牛顿法来计算下降方向,当然拟牛顿法也有其缺陷,下面我们来分析一下。
首先我们介绍一下割线法,用弦的斜率近似代替目标函数的切线斜率,下面给出割线法的公式这在本质上是计算函数的数值微分,但这种方法在接近收敛时会出现数值不稳定的情况,当接近收敛时,舍入误差占比变大,数值会发生很大的起伏变化。
由此我们可以推导出拟牛顿法的公式这里不在需要计算其hessian矩阵,由于hessian矩阵是级别的,拟牛顿法对于大规模问题来说是非常节约资源的方法。
于是我们知道了
现在的情况与牛顿发不同,并不知道,这是一个不定方程组:
这里的是阶的矩阵,而我们只有n个方程,下面有SR1、BFGS等方法来求解。
详见 拟牛顿法的下降方向计算(一)
此时,局部二次型的方程变为;
这里还有一条路,就是去构建,这时我们不需要再去求解线性方程组(这里设),这里=I时,就是最速下降。
这里有拟BFGS等方法来求解,详见 拟牛顿法的下降方向计算(二)
-
论文中常用的一些矩阵求导公式和二阶范数公式
2017-08-11 19:00:401 二阶范数 ||A||2=tr(AAT) ||A||^2 = tr(AA^T) \quad\quad\quad...2 矩阵求导基本公式(等式两边同时去除tr,公式不变):∂tr(AX)∂X=AT \frac{\partial tr(AX)}{\partial X} = A^T \quad\quad\quad\quad\quad\qua1 二阶范数
||A||2=tr(AAT)
2 矩阵求导基本公式(等式两边同时去除tr,公式不变):tr(A)=tr(AT)∂tr(AX)∂X=AT∂tr(AX)∂XT=A∂tr(AXB)∂X=(BA)T=ATBT
3 则简单公式均可以推导出来:∂tr(XTAX)∂X=AX+(XTA)T=(AT+A)X∂tr(XTAX)∂XT=(AX)T+XTA=XT(AT+A)∂tr(ABATC)∂A=(BATC)T+CAB=CTABT+CAB -
截断光束的二阶矩矩阵
2021-02-09 05:46:57采用复高斯展开法和维格纳分布函数(WDF),推导出了截断光束的二阶矩矩阵通过大气湍流的传输公式。研究表明,将硬边光阑的复高斯展开函数引入z=0平面处的WDF中,能够避免截断光束二阶矩的积分发散问题,得到z=0平面处... -
二阶龙格库塔公式推导_从零推导斐波那契数列的通项公式
2020-12-07 18:22:48学习阶段:高中数学。前置知识:等比数列。1. 斐波那契数列的定义斐波那契数列大部分人都耳熟能详,就是 ,...成熟的推导通项公式的方法有特征方程法、生成函数/母函数法、矩阵对角化法等等,但这些方法“集成度”过...学习阶段:高中数学。
前置知识:等比数列。
1. 斐波那契数列的定义
斐波那契数列大部分人都耳熟能详,就是
,每一项都是前两项之和。我们用数列的递推公式严格定义一下:
2. 从零推导斐波那契数列的通项公式
相信也有不少的人见过斐波那契数列的通项公式,感觉还是比较复杂的,有什么
啊,
特征方程法、生成函数/母函数法、矩阵对角化法等等,但这些方法“集成度”过高,需要很多其他知识的铺垫,理解起来不是很清晰。现在我们忘记这些方法,从零开始推导一下它的通项公式,便于大家记(zhuang)忆(bi)。次方等等的复杂结构。成熟的推导通项公式的方法有
等差数列
和等比数列
我们已经研究透彻了,我们一般的思路就是把待求数列化归为这两种数列。
2.1 二阶递推化为一阶递推
首先,
这个鬼二阶递推公式,似乎没办法化归啊?没事,我们暴力假设它能变形为
这种等比数列的形式(有人问我这个暴力假设怎么来的。呃,这要一点凑的数学直觉,就像凑不等式和凑微分。把递推式子凑出等比数列的形式,还要每项都能对应上,差不多只能设出这种形式),然后看看能不能把常数
与
求出来。对应系数,有:
成功解出
,说明
和
是可以解出来的嘛!
然后利用等比数列的性质,有
成功地把二阶的递推式化成了一阶递推式!
2.2 一阶递推化为通项公式
现在故技重施,还是暴力假设把它化为等比数列的形式,巧妙地设计待定的系数:
因为
设
得
哇哦!这下子
的通项已经被彻底地解出来了,剩下的只是繁琐的计算:
现在要把
的值全部带进去。
的值有两个,随便选一个就行了(结果是一样的),我选
,则
,立刻得到:
其实,这个过程正是特征方程法的由来。待定系数法是如此强大!
-
python中函数不包括参数函数二阶导数公式_如何在Tensorflow中计算所有二阶导数(只有Hessian矩阵的对角线)?...
2020-12-07 14:37:04我有一个损失值/函数,我想计算所有关于张量f(大小为n)的二阶导数.我设法使用了两次tf.gradients,但是当第二次应用它时,它会对第一个输入中的导数求和(请参阅我的代码中的second_derivatives).我还设法检索Hessian...我有一个损失值/函数,我想计算所有关于张量f(大小为n)的二阶导数.我设法使用了两次tf.gradients,但是当第二次应用它时,它会对第一个输入中的导数求和(请参阅我的代码中的second_derivatives).
我还设法检索Hessian矩阵,但我想只计算它的对角线以避免额外的计算.
import tensorflow as tf
import numpy as np
f = tf.Variable(np.array([[1., 2., 0]]).T)
loss = tf.reduce_prod(f ** 2 - 3 * f + 1)
first_derivatives = tf.gradients(loss, f)[0]
second_derivatives = tf.gradients(first_derivatives, f)[0]
hessian = [tf.gradients(first_derivatives[i,0], f)[0][:,0] for i in range(3)]
model = tf.initialize_all_variables()
with tf.Session() as sess:
sess.run(model)
print "\nloss\n", sess.run(loss)
print "\nloss'\n", sess.run(first_derivatives)
print "\nloss''\n", sess.run(second_derivatives)
hessian_value = np.array(map(list, sess.run(hessian)))
print "\nHessian\n", hessian_value
我的想法是tf.gradients(first_derivatives,f [0,0])[0]可以检索例如关于f_0的二阶导数,但似乎张量流不允许从张量的张量中导出.
-
10.0.高等数学四-多元函数的泰勒公式(二元函数二阶导数海赛矩阵)
2020-12-13 18:39:36多元函数的泰勒公式问题引入海赛矩阵二级目录三级目录 问题引入 海赛矩阵 二级目录 三级目录 -
单位矩阵的逆矩阵是它本身吗_如何求矩阵的逆矩阵?
2020-12-31 08:46:49求逆矩阵最有效的方法是初等变换法(虽然还有别的方法)。如果要求方阵 \(A\) 的逆矩阵,标准的做法是:将矩阵 A 与单位矩阵 I 排成一...例1:求二阶矩阵的逆矩阵。解:因为矩阵是二阶矩阵,我们可以直接利用二阶逆矩... -
机器学习:常用的矩阵向量求导公式
2018-09-23 11:06:58学习机器学习的时候有很多线性代数的知识,其中有一些矩阵向量求导的东西不是很熟悉,今天查了很久决定做一个总结。 定义1.梯度(Gradient) [标量对列向量微分] 设是一个变量为的标量函数,其中。那么定义对... -
可逆矩阵的特征值和原来矩阵_可逆矩阵与伴随矩阵(1)
2020-12-31 08:17:35(2)第1题: 二阶矩阵的逆适合用公式法, AA*=A*A=|A|E, 由此公式可以推导出A逆的计算公式。这里请注意一些细节问题(提示:不要漏掉某一项, A*=(Aij)^T), 并可以尝试编出辅助记忆的口诀: 行列式分之“主换副反”。(3)第2... -
二阶优化算法:牛顿法
2018-06-02 12:14:50牛顿法的基本思想:利用迭代点处的一阶导数(梯度)和二阶导数(Hessian矩阵)对目标函数进行二次函数近似,然后把二次模型的极小点作为新的迭代点,并不断重复这一过程,直至求得满足精度的近似最小值。 牛顿法的... -
【线性代数】1.3伴随矩阵和逆矩阵
2020-04-03 20:19:06二阶矩阵的逆矩阵3.公式2.逆矩阵1.定义2.定理3.公式3. 1.伴随矩阵 1.定义 设A=[aij]A=\lbrack a_{ij}\rbrackA=[aij]是nnn阶矩阵,行列式∣A∣\left|A\right|∣A∣的每个元素aija_{ij}aij的代数余子式AijA_{ij}... -
矩阵论学习笔记2
2015-01-24 15:11:47实际计算中,二阶分块矩阵的初等变换是用得最多的,它是二阶矩阵初等变换的直接推广。我们定义如下: 这很有用,我们将会在机器学习中的最小二乘法中看到。这实际是降阶公式。这是如何想到的呢?这是凑巧的吗?实际... -
高等数学学习笔记——第七十一讲——多元函数的泰勒公式
2020-04-19 20:14:062. 一元函数的导数,二元函数一阶导数,梯度及二元函数的二阶矩阵(海塞矩阵) 3. 海塞矩阵计算示例 4. 二元函数的带拉格朗日余项的麦克劳林公式 5. 二元函数的泰勒公式及拉格朗日中值公式 ... -
UVA10655 Contemplation! Algebra —— 推公式、矩阵快速幂
2019-10-06 22:12:03...a+b、ab的值分别为p、q,求a^n+b^n。...2.看到a^n+b^n 这个式子就想到二阶齐次递推式的通项公式,然后就想是否能通过通项公式反推回递推式。结果发现a、b的值是不能确定是否相等的,而求二阶齐... -
Hessian 矩阵以及在血管增强中的应用:OpenCV 实现
2019-12-27 23:30:28有别于广为人知的Sobel、Canny等一阶算法,基于Hessian矩阵能够得到图像二阶结果,这将帮助我们深入分析图像本质。 Hessian矩阵在图像处理中有着广泛的应用:其中在图像分割领域,包括边缘检测、纹理分析等;在图像... -
矩阵(题型)
2020-04-17 00:09:42求伴随 1.高阶伴随用公式 2.二阶伴随,主对调,副变号 (G了别记成二阶的逆矩阵公式) ... -
线代--求逆矩阵
2018-10-10 23:31:59首先公式是酱紫的 若|A|≠0(保证矩阵A可逆),则有 = 其中|A|为方阵的行列式,即由n阶方阵A的元素所构成的行列式...eg:已知二阶矩阵A=,则其逆矩阵为___(ad-bc)_____//智障如我,不会给公式加下划线,please ... -
D粒子的协变矩阵理论
2020-04-21 06:50:13从所谓的光前矩阵理论的DLCQ解释的角度,我们以11维二阶平Minkowski时空的形式,以明显的洛伦兹-协变形式重新构造了D粒子的矩阵理论。 该理论的特点是各种对称属性,包括更高规格的对称性,其中特例包含通常的SU(N... -
matlab中服从高斯分布的矩阵_Hessian矩阵以及在血管增强中的应用—OpenCV实现
2021-01-06 02:13:35有别于广为人知的Sobel、Canny等一阶算法,基于Hessian矩阵能够得到图像二阶结果,这将帮助我们深入分析图像本质。Hessian矩阵在图像处理中有着广泛的应用:其中在图像分割领域,包括边缘检测、纹理分析等;在图像... -
Hessian矩阵以及在血管增强中的应用—OpenCV实现
2020-04-14 15:11:47有别于广为人知的Sobel、Canny等一阶算法,基于Hessian矩阵能够得到图像二阶结果,这将帮助我们深入分析图像本质。Hessian矩阵在图像处理中有着广泛的应用:其中在图像分割领域,包括边缘检测、纹理分析等;在图像... -
斐波那契数列(二)--矩阵优化算法
2018-01-18 12:23:19之前写了一篇从斐波那契数列分析递归与动态规划...下面我们将其从一维上升到二维,用二阶矩阵推导斐波那契数列,该算法的复杂度为O(logn)。矩阵定义一个m*n的矩阵是一个由m行n列元素排成的矩形阵列。矩阵里的元素可... -
opencv纹理特征提取_Hessian矩阵以及在血管增强中的应用—OpenCV实现
2020-12-06 02:44:30有别于广为人知的Sobel、Canny等一阶算法,基于Hessian矩阵能够得到图像二阶结果,这将帮助我们深入分析图像本质。Hessian矩阵在图像处理中有着广泛的应用:其中在图像分割领域,包括边缘检测、纹理分析等;在图像... -
深度学习之Hessian矩阵在牛顿法中的应用
2018-06-06 14:52:13如果使用梯度下降,有可能在某一方向上导数增加很快,而在另外一方向上增加很慢,梯度下降是不知道导数的这些信息的,因为梯度只是一阶导数,只有二阶导数能反应一阶导数的变化情况,也就是Hessian矩阵。一般来说, ... -
一维灰度值一阶导二阶导对应卷积掩码推导
2013-04-26 21:38:47一维边缘提取过程中,计算离散一维灰度值剖面的导数: Fi’=1/2(fi+1– fi-1) Fi’’=1/2(fi+1–2fi + fi-1) ...三点拟合抛物线,抛物线公式:y = ax^2+bx+c,表示为矩阵方式为: f(x) + e(x) = [x^2 x 1] [a] -
海森矩阵和牛顿法
2019-05-18 11:12:00海森矩阵:函数的二阶导数是海森矩阵,海森矩阵经常用于牛顿法优化方法中,牛顿法是一种迭代求解方法,有一阶和二阶方法,主要应用在两个方面:1、求方程的根,2、最优化方法。 求解方程的根 当方程没有求根公式,...
-
皖南古村落旅游开发对居民影响及查济村旅游建言献策_主题作品.docx
-
“造血式”扶贫调研_主题报告.pdf
-
项目38-结束-源码
-
精通编译Makefile,Nina, 从底层uboot到Android
-
基于大数据的P2P信贷风险管理模式分析与探索.pdf
-
FFmpeg4.3系列之16:WebRTC之小白入门与视频聊天的实战
-
Codeforces Round #652 (Div. 2)
-
使用 Java 8 的流获取 List 中的重复元素
-
vue 使用引入 scss 报错,需要降版本的正确方法
-
MySQL 备份与恢复详解(高低版本 迁移;不同字符集 相互转换;表
-
做了五年Android开发,有些话想对大家说…
-
量价分析分析价格成交量持仓量三者关系
-
学 习 ~~
-
jtrussell.github.io:又一堆尖括号-源码
-
论软件项目需求文档的撰写
-
项目通道-源码
-
安装Homebrew
-
基于Flink+Hudi构建企业亿级云上实时数据湖教程(PC、移动、小
-
基于CAN总线的棉花在线测产系统设计
-
Mysql数据库面试直通车