优化算法综述

Doris232

本文主要对计算机视觉图像配准中搜索空间算法引发讨论，即当图片配准后，讨论下一步怎么办，往哪个方向，多大步长的进行搜索。是一种优化算法
本文将介绍设计到的基本的数学知识、一阶优化算法、针对多阶方程的梯度下降法以及他的改进、牛顿法以及他的改进，神经网络的优化算法等。
本文所有的知识全部来自于B站一位老师的讲解视频以及《优化算法》，现在本人也有许多不理解之处，后续会慢慢修改，接下来的文章我将用最简单的语言解释这复杂的算法
最优化导论  第4版.pdf
32.7M
· 百度网盘


基础数学知识：基础数学知识

1、梯度

导数相信大家都知道了，作用在一元方程中名字通常就叫斜率，作用在二元方程中，针对X，就是对X的偏导；针对Y，就是对Y的偏导。对X的二次导，对Y的二次导数等等。
梯度：就是对X、Y、Z等偏导的数组。他的现实中的意义就是在多维度的平面中，观察他的下降趋势。
类似于登山，对自己坐标做一个XY坐标轴，梯度就是当前X方向、Y方向的倾斜程度，判断山是否倾斜的一个量化
2、黑塞矩阵
黑塞矩阵是什么？简单来说就是在多维的情况下对梯度的导数，我们可以看出，一个N元方程做一次导数，变成了n维的数组，这个时候，对n维的数组再做一次导数，就变成了NXN的矩阵。这就是黑塞矩阵。
3、雅各比矩阵
雅各比矩阵，他的运算并不是对X、Y等求偏导，而是针对n维的向量函数的。
简单理解就是：黑塞矩阵式=雅各比矩阵（一阶偏导数组）
4、泰勒公式
后面我们方式涉及到牛顿法、伪牛顿法等，都是以泰勒公式为核心
泰勒公式简单来说就是，把任意一个方程，都可以写成很多很多项的和
泰勒公式
我们可以看到里面由一次导数、二次导数等等，我们是否可以利用它来进行极值点的判断
Tip：他们有什么用？
众所周知：导数，表示一个曲线的变化趋势，二阶导数表示一阶导数的变化趋势问题，简单的求极值问题中，导数为零表示有极大或者极小值，这个情况下，二阶导数的正负表示函数的凹凸性，进一步判断这个点是极大值还是极小值。
推广到多维中，多个方向->梯度数组；两两配合的二阶导数，变成了一个N*N的矩阵->黑塞矩阵
<hr/>极值点的条件

1、一阶必要条件：
当在内部时：
要求所有的导数全等于0
梯度数组全为0
当在边界时：
同样，在可行方向上，全等于零
2、二阶必要条件
如下面公式
引入黑塞矩阵，d为方向向量
此时：d表示方向向量，H表示黑塞矩阵。右面是证明过程。
3、充分必要条件：
上述并不是充分条件。因为黑塞矩阵可能不是正定的（本征值不一定为正数）
何时？：当一阶导数等于零，H大于零
<hr/>迭代算法的基础知识

首先，我们需要知道什么是迭代算法，迭代算法类似于我们通过条件求解出的结果，变成了下一步的条件，并且以相同的方式进行求解。也就是一个螺旋向上的过程。
优化算法的要素：
起始点的选择：选用所有的极值点（导数为零的点）、尽可能的接近目标、选择
方向的确定：就是我们说讨论的优化算法：目标函数【分割】、一阶导数【二分法】、二阶导数【牛顿法等】
步长的确定：其表示每一次迭代的距离。
目标是否能够达成：收敛条件、总能量是否足够小【每一次优化后，是否变化的不明显】、步长是否足够的小【结构是否稳定】、导数是否足够小【变化趋势变化不明显】
<hr/>优化算法：黄金分割法【一维】【一维无方向，确定步长】
本方法的根本思路就是：二维平面，一元函数，对其进行结果的逼近方法。类似于二分法。他的前提条件是：是一个单峰函数
不断地对极值逼近
我们自己算一个函数值，这个时候就可以建立一元二次函数：
如图发现，这个数就是黄金分割比例。
<hr/>优化算法：斐波那契数列【步长】
我们进一步对黄金分割法进行更大的优化：
我们每次压缩的比例ρ是变化的，这个时候迭代的关系：
那么怎么样选取可变的ρ呢？
数学家告诉我们：斐波那契数列（1、2、3、5、8、13等）
0.618-0.5
<hr/>优化算法：二分法【步长】
需要一个额外的信息：一阶导数的正负，决定他往哪儿去。
这个时候用二分法，压缩比最大
<hr/>优化算法：牛顿法与割线法【一维】【步长】

注：他是基于二次型目标函数，是找关键点的第一步
步骤：
泰勒展开：
泰勒展开式
求：
目标函数
对其求导：
求导
得到下一步迭代的点（步长）
则继续迭代。
问题：一阶牛顿法出现几个问题，他可能找出的时极小值点，也有可能是极大值点。这么解决？
解决办法：我们通过前面所学的逼近法，将初始点逼近到很小的范围内，然后再使用牛顿法进行求极值即可。
<hr/>优化算法之划界法【初始点】

