最优化算法
Last updated
Was this helpful?
Last updated
Was this helpful?
若无特殊说明，《最优化方法》中的x含义都是向量，f是多元函数。
因为自变量x是向量，而函数的值是一个实数，因此目标函数是一个高维空间到一维空间的映射。
比如，在某次经济大萧条时期，基本的饮食也需要精打细算的时候，面包单价 c1 元，牛奶单价 c2 元，鸡蛋单价 c3 元，购买数量分别是x1，x2，x3，那么目标函数就可以写作f(x)=c1×x1+c2×x2+c3×x3
此时求解这个目标函数最小值的最优解是什么呢？可以发现当购买数量全部为0时，目标函数值最小，开销最小。
但每个人都有最低营养摄入需求，每天都需要摄入热量 b1，蛋白质 b2，维生素 b3，这便是约束条件。
面包
c1
a11
a12
a13
x1
牛奶
2
a21
a22
a23
x2
鸡蛋
c3
a31
a32
a33
x3
给定一组由x->y映射的坐标点，现要求找出一条直线，这条直线最能够体现这些点变化的趋势，那么这条直线的表达式即线性拟合中的目标函数。
多元函数的梯度可以与一元函数的导数类比，梯度是个向量
注：下降最快不代表下降幅度最大
二阶充分必要条件，满足梯度为0，且H矩阵大于0的点即为所求的最小值点。
但实际情况的目标函数往往非常复杂，没办法求得这两个条件，因此用迭代计算的方法来求得最优解。
我的通俗理解：先算梯度，负梯度的方向就是下降最快的方向，这是第一次迭代，把0代入梯度表达式中的各个未知数计算，可以算出具体的方向d(0)，然后算范数（也是直接把0代入），满足条件就可以结束了，若不满足条件，确定方向之后算步长λ，易知第一次迭代这一小步走完后的表达式为f(x(0)+λd(0))，那么令其导数等于0，可得此表达式的极值点，此点即为延d(0)方向下降最快的点，可算出λ(0)，第一次迭代结束。
用目标函数的二阶泰勒展开近似该目标函数，通过求解这个二次函数的极小值来求解凸优化的搜索方向。
"除以二阶导数"这个运算换算成"Hessian矩阵的逆矩阵"。
牛顿法的优点是收敛速度非常快，缺点是对初始点、目标函数要求高，要求Hessian矩阵必须可逆，计算量、存储量大（需要计算、存储Hesse矩阵及其逆）。
共轭梯度法（Conjugate Gradient）是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hessian矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。
注：对于n元正定二次目标函数，如果从任意初始点出发经过有限次迭代就能够求到极小点，那么称这种算法具有二次终止性。例如，Newton法对于二次函数只须经过一次迭代就可以求到极小点，因此是二次终止的；共轭梯度法、拟Newton法等也是二次终止的；而最速下降法就不具有二次终止性。
注：共轭梯度法对于更高次的函数在有限步之内也可以达到极值点。
由初等微积分的知识可知，某一点处的梯度方向是函数值增长最快的方向，那么梯度的反方向就是函数值下降最快的方向。因此在函数一阶可微的情况下，我们直接求取 ，那么 就是函数下降方向最快的方向了。
d(0)和λ(0)都算出来了，现在进入第二次迭代，算出第二次迭代的初点x(1)，然后计算梯度（和第一次迭代时的梯度表达式一样，只不过第二次迭代是把所有未知数=1代入表达式计算），然后算范数，满足条件，结束。，
上述是一元函数的牛顿法原理，对于多元函数的最优化问题，按下面这样的对应关系替换类比即可：
