非线性规划理论和算法

《非线性规划理论和算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、非线性最优化理论与算法第一章引论本章首先给出了一些常见的最优化问题和非线性最优化问题解的定义，并且根据不同的条件对其进行了划分。接着给出了求解非线性优化问题的方法，如图解法等，同时又指出一个好的数值方法应对一些指标有好的特性，如收敛速度与二次终止性、稳定性等。随后给出了在非线性最优化问题的理论分析中常用到的凸集和凸函数的定义和有关性质。最后给出了无约束优化最优性条件。第二章线搜索方法与信赖域方法无约束优化的算法有两类，分别是线搜索方法和信赖域方法。本章首先给出了两种线搜索方法即精确线搜索方法和非精确线搜索方法。线搜索方法最重要的两个要素是确定搜索方向和计算搜索步长

2、，搜索步长可确保下降方法的收敛性，而搜索方向决定方法的收敛速度。精确线搜索方法和非精确线搜索方法对于精确线搜索方法，步长ακ满足αk=argminα≥0ƒxk+αdk这一线搜索可以理解为αk是f(xk+αdk)在正整数局部极小点，则不论怎样理解精确线搜索，它都满足正交性条件：dkT∇ƒ(xk+αkdk)=0但是精确搜索方法一般需要花费很大的工作量，特别是当迭代点远离问题的解时，精确的求解问题通常不是有效的。而且有些最优化方法，其收敛速度并不依赖于精确搜索过程。对于非精确搜索方法，它总体希望收敛快，每一步不要求达到精确最小，速度快，虽然步数增加，则整个收敛达到快速。

3、书中给出了三种常用的非精确线搜索步长规则，分别是Armijo步长规则、Goldstein步长规则、Wolfe步长规则。第一个步长规则的不等式要求目标函数有一个满意的下降量，第二个不等式控制步长不能太小，这一步长规则的第二式可能会将最优步长排除在步长的候选范围之外，也就是步长因子的极小值可能被排除在可接受域之外。但Wolfe步长规则在可接受的步长范围内包含了最优步长。在实际计算时，前两种步长规则可以用进退试探法求得，而最后一种步长规则需要借助多项式插值等方法求得。紧接着，又介绍了Armijo和Wolfe步长规则下的下降算法的收敛性。信赖域方法线性搜索方法都是先方向再

4、步长，即先确定一个搜索方向dk，然后再沿着这个搜索方向dk选择适当的步长因子αk，新的迭代点定义为xk+1=xk+αkdk。与线搜索方法不同，信赖域方法是先步长再方向,此方法首先在当前点附近定义目标函数的一个近似二次模型，然后利用目标函数在当前点的某邻域内与该二次模型的充分近似，取二次模型在该邻域内的最优值点来产生下一迭代点。它把最优化问题转化为一系列相对简单的局部寻优问题。信赖域方法的思想为：设当前点xk的邻域定义为Ωk=dϵRnd-dk≤∆k其中，∆k称为信赖域半径。目标函数在极值点附近近似一个二次函数，因此对于无约束优化问题，利用二次逼近，构造如下信赖域模型

5、。一般的，信赖域模型的目标函数取为mkd=ƒk+gkTd+12dTBkd其中，Bk∈Rn×n对称，是ƒ在dk处Hesse阵∇2ƒk或者其近似。这个问题就是信赖域方法模型的子问题。设dk是信赖域子问题的解，我们称目标函数ƒ在第k步的实下降量Aredk=ƒxk-ƒxk+dk函数的预下降量Predk=mk0-mkdk定义比值rk=AredkPredk它衡量了二次模型与目标函数的逼近程度。一般的，Predk>0。若rk<0，xk+dk不能作为下一迭代点，需要缩小信赖域半径，重新计算dk；若rk>0且靠近1，说明二次模型与目标函数在信赖域内有很好的近似，在下一迭代时可以扩大

6、信赖域半径；对其他情况信赖域半径不变。随后又给出了信赖域算法，只是由于信赖域模型利用负梯度方向为搜索方向，算法的效率很低，然后就给出了建立信赖域方法超线性收敛性的子问题的三种求解方法，分别是折线法、二维子空间方法和精确解方法。信赖域方法和线性搜索方法是求解非线性优化问题的两类主要的数值方法。与线性搜索方法相比，信赖域方法思想新颖，具有可靠性、有效性和很强的收敛性。第三章最速下降法与牛顿方法本章主要介绍最速下降法和牛顿方法，最速下降法又称为梯度法，是根据目标函数的线性近似得到的，但是它的收敛速度并不快。相比之下，牛顿方法具有快的收敛速度，它是根据目标函数的二次近似得

7、到的，是没有步长搜索的算法。最速下降法最速下降法从目标函数的负梯度方向一直前进，直到达到目标函数的最低点。书中首先给出了最速下降法的算法和算法的性质，然后讨论了最速下降法的收敛速度。最速下降方法的迭代公式是：xk+1=xk+αkdk其中dk=-gk为最速下降方向，ƒxk+αkdk=minα≥0f(xk+αdk)为最优步长。在最速下降法中，两个相邻的搜索方向是正交的，即dk，dk+1=0最速下降法具有锯齿现象，即在极小点附近，目标函数可以用二次函数近似，其等值面近似于椭圆面，长轴和短轴分别位于对应最小特征值和最大特征值的特征向量的方向。其大小与特征值的平方根成反比。

8、最速下降法