运筹学及最优化方法第2章

1、无约束非线性规划无约束非线性规划例题见例题见P11-12设有一维无约束非线性规划设有一维无约束非线性规划Rxxf),(min(2.2.1)则由数学分析的知识我们有则由数学分析的知识我们有 (1)若函数若函数f(x)可微，则它在点可微，则它在点x*取得局部最优解取得局部最优解(极值极值)的必要条的必要条件是件是是驻点，即 *0*)(xxf(2)若函数若函数f(x)在点在点x*处有二阶连续导数，则它在点处有二阶连续导数，则它在点x*取得局部最取得局部最优解优解(极值极值)的充分条件是的充分条件是0*)(, 0*)( xfxf且 利用上述结论我们在数学分析中求局部最优解利用上述结论我们在数学分析中求

2、局部最优解(极值极值)的方法的方法已很熟悉，但问题是在实际工作要找已很熟悉，但问题是在实际工作要找“驻点驻点”的精确值往往是行的精确值往往是行不通的。因此在这里要单间介绍数值近似法的主要思想。不通的。因此在这里要单间介绍数值近似法的主要思想。基本思想：基本思想：确定一个包含最优值的已知区间，在保证不失去最优值的条件下逐步缩小区间，当把区间缩得足够小时，即可用该区间内的任何点做为近似最优点。黄金分割法（黄金分割法（0.618法）法） 该方法是以不变的区间缩短率(黄金分割数(5-1)/2=0.618 ) 缩小区间长度。其特点是效率低，但适用范围广（不需对函数有连续等附加条件）且编程方便。因此有因此

3、有0.6180.618法计算步骤如下法计算步骤如下: :切线法（一维牛顿法）切线法（一维牛顿法） 设函数f(x)在(a,b)内有二阶连续导数0010011(),()()(),(),1()kkkkkkkkfxxab xxfxfxxxfxfxxxfx令或为第1次探索点,为第k次探索点则对给定的误差当时求解思路是：在初始探索点xk 处用泰勒展式作 f(x)的二次近似函数g(x) ，再用 g(x) 的最小点作新的探索点。即所以所以,当当|xk+1-xk|小于给定误差小于给定误差时，时，xk是最优解的近似值。是最优解的近似值。abx1x2xkf(x)abx1x2xkf (x)f (x)的切线法式方程示意

4、图的切线法式方程示意图牛顿法示意图牛顿法示意图故也可解释为用牛顿求根公式故也可解释为用牛顿求根公式法求法求f(x)的驻点的驻点x*1()()( )kkkkkfxxxfxfxx注意为在点 处的法式切线方程因此有牛顿因此有牛顿法算法框图法算法框图如下如下: : 其特点是收敛快效率高，但要求条件下高（需对函其特点是收敛快效率高，但要求条件下高（需对函数有二数有二阶连续可微的附加条件）。阶连续可微的附加条件）。初始x1,1, 2 0k=1 f (xk ) 0?N输出求解失败Yxk +1= xk - f (xk ) f(xk )| xk +1-xk | 2 YNk=k+1例例 求求 min ()= ar

5、ctan t d t 解：解： () =arctan , ()=1(1+ 2) 迭代公式：迭代公式： k +1= k - (1+ 2) arctan k 取取1= 1，计算结果：，计算结果： k k (k) 1(k ) 1 1 0.7854 2 2 -0.5708 -0.5187 1.3258 3 0.1169 -0.1164 1.0137 4 -0.001095 -0.001095 4 * =0 取取1=2，计算结果如下：，计算结果如下： k k (k) 1(k ) 1 2 1.1071 5 2 -3.5357 -1.2952 13.50 3 13.95 不收敛。不收敛。 0k k (k)

6、1(k ) 1 2 1.1071 5 2 -3.5357 -1.2952 13.50 3 13.95 不收敛。不收敛。插值法：插值法： 用用()在在2 或或3 个点的函数值或导数值，构造个点的函数值或导数值，构造2 次或次或3次多项式作为次多项式作为()的近似值，以这多项式的极小点的近似值，以这多项式的极小点为新的迭代点。为新的迭代点。 3点点2次，次，2点点2次，次，4点点3次，次，3点点3次，次，2点点3次等次等 以以3点点2次为例：次为例： 取取 1， 2，3，求出，求出(1)， (2)， (3)割线法（一维拟牛顿法）割线法（一维拟牛顿法） 牛顿特点是收敛快效率高，但每步要计算二阶导数，

7、牛顿特点是收敛快效率高，但每步要计算二阶导数，在函数复杂时，求导数是很难的。可用差商近似导数，则在函数复杂时，求导数是很难的。可用差商近似导数，则牛顿切线法公式变换为牛顿切线法公式变换为111()()()()kkkkkkkfxxxxxfxfx11()()()kkkkkfxfxfxxx它的几何意义是用两点它的几何意义是用两点xk-1 ， xk的割线代替的割线代替f (x)在点在点xk的切线。的切线。它不需计算它不需计算二阶导数二阶导数，但它收敛速度也慢于，但它收敛速度也慢于切线法。切线法。 二次插值多项式：二次插值多项式： g(x) = x2 + x + x12 + x1 + = g(x1) x

8、22 + x2 + = g(x2) x32 + x3 + = g(x3) 解得解得)()()()()()()()(133221213132321xxxxxxxgxxxgxxxgxx)()()()()()()()(133221221231232232221xxxxxxxgxxxgxxxgxxxxxxg*,2,0)(则得令插值法插值法 设设 a,b是是f(x)的单谷区间的单谷区间 ，x*为为f(x)在在a,b中的极小点，中的极小点，在在a,b中任取中任取x2 ，令，令x1=a,x3=b, 用如下用如下二次插值多项式插值二次插值多项式插值设有多维无约束非线性规划设有多维无约束非线性规划nRxxf),

