概述
其中 x 是n维向量，在实际问题中也被叫做决策变量，s.t.为subject to的缩写，用来表示约束条件，因此， hi(x) 和 gj(x) 称为约束函数，其中 hi(x)=0 为等式约束， gj(x)≥0 为不等式约束。求极小值的函数f称为目标函数，求极大值的问题可以通过取负数转换为极小值问题，因此这里都以极小值问题来讨论。
因此，根据有无约束函数，可以将最优化问题分为有约束最优化和无约束最优化问题;根据目标函数和约束函数的类型，可分为线性规划（目标函数和约束函数均为线性函数）和非线性规划; 另外，如目标函数为二次函数，而约束函数全部是线性函数的最优化问题称为二次规划问题，当目标函数不是数量函数而是向量函数时，就是多目标规划，还有用于姐姐多阶段决策问题的动态规划等
无约束最优化问题
梯度下降（Gradient Descent)
收敛速度：线性收敛
因此，虽然最速下降法具有很好的整体收敛性，但由于其收敛速度太慢并不是很好的实用算法，但是有一些有效算法是基于它改进的，如批量梯度下降，随机梯度下降等，以后整理。
Newton法
最速下降法的本质是用线性函数去近似目标函数，因此要想快速得到，需要考虑对目标函数的高阶逼近。牛顿法就是通过二次模型近似目标函数得到的，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。先建立一个这样的宏观认识，下面详细说。
Newton法解方程
Newton法最优化
由前面我们知道我们的任务是最小化目标函数 f ，因此可以转化为求解函数f的导数
f′=0
推导：
对目标函数 f(x) 在 xk 进行泰勒级数展开,忽略二阶导之后的高阶项
f(x)≈qk(x)=fk+gTk(x−xk)+12(x−xk)TGk(x−xk)
矩阵的形式你可能看起来有点懵，其实对应我们常见的形式就是
根据上一节解方程的过程我们知道下一次近似的 xk+1 应满足 ∇qk(xk+1)=0=gk+Gk(xk+1−xk)
xk+1=xk−G−1kgk
在实际应用中，求逆运算太复杂，我们一般通过解方程 Gkp=−gk 来确定.
基本步骤：
每一步迭代过程中，通过解线性方程组得到搜索方向，然后将自变量移动到下一个点，然后再计算是否符合收敛条件，不符合的话就一直按这个策略（解方程组→得到搜索方向→移动点→检验收敛条件）继续下去。
优缺点：
收敛速度快：二阶收敛速度（收敛速度明显快过梯度下降）
- 局部收敛，只有当初始点充分接近极小点时才能保证收敛，即使Newton法收敛也不一定收敛到极小点，还可能是鞍点或极大点。
- 牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂，且G还可能是奇异矩阵。
- 虽然我们提到可以使用解方程 Gkp=−gk 来确定下一个移动点，但是这个方程有可能是病态的
ref: http://www.codelast.com/%e5%8e%9f%e5%88%9b-%e5%86%8d%e8%b0%88-%e7%89%9b%e9%a1%bf%e6%b3%95newtons-method-in-optimization/
因为牛顿法的收敛速度确实很快，因此人们针对牛顿法的缺点做出了各种改进版本，如阻尼牛顿法，Goldstein-price修正等，上面这个参考连接中有提到。
共轭方向法
共轭方向法是介于梯度下降法和Newton法之间的方法，为什么这么说呢？我们根据Newton法的介绍可以知道对于二次函数，Newton法只需要迭代一次就可以得到极小值（当然假设是存在的），而最速下降法需要迭代无穷多次，但是Newton法的计算代价太大，因此我们放松要求，只要找到在有限次迭代后可得到二次函数极小点的算法就是有效的算法，这种算法称为具有二次终止性。
理论基础：共轭方向及其性质
设 G 为n阶正定矩阵， p1,p2,...,pk 为n维向量组，如果 pTiGpj=0,i,j=1,2,...,k,i≠j
则称向量组 p1,p2,...,pk 关于 G 共轭。如果 G 为单位矩阵I ，则 p1,p2,...,pk 是正交的。
这里的证明需要知道很多性质和定理，就不一一说明了，找一本最优化的书看可能比较好，或者参考连接2中的博客有写的比较好懂。
基本思想
共轭梯度法
拟Newton法
参考
- 《最优化方法》解可新，韩健，林书联 编
- http://www.codelast.com/ （感谢博主的文章）
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/227750.html原文链接：https://javaforall.net
