第六章非线性规划

1、 赵 超建筑工程学院 2013年1月Page 2基本概念基本概念凸函数和凸规划凸函数和凸规划一维搜索方法一维搜索方法无约束最优化方法无约束最优化方法约束最优化方法约束最优化方法Page 3第一节第一节 基本概念基本概念非线性规划问题非线性规划问题非线性规划方法概述非线性规划方法概述Page 4一、非线性规划问题引例一、非线性规划问题引例例例1 曲线的最优拟合问题曲线的最优拟合问题已已知知某某物物体体的的温温度度 与与时时间间 t 之之间间有有如如 下下形形式式的的经经验验函函数数关关系系： tcetcc321 (*) 其其中中1c，2c，3c是是待待定定参参数数。现现通通过过测测 试试获获得得

2、 n 组组 与与 t 之之间间的的实实验验数数据据),(iit ， i=1，2，,n。试试确确定定参参数数1c，2c，3c， 使使理理论论曲曲线线(*)尽尽可可能能地地与与 n 个个测测试试点点 ),(iit 拟拟合合。 t n1i221)( min3 itciietcc Page 5例例2 构件容积问题构件容积问题x1x2x3 0, 0 2 .)3/1 ( max212121222211221xxSxxxxaxxtsxxaV 设计一个右图所示的由圆锥和圆柱设计一个右图所示的由圆锥和圆柱面围成的构件，要求构件的表面积面围成的构件，要求构件的表面积为为S，圆锥部分的高，圆锥部分的高h和圆柱部分的

3、和圆柱部分的高高x2之比为之比为a。确定构件尺寸，使其。确定构件尺寸，使其容积最大。容积最大。hPage 6二、二、 数数 学学 模模 型型 qjxhpixgRxDjin,.,1, 0)(,.,1, 0)(约束集约束集或或可行域可行域 qjxhpixgtsxfPji,.,1, 0)( ,.,1, 0)( .)( min)(模型的一般形式模型的一般形式其中其中x=(x1,x2,.,xn )TRn ，的的实实值值函函数数为为xxgxhxfji)(),(),(D中的点称为中的点称为可行解可行解或或可行点可行点)(minxfDx模型也可写成Page 7三、三、 分分 类类（1）线性规划：目标函数和约束

4、条件皆为）线性规划：目标函数和约束条件皆为x的线的线性函数。性函数。（2）非线性规划：目标函数和约束条件中至少）非线性规划：目标函数和约束条件中至少有一个是有一个是x的非线性函数。的非线性函数。本章讨论非线性规划。本章讨论非线性规划。（1）当）当p=0,q=0 ,即可行域即可行域D=Rn 时，时， (P)可可 写成写成)(minxf称为无约束非线性规划或无约束最优化问题。称为无约束非线性规划或无约束最优化问题。（2）若可行域）若可行域DRn ， (P)称为约束非线性规划称为约束非线性规划或约束最优化问题。或约束最优化问题。Page 8定义定义 1 对于非线性规划对于非线性规划(P)，若，若 并

5、且存在并且存在x*的一个邻域的一个邻域 0 )(* ，xxRxxNnDxNxxfxf)( ),()(* 则则x*称为称为局部最优解局部最优解或或局部极小点局部极小点，称称f(x*)为为局部最优值局部最优值或或局部极小值局部极小值。* ,)( ),()(xxDxNxxfxf 则称则称x*为为严格局部最优解严格局部最优解或或严格局部极小点严格局部极小点,称称f(x*)为为严格局部最优值严格局部最优值或或严格局部极小值严格局部极小值。 若使得若使得,*Dx 使得使得四、最优解和最优值四、最优解和最优值Page 9四、最优解和最优值四、最优解和最优值Page 10 010101.),(min21212

6、22121xxxxtsxxxxf全局最优解为全局最优解为x*=(1/2,1/2)T ,全局最优值为全局最优值为f(x*)=1/2。1 x1x21x*若目标函数改为：若目标函数改为：222121)32()32(),(min xxxxf其最优解和最优值如何？其最优解和最优值如何？Page 11五、非线性规划方法概述五、非线性规划方法概述迭代法迭代法:按某种方法给出目标函数极小点的一个初始估计，按某种方法给出目标函数极小点的一个初始估计，称为初始点。然后按某种特定的迭代规则产生一称为初始点。然后按某种特定的迭代规则产生一点列点列xk，使得，使得xk 为有穷点列时，其最后一个为有穷点列时，其最后一个点

7、是最优解；当点是最优解；当 xk 是无穷点列时，其极限点是无穷点列时，其极限点是最优解是最优解(此时称该方法是收敛的此时称该方法是收敛的)。kkkxxx 10,1 kkkkktptxx或或的的步步长长。轮轮沿沿搜搜索索方方向向为为第第轮轮搜搜索索方方向向，为为第第称称kkkpktkpPage 12，设设0,: pRpRxRRfnnn，使使得得若若0 定义定义3), 0( ),()( txftpxf则称向量则称向量p是函数是函数f(x)在点在点 处的下降方向。处的下降方向。x，设设0, pRpDxRDnn定义定义4Dtpx ，使使得得若若0 t则称向量则称向量 p是函数是函数 f (x)在点在点

8、 处的可行方向。处的可行方向。xPage 13基本迭代格式基本迭代格式第第1步步 选取初始点选取初始点 ,0 xk:=0;第第2步步 构造搜索方向构造搜索方向kpkpkt第第3步步 根据根据，确定步长，确定步长kkkkptxx 1令令第第4步步 若若x k+1已满足某种终止条件，停止迭代，输出已满足某种终止条件，停止迭代，输出近似解近似解. 否则令否则令k:=k+1，转回第，转回第2步。步。Page 14随机性方法随机性方法是按照某种规则随机产生迭代点是按照某种规则随机产生迭代点, 迭代迭代点列依概率收敛到最优解，包括遗传算法点列依概率收敛到最优解，包括遗传算法,模拟退火模拟退火算法算法,神经

9、网络算法等神经网络算法等,这类方法具有对函数性质要这类方法具有对函数性质要求低、容易实现等优点求低、容易实现等优点, 但效率低、可靠性差、不但效率低、可靠性差、不能保证产生优化问题的最优解能保证产生优化问题的最优解.全局优化算法概述全局优化算法概述全局优化方法可分为随机性方法和确定性方法全局优化方法可分为随机性方法和确定性方法.Page 15全局优化算法概述全局优化算法概述确定性方法确定性方法充分利用了问题的解析性质充分利用了问题的解析性质, 如函数的如函数的凸性、单调性、稠密性等凸性、单调性、稠密性等, 产生一个确定性的有限产生一个确定性的有限或无限点序列或无限点序列, 使得该点序列收敛于全

10、局最优解使得该点序列收敛于全局最优解. 包包括分枝定界算法、区间算法、填充函数法、割平面括分枝定界算法、区间算法、填充函数法、割平面法、顶点枚举法等法、顶点枚举法等,这类算法在理论上有较强的可行这类算法在理论上有较强的可行性性, 但对较为复杂的大型优化问题却难于应用但对较为复杂的大型优化问题却难于应用.全局优化方法可分为随机性方法和确定性方法全局优化方法可分为随机性方法和确定性方法.Page 16第二节第二节 凸函数和凸规划凸函数和凸规划q凸函数及其性质凸函数及其性质q凸规划及其性质凸规划及其性质Page 17一、凸函数及其性质一、凸函数及其性质nRS RSf:，及及)1 , 0( 定义定义

11、5 设设是非空凸集是非空凸集，如果对任意的如果对任意的有有)()1()()1(2121xfxfxxf Sxx 21,则称则称 f 是是S上的上的凸函数凸函数，或，或 f 在在S上是上是凸凸的。的。)1 , 0( 有有，)()1()()1(2121xfxfxxf 21xx 则称则称 f 是是S上的上的严格凸函数，严格凸函数，或或 f 在在S上是上是严格凸的。严格凸的。如果对于任意的如果对于任意的若若 f 是是S上的（严格）凸函数，则称上的（严格）凸函数，则称 f 是是S上的上的（严格）（严格）凹函数凹函数或或 f 在在S上是上是（严格）凹的（严格）凹的Page 18例例1 线性函数线性函数,)(

12、1RbRxabxaxfnT 其中其中在在Rn上既是凸函数又是凹函数。上既是凸函数又是凹函数。例例2 函数函数是是凸凸函函数数。，nRxxxf |)(证证证证Page 19证证: (1) nRS 设设，0 k)(xkf则则)(),(21xfxf若若)()(21xfxf 定理定理 1 (1)若若f(x)是是S上的凸函数，上的凸函数，都是都是S上的凸函数上的凸函数,是是S上的凸函数。上的凸函数。 是非空凸集。是非空凸集。(2)则则也是也是S上的凸函数。上的凸函数。 nRxx 21,)1 , 0(， )()1()()()1()()1(212121xkfxkfxfxfkxxkf 凸函数的性质凸函数的性质

13、Page 20nRS 设设，0 k)(xkf则则定理定理 1 (1)若若f(x)是是S上的凸函数，上的凸函数，是是S上的凸函数。上的凸函数。 是非空凸集。是非空凸集。)()()1()()()()1()()()1()()1()1(2221121122122111212211xfxfxfxfxfxfxfxfxxfxxf 凸函数的性质凸函数的性质)(),(21xfxf若若)()(21xfxf 都是都是S上的凸函数上的凸函数,(2)则则也是也是S上的凸函数。上的凸函数。 证证: (2) nRxx 21,)1 , 0(， Page 21 cxfSxcfHS )(),(nRS RSf:Rc 定理定理 2

14、设设是非空凸集，是非空凸集，是凸函数，是凸函数，则集合，则集合是凸集。是凸集。证：证：),(,21cfHxxS 及及则有则有Sxx 21,cxfcxf )(,)(21水平集水平集SxxS 21)1(),1 , 0( 为凸集，故为凸集，故因因又因又因 f 是是S上的凸函数，所以上的凸函数，所以)1(21xxf )()1()(21xfxf ccc )1( ),()1(21cfHxxS 故故凸函数的性质凸函数的性质Page 22nRS RSf:)()()()(12121xfxfxxxfT Sxx 21, Tnxxfxxfxf)(,.,)()(1111 其中其中1x)()()()(12121xfxfx

15、xxfT 2121,xxSxx 定理定理 3 设设是非空开凸集，是非空开凸集，是函数是函数f在点在点处的梯度处的梯度（1）f是是S上的凸函数的充要条件是上的凸函数的充要条件是（2）f是是S上的严格凸函数的充要条件是上的严格凸函数的充要条件是可微可微，则则凸函数的判定凸函数的判定Page 23)()()()(12121xfxfxxxfT Sxx 21, 有有),1 , 0( 证证 (1) 必要性必要性.设设f是是S上的凸函数，则对上的凸函数，则对)()1 ()()1 (1212xfxfxxf 1211()()f xxxf xSxx 21, 代入得代入得)()(|)(|)()(1212121xfx

16、fxxoxxxfT )()()()(012121xfxfxxxfT 得得：令令 121121()()()()f xxxf xf xf x由泰勒公式得由泰勒公式得|)(|)()(12121xxoxxxfT Page 24)()()()(12121xfxfxxxfT Sxx 21, ,)1 (),1 , 0( 21xxx 取取证证 Sxx 21, )()()()(12121xfxfxxxfT ，是是凸凸的的，故故因因SxS 分分别别有有和和对对SxxSxx ,21SxxfxxxfxfT 111),()()()(SxxfxxxfxfT 222),()()()(（1）（2）得得)1)(2()1( Sx

17、xxfxfxxxxfxfT 212121,),()1()()1()()( )1(21xxf )(xf对对和和 充分性充分性.设设Page 25nRS 22221222222122122122122)()()(.)(.)()()(.)()()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf定理定理 4 设设是非空开凸集，是非空开凸集，则则f 是是S上的凸函数的充要条件是上的凸函数的充要条件是f 的的Hesse矩阵矩阵在在S上是半正定的上是半正定的.注意注意：该逆命题不成立。该逆命题不成立。f在在S上二阶连续可导上二阶连续可导,在在S上正定时，上正定时，f是是S上

18、的严格凸函数上的严格凸函数.)(2xf 当当凸函数的判定凸函数的判定Page 26二二 次次 型型二次型函数二次型函数cxbAxxxfTT 21)(其中其中xR n ,A是一个是一个n阶对称矩阵，阶对称矩阵，1,RcRbn bAxxf )(因因Axf )(2所以当且仅当所以当且仅当A为半正定矩阵时，为半正定矩阵时，f(x)是凸函数。是凸函数。A为正定矩阵时，为正定矩阵时，f(x)是严格凸函数。是严格凸函数。例例上上是是严严格格凸凸函函数数。在在验验证证nRxxxxxxxxxxxxf212131232221321222),( Page 27二、二、 凸规划及其性质凸规划及其性质约束集约束集 qj

19、xhpixgRxDjin,.,1, 0)(,.,1, 0)(如果如果(P)的约束集的约束集D是凸集，目标函数是凸集，目标函数f是是D上的凸函上的凸函数，则数，则(P)叫做叫做非线性凸规划非线性凸规划，或简称为，或简称为凸规划凸规划。 qjxhpixgtsxfPji,.10,)( ,.,1, 0)( .)( min)(非线性规划非线性规划Page 28定理定理 5 对于非线性规划对于非线性规划(P)，若，若，pixgi,.,1),( 并且并且f 是是D上的凸函数，则上的凸函数，则(P)是凸规划。是凸规划。qjxhj,.,1),( 皆为皆为Rn上的凸函数，上的凸函数，皆为线性函数皆为线性函数证：证

20、： ., 10)(|, 10)(|21qjxhRxSpixgRxSjnin ，令令为凸集，为凸集，故故1S为为凸凸集集21SSD 又因又因f 是是D上的凸函数，上的凸函数，(P)是凸规划是凸规划 为凸集为凸集则则pixgRxgHinii,.,1,0)(|)0 ,( 为凸集为凸集同理同理2SPage 29定理定理 6 6 凸规划的任一局部最优解都是它的全局凸规划的任一局部最优解都是它的全局最优解。最优解。证：证：优解，由定义优解，由定义是凸规划的一个局部最是凸规划的一个局部最设设*x使得使得的邻域的邻域存在存在),(*xNx )(),()(*xNDxxfxf 使得使得不是全局最优解，存在不是全局

21、最优解，存在若若,*Dxx )()(*xfxf 又因又因f 是凸函数，所以是凸函数，所以)()1()()1(*xfxfxxf )()()1()(*xfxfxf )()1(,0*xNDxx 有有充充分分小小时时当当矛盾矛盾Page 30例：例： 验证下列规划为凸规划验证下列规划为凸规划 0)(162)(02)(.222),(min32133212322211212131232221321xxxxgxxxxgxxxxgtsxxxxxxxxxxxxfPage 31第三节第三节 一维搜索方法一维搜索方法 非精确一维搜索方法非精确一维搜索方法 Goldstein法法 Armijo法法精确一维搜索方法精确

22、一维搜索方法 0.618法法 Newton法法Page 32max0min( )t tt 目标函数为单变量的非线性规划问题称为一维搜索目标函数为单变量的非线性规划问题称为一维搜索问题问题数学模型数学模型由定义知，由定义知，t*是是 在在a,b上的唯一极小点。上的唯一极小点。)(t 一、基本原理一、基本原理定义定义1 如果存在一个如果存在一个 ，使得，使得 在在 区间区间 上严格递减，且在区间上严格递减，且在区间 上严格上严格递增，则称递增，则称函数函数 在区间在区间a,b上是上是单谷的，单谷的，区间区间 a,b 称为称为 的的单谷区间单谷区间。,*bat )(t ,*ta,*bt)(t )(t

23、 Page 33, 0, 0,maxtbaba 或或给给出出区区间间使得使得,*bat ，称，称a, b为搜索区间。为搜索区间。不断缩短搜索区间的长度，当区间足够小时不断缩短搜索区间的长度，当区间足够小时,得到得到所求问题的近似最优解。所求问题的近似最优解。在区间在区间a,b上任取两点上任取两点t1, t2，设，设t1 t2，有有下下列列两两种种情情形形：,),()()1(2*21tattt 则则 ,),()()2(1*21btttt 则则 然后，然后，Page 34abtbabattbat 1212, 令令)()(1(21abatabat ，则则让下一次迭代中区间缩短相同的比例让下一次迭代中

24、区间缩短相同的比例，并且，并且已有一个计算过的点在缩短后的区间内。已有一个计算过的点在缩短后的区间内。二、二、0.618法（近似黄金分割法）法（近似黄金分割法）abt1t2Page 35abtbabattbat 1212, 令令)()(1(21abatabat ，则则设新的探索区间为设新的探索区间为a ,t2,其上的两个探索点为其上的两个探索点为21tt ，取取或或要求要求121ttt atttatat21222且且)()(21222abttabat ，解解得得012,211 则得则得若令若令tt，不不可可能能1 01,212 则得则得若令若令tt618. 0215 0.618法（近似黄金分割

25、法）法（近似黄金分割法）Page 36abtbabattbat 1212, 令令)()(1(21abatabat ，则则由以上分析得迭代公式：由以上分析得迭代公式：)(382. 01abat )(618. 02abat )(618. 0abb 0.618法（近似黄金分割法）法（近似黄金分割法）Page 37算法步骤：算法步骤：Page 38例例1：试用黄金分割法求解：试用黄金分割法求解12)(min30 tttt 解解 (1) 5 . 0,3 , 0)( 的单谷区间为的单谷区间为t146. 1)03(382. 001 t854. 1)03(618. 002 t6648. 3)(,2131. 0

26、)(2211 tt 5 . 00854. 1),()(221 attt 因因,:,:122tttb 所所以以令令708. 0)0854. 1(618. 0854. 11 t12: 0611. 0)708. 0(1 Page 39 (2) 5 . 0146. 1,221 at 因因122:,:tttb 所以令所以令438. 0)0146. 1(618. 0146. 11 t12: 2082. 0)438. 0(1 (3) 5 . 0708. 0,121 tb 因因211:,:ttta 所以令所以令876. 0)348. 0146. 1(618. 0438. 02 t21: 0798. 0)876

27、. 0(2 (4) 5 . 0438. 0708. 0146. 1,121 tb 因因 得最优解得最优解 ：876. 02 tPage 40三、斐波那契（三、斐波那契（Fibonacci）法）法定义定义2 设数列设数列Fn满足：满足：1)1(10 FF,.2 , 1,)2(11 kFFFkkk数列数列Fk 称为斐波那契（称为斐波那契（Fibonacci）数列）数列 。k0 1 2 3 4 5 6 7 8 Fk1 1 2 3 5 8 13 21 34Page 41一、斐波那契（一、斐波那契（Fibonacci）法）法计算计算n次函数值所得最大缩短率为次函数值所得最大缩短率为1/Fn要把区间缩短为

28、原区间的要把区间缩短为原区间的(0，有，有|)(|)()()(tpopxftxftpxfT 00)( tpxfT，由由于于有有，对对所所以以), 0(0 t0|)(|)( tpopxftT), 0()()( txftpxf，所所以以处的下降方向。处的下降方向。在点在点是是由定义知，由定义知，xfpPage 55定理定理2 处处可可微微，在在点点设设nnRxRRf :若若x*是是(UP)的的0)(* xf定理定理3 存在，存在，矩阵矩阵处的处的在点在点设设)(:*2xfHesseRxRRfnn 正正定定，且且若若)(0)(*2*xfxf 则则x*是是(UP)的严格局部最优解。的严格局部最优解。局

29、部最优解，则局部最优解，则的的驻点。的的驻点。称为函数称为函数的点的点使使fxxf0)( 一、无约束问题的最优性条件一、无约束问题的最优性条件Page 56定理定理4 上上的的可可微微凸凸函函数数，若若是是，设设nnnRfRxRRf,:* 0)(* xf则则x*是是(UP)的全局最优解。的全局最优解。知知上上的的可可微微凸凸函函数数，定定理理是是因因为为3nRfnTRxxfxfxxxf ),()(*)()(*0)(* xf由由于于nRxxfxf ),()(*x*是是(UP)的全局最优解。的全局最优解。一、无约束问题的最优性条件一、无约束问题的最优性条件Page 57例例112322213212

30、4),(minxxxxxxxf 解解0)2 ,8 , 22()(321 Txxxxf令令Tx)001(*，得得驻驻点点 目标函数的目标函数的Hesse矩阵为矩阵为 200080002)(2xf正定，正定，)(2xf 上的凸函数，上的凸函数，是是nRxf)(是全局最优解。是全局最优解。，Tx)001(* 一、无约束问题的最优性条件一、无约束问题的最优性条件Page 58定理定理 4.4.1 设设RRfn:在点在点nRx 处可微。处可微。若存在若存在nRp ，使，使 0)( pxfT 则向量则向量 p 是是 f 在点在点x处的下降方向。处的下降方向。 定定理理 4.4.2 设设RRfn:在在点点n

31、Rx 处处可可微微。若若*x是是(UMP)的的局局部部最最优优解解，则则 0)(* xf 定定理理 4.4.3 设设RRfn:在在点点nRx 处处的的 Hesse 矩矩阵阵)(*2xf 存存在在。若若 0)(* xf，并并且且)(*2xf 正正定定 则则*x是是(UMP)的的局局部部最最优优解解。 定定理理 4.4.4 设设RRfn:，nRx *，f 是是nR上上得得可可微微凸凸函函数数。若若有有 0)(* xf 则则*x是是(UMP)的的整整体体最最优优解解。 一、无约束问题的最优性条件一、无约束问题的最优性条件Page 59二、最速下降法二、最速下降法基本思想：基本思想：从当前点从当前点x

32、k出发，取函数出发，取函数 f(x)在点在点 x k处处下降最快的方向为搜索方向下降最快的方向为搜索方向 pk，即负梯度方向。，即负梯度方向。设目标函数设目标函数f(x)一阶连续可微一阶连续可微.Page 60二、最速下降法二、最速下降法算法步骤：算法步骤：第第1步步 选取初始点选取初始点x0,给定终止误差给定终止误差 0,令令k:= 0；第第2步步 计算计算)(kxf ，停止迭代，停止迭代，若若 |)(|kxf步步；，否否则则转转第第输输出出3kx第第4步步 进行一维搜索，求进行一维搜索，求 t k使得使得)(min)(0kktkkkptxfptxf 第第3步步 )(kkxfp 取取步步。转

33、转第第2, 1:,1 kkptxxkkkk用最速下降法求得最优解是目标函数的一个驻点。用最速下降法求得最优解是目标函数的一个驻点。Page 61例例2 用最速下降法求解用最速下降法求解22212125),(minxxxxf 6010,)2 , 2( Tx取取解：解：Txxxf)50,2()(21 Txf)100, 4()(0 Txfp)100, 4()(00 取取 ttttpx100242100422002200)1002(25)42()(tttpxf 0)(00 tpxfdtd令令020037. 00 t得得 003070. 0919878. 10001ptxx所所以以经经10轮迭代得最优解

34、。轮迭代得最优解。Page 62三、共轭方向法三、共轭方向法定义定义 设设A是是n阶实对称矩阵，若阶实对称矩阵，若且且非非零零nTRqpAqp , 0则称则称p和和q是相互是相互A共轭的。共轭的。对于非零向量组对于非零向量组1,.,1 , 0, niRpnijinjiAppjTi , 1,.,1 , 0, 0)(若若有有则称则称p0, p1,., pn-1是是A共轭方向组，或称一共轭方向组，或称一组组 A共轭方向。共轭方向。00 qpAqpATT，变为，变为为单位矩阵时，为单位矩阵时，当当共轭概念是正交概念的推广。共轭概念是正交概念的推广。Page 63证证使使得得设设,110 n 01111

35、00 nnppp 得得上上式式两两端端左左乘乘)1, 1 , 0()( niApTi0)()()(111100 nTinTiTiAppAppApp 共共轭轭方方向向为为一一组组因因Apppn 110, 1, 1 , 0, 0)( niAppiTii 0)( iTiAppA正正定定，因因1, 1 , 0, 0 nii 线性无关线性无关Page 64共轭方向组中最多含共轭方向组中最多含n个向量，且线性无关个向量，且线性无关nnA 反之，反之，n维空间的一组基可以构造一组维空间的一组基可以构造一组A共轭方向共轭方向线线性性无无关关，设设1, 1 , 0)( nivi 2, 1 , 0)(0)()()

36、()1()1()1()0()0(nkpAppApvvpvpikiiTiiTkkk，令令共共轭轭的的是是，则则Ankpk1, 1 , 0)( 共轭方向组的构造共轭方向组的构造由定理知：由定理知：Page 65二次严格凸函数的无约束最优化问题二次严格凸函数的无约束最优化问题110,., npppnRx 0110,., nppp定理定理 6 对于问题对于问题(QP)，若，若组组A共轭方向，则由任意初始点共轭方向，则由任意初始点出发，依次沿出发，依次沿 则最多经则最多经n次迭代可次迭代可得得(QP)的整体最优解。的整体最优解。为任意一为任意一进行精确一维搜索，进行精确一维搜索，由任意初始点出发，依此沿

37、某共轭方向组进行一维搜由任意初始点出发，依此沿某共轭方向组进行一维搜索求解无约束优化的方法叫索求解无约束优化的方法叫共轭方向法。共轭方向法。利用迭代点处的负梯度向量为基础产生一组共轭方向，利用迭代点处的负梯度向量为基础产生一组共轭方向，这种方法叫这种方法叫共轭梯度法。共轭梯度法。Page 66共轭梯度法共轭梯度法（1） 2, 1 , 0|)(|)(|)()(2211100nkxfxfpxfpxfpkkkkkkk 公式（公式（1）是由）是由Fletcher和和Reeves于于1964年提出的，称为年提出的，称为F-R公式，用公式（公式，用公式（1）求解无约束最优化问题最优解的）求解无约束最优化问

38、题最优解的方法简称为方法简称为F-R法。法。Page 67第第1步步 选取初始点选取初始点x0,给定终止误差给定终止误差 0；第第2步步 计算计算)(0 xf ，停止迭代，停止迭代，若若 |)(|0 xf步步；，否否则则转转第第输输出出30 x第第4步步 进行一维搜索，求进行一维搜索，求 t k使得使得)(min)(0kktkkkptxfptxf 第第3步步 ; 0:)(00 kxfp，令，令取取；令令kkkkptxx 1F-R法步骤法步骤Page 68第第5步步 计算计算)(1 kxf，停止迭代，停止迭代，若若 |)(|1kxf步步；，否否则则转转第第输输出出61 kx步；步；否则，转第否则

39、，转第步步转第转第令令若若7;3,:,10nxxnk 第第6步步 第第7步步 用用F-R公式取公式取kkkkpxfp )(11221|)(|)(|kkkxfxf 其中其中;4, 1:步步转第转第令令 kkPage 69例例2 用用F-R法求解法求解22212125),(minxxxxf 6010,)2 , 2( Tx取取解：解：Txxxf)50,2()(21 Txf)100, 4()(0 Txfp)100, 4()(00 取取Tx)00307. 0,91988. 1(1 利用利用F-R公式得：公式得：，001472. 0|)(|)(|20210 xfxf 00615. 084565. 3)(0

40、011pxfp Page 70 tttpx00615. 000307. 084565. 391988. 11149923. 00)(111 ttpxfdtd得得由由 0000615. 0845645. 349923. 000307. 091988. 11112ptxx 0|)(|2xfTx)0 , 0(2 最最优优解解若用某种方法求解若用某种方法求解(QP)问题，经有限轮迭代可以达到最问题，经有限轮迭代可以达到最优解，称此方法具有二次终止性。优解，称此方法具有二次终止性。F-R法具有二次终止性。法具有二次终止性。Page 71第五节第五节 约束最优化方法约束最优化方法v约束最优化问题约束最优化

41、问题的最的最 优优 化条件化条件v简简 约约 梯梯 度度 法法v惩惩 罚罚 函函 数数 法法Page 72 qjxhpixgtsxfPji,.,1, 0)( ,.,1, 0)( .)( min)(模型的一般形式模型的一般形式 qjxhpixgRxDjin,.,1, 0)(,.,1, 0)(约束集约束集，有有qjxhDxj,.,1, 0)(,* pixgxgii,.,1, 0)(0)(* 或或可可能能有有两两种种情情况况：而而对对于于不不等等式式约约束束的的一一个个积积极极约约束束称称为为点点的的约约束束使使*0)(0)(xxgxgii IixgixIpIi , 0)(|)(,.,2 , 1*令

42、令 qJ,.,2 , 1 Page 73一、约束最优化问题的最优化条件一、约束最优化问题的最优化条件)(,:*xIiRRgRRfnin 和和设设定理定理 1 处可微，处可微，)(,*xIIigi 在点在点 x* 处连续，处连续，在点在点 x*处处连连续续可可微微，在在*xhj线线性性无无关关，,),(*Jjxhj 划划(P)的局部最优解，则存在两组实数的局部最优解，则存在两组实数)(,*xIii 使使得得和和Jjj ,* )( , 00)()()(*)(*xIixhxgxfiJjjjxIiii 若若x*是非线性规是非线性规，)(),(*xIixgi 线性无关，线性无关，Jjxhj )(*，)(

43、),(*xIixgi 称约束规范条件称约束规范条件Kuhn-Tucker条件，简称条件，简称K-T条件条件Page 74特殊地，对于只有不等式约束的非线性规划问题特殊地，对于只有不等式约束的非线性规划问题若若x*是局部最优解，则存在实数是局部最优解，则存在实数使使得得)(,*xIii )( , 00)()(*)(*xIixgxfixIiii 对于只有等式约束的非线性规划问题对于只有等式约束的非线性规划问题0)()(* Jjjjxhxf 一、约束最优化问题的最优化条件一、约束最优化问题的最优化条件Page 75条条件件可可写写成成处处可可微微，则则在在点点若若要要求求TKxIixgi *),(*

44、()()()0()0, 0, iijji Ij Jiiif xg xh xg xiI互互补补松松紧紧条条件件现引进现引进Lagrange函数如下：函数如下： JjjjIiiixhxgxfxL)()()(),( *(,)0()0, 0, xiiiL xg xiI一、约束最优化问题的最优化条件一、约束最优化问题的最优化条件K-T条件为：条件为：Page 76JjhIigfji , , ,)(, ,*xIigfi Jjhj , 定理定理 2 对于问题对于问题(P)，若，若在点在点x*处连续可微，若可行点处连续可微，若可行点x* 满足满足(P)的的K-T条件，且条件，且是凸函数是凸函数, 是线性函数，

45、则是线性函数，则 x* 是是(P)的全局最优解。的全局最优解。一、约束最优化问题的最优化条件一、约束最优化问题的最优化条件例例 用用K-T条件解非线性规划条件解非线性规划2max( )(4)16f xxxPage 77二、简约梯度法二、简约梯度法0 , | xbAxRxDnl可可行行域域 0 .)( minxbAxtsxf考虑考虑mnmnnRbmArRRfRx ，其中其中)(: ,假设（假设（1）每个可行点至少有）每个可行点至少有m个大于个大于0的分量的分量（2）A的任意的任意m列线性无关列线性无关简约梯度法的基本思想是简约梯度法的基本思想是Wolfe于于1962年提出年提出Page 78二、

46、简约梯度法二、简约梯度法基本思想：基本思想：类似于单纯形法，将当前点类似于单纯形法，将当前点xk的的m个个最大正分量定为基变量，其余的最大正分量定为基变量，其余的m-n个分量作为个分量作为非基变量，那么目标函数作为非基变量的函数求非基变量，那么目标函数作为非基变量的函数求负梯度方向，并依据这一方向构造从负梯度方向，并依据这一方向构造从xk到到xk+1的的可行下降方向。可行下降方向。Page 79二、简约梯度法二、简约梯度法0, BNBxxxx其中其中令令),(NBA bNxBxbAxNB 可可写写成成则则NBNxBbBxB11 可逆，所以可逆，所以因因),()(),()(11NNNNNBxNx

47、BbBfxFxxxfxf 的的函函数数，可可写写成成目目标标函函数数)()()()(1xfxfNBxFrNBTNN 其其梯梯度度为为称称rN为为f 在点在点x处对应于基矩阵处对应于基矩阵B的的简约梯度简约梯度。首先，求首先，求f 对非基变量的梯度对非基变量的梯度Page 80二、简约梯度法二、简约梯度法),(, 0kkkBkBkNBAIxmx 相应地相应地的下标集记为的下标集记为这些分量这些分量为为个最大分量组成的向量个最大分量组成的向量的的设设的简约梯度为的简约梯度为处对应于处对应于在点在点kkBxxf)()()()(1kNkBTkkkNxfxfNBr 其次，在迭代点其次，在迭代点xk处依据

48、简约梯度构造可行下降方向处依据简约梯度构造可行下降方向 kNkBkppp令令取取 ，则，则 是下降方向，但不一定是可行方向。是下降方向，但不一定是可行方向。kkNNpr kNpPage 81二、简约梯度法二、简约梯度法这是因为，这是因为，非非基基个个分分量量的的第第若若0)( kikNrir有有，则则对对个个分分量量有有的的第第而而此此时时的的00 kkiktxix不不满满足足非非负负要要求求, 01 kikkikkikirtrtxx如如下下非非基基的的分分量量取取)(kNpkBkikikikikikikNIirrxrrpp 0 0 ,:Page 82二、简约梯度法二、简约梯度法为为可可行行方

49、方向向，应应满满足足，为为使使下下求求kkBppbAptAxptxAAxkkkkkkk )(1bAxxkk 为为可可行行点点，所所以以因因0 kt又又因因0 kNkkBkpNpBkNkkkBpNBp1 综上所述，利用简约梯度综上所述，利用简约梯度 如如下下构构造造出出的的搜搜索索方方向向kkNpr kNkkkBkBkikikikikikikNkpNBpIirrxrrppP1 0 0 ,:：0 kAp（*）Page 83lkDx 0 kBkNkBkxxxx，并并且且由由下下式式确确定定若若kp kNkkkBkBkikikikikikikNpNBpIirrxrrpp1 0 0 ,:的的可可行行下下

50、降降方方向向处处关关于于在在点点是是时时，）当当（lkkkDxfpp01 点点问问题题的的的的充充要要条条件件是是）（TKxpkk 02定理定理 3 设设f 是可微函数，是可微函数，二、简约梯度法二、简约梯度法Page 84二、简约梯度法二、简约梯度法最后，考察如何从点最后，考察如何从点 xk Dl 沿上面构造的可行下降方向沿上面构造的可行下降方向pk进行有效一维搜索。进行有效一维搜索。bptxAAxtAPkkkkkk )(001有有，所所以以因因niptxxkikkiki,.,101 ，时时，上上式式总总成成立立，故故当当，因因0,.,10 kikipnixkikikkikipxtxp 须须

51、使使时时，为为使使当当, 001因而取因而取t的上界为的上界为 00|min01max不不全全，kkikikinikkpppxpt为使为使Page 85Wolfe法步骤法步骤Page 86Wolfe法步骤法步骤Page 87例例 用用Wolfe法求解极小化问题法求解极小化问题 0,24.622)(min21212121212221xxxxxxtsxxxxxxxf6010,)1 , 1( Tx取取解解 上面问题可化为下列问题上面问题可化为下列问题 0,24.622)(min2142132121212221xxxxxxxxtsxxxxxxxfPage 88二、惩罚函数法二、惩罚函数法罚函数法罚函数

52、法障碍函数法障碍函数法基本思想基本思想：利用问题中的约束函数做出适当的：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数，构造出带参数的增广目标函上加上惩罚函数，构造出带参数的增广目标函数，把问题的求解转换为求解一系列无约束非数，把问题的求解转换为求解一系列无约束非线性规划问题。线性规划问题。Page 89罚函数法罚函数法 qjxhpixgtsxfji,.,1, 0)( ,.,1, 0)( .)( min 考虑问题：考虑问题：设法适当地加大不可行点处对应的目标函数值，使不设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。可行点不能成为相应无约束极小化问题的最优解。 qjjpiicxhcxgcxp1212)(2)0),(max()()()()(xpxfxFcc 增增广广目目标标函函数数为为：可行域为可行域为D构造罚函数：构造罚函数：)( minxFc问问题题转转化化为为c称为罚