划界法并不是独立使用，是初始点的问题。（得判断是不是在它的范围之内）
以上图为例，如果出现2>1>0，这个时候  ，如果不行，则增加2* ，保证快速的找到边界。
直到满足
推广到多维的优化问题，我们操作的是步长，
每一次改进步长，进行优化
怎么增加步长？
Armijo：a不太大，a不太小的问题。
<hr/>优化算法之最速下降法【高维】【步长&方向】
高维的情况下，优化的步骤是：找方向、找步长。
迭代函数
1、梯度法（方向）
在梯度方向的反方向是下降最快的方向
方向，梯度的反方向
2、步长（使用上面学的方法）
步长，目标函数
例题：
例题
这个时候，会发现每一次的方向是垂直的。如下公式：
发现每一次的方向都是共轭的
Tip：本小节就是阐述了方向怎么找的问题。梯度的反方向！
<hr/>优化算法之二次型函数的梯度下降法【步长H&方向】

函数的另外一种形式

二次型函数的一般形式：
一般形式
二次型函数的矩阵形式
矩阵形式
参考
二次型函数的梯度：
一般形式的梯度求解
二次型函数的梯度的矩阵形式：
矩阵形式的梯度求解
二次型函数的二阶导数（海森矩阵）
引出海森矩阵
二次型函数的转变（让海森矩阵表示）
以海森矩阵表示方程式，这样更加的简洁
梯度下降法在二次型函数的应用:
梯度步长？
这个时候搜索步长怎么算呢？
要求：
目标函数
求导为0
要求梯度方向和函数的点积为0。
求得步长
<hr/>优化算法之牛顿法【二维】【方向H&步长x】
对于一元的迭代的牛顿法：
我们尝试将一元的方法推到成多元的方法
推广
替代（泰勒公式）
泰勒公式
牛顿法的缺点：
计算量大（海森矩阵以及海森矩阵的逆）、不能保证目标函数下降，不能保证收敛
<hr/>最优化算法之修正牛顿法【加冗余值&雅各比矩阵替换】

牛顿法计算量大、黑森矩阵也许是非正定的、奇异的、不能保证函数的收敛等
改进一：保证下降到方向【初始点的确定】
利用上述的划界法等
改进二：保证海森矩阵为正【冗余值】
加一个冗余值
加了一个冗余值，保证G一定大于0.本征值一定大于零。
当μ->无穷时，就是梯度下降法
改进三：需要计算海森矩阵还有他的逆矩阵那个，计算量太大了。（高斯牛顿法）
利用雅各比矩阵替换海森矩阵：
雅可比矩阵与海森矩阵的关系：
雅各比矩阵的定义
高斯牛顿法应用于非线性的拟合。
n个观测点，有p个变量，这个时候，
要求误差和最小。
则目标函数
目标函数
导数
求导
梯度：
二阶导数：（海森矩阵）
展开：
得到黑塞矩阵和雅各比矩阵的关系
利用雅各比矩阵代替海森矩阵
替代
出现非正定得问题：
雅各比矩阵会出现－的情况
<hr/>优化算法之共轭梯度法【海森矩阵转变成计算共轭矩阵的向量】

1、正交向量
共轭的定义如上
W和V关于A正交。
推广：
由上图发现：本征向量是关于A相互共轭。
如果存在a，有：

证明共轭向量线性独立
给定了一组向量，关于A共轭，这个时候类比：
类比牛顿法
得：这个问题并没有求海森矩阵的逆，大大减小了其计算量。我们只需要找到一组关于海森矩阵得共轭得向量u即可！！！
<hr/>优化算法之秩一算法【海森->差分近似的Z】

对于多元函数，差分近似是否也能够解决？
在牛顿法里我们最终的目标是得到海森矩阵的逆矩阵。
下面是我们多维情况下通过差分近似，海森矩阵。我们试一试能不能得到逆矩阵。
类比一维牛顿法，对于多维的，差分近似的应用
此时B代表海森矩阵的逆矩阵的近似。
两个新向量外积，获得了一个矩阵。而且他的本征值只有一个不为零。->置一
优化算法采用迭代的算法，
加一个冗余值，建立目标方程
这个时候，求出z，就可以让 其迭代。
计算步骤：
首先：原始条件：
目标方程：A式
这个时候我们需要求出z的解。
求出Z的表示解
得：
最终解的：
代入
回顾原先的关系：
两边同时*g的转置，得：
由A式为根本，3、1式代入A式得：
最终方程，迭代
总结：
w:方向
e：步长
r:下一个搜索点
t：为了避免计算海森矩阵以及海森矩阵的逆矩阵求解。
<hr/>优化算法值之DFP算法【非正定&->打开】