9、(min(2.4.1)算法概述算法概述问题问题1、如何选择初始点？、如何选择初始点？2、如何、如何产生新点产生新点xk+1 ，即，即如何确定搜索方向和步长？如何确定搜索方向和步长？3、选择什么迭代终止准则好？、选择什么迭代终止准则好？算法的收敛速度算法的收敛速度 问题问题 对于某一确定的下降算法，其优劣如何评价？人们对于某一确定的下降算法，其优劣如何评价？人们通常通常采用收敛速度来评价。采用收敛速度来评价。下面给出度量收敛速度的几个概念。下面给出度量收敛速度的几个概念。复习梯度的性质：复习梯度的性质：函数在某点的梯度方向为函数过该点的等值线的法线方向；函数在某点的梯度方向为函数过该点的等值线的

10、法线方向；函数值沿梯度方向增加最快，沿负梯度方向下降最快；函数值沿梯度方向增加最快，沿负梯度方向下降最快；梯度描述的只是函数某点邻域内的局部信息。梯度描述的只是函数某点邻域内的局部信息。参见参见P27图图2-16。梯度法（最梯度法（最 速速 下降法）下降法） 对于迭代式，当取搜索方向为负梯度方向时构成的寻对于迭代式，当取搜索方向为负梯度方向时构成的寻优算优算法，称为求解无约束优化问题的梯度法。法，称为求解无约束优化问题的梯度法。迭代步骤迭代步骤梯度法的特点梯度法的特点 梯度法寻优效率受目标函数性态影响较大。若目标函数梯度法寻优效率受目标函数性态影响较大。若目标函数等值等值线为圆，则一轮搜索就可

11、找到极致点；若当目标函数等值线为扁线为圆，则一轮搜索就可找到极致点；若当目标函数等值线为扁椭圆时，收敛速度则显著下降。椭圆时，收敛速度则显著下降。梯度法中相邻两轮搜索方向相互垂直。梯度法中相邻两轮搜索方向相互垂直。Newton法法设设f(x)二阶可微，取二阶可微，取f(x)在在x(k)点附近的二阶点附近的二阶Taylor近似函数：近似函数： gk(x)=f(x(k)+ Tf(x(k)(x-x(k) +12 (x-x(k)T2f(x(k) (x-x(k) 求驻点：求驻点： gk(x)= f(x(k)+ 2f(x(k) (x-x(k)=0当当2f(x(k) 正定时，有极小点：正定时，有极小点： x

12、(k+1)=x(k)-2f(x(k) -1 f(x(k) Newton迭代公式迭代公式 二维二维Newton法的几何意义法的几何意义:在在x(0)点附近点附近,把曲面把曲面z= f(x),用它用它在在该点的密切抛物面该点的密切抛物面z= g0(x)近似代替近似代替,然后再用然后再用g0(x)的最小点的最小点x(1)作作为新的起点为新的起点,用同样的方法去找用同样的方法去找x(k),直到直到| 2f(x(k) |0, k=12f(x(k) , s(k) = -2f(x(k) 2f(x(k) | 2f(x(k) |0s(0)=- f(x(1),k=0k=k+1| f(x(k)|0令x(k+1)=x

13、(k)+tk s(k) K0, k=0s(k)=-H(k) f(x(k)一维搜索得tkx(k+1)=x(k)+ tk s(k)|x(k+1)-x(k)| ?修正H(k)产生H(k+1)Stop. x(k+1)-解k=k+1yNkn-1Nyx(0)=x(n)s(0)=-H(0) f(x(0),k=0拟牛顿法的算法拟牛顿法的算法拟牛顿法的算法优拟牛顿法的算法优缺点：缺点：优优点：点： 收敛速度快，一般可达到超线性收敛；只需用到函数的一阶收敛速度快，一般可达到超线性收敛；只需用到函数的一阶梯度；（梯度；（Newton法用到二阶法用到二阶Hesse阵）阵）对于正定二次函数，有二次终结性（至多对于正定二次函数，有二次终结性（至多n次迭代可达次迭代可达opt