【非线性无约束最优化】理论

在数学规划中，至少有一个非线性函数出现（无论是目标还是约束），就叫做非线性规划（Nonlinear Programing）

一维搜索算法

平分法

适用于一维、单峰、可微的情况

1. 找到初始区间[a,b]
   x0为初始点，Δx是步长。如果f′(x0)<0,则x1=x0+Δx.如果f′(x1)<0,那么x2=x1+Δx.一直做下去，直到f(xn)>0

2. 迭代寻优
   x0=(a+b)/2.如果f(x0)>0,区间为[a,x0].如果f(x0)<0,区间为[x0,b].

3. 重复第2步

0.618法

适用于一维、单峰的情况，不需要微分

这是另一种搜索方式，从[ak,bk]内，找到一个子集[uk,vk]，
(不妨假设f(ak)>f(bk)的情况)，
如果f(uk)>f(vk),那么，最小值点在[uk,bk]，
如果f(uk)<f(vk)，那么，最小值点在[ak,vk].

显然，这样的[uk,bk]是有无穷多种的，如果满足这些条件，计算量显然会小很多：

• 每次迭代，等可能性的保留[uk,bk],[ak,vk]，那么[uk,bk]在[ak,bk]的对称位置是合理的附加条件
• 每次迭代，区间缩短的比例λ都是相同的,为了迭代更快，λ越小越好。
• k次迭代计算的某一个分割点，也是k+1次迭代计算的某一个分割的（少算一次函数值）

满足以上规则的试探点，正好是黄金分割点(−1+5–√)/2约等于0.618,迭代式如下：
uk=ak+0.382∗(bk−ak)vk=ak+0.618∗(bk−ak)

梯度下降法

沿着负梯度方向，f(x)下降的最快，因此有这么一种迭代求最优的方法 xk+1=xk−ρk∇f(xk)

最速下降法

梯度下降法(gradient)或最速下降法(steepest descent)
沿着负梯度方向，做一维搜索（可以是黄金分割法或其它算法），找到这个方向上的最小值点。
在新的点上，按同样的方法继续沿着负梯度方向一维搜索

这里有一个规律：相邻两次的搜索方向是正交的

输入：目标函数f(x),梯度函数g(x)=∇f(x), 精度ϵ

输出：f(x)的极小值点x∗

算法：
step1：取初始值x0,k=0
step2: 计算f(xk)
step3: 计算gk=g(xk), 如果∣∣gk∣∣<ϵ,x∗=xk 算法终止。否则求出：
λk=argminλ≥0f(xk−λg(xk))
step4: xk+1=xk−λkg(xk)
如果∣∣f(xk+1)−f(xk)∣∣<ϵ或者∣∣xk+1−xk∣∣<ϵx∗=xk，算法终止
step5: k=k+1，转到3

共轭梯度法

前提：二阶可微
思路：共轭梯度法用于二次函数。也可以推广到一般函数时，认为局部是二次函数。

Q-共轭 piQpj=0叫做pi,pj是 Q-共轭 的

目标函数为二次函数f(x)=12xTQx+bTx+c，其中Q为实对称矩阵，x=(x1,…,xn)T
那么可以找到一组基{p1,p2,...pn}，这组基两两 Q-共轭
在这组基下，f(x)转化为这个形式f(x)=f1(x1)+f2(x2)+…+fn(xn)
对于这个形式，只需要沿着每个坐标轴进行一次一维搜索，就可以找到全局最优解（总共n次搜索）
整个算法围绕如何找到这一组基展开

算法如下
step1：任选一个初始点x(1)∈Rn,令p1=−∇f(x(1)),k=1
step2：若∇f(x(k))=0，算法终止；否则
x(k+1)=x(k)+αkpk
αk=−pTk∇f(x(k))pTkQpk
pk+1=−∇f(x(k+1))+λkpk
λk=pTkQ∇f(x(k+1))pTkQpk
step3：k=k+1，返回step2

可以证明，以上算法得到的p1,p2,…pn两两Q-共轭，因此迭代n次后，一定得到最优解。

对于一般二阶可谓函数f(x)，在每个局部
f(x)≈f(x(x))T(x−x(k))+12(x−x(k))∇2f(x(k))(x−x(k))
用Hesse矩阵来作为二次函数中的Q是合理的。
进一步说，Hesse矩阵计算量巨大，考虑进一步优化，幸运的是这个成立：λk=∣∣∇f(x(k+1))∣∣2∣∣∇f(x(k))∣∣2

算法如下
step1：任选一个初始点x(1)∈Rn,令d1=−∇f(x(1)),k=1
step2：若∇f(x(k))=0，算法终止；否则
x(k+1)=x(k)+αkdk
αk=argminf(x(k)+αdk)
dk+1=−∇f(x(k+1))+λkdk
λk=∣∣∇f(x(k+1))∣∣2∣∣∇f(x(k))∣∣2
step3：k=k+1，返回step2

目标函数是二次函数时，用共轭方向作为搜索方向。
一般的二阶可微函数，局部近似视为二次函数，用共轭方向作为搜索。

牛顿法

牛顿法(Newton method)和拟牛顿法(quasi Newton method), 优点是收敛速度快。
牛顿法每一步需要求解Hesse矩阵的逆矩阵。
拟牛顿法用正定矩阵近似Hesse矩阵的逆矩阵，进一步简化了运算。

牛顿法

• 需要知道一阶导数和二阶导数。
• 牛顿法收敛速度非常快。
• 如果二阶梯度不正定，可能不收敛

• 二阶可微函数，局部近似视为二次函数，搜索方向和大小可以立即用解析式确定。
• 反复迭代。

考虑无约束最优化问题minx∈Enf(x)
梯度为gk(x), Hesse矩阵为H(x)=[∂2f∂xi∂xj]n×n

二阶泰勒展开：f(x)=f(xk)+gT(xk)(x−xk)+1/2(x−xk)TH(xk)(x−xk)
两边求一阶导数，∇f(x)=H(xk)(x−xk)+gT(xk)
根据最优性条件∇f(x)=0,得出x∗−xk=−Q−1b

利用极小值的必要条件∇f(x)=0，推出
x=xk−H−1(xk)g(xk)

所以，迭代方法为xk+1=xk−H−1(xk)g(xk)

算法流程：
输入：f(x),g(x)=∇f(x),H(x)，精度要求ε
step1: 取初始点x0,k=0
step2: 计算gk=g(xk)，if ∣∣gk∣∣<ε : x∗=xk,停止运算
step3：计算Hk=H(xk)，求pk，使得Hkpk=−gk
step4: xk+1=xk+pk
step5: k=k+1转到2

拟牛顿法

牛顿法中，需要计算Hesse矩阵的逆矩阵，这一计算较为复杂 所以考虑用G去逼近H−1
包括DFP算法
BFGS算法 Broyden算法

修正牛顿法

如果二阶梯度不正定，牛顿法可能不收敛，为解决这个问题，引入修正牛顿法。

参考资料

施光燕：《最优化方法》，高等教育出版社
龚纯：《Matlab最优化计算》，电子工业出版社
David R. Anderson ：《数据、模型与决策–管理科学篇》，机械工业出版社
https://blog.csdn.net/johnnyconstantine/article/details/46335763
http://www.jianshu.com/p/96db9a1d16e9
http://www.cnblogs.com/zhangchaoyang/articles/2726873.html