《高级运筹学》无约束非线性规划.ppt

《《高级运筹学》无约束非线性规划.ppt》由会员分享，可在线阅读，更多相关《《高级运筹学》无约束非线性规划.ppt（74页珍藏版）》请在三一办公上搜索。

1、无约束非线性规划,2015年5月,研究生高级运筹学课件,本章内容,第一节：最优性条件第二节：一维搜索第三节：最速下降法和共轭梯度法第四节：牛顿法和拟牛顿法,第一节:最优性条件,本章仅讨论如下无约束非线性规划问题：,假定f(x)具有二阶连续偏导数。,现有多元函数 f(x1,x2,xn),若点 x(0)=(x10,x20,xn0)T 存在一邻域(x(0),使对任意x(x(0),均有f(x(0)f(x),则称 x(0)是 f(x)的局部极小点。,一、无约束极小化问题的最优性条件,无约束极小化问题的最优解必是f(x)的局部极小点。,利用局部极小点的一阶必要条件，求多元函数极值问题往往化成求解,局部极小

2、点的一阶必要条件：设函数f(x)在点x处可微，且x(0)为局部极小点，则必有,即,的问题,该方程组很难求解，一般不采用此法。,求解无约束非线性规划问题常用数值解法中的迭代法1.迭代法的基本思想：给定f(x)的极小点位置的一个初始估计x(0)，依次计算产生一系列点x(k)（1,2,),希望点列x(k)的极限x*就是f(x)的一个极小点。计算公式：,其中:,不同算法的区别在于得出搜索方向和步长的方式不同。,二、迭代法,2.选择搜索方向和步长的原则：（1）目标函数值逐次减小，这种算法称为下降算法。,（2）算法具有收敛性。即：序列中的某一点，或序列的极限点是函数的极小点。,3.迭代法的基本步骤：(1)

3、选择初始点x(0);(2)如已得到的迭代点x(k)不是最优解，确定从x(k)点出发 的搜索方向d(k)，使f(x)沿d(k)方向可以找到x(k+1)，目标函数有所下降。(3)在射线x(k)+d(k)(0)上选取步长k,使,从而确定下一个点,(4)检验新得到的点x(k+1)是否为最优或近似最优，若是则停止迭代，否则继续迭代。检验方法：,第二节：一维搜索,在求解无约束非线性规划的算法中，要进行一系列如下格式的迭代计算:,当方向d(k)给定，求最佳步长k,就是求一元函数,的极小点问题。,这一过程称为一维搜索。,一、一维搜索的定义,二、一维搜索的方法：,1.精确线搜索，即解方程：,2.试探法；按照某种

4、方式找试探点，通过一系列试探点的比较确定极小点。3.函数逼近法：用较简单的曲线近似代替原来的曲线，用近似曲线的极小点来估计原曲线的极小点。,三、一维搜索的基本思想：,1.单谷(峰）区间 在给定区间内仅有一个谷值(极大或极小)的函数称为单谷函数，其区间称为单谷区间,函数值：大小大图形：高低高单谷区间中一定有极小点,2.一维搜索的基本思想（1）确定初始单谷区间（2）根据区间消去法原理逐步缩小此区间（3）根据迭代精度要求确定最优解的近似值,(1)确定初始单谷区间的进退法,基本思想：对f(x)任选一个初始点a1及初始步长h，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为

5、“高低高”形态,计算步骤Step1.选定初始点a1，初始步长h，计算 f 1f(a1),f 2f(a1+h)Step2.比较f 1和f 2。（a）如f 1 f 2,向右前进；加大步长 h 2 h，转step3 向前探测（b）如f 1 f 2,向左后退；h-h，转（3）向后探测，（c）如f 1 f 2，极小点在a1 a1 h 之间。,Step3.产生新的探测点 a3a1h，f3f(a3);Step4.比较函数值 f2与f3：（a）如f20时，a,b=a1,a3;hf3,加大步长 h2 h，a1=a2,a2=a3,转step3 继 续探测,(2)消去法的基本原理,单谷区间确定后，假定在区间内任取两

6、点a1,b1;且 a1 b1。计算函数值，f1f（a1），f2f（b1）有下列三种情况：,综合为两种情况：若f(a1)f(b1),则取 a,b1为缩短后的搜索区间。若f(a1)f(b1),则取 a1,b为缩短后的搜索区间。,四、黄金分割法（0.618法）,黄金分割律是公元前六世纪，希腊的大数学家毕达哥拉斯发现的：如果把一条线段分成两部分，长段和短段的长度之比是1:0.618，整条线段和长段的比也是1:0.618时，才是和黄金一样最完美的分割，进行分割的这个点就叫黄金分割点 黄金分割法适用于a,b区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法

7、的适应面相当广.黄金分割法也是建立在区间消去法原理基础上的试探方法。在搜索区间a,b内适当插入两点1,2，将区间分成三段；利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点的数值近似解,黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布,1 2 将区间分成三段,黄金分割法要求插入两点：,黄金分割法区间消去示意：,黄金分割法的搜索过程：1）给出初始搜索区间及收敛精度，将赋以0.618。,2）按坐标点计算公式计算1，2;并计算其对应的函数值f1,f2。,3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需

8、进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。如果f1f2,则新区间a,2,令b=2,2=1,f2=f1,记N0=0;如果f1f2,则新区间1,b,令 a=1,1=2,f1=f2,记N0=1;,4）若b-a,则取最后两试验点的平均值作为极小点的数值近似解。否则，转向步骤 5）。,5）产生新的插入点：如N0=0，则取 1=a+0.382(b-a),f1=f(1)；如N0=1，则取 2=a+0.618(b-a),f2=f(2)，转向3）进行新的区间缩小。,(a2),(b),(a1),(a2),(a),(a1),黄金分割法,例1 用黄金分割法求解下列问题,初始区间为a,b=-1,1

9、,=0.16,解：计算结果列表如下,经过6次迭代，b-a=0.1110.16,满足精度要求，取,问题的精确最优解为 0.25。,五、牛顿法,牛顿法的基本思想：在迭代点附近，用二次函数（目标函数的二阶泰勒展开式）近似目标函数f(x),进而求出极小点的估计值。,牛顿法是函数逼近法中的一种。,考虑问题：,在迭代点k附近，令,然后以二次函数()的极小点作为f()极小点的一个近似，根据极值的必要条件,得,以此作为下一个迭代点，即,牛顿法的迭代公式,对牛顿法的几何解释f()的极小点*应满足极值必要条件f(*)=0。所以求f()的极小点也就是求解方程f()=0 的根。在k处用一抛物线k()代替曲线f()相当

10、于用一斜线k()代替曲线f()。抛物线顶点k+1 作为一个近似点应处于斜线k()与 轴的交点处。这样各个近似点是通过对f()作切线求得与轴的交点而找到的，所以牛顿法又称作切线法。,牛顿法的计算步骤,牛顿法的特点 牛顿法最大的优点是收敛速度快。但是在每一点处都要计算函数的二阶导数，因而增加了每次迭代的工作量。特别是用数值微分代替二阶导数时，舍人误差会影响牛顿法的收敛速度。牛顿法要求初始点选得比较好（离极小点不能太远），否则有可能使极小化序列发散或收敛到非极小点。,练习,第三节：最速下降法和共轭梯度法,求解无约束非线性规划问题的迭代算法包含两个关键步骤，得到迭代点x(k)后：(1)如何选择搜索方向

11、d(k)？(2)在选定的搜索方向上，如何进行一维搜索？（已介绍）,常用的确定搜索方向的方法。最速下降法共轭梯度法牛顿法拟牛顿法（变尺度法）,一、最速下降法,问题：在x(k)处，沿什么方向d(k)，函数f(x)下降最快？,结论：负梯度方向是函数的最速下降方向。,最速下降法就是以x(k)处的负梯度方向作为搜索方向，即令,求解问题,最速下降法的具体步骤：,其中，在第三步中，可以直接使用精确线搜索。,即令,可以解出k.,由,可以看出，d(k)和d(k+1)是正交的。,例2 用最速下降法求 的极小点。迭代两次，计算各迭代点的函数值、梯度及其模，并验证相邻两个搜索方向是正交的。,解：设初始点为,其中0由,

12、利用一阶必要条件,解得,由,求得,验证相邻两个搜索方向的正交性,最速下降法的优点程序设计简单，计算量小，存储量小，对初始点没有特别要求有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛,最速下降法的缺点：最速下降法是线性收敛的，并且有时是很慢的线性收敛,原因：虽然最速下降（负梯度）方向确实是从当前迭代点出发作微小移动时函数值下降最快的方向，然而由于采用精确线搜索，每次迭代点的移动并非总是微小的，因而迭代过程中并未得到使函数值“最速下降”的好处。相邻两次迭代的搜索方向彼此正交，容易产生锯齿型迭代移动，这种绕弯路向最优解移动的路径，形象的表明最速下降法的收敛速度是不理想的。,结 论：最速下降

13、法是基本算法之一，而非有效的实用算法最速下降法的本质是在迭代点处用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近,练习：用最速下降法求解,取初始点x(1)=(1,1)T,迭代两次。,二、共轭梯度法,共轭梯度法是针对二次函数,的无约束非线性规划问题，考虑出一种搜索方向的合理选取方法，然后形式地推广到一般可微函数。,对于变量分离的函数,从任意一点x(1)出发，分别沿着每个坐标轴方向进行一维搜索（共进行n次搜索）以后，一定能得到minf(x)的最优解。,对于二次函数,如果Q为实对称正定矩阵，则可以选择一组基p1,p2,pn,满足,在新的基下，f(x)就成为变量分离的形式。于是

14、，从任何一个初始点x(1)出发，分别沿着每个pi方向作线搜索，经过一轮后，肯定能得到最优解。,定义：设Q为n 阶实对称正定矩阵，若n维方向x和y满足,则称方向x和y是Q-共轭的。,问题：如何构造出两两Q-共轭的方向？,在每个迭代点x(k)处，以负梯度-f(x(k)和前一个搜索方向pk-1的适当组合，构成和前面k-1个搜索方向p1,p2,pk-1均两两Q-共轭的搜索方向pk。,即：,推导过程：,可以证明，在中途不停机的情况下，这样得到的p1,p2,pn，是两两Q-共轭的，因此x(n+1)一定是原问题的最优解。,精确线搜索结果的推导,对于一般可微函数的f(x)，在每一迭代点x(k)可以近似的视为二

15、次函数,因此设想利用共轭梯度法也能得到好的效果。此时，式子中的Q应该以x(k)点处的Hesse矩阵代替，计算量太大。,解决方法：修改迭代公式，使之不含Q，修改后的计算公式：,为了保证算法具有某种收敛性，注意到共轭梯度法的第一步和最速下降法相同，最速下降法具有收敛性。通常采用如下的起点周期性变化的共轭梯度法：从初始点x(1)出发依次用共轭梯度法产生迭代点x(2),x(3),x(n+1)后，以x(n+1)作为新的x(1)，周期性重复以上步骤。,由于搜索方向不一定是下降方向，因此，这样做可以减少迭代误差的累积，达到良好的计算效果。,例3 用共轭梯度法求解,解：共轭梯度法的第一步和最速下降法相同，由例

16、2知；,|f(x(1)|较大，还需迭代，下一个搜索方向：,停止迭代，x(2)即为所求极小点,一、牛顿法,第四节 牛顿法和拟牛顿法（变尺度法）,考虑,当Q正定时,对于一般二阶连续可微函数，在x(k)的局部,当2f(x(k)正定时，,据此设计出牛顿法,若f(x)是一元函数，则牛顿法就是用切线法解方程f(x)=0,在实际使用牛顿法时，如何合适选取初始点是一个难以解决的问题。当f(x(k)0且2f(x(k)正定时，牛顿方向-G(x)-1 g 是一个下降方向,牛顿法的收敛性与初始点的选取有关。若初始点选取合适，则收敛很快（至少二阶收敛）。若初始点选择不好，则可能不收敛。,于是可以把牛顿法中的指定后继点迭

17、代公式,修改为，沿方向,作线搜索得后继点，即,二、拟牛顿法（变尺度法）,修改牛顿法具有全局收敛性，但每步确定搜索方向时都要计算Hesse矩阵及其逆矩阵,1959年,Davidon提出设想仅用每次迭代中得到的梯度信息来近似Hesse矩阵，基于此导致了一类非常成功的拟牛顿法,算法原理：将确定搜索方向d(k)公式中的 2f(x(k)-1 用n阶矩阵Hk代替，从而在第k步迭代时，,k由线搜索得到。初始点x(1)和初始矩阵H1是预先给定的，Hk在迭代中利用已得迭代点及目标函数值，最多再利用一阶导数按某种规则获得。,确定Hk的一种自然想法是，将Hk 作为2f(x(k)-1 的近似来构造，注意到2f(x(k)是对称的，且有近似关系,即,则Hk 应满足条件,对称正定的；满足拟牛顿方程,另外，设想Hk由Hk-1经过简单修正得到，Hk=Hk-1+Ek;,校正矩阵Ek应该对称，且满足,满足上式的对称矩阵有无穷多个，因此拟牛顿法是一族算法。DFP算法是其中最常用最有效的方法之一。,设校正矩阵的形式为,其中k,k 为待定参数，Uk,Vk为待定向量，这种形式显然是对称的，把上式代入拟牛顿方程,不妨取,为使上式成立，简单的做法是取,DFP算法中的校正矩阵Ek和矩阵Hk的计算公式为：,DFP算法的步骤,例4 用DFP算法求解,解：取H0=I,DFP算法第一步与最速下降法相同,以下作第二次迭代,