运筹学-非线性规划.ppt

《运筹学-非线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学-非线性规划.ppt（192页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、高级运筹学非线性规划教材及参考书指定教材：沈荣芳，运筹学高级教程（第二版），高等教育出指定教材：沈荣芳，运筹学高级教程（第二版），高等教育出版社，版社，2008.8参考资料：参考资料：1.韩伯棠，管理运筹学（第三版），高等教育出版社，韩伯棠，管理运筹学（第三版），高等教育出版社，2013.122.FREDERICK S.HILLIER GERALD J.LIEBERMAN，INTRODUCTION TO OPERATIONS RESEARCH，Ninth Edition,20103.吴祈宗，运筹学与最优化方法（第二版），机械工业出版社，吴祈宗，运筹学与最优化方法（第二版），机械工业出版社，20

2、124.David G.Luenberger，Linear and Nonlinear Programming，Springer，2008非线性规划非线性规划非线性规划 在科学管理和其他领域中，大量应用问题可以归结为线性规划问在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外一些问题，其目标函数和（或）约束条件很难用题，但是，也有另外一些问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。线性函数，则这样的规划问题就属于非

3、线性规划。一般来说，求解非线性规划问题比线性规划问题困难得多。而且，一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法，非线性规划目前还也不象线性规划那样有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。没有适合于各种问题的一般算法，这是需要深入研究的一个领域。非线性规划研究核心问题：非线性规划研究核心问题：u 最优性条件（必要条件，充分条件，最优性条件（必要条件，充分条件，LagrangeLagrange乘子理论，灵敏性乘子理论，灵敏性分析，对偶理论）分析，对偶理论）u 迭代算法迭代算法解解:

4、设投资决策变量为设投资决策变量为问题归结为总资金的限制条件下问题归结为总资金的限制条件下,极大化总收益和总投资之比极大化总收益和总投资之比,数学模型为数学模型为 1,(i=1,2,n)0,iixii=决定投资第决定投资第 个项目个项目决定不投资第决定不投资第 个项目个项目例：投资决策问题例：投资决策问题某企业有某企业有n个项目可供选择投资个项目可供选择投资,并且至少要对其中一个项目投资并且至少要对其中一个项目投资.已知该企业拥有总资金已知该企业拥有总资金A元元,投资于第投资于第i(i=1,2,n)个项目需要花个项目需要花资金资金ai 元元,并预计收益为并预计收益为bi元元,试选择最佳投资方案使

5、得总收益和试选择最佳投资方案使得总收益和总投资之比最大总投资之比最大.一般地，非线性规划的数学模型为一般地，非线性规划的数学模型为 其中其中 X称为可行域称为可行域可行域中的点可行域中的点 称为可行点，称为可行点，f(x)称为目标函数称为目标函数当当 时，非线性规划模型称为无约束问题；时，非线性规划模型称为无约束问题；当当 时，非线性规划模型称为有约束问题时，非线性规划模型称为有约束问题使使f(x)在在X上取得最小值的点称为最优解，对应的目标函数值称为上取得最小值的点称为最优解，对应的目标函数值称为最优值最优值定定义义：如如果果目目标标函函数数或或约约束束条条件件中中至至少少有有一一个个是是非

6、非线线性性函函数数，则则称这种规划为非线性规划问题。称这种规划为非线性规划问题。为统一起见为统一起见,称以下模型称以下模型 min f(x)s.t.gi(x)0 i=1，2，m （1）hj(x)=0 j=1，2，l为为标标准准的的非非线线性性规规划划模模型型,其其中中f(x),gi(x),hj(x)中中至至少少有有一一个个是是x的非线性函数的非线性函数.称称gi(x)0为不等式约束为不等式约束,hj(x)=0为等式约束为等式约束.满足所有约束条件的满足所有约束条件的x称为可行解称为可行解,所有可行解构成的集合所有可行解构成的集合称为可行域。称为可行域。例例:考虑如下非线性规划问题：考虑如下非线

7、性规划问题：min f(x)=(x14)2+(y15)2 1/2 s.t.(x-8)2+(y-9)2 49 x 2，x 13 x+y 24 非线性规划的最优解未必在顶点处达到；非线性规划的最优解未必在顶点处达到；非线性规划的最优解是一组同心圆最先与非线性规划的最优解是一组同心圆最先与可行域相交的点，在可行域的边界上达到可行域相交的点，在可行域的边界上达到二维非线性规划问题二维非线性规划问题的图解分析的图解分析例：请考虑如下非线性规划问题：例：请考虑如下非线性规划问题：min f(x)=(x8)2+(y8)2 s.t.(x-8)2+(y-9)2 49 x 2，x 13 x+y 24 非线性规划的