他是牛顿法的一种改进，也是对秩一算法的一种改进
秩一的算法缺点：对于上述的t在运算迭代的过程中，B这个矩阵不一定正定。有一个÷0的问题。
证明略。
上述这个方法保证了不会÷0，而且也是一个共轭方向法。但是不能保证它不是一个奇异矩阵。也就是说，他有可能是为零的。
<hr/>优化算法之BFPS算法【/0->对偶原理->解数学公式】

保证其是一个正定的矩阵（DFP会遇到奇异的问题）
秩一与DFP算法都是对其海森矩阵的 逆矩阵的迭代更新。
BFPS针对黑塞矩阵H的更新而不是对其逆的更新。
基于对偶原理：
这样的话，我们就得到了海森矩阵的关系
根据牛顿法，我们需要海森矩阵逆矩阵。这个时候我们获得了海森矩阵，怎么求逆呢？
数学上有一个公式：
数学公式
对于VV公式，会发现需要计算两次！
求得：
BFPS算法的优点：

无需解释海森矩阵逆牛顿法共轭方向法正定

优化算法之多元拟合算法【矩阵无解下，求近似解->A (伪逆)】

在一元线性拟合中，用最小二乘法，求其自变量因变量的关系
多元线性拟合中，y比较多。
结果
X为m*n的阵，Y是m的数组
模型：目标函数
目标函数
矩阵形式即：
目标函数
给他转化为线性方程组的问题：
线性方程
当m=n时：
m=n，只要用简单的方法就可以得到
当m>n时：
这个时候根本无解，我们只能求其近似值：
两边同时乘以A的转置：
这个时候，没有解，只能求近似的最优解
之后就可以求逆。
伪逆
X的解是什么意义了呢？和线性二重法有什么关系呢？
通过一系列公式发现：
通过上述公式：x的意义就是最小二重法的解！
那么X怎么求呢？
【放弃！看不懂。】
<hr/>递推最小二乘法

上述的观察值，如果后续还有源源不断地观察值，应用迭代计算需求，不断的更新。【在上一次解的情况下优化问题！】
<hr/>优化算法如何解决神经网络的问题【多元拟合问题】

神经网络就是模拟神经的方式，在数学处理上，进行输出

表示求和，有n个输出值X，m个输入值Y，让其误差足够的小。
<hr/>反向传播算法【多元拟合问题】

神经网络
神经网络
每一层都是线性的，最终他不是线性的。
怎么获得最佳的权重？
中间层：
中间层的加成
输出层：
最后一成的加成
优化的目标（学习的输出和我们实际观测的尽可能的小）
优化函数，有了它，就可以用梯度下降法
求解：用梯度下降法：
从中间层到输出层（最后一次）
梯度：
求导
从输入层到中间层（中间-比较复杂）
y改变了
求导
图示：输出层的更新：
图示：中间层的迭代更新
<hr/>补充：
1、连续优化方法
Powell算法、Simplex算法、梯度下降【GD】算法、共轭梯度【CG算法】、伪牛顿算法【QN】、LM算法、随机梯度算法【SGD】

0）Powell算法：鲍威尔算法是一种十分有效的直接搜索法。共轭方向可以加快收敛速度的性质形成的一种搜索方法。该方法不需要对目标函数进行求导，当目标函数的导数不连续的时候也能应用 1）Simplex算法：单纯形法求解线性规划问题最常用、最有效的算法之一。线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止 p、s算法不需要计算导数，所以他会非常的快。但是会收敛于某一个局部最优点，只适合低自由度图像的配准 2）GD:梯度下降法                    1、定义步长为迭代次数的函数                    2、不确定性搜索算法的梯度下降 3）CG比GD拥有更好的收敛速度：它的下一步搜索方向并不是遵循新的梯度，而是与先前梯度共轭 4）QN：伪牛顿法有更好的理论收敛速度，是从牛顿算法发展过来的，牛顿算法（在计算海森矩阵）耗费了大量时间，而QN把海森矩阵逆给估计出来，作为下一步的步长，这样节省了大量的时间。（BFGS\DFP两个变种），现如今应用于三维超声序列的配准以及非刚性配准及其图谱重建 5）LM也是估计了海森矩阵的逆矩阵，但是他用一个加权的因子去达到其稳定性以及算法优化速度,QN是其的一个特例：LM算法有一个微分同胚算法特别有名 6）SGD:随机梯度算法，现在方向也不按照梯度的方向迭代更新了，也是一个随机的估计值了          三种估计方法：（KW、SP、RM）          KW：有限差分来估计目标函数          SP（同步扰动）：沿着一个随机扰动矢量进行扰动          RM：随时间减少的步长（性能最好----->随机梯度下降优化算法ASGD）

2、离散优化方法

1.基于图的优化算法：简单来说就是给定一个标签，然后节点不断地变换下，最后标签变成了什么样。在分割出每一次变化中的标签？？？（后续查询，在进行补齐） 2.基于消息传递的优化算法：局部交换信息进行回溯，从局部到整体 3.基于线性规划的优化算法：基于网格形变的位移场

梯度下降法的迭代过程


<hr/>

XGundam05

优秀