8、最优解在可行域内部达到非线性规划的最优解在可行域内部达到可以看出可以看出,x2,x3,x4是局部最优解是局部最优解,且且x3还是全局最优解还是全局最优解,x1,x2,x3,x5是严格局部最优解是严格局部最优解,x4不是严格局部最优解不是严格局部最优解.xf0 x1x2x3x4x5f(x)D一个全局最优解一定是局部最优解，反之不真。一个全局最优解一定是局部最优解，反之不真。对求极小化非线性规划问题，如果目标函数为凸函数，可行域为凸集，对求极小化非线性规划问题，如果目标函数为凸函数，可行域为凸集，则局部最优解一定为全局最优解。则局部最优解一定为全局最优解。与线性规划不同与线性规划不同,非线性规划有

9、局部最优解和全局最优解之分非线性规划有局部最优解和全局最优解之分.凸集凸集i)定定义义非非空空集集合合D称称为为凸凸集集,如如果果对对于于任任意意的的x1,x2 D及任意实数及任意实数a,0a1,有有ax1+(1a)x2D.凸凸集集的的几几何何意意义义：若若一一个个集集合合是是凸凸的的，则则该该集集合合中中任任意意两两点的线段也必包含在此集合中。点的线段也必包含在此集合中。x1x2Dx1x2D凸集凸集不是凸集不是凸集凸集、凸函数和凸规划凸集、凸函数和凸规划(1)集合集合D=xEn|Axb,x0是凸集。是凸集。例：例：定理：设定理：设D1,D2是是En中的凸集，则中的凸集，则凸函数与凹函数凸函数

10、与凹函数定义定义:D为为凸集凸集,若对任意若对任意x1,x2 D及任意实数及任意实数a,0a1有有f(ax1+(1a)x2)a f(x1)+(1a)f(x2)则称则称 f(x)为为凸函数凸函数凸函数凸函数;若若变为变为,称称f(x)为为严格凸函数严格凸函数严格凸函数严格凸函数。若上式中的若上式中的(),则称则称f(x)为为凹函数凹函数/严格凹函数严格凹函数严格凹函数严格凹函数。凸函数的特征是，曲线上任意两点的连线总是位于这两点间曲线的上方。凸函数的特征是，曲线上任意两点的连线总是位于这两点间曲线的上方。凸函数的判定凸函数的判定(一一阶阶条条件件)：设设 f(x)在在凸凸集集D上上有有一一阶阶连

11、连续续导导数数，则则 f(x)是是D上上凸函数的充要条件是对任意两点凸函数的充要条件是对任意两点x,z D,x z,必有必有如果上式严格成立，则是严格凸函数的充要条件。如果上式严格成立，则是严格凸函数的充要条件。几何意义：凸函数几何意义：凸函数 f(x)在曲在曲线上任何一点做曲线的切线，线上任何一点做曲线的切线，那么那么f(x)都在切线上方。都在切线上方。(二二阶阶条条件件)：设设D是是一一个个非非空空开开凸凸集集，设设f在在D上上二二次次可可微微，则则 f(x)是是凸凸函函数数，当当且且仅仅当当对对所所有有x D,Hessian 矩矩阵阵 是是半正定矩阵半正定矩阵;注意：注意：Hesse矩阵

12、在矩阵在D中的每一点都是正定的，则中的每一点都是正定的，则f是严格是严格凸的；可是，如果凸的；可是，如果f是严格凸的，则是严格凸的，则Hesse矩阵在矩阵在S中的每一中的每一点都是半正定的。点都是半正定的。上述定理在检验函数的凹凸性是有效的，特别是当函数为上述定理在检验函数的凹凸性是有效的，特别是当函数为二次函数时，二次函数时，Hesse矩阵不依赖点矩阵不依赖点x，因此检验其凸性简，因此检验其凸性简化为检验一个单一矩阵的特征值的非负性。化为检验一个单一矩阵的特征值的非负性。例：检验函数例：检验函数f(x1,x2)=2x1+6x2-2x12-3x22+4x1x2是凸的，凹是凸的，凹的。或者两者都

13、不是。的。或者两者都不是。解：将解：将f 改写为下面更方便的形式：改写为下面更方便的形式：以下通过解下面的方程来计算特征值以下通过解下面的方程来计算特征值方程的解为方程的解为凸规划定义：凸规划定义：已知非线性规划已知非线性规划 若若可可行行域域D是是凸凸集集，且且f(x)是是定定义义在在D上上的的凸凸函函数数，则则该该非非线性规划称为凸规划。线性规划称为凸规划。定定理理：对对非非线线性性规规划划，如如果果gj(x)(i=1,2,m)是是En 上上的的凸凸函函数数，hj(x)(j=1,2,p)为为线线性性函函数数，且且f(x)为为可可行行域域D上上的的凸凸函函数数，则则该非线性规划问题是凸规划。

14、该非线性规划问题是凸规划。(作业作业1)定理定理定理定理1 1：设：设D为非空凸集，为非空凸集，f(x)连续，考虑如下问题连续，考虑如下问题(1)如果如果 f 是凸函数，则局部最优解也是全局最优解；是凸函数，则局部最优解也是全局最优解；(2)如果如果 f 是严格凸函数，则是严格凸函数，则 x*为为唯一唯一唯一唯一的全局最优解。的全局最优解。定理定理定理定理(最优性条件最优性条件最优性条件最优性条件):考虑凸规划考虑凸规划 ,(1)x*是最优解的充要条件是对是最优解的充要条件是对xX,有有(2)若若D是开集是开集,x*是最优解的充要条件是是最优解的充要条件是由定理结论由定理结论(1)可知，如果某

15、点可知，如果某点x*是最优解，则对任意是最优解，则对任意xD,向向量量x-x*与函数与函数f在点在点x*处的梯度向量处的梯度向量 所成的角度小于所成的角度小于90。.例：考虑如下非线性规划问题：例：考虑如下非线性规划问题：试验证最优性条件成立。试验证最优性条件成立。分析：题意是要求验证非线性规划的最优解分析：题意是要求验证非线性规划的最优解x*满足满足解：显然，目标函数解：显然，目标函数是凸函数是凸函数,且约束条件为线性函且约束条件为线性函数数,故此规划问题为凸规划故此规划问题为凸规划.点点x*=(1,3)T是唯一最优解是唯一最优解.由于由于f在点在点(1,3)的梯度为的梯度为从图中可以看出，

16、向量从图中可以看出，向量与与 所成的角度小所成的角度小于等于于等于90。.而对点而对点(0,0)T而言，显然不而言，显然不是最优解。因为是最优解。因为对任意非零点对任意非零点xD,有有-3x1-10 x20,即向量即向量(x1-0,x2-0)T 与与 所成角度大于所成角度大于90。,不不满足最优性条件满足最优性条件,原点不会是原点不会是最优解。为使目标函数值下最优解。为使目标函数值下降，最好的局部下降方向是降，最好的局部下降方向是思考题：思考题：如果某凸规划的可行域为如果某凸规划的可行域为D=x|x0，请讨论此凸规划问题，请讨论此凸规划问题的最优解的充要条件的形式。的最优解的充要条件的形式。无

17、约束问题无约束问题 一阶二阶必要和充分条件一阶二阶必要和充分条件等式约束问题等式约束问题 Lagrange 乘子理论乘子理论一般约束问题一般约束问题 一阶二阶必要和充分条件一阶二阶必要和充分条件最优性条件最优性条件二阶必要条件二阶必要条件：设：设f:RnR1在点在点x*Rn 处二阶可微，如果处二阶可微，如果x*是局部极小解是局部极小解,则则f(x*)=0,且且2f(x*)为半正定矩阵为半正定矩阵.对无约束极值问题对无约束极值问题 min f(x)，x Rn （1）一阶必要条件：设一阶必要条件：设f:Rn R1在点在点x*Rn处可微，处可微，如果如果x*是局部极是局部极小点小点,则则 f(x*)

18、=0.定义定义:设设 f:En E1在点在点x*处可微处可微,若若f(x*)=0,称称x*函数函数f的驻点的驻点.驻点驻点极小点极小点驻点驻点极大点极大点驻点驻点鞍点鞍点fOx对无约束极值问题对无约束极值问题 min f(x)，x Rn （1）定理定理(一阶必要条件一阶必要条件)：设：设f:Rn R1在点在点x*Rn处可微，处可微，如果如果x*是是局部极小点局部极小点,则则 f(x*)=0.推论：设推论：设f:Rn R1在点在点x*Rn处可微，处可微，f是是Rn上的凸函数，上的凸函数，如果如果f(x*)=0,则则x*是无约束问题的全局最优解。是无约束问题的全局最优解。定理定理(二阶必要条件二阶

19、必要条件)：设：设f:RnR1在点在点x*Rn 处二阶可微，处二阶可微，如果如果x*是局部极小解是局部极小解,则则f(x*)=0,且且2f(x*)为半正定矩阵为半正定矩阵.注意：该定理仅是必要的，而不是充分的。注意：该定理仅是必要的，而不是充分的。定理定理(二阶充分条件二阶充分条件I)：设设f:RnR1在点在点x*Rn 处二阶可微，如果处二阶可微，如果f(x*)=0,且且2f(x*)为为正定正定矩阵矩阵,则则x*是无约束问题的是无约束问题的严格严格局部极小解局部极小解证明证明:设设 为为 的最小特征值的最小特征值.利用二阶利用二阶Taylor展式有展式有定理定理(二阶充分条件二阶充分条件II)

20、:设设f:EnE1在点在点x*En 的一个邻域的一个邻域 处二阶连续可微，处二阶连续可微，如果如果 f 满足满足f(x*)=0,且且2f(x)在在 内半正定内半正定,则则 x*是是无约束问题的局部极小解无约束问题的局部极小解.思考题：考虑二次函数的无约束极小化问题思考题：考虑二次函数的无约束极小化问题其中其中Q为为n阶对称矩阵，阶对称矩阵，b为为n维列向量。维列向量。等式约束极值问题等式约束极值问题min f(x)，x Rns.t.hi(x)=0,i=1,2,m 最优性条件最优性条件(必要条件必要条件):定理定理:设等式约束问题中函数设等式约束问题中函数f与与hi(x)(i=1,m)是连续可微

21、函数是连续可微函数,x*为局部最优解且为正则点为局部最优解且为正则点(即即 线性无关线性无关,则存在实数组则存在实数组 ,使得使得如果函数如果函数f与与hi(x)(i=1,m)是二次连续可微是二次连续可微,则则注：等式约束问题的一阶必要条件的直观的几何意义：注：等式约束问题的一阶必要条件的直观的几何意义：注注1：定理中给出的一阶必要条件仅当约束函数满足一定条件时：定理中给出的一阶必要条件仅当约束函数满足一定条件时才成立，该条件称为约束规格才成立，该条件称为约束规格注：该定理表明等式约束极值问题的极值点处的目标函数与约束注：该定理表明等式约束极值问题的极值点处的目标函数与约束函数梯度之间通过函数

22、梯度之间通过Lagrange乘子向量存在的关系乘子向量存在的关系,是是Lagrange乘乘子法的出发点子法的出发点.引入拉格朗日函数引入拉格朗日函数L(x,V),其中参数向量其中参数向量 称为称为拉格朗日乘子拉格朗日乘子拉格朗日乘子拉格朗日乘子.n+p个方程解个方程解n+p个未知量可得个未知量可得L的驻点的驻点,但是否驻点就是此非规划模但是否驻点就是此非规划模型的极小解，还需要充分条件的判断；型的极小解，还需要充分条件的判断；但是对于特殊的如二次规划问题，可以通过计算但是对于特殊的如二次规划问题，可以通过计算L对对X的的Hesse矩阵矩阵判定该驻点是极大值点还是极小值点判定该驻点是极大值点还是

23、极小值点.即即定理定理:设等式约束问题中函数设等式约束问题中函数f与与hi(x)(i=1,m)是连续可微函数是连续可微函数,x*为为f的局部最优解的局部最优解,线性无关线性无关,则存在乘子则存在乘子向量向量 ,使得使得练习练习:求等式约束极值问题求等式约束极值问题(书书61-62页页)(充分条件充分条件):定理定理:设等式约束问题中函数设等式约束问题中函数f与与hi(x)(i=1,m)是二次连续可微是二次连续可微函数函数,则则x*是一个极小点是一个极小点。1.含不等式约束的极值问题含不等式约束的极值问题min f(x)，x Rns.t.gi(x)0,i=1,2,m (3)最优性条件最优性条件设

24、设x*是问题是问题(3)的可行解的可行解,约束条件约束条件gi(x)0可分为两类可分为两类,x*点的点的起作用约束起作用约束起作用约束起作用约束(active constraints(active constraints)：gi(x*)=0；x*点的点的不起作用约束不起作用约束不起作用约束不起作用约束(inactive constraints(inactive constraints)：gi(x*)0.记点记点x*处所有起作用约束下标的集合为处所有起作用约束下标的集合为I(x*),即即如何找到在点如何找到在点x0处的可行方向？处的可行方向？如果如果x*为局部最优解为局部最优解,则在该点处不可能

25、存在可行下降方向则在该点处不可能存在可行下降方向.几何意义说明如下几何意义说明如下:设设A1,A2,A3是三个二维向量是三个二维向量.若若A1,A2,A3不在任一条直线的同一不在任一条直线的同一侧侧,就无法找到使就无法找到使AiTp0(i=1,2,3)均均满足的向量满足的向量p.这时总可以适当缩小这时总可以适当缩小或放大各向量或放大各向量Ai的长度的长度,使它们合成使它们合成为零向量为零向量,即可找到不全为零的非负即可找到不全为零的非负实数实数,使使若均位于某直线若均位于某直线H的同一侧的同一侧,则总可则总可找到某一向量找到某一向量p,使使AiTp0(i=1,2,3);定理：设定理：设x*是不

26、等式约束极值问题是不等式约束极值问题(3)的可行解，的可行解，I(x*)为在为在x*起作用起作用约束的下标集合，假设约束的下标集合，假设f(x),gi(x)(i I(x*)在在x*处可微，处可微，如果如果x*是局部最优解，则对于是局部最优解，则对于i I(x*)，存在，存在如果如果gi(x)在在x*处都可微处都可微(i=1,2,m)，则上述结论可叙述为，则上述结论可叙述为存在存在在在x*处连续，向量组处连续，向量组 线性无关。线性无关。此处的此处的(1)(2)两式称为两式称为Krush-Kuhn-Tucker条件，简称条件，简称K-K-T条件；满足条件；满足K-K-T条件的点称为条件的点称为K

27、-K-T点。点。可表示为的非负线性组合.由此可见,若x*是K-K-T点,目标函数在点x*处的负梯度K-K-T条件的几何意义2.一般约束极值问题的一般约束极值问题的KT条件条件min f(x)，x Rns.t.gi(x)0,i=1,2,m (3)hj(x)=0,j=1,2,p 最优性条件最优性条件则存在则存在及及使得使得线性无关线性无关.如果如果x*是局部最优解是局部最优解,定理：设定理：设x*是一般约束极值问题是一般约束极值问题(3)的可行解的可行解,I(x*)为在为在x*起作用约束起作用约束的下标集合的下标集合,假设假设gi(x)(i=1,2,m)在在x*处连续处连续,f(x),gi(x)(

28、i I(x*)在在x*处可微处可微,hj(x)(j=1,2,p)在在x*的某邻域内连续可微的某邻域内连续可微,约束规格约束规格如果如果在在x*也是可微的，则也是可微的，则最优性条件最优性条件前面的定理表明前面的定理表明,如果局部最优解满足约束规格如果局部最优解满足约束规格,则则K-K-T条件成条件成立立;如果局部最优解不满足约束规格，则如果局部最优解不满足约束规格，则K-K-T条件条件可能可能不存在解不存在解.Krush-Kuhn-Tucker条件是确定某点为最优解的必要条件条件是确定某点为最优解的必要条件,只要只要是最优解是最优解,且此处起作用约束的梯度线性无关且此处起作用约束的梯度线性无关

29、,就一定满足就一定满足K-K-T条件条件,但一般来说它并不是充分条件但一般来说它并不是充分条件.因而因而,满足这个条件的点不满足这个条件的点不一定是最优点一定是最优点.下面的定理说明下面的定理说明,对于凸规划对于凸规划,Krush-Kuhn-Tucker条件不但是最条件不但是最优点存在的必要条件优点存在的必要条件,同时也是充分条件同时也是充分条件.定理：设定理：设f(x),gi(x)(i=1,2,m),hj(x)(j=1,2,p)在在x*处连续可微，处连续可微，且且f(x),gi(x)(i=1,2,m)是凸函数，是凸函数，hj(x)是线性函数，若是线性函数，若x*是非线性是非线性规划模型的规划

30、模型的K-K-T点，则点，则x*是其全局极小点。是其全局极小点。最优性条件最优性条件最优性条件最优性条件二次规划及其应用二次规划是一个有二次目标函数和线性约束条件的优化问题,其数学模型如下：二次规划的K-K-T条件引入松弛变量S,使之成为等式S=b-AX,并分别设与条件AXb和X0对应的Lagrange乘子向量为u和v，则二次规划的K-K-T条件为二次规划及其应用二次规划及其应用由于二次规划是凸规划,故点X*是最优解的充要条件是存在u,v,S,X共同满足以上K-K-T条件.于是,原问题的最优解等价于找以上K-K-T条件的可行解.二次规划及其应用二次规划及其应用至此，对二次规划的求解已经转化为线

31、性互补问题，可以用互补转轴算法找出二次规划的K-K-T点。例：写出二次规划的K-K-T条件：称为互补松弛条件，即u1,s1不能同时为零，vi和xi不能同时为零。二次规划及其应用二次规划及其应用例：考虑二次规划问题解：设与约束条件x1+x22,-x1+2x22,x10,x20对应的Lagrange乘子向量分别用u=(u1,u2)T和v=(v1,v2)T表示，二次规划及其应用二次规划及其应用于是，可得K-K-T条件如下：二次规划及其应用二次规划及其应用线性互补问题线性互补问题如何解决线性互补问题？线性互补问题线性互补问题线性互补问题线性互补问题线性互补问题线性互补问题100001000010000

32、100-1-1001-21-1-22122-4-122-2-6-1-1-1（）线性互补问题线性互补问题100001000010-1-1-1-111012232-1-3-4-2566-408846001（）线性互补问题线性互补问题10000100-5/6-11/6-2/3-1/60-1/6-1/31101-1/2-11/207/31-2/32/30010014/342/310/3001（）线性互补问题线性互补问题3/7-3/72/70100-5/14-3/7-1/14-3/14-2/7-3/14-11/145/141/710010014/342/310/3001（）-2/7-9/14-1/141

33、/143/74/72/75/7000线性互补问题线性互补问题3/5-1/52/50100-1/10-3/51/10-1/10-2/7-3/1003/101/5100104/56/514/5-2/5-3/101/1000-9/1001000-3/5-4/5-2/57/52/5对于可微函数对于可微函数 f(x)来说，为了求最优解，可以令梯度来说，为了求最优解，可以令梯度由此求得驻点，然后再利用充分条件进行判别。但是，对于一由此求得驻点，然后再利用充分条件进行判别。但是，对于一般的般的n元函数元函数 f(x)来说来说,令令 得到的常是一个非线性方得到的常是一个非线性方程组，求解相当困难；此外，很多实

34、际问题往往很难求出或根程组，求解相当困难；此外，很多实际问题往往很难求出或根本求不出目标函数对各自变量的偏导数，从而使得一阶必要条本求不出目标函数对各自变量的偏导数，从而使得一阶必要条件很难应用。因此，除个别情形外，一般都是采用迭代法而不件很难应用。因此，除个别情形外，一般都是采用迭代法而不是从令是从令 求解的。求解的。搜索算法概述搜索算法概述迭代算法的基本思想：迭代算法的基本思想：首先,确定目标函数f(x)的极小点x*的一个初始估计点x(0),然后按照一定的迭代规则(即所谓算法)，先找到一个比x(0)更好的点x(1),即f(x(1)f(x(0),再找比x(1)更好的点x(2),如此继续下去,

35、得到点列x(k),k=1,2,使得当点列x(k)是有穷点列时，其最后一个点是非线性规划问题的最优解；当点列x(k)是无穷点列时,它有极限点x*，且极限点x*就是非线性规划问题的最优解.对极小化问题对极小化问题,要求按照某一算法产生的点列要求按照某一算法产生的点列x(k)满足以下性质：满足以下性质：具有这种性质的算法称为具有这种性质的算法称为下降迭代算法下降迭代算法下降迭代算法下降迭代算法.下降迭代算法的一般迭代格式：使用迭代算法求解非线性规划问题的关键在于如何构造每一轮的搜索方向和确定适当的步长！(1)选取某一初始迭代点x(0);(2)确定搜索方向：若已得一迭代点x(k),且x(k)不是极小点

36、,就从x(k)出发确定一搜索方向p(k),沿这一方向找到使目标函数值下降的点.(3)确定步长：沿p(k)方向前进一个步长,得到下一迭代点xk+1),即在由点x(k)出发的射线x=x(k)+tp(k)(t0),选定步长t=tk,得到下一迭代点x(k+1)=x(k)+tkp(k),使得f(x(k+1)f(x(k).(4)检验新的迭代点是否为要求的极小点或近似极小点，如果满足要求，迭代停止；否则令k=k+1,转步骤(2)继续迭代.当已知迭代点和下降方向时，要确定适当的步长，按照当已知迭代点和下降方向时，要确定适当的步长，按照对步长选取的不同原则，可分为两种类型：对步长选取的不同原则，可分为两种类型：

37、(1)最优一维搜索最优一维搜索：用一定方法求得步长：用一定方法求得步长 tk,使目标函数使目标函数 f 从当前点从当前点 x(k)出发沿方向出发沿方向 p(k)取得最优值，即取得最优值，即 即求步长即求步长 tk,使得使得(2)可接受一维搜索：可接受一维搜索：即寻找步长即寻找步长 精确一维搜索的重要性质：精确一维搜索的重要性质：图：精确一维搜索时搜索方向与图：精确一维搜索时搜索方向与最优点处函数等值面相切最优点处函数等值面相切常用的终止迭代准则有：常用的终止迭代准则有：(1)根据相继两次迭代结果的绝对误差根据相继两次迭代结果的绝对误差:(2)根据相继两次迭代结果的相对误差根据相继两次迭代结果的

38、相对误差:(3)根据函数梯度的模足够小根据函数梯度的模足够小:算法的收敛性常同初始点选择有关。算法的收敛性常同初始点选择有关。（1）当点）当点x0充分接近于最优解充分接近于最优解x*时，由某方法产生的点列才收时，由某方法产生的点列才收敛于敛于x*，则该方法叫做具有，则该方法叫做具有局部收敛性局部收敛性；（2）对任意初始点）对任意初始点x0，由某方法产生的点列都收敛到，由某方法产生的点列都收敛到x*，则该，则该方法叫做具有方法叫做具有全局收敛性全局收敛性；（3）若某方法经过有限轮迭代就可达到目标函数为二次函数的）若某方法经过有限轮迭代就可达到目标函数为二次函数的无约束非线性规划模型的最优解，此方

39、法叫做具有无约束非线性规划模型的最优解，此方法叫做具有二次收敛性二次收敛性.通常，一个非线性规划算法还要求具有收敛性：设由该算法通常，一个非线性规划算法还要求具有收敛性：设由该算法产生的迭代点列为产生的迭代点列为 ，当点列为有穷点列时，其最后一个，当点列为有穷点列时，其最后一个点是最优解，当点列为无穷点列时，在某种模的意义下它收点是最优解，当点列为无穷点列时，在某种模的意义下它收敛于问题的最优解，即敛于问题的最优解，即 各种迭代算法的迭代过程是相同的，无论是求解无约束极值问题各种迭代算法的迭代过程是相同的，无论是求解无约束极值问题或是求解约束极值问题，在确定最优步长的过程中往往都会遇到或是求解

40、约束极值问题，在确定最优步长的过程中往往都会遇到一元函数极值问题，以下将介绍一元函数求极值的直接方法一元函数极值问题，以下将介绍一元函数求极值的直接方法一维搜索法一维搜索法一维搜索法一维搜索法对一维极小化问题对一维极小化问题,设设 a,b是目标函数是目标函数 的的单峰区间单峰区间。其其本本思思路路是是：找找出出已已知知包包含含最最优优解解点点的的单单峰峰区区间间，通通过过迭迭代代逐逐渐渐缩缩小小单单峰峰区区间间的的长长度度以以达达到到任任何何所所需需的的精精度度来来近近似似确确定定最优点的位置。最优点的位置。一维搜索法主要用于严格一维搜索法主要用于严格单峰函数单峰函数的一元函数。的一元函数。一

41、个区间是某函数的单峰区间意味着该区间中函数只有一个极小值一个区间是某函数的单峰区间意味着该区间中函数只有一个极小值.在单峰区间上的函数，即单峰函数如下图在单峰区间上的函数，即单峰函数如下图(1)所示：所示：(1)(2)图图:单峰区间与单峰函数单峰区间与单峰函数单峰函数的重要性质单峰函数的重要性质通过单峰区间内相异两点函数值的通过单峰区间内相异两点函数值的计算，可以划定极小值点所在位置。计算，可以划定极小值点所在位置。设设 a,b是是目目标标函函数数 的的单单峰峰区区间间。以以下下介介绍绍的的两两种种方方法法不不是是直直接接找找出出最最优优点点，而而是是通通过过不不断断缩缩短短单单峰峰区区间间长

42、长度度来来搜搜索索并并得得到到一一维维极极小小化化问问题题的的两两种种近近似似求求解解方方法法二二分分法法、黄黄金分割法与斐波那契法。金分割法与斐波那契法。对一维极小化问题对一维极小化问题,设已知单峰函数设已知单峰函数 的峰点的峰点t*(最小点最小点)处在处在t=a,b区间区间(见下图见下图a)在在a,b中中,任任取取两两点点t1、t2 且且t1t2,计计算算 和和 则则t*必必在在区区间间a,t2(如下图如下图(a),或者或者t*必在必在t1,b中中(如下图如下图(b).0a t*t1t2bt (a)0a t1t*t2bt (b)这样反复进行，直到把区间缩小到一定精度为止。这样反复进行，直到

43、把区间缩小到一定精度为止。由由此此可可知知，随随着着迭迭代代次次数数的的增增加加，包包含含t*的的子子区区间间长长度度越越来来越越短短，而而这这一工作是通一工作是通过过一次次一次次计计算并比算并比较较有关点有关点处处函数函数值值来来实现实现的。的。问问题题：如如何何选选取取比比较较点点的的位位置置，可可使使在在进进行行相相同同迭迭代代次次数数之后，之后，“浓缩浓缩”的区的区间长间长度尽可能地短？度尽可能地短？可见可见,只要在只要在a,b内任取两点内任取两点,就必能把就必能把t*压缩在区间压缩在区间a,t2或或t1,b内内.若要继续缩小区间若要继续缩小区间,只需再计算只需再计算1个点又可缩短一部

44、分区间长度个点又可缩短一部分区间长度.二分法二分法的具体做法如下：令的具体做法如下：令I0=a,b为当前的搜索区间为当前的搜索区间,二分法中取的点二分法中取的点a1和和b1的值关于当前搜索区间的中点对称，的值关于当前搜索区间的中点对称，这意味着这意味着重复运用这一算法就保证搜索的区间的长度将趋向于所需要重复运用这一算法就保证搜索的区间的长度将趋向于所需要的精度的精度.但是，在二分法的每次迭代时要计算两个值但是，在二分法的每次迭代时要计算两个值f(t1)和和f(t2),但最但最后又放弃了一个，黄金分割法通过在每次迭代中将放弃的这后又放弃了一个，黄金分割法通过在每次迭代中将放弃的这个值利用起来，以

45、节省计算量。个值利用起来，以节省计算量。黄金分割法黄金分割法的具体做法如下：令的具体做法如下：令I0=a,b为当前的搜索区间为当前的搜索区间,则下一步迭代的搜索区间则下一步迭代的搜索区间I1=a,t2 或或t1,b.考虑搜索区间为考虑搜索区间为I1=a,t2 的情形，这意味着的情形，这意味着t1包含在区间包含在区间I1中，中，在第二次迭代时选择在第二次迭代时选择t2等于第一次迭代时的等于第一次迭代时的t1，可以推出，可以推出，黄金分割法的设计保证搜索区间可以减少为上次迭代的黄金分割法的设计保证搜索区间可以减少为上次迭代的 倍倍黄金分割法比二分法收敛更快黄金分割法比二分法收敛更快斐波那契法斐波那

46、契法斐波那契法优点斐波那契法优点寻优收敛快寻优收敛快,计算次数少计算次数少;斐波那契法缺点斐波那契法缺点 每步取点繁琐；每步取点繁琐；开始寻优之前计算函数值的次数需事先知道；开始寻优之前计算函数值的次数需事先知道；各步缩短率不同。各步缩短率不同。这里的二分法、黄金分割法和斐波那契法都属于用直接法解这里的二分法、黄金分割法和斐波那契法都属于用直接法解决单变量函数的优化问题的方法，即只用到函数值，而未用决单变量函数的优化问题的方法，即只用到函数值，而未用到函数的解析性质。到函数的解析性质。通常，直接法的收敛速度较慢，只在变量较少时才适用。但通常，直接法的收敛速度较慢，只在变量较少时才适用。但直接法

47、的迭代步骤简单，特别是当目标函数的解析表达式十直接法的迭代步骤简单，特别是当目标函数的解析表达式十分复杂，甚至写不出具体的表达式或它们的导数很难求得，分复杂，甚至写不出具体的表达式或它们的导数很难求得，或根本不存在，就只有用直接法了或根本不存在，就只有用直接法了.多维无约束寻优方法 无约束极值问题可简单表述为：无约束极值问题可简单表述为：min f(x)，x Rn 求求解解非非线线性性规规划划问问题题的的迭迭代代法法，关关键键是是如如何何求求出出每每步步的的搜搜索索方方向向p(k)及及步步长长t。由由于于确确定定p(k)及及t的的途途径径不不同同，从从而而导导致致不不同同的的寻寻优优方方法。其

48、中可分两大类法。其中可分两大类:解析法解析法解析法解析法：迭代中需用到函数的一阶导数：迭代中需用到函数的一阶导数(梯度梯度)或二阶导数或二阶导数;直接法直接法直接法直接法：迭代中不用函数的导数等解析性质。：迭代中不用函数的导数等解析性质。x(k+1)=x(k)+p(k)且满足fx(k+1)fx(k)，逐步迭代直至满足精度条件fx(k+1)1或fx(k+1)fx(k)2时迭代停止(其中1，2为给定精度)。梯度法梯度法最速下降法最速下降法最速下降法最速下降法(1)搜索方向搜索方向p(k)的确定的确定设设p为为单单位位向向量量,|p|=1.考考虑虑从从点点x(k)出出发发沿沿方方向向p取取步步长长t

49、得得到到邻邻近近点点x(k)+tp，由由于于选选择择方方向向时时只只考考虑虑到到当当前前下下降降最最快快，未未顾顾及及到到总总寻寻优优快快慢慢，因而最速下降法又称因而最速下降法又称“瞎子爬山法瞎子爬山法”。(3)算法终止条件：算法终止条件：通常用通常用f(x(k)=0或或|f(x(k)|0是充分小的正数是充分小的正数)作为最速作为最速下降法的迭代终止条件下降法的迭代终止条件.最速下降法的优缺点最速下降法的优缺点:(1)方法简单，每一轮迭代工作量少，所需计算的存储量也少方法简单，每一轮迭代工作量少，所需计算的存储量也少,且且此法对初始点的选取没有特别要求。此法对初始点的选取没有特别要求。(2)由

50、于梯度是局部性质，从一点的邻近来说函数值下降的快由于梯度是局部性质，从一点的邻近来说函数值下降的快,对对于整个求解极小点过程不一定是最快的；于整个求解极小点过程不一定是最快的；(3)用最速下降法寻找极小点时，用最速下降法寻找极小点时，搜索路径呈直角锯齿形搜索路径呈直角锯齿形，开头，开头几步目标函数下降较快，但是当接近极小点时，搜索步长较小几步目标函数下降较快，但是当接近极小点时，搜索步长较小收敛速度减慢。收敛速度减慢。为了克服最速下降法的搜索路径呈锯齿形的困难，后面介绍的为了克服最速下降法的搜索路径呈锯齿形的困难，后面介绍的算法将不再沿算法将不再沿 方向移动，而是沿方向移动，而是沿 或或 其中