运筹学第4章非线性规划

1、第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外第第4 4章章 非线性规划非线性规划Non-linear ProgrammingNon-linear Programming第第2页页v4.1 4.1 基本概念基本概念v4.2 4.2 凸函数和凸规划凸函数和凸规划v4.3 4.3 一维搜索方法一维搜索方法v4.4 4.4 无约束最优化方法无约束最优化方法v4.5 4.5 约束最优化方法约束最优化方法第第4章章 非线性规划非线性规划第第3页页1. 非非线线性性规规划划问问题题例例4.1.1 曲线的最优拟合问题曲线的最优拟合问题已知某物体的温度已知某物体的温度 与时间与

2、时间 t 之间有如之间有如 下形式的经验函数关系：下形式的经验函数关系： tcetcc321 (*) 其中其中1c，2c，3c是待定参数。是待定参数。现通过测现通过测 试获得试获得 n 组组 与与 t 之间的实验数据之间的实验数据),(iit ， i=1，2，,n。试确定参数试确定参数1c，2c，3c， 使理论曲线使理论曲线(*)尽可能地与尽可能地与 n 个测试点个测试点 ),(iit 拟合。拟合。 t n1i221)( min3 itciietcc 4.1 基本概念基本概念第第4页页例例2 构件容积问题构件容积问题设计一个右图所示的由圆锥和圆柱面 围成的构件，要求构件的表面积为S， 圆锥部分

3、的高h和圆柱部分的高x2之 比为a。确定构件尺寸，使其容积最 大。 x1x2x3 0, 0 2 . .) 3/1 ( max212121222211221xxSxxxxaxxtsxxaV 4.1 基本概念基本概念1. 非非线线性性规规划划问问题题第第5页页数数学学规规划划设设nTnRxxx ),.,(1，RRqjxhpixgxfnji:,.,1),(;,.,1),();( , 如如下下的的数数学学模模型型称称为为数数学学规规划划(Mathematical Programming, MP)： qjxhpixgtsxfji,.,1, 0)( ,.,1, 0)( .)( min qjxhpixgRx

4、Xjin,.,1, 0)(,.,1, 0)(约束集或可行域约束集或可行域MP中目标函数和约束函数中至少有一个不是中目标函数和约束函数中至少有一个不是x的的线性函数，称线性函数，称(MP)为非线性规划为非线性规划4.1 基本概念基本概念Xx MP的可行解或可行点的可行解或可行点第第6页页向向量量化化表表示示当当p=0,q=0时，称为时，称为无约束非线性规划无约束非线性规划或者或者无约无约束最优化问题束最优化问题。否则，称为否则，称为约束非线性规划约束非线性规划或者或者约束最优化问约束最优化问题题。4.1 基本概念基本概念第第7页页最最优优解解和和极极小小点点定定义义4.1.1 对对于于非非线线性

5、性规规划划(MP)，若若Xx *，并并且且有有 X ),()(* xxfxf 则则称称*x是是(MP)的的整整体体最最优优解解或或整整体体极极小小点点，称称)(*xf是是 (MP)的的整整体体最最优优值值或或整整体体极极小小值值。如如果果有有 * ),()(xxX,xxfxf 则则称称*x是是(MP)的的严严格格整整体体最最优优解解或或严严格格整整体体极极小小点点，称称 )(*xf是是(MP)的的严严格格整整体体最最优优值值或或严严格格整整体体极极小小值值。 4.1 基本概念基本概念第第8页页最最优优解解和和极极小小点点定定义义 4.1.2 对对于于非非线线性性规规划划(MP)，若若Xx *，

6、并并且且存存在在*x的的一一个个 领领域域 ), 0( )(*RxxRxxNn ，使使 XxNxxfxf)( ),()(* ， 则则称称*x是是(MP)的的局局部部最最优优解解或或局局部部极极小小点点，称称)(*xf是是(MP)的的局局部部 最最优优值值或或局局部部极极小小点点。如如果果有有 * ,)( ),()(xxXxNxxfxf ， 则则称称*x是是(MP)的的严严格格局局部部最最优优解解或或严严格格局局部部极极小小点点，称称)(*xf是是(MP) 的的严严格格局局部部最最优优值值或或严严格格局局部部极极小小点点。 4.1 基本概念基本概念第第9页页求解。似于线性规划的图解法单的非线性规

7、划可用类和约束条件较简数对于二维空间中目标函)(xf例：例：2221)2()2()(minxxxf06)(. .21xxxhts*2*13xx2, 0)(0)(*2*1xxxhxh则换为如非线性规划的图解法2)(xf1x2x4)(xf226363cDAB第第10页页2. 非线性规划方法概述：非线性规划方法概述：4.1 基本概念基本概念第第11页页线搜索框架下的迭代算法第第12页页基基本本迭迭代代格格式式4.1 基本概念基本概念第第 1步步 选取初始点选取初始点0 x，k:=0; 第第 2步步 构造搜索方向构造搜索方向kp； 第第 3步步 根据根据kp，确定步长，确定步长kt； 第第 4步步 令

8、令kkkkptxx 1， 若若1 kx已满足某种终止条件，停止迭代，输出已满足某种终止条件，停止迭代，输出 近似解近似解1 kx；否则令；否则令k:=k+1，转回第，转回第2步。步。 第第13页页4.2 凸函数和凸规划凸函数和凸规划1. 凸函数的定义凸函数的定义定义定义 4.2.1 设设nRS 是非空凸集，是非空凸集，RSf:，如果对任意的，如果对任意的)1 , 0( 有有 )()1()()1(2121xfxfxxf ，Sxx 21, 则称则称 f 是是 S 上的上的凸函数凸函数，或，或 f 在在 S 上是上是凸凸的。的。如果对于任意的如果对于任意的)1 , 0( 有有 )()1()()1(2

9、121xfxfxxf ，21xx 则称则称 f 是是 S 上的上的严格凸函数严格凸函数，或或 f 在在 S 上是上是严格凸严格凸的。的。 若若-f是是S上上的的（严严格格）凸凸函函数数，则则称称f是是S上上的的（严严格格）凹凹函函数数， 或或f在在S上上是是（严严格格）凹凹的的。 第第14页页(a) 凸函数凸函数 (b)凹函数凹函数4.2 凸函数和凸规划凸函数和凸规划第第15页页定定理理 4.2.2 设设nRS 是是非非空空凸凸集集，RRfn:是是凸凸函函数数，Rc ，则则集集合合 cxfSxcfHS )(),( 是是凸凸集集。 4.2 凸函数和凸规划凸函数和凸规划2. 凸函数的一些基本性质凸

10、函数的一些基本性质注：一般来说上述定理的逆是不成立的。注：一般来说上述定理的逆是不成立的。第第16页页定定理理 4.2.3 设设nRS 是是非非空空开开凸凸集集，RSf:可可微微，则则 （1） f 是是 S 上上的的凸凸函函数数的的充充要要条条件件是是 )()()()(12121xfxfxxxfT ， Sxx 21, 其其中中Tnxxfxxfxf)(,.,)()(1111 是是函函数数 f 在在点点1x处处的的一一阶阶 导导数数或或梯梯度度。 （2） f 是是 S 上上的的严严格格凸凸函函数数的的充充要要条条件件是是 )()()()(12121xfxfxxxfT ， 2121, xxSxx 4

11、.2 凸函数和凸规划凸函数和凸规划2. 凸函数的一些基本性质凸函数的一些基本性质第第17页页定定 理理 4.2.4 设设nRS 是是 非非 空空 开开 凸凸 集集 ，RSf:二二 阶阶 连连 续续 可可 导导 ， 则则 f 是是S 上上 的的 凸凸 函函 数数 的的 充充 要要 条条 件件 是是 f 的的 Hesse 矩矩 阵阵)(2xf 在在 S 上上 是是 半半 正正 定定 的的。 当当)(2xf 在在 S 上上 是是 正正 定定 矩矩 阵阵 时时 ， f 是是 S 上上 的的 严严 格格 凸凸 函函 数数 。（ 注注 意意 ： 该该 逆逆 命命 题题 不不 成成 立立 。 ） 22221

12、222222122122122122)()()(.)(.)()()(.)()()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf 4.2 凸函数和凸规划凸函数和凸规划2. 凸函数的一些基本性质凸函数的一些基本性质第第18页页,. 1对称件：矩阵的正定等定义及条HEHnn正定。称如HxHxxT, 0, 0) 1 (0 所有主子式正定H半正定。称如HxHxxT, 0)2(0, 0)3(xHxxT负定：如负定H各阶主子式负正负正相间（第一个为负）0 所有顺序主子式0 所有主子式半正定H第第19页页3.凸凸规规划划的的定定义义 qjxhpixgtsxfji,.10,)

13、( (MP) ,.,1, 0)( .)( min qjxhpixgRxXjin,.,1, 0)(,.,1, 0)(约束集如果如果(MP)的约束集的约束集X是凸集，目标函数是凸集，目标函数f是是X上的上的凸函数，则凸函数，则(MP)叫做叫做非线性凸规划非线性凸规划，或简称为，或简称为凸凸规划规划。4.2 凸函数和凸规划凸函数和凸规划第第20页页定定理理 4.2.5 对对于于非非线线性性规规划划(MP)，若若pixgi,.,1),( 皆皆为为nR上上的的凸凸函函数数，qjxhj,.,1),( 皆皆为为线线性性函函数数， 并并且且f是是X上上的的凸凸函函数数，则则(MP)是是凸凸规规划划。 定理定理

14、 4.2.6 凸规划的任一局部最优解都是它的凸规划的任一局部最优解都是它的整体最优解。整体最优解。4.2 凸函数和凸规划凸函数和凸规划4.凸规划的性质：凸规划的性质：第第21页页本节练习本节练习 1. 验证 )(P44min12221xxx02. .221 xxts1210 xx ）半正定）为凸规划（用xH(第第22页页4.3 一维搜索方法一维搜索方法精确一维搜索方法：精确一维搜索方法： 0.618法法， Newton法法非精确一维搜索方法：非精确一维搜索方法： Goldstein法法， Armijo法法第第23页页1. 0.618法（近似黄金分割法）法（近似黄金分割法）4.3 一维搜索方法一

15、维搜索方法第第24页页2. Newton法法4.3 一维搜索方法一维搜索方法第第 1 步步 给定初始点给定初始点1t ，0 e e，1: k； 第第 2 步步 如果如果e e )(kt，停止迭代，输出，停止迭代，输出kt 。 否则，当否则，当0)( kt 时，停止，时，停止， 解题失败；解题失败；当当0)( kt 时，转下一步；时，转下一步； 第第 3 步步 计算计算)()(1kkkktttt ，如果，如果e e kktt1，停止迭代，输出，停止迭代，输出1 kt。 否则否则1: kk， 转第转第2 步。步。 第第25页页abcd)0( )(ty ty)0()0( tmy)0()0(1 tmy

16、)0()0(2 3. Goldstein法法4.3 一维搜索方法一维搜索方法第第26页页Goldstein法步骤法步骤:4.3 一维搜索方法一维搜索方法第第27页页4. Armijo法法tmy)0()0( )0( )(ty ktkMt4.3 一维搜索方法一维搜索方法取定取定Mm 10，用一下两个式子限定，用一下两个式子限定kt 不太大也不太小：不太大也不太小： )0()0()( kkmtt )0()0()( kkmMtMt 第第28页页4.4 无约束最优化方法无约束最优化方法v无约束问题的最优性条件无约束问题的最优性条件v最速下降法最速下降法v共轭方向法共轭方向法第第29页页1、无约束问题的最

17、优化条件、无约束问题的最优化条件4.4 无约束最优化方法无约束最优化方法第第30页页4.4 无约束最优化方法无约束最优化方法1、无约束问题的最优化条件、无约束问题的最优化条件第第31页页2. 最速下降法（又称梯度法）最速下降法（又称梯度法）4.4 无约束最优化方法无约束最优化方法第第32页页4.4 无约束最优化方法无约束最优化方法最速下降法的计算步骤：最速下降法的计算步骤：第第33页页3. 共轭方向法共轭方向法4.4 无约束最优化方法无约束最优化方法第第34页页4.4 无约束最优化方法无约束最优化方法3. 共轭方向法共轭方向法第第35页页F-R法步骤法步骤4.4 无约束最优化方法无约束最优化方

18、法第第36页页4.5 约束最优化方法约束最优化方法v约束最优化问题的最优化条件约束最优化问题的最优化条件v简约梯度法简约梯度法v惩罚函数法惩罚函数法qjRRhpiRRgRRfRxnjninn,.,1 :,.,1 ,: : , 其中其中 ,.,1 0)( 1 0)( .)( minqjxh,.,pixgtsxfji(MP)第第37页页1. 约束最优化问题的最优化条件约束最优化问题的最优化条件qjxhpixgRxXjin,.,1,0)(,.,1,0)(MP)问题的可行区域为设, 0)( |)(*IixgixIi积极约束的下标集：JjxhqJXxj ,0)(,2, 1, *，即满足令对4.5 约束最

19、优化方法约束最优化方法第第38页页Kuhn-Tucker条件（条件（K-T条件）：条件）：4.5 约束最优化方法约束最优化方法注：凡是满足注：凡是满足K-T条件的点叫条件的点叫K-T点点第第39页页4.5 约束最优化方法约束最优化方法第第40页页简约梯度法简约梯度法 0 .)( minxbAxtsxf 其中，RRfRxnn: , ，mArnm )(，mRb (4.5.12)定理定理 4.5.3 对于非线性规划问题对于非线性规划问题(4.5.12)，设，设 f 是可微函数，是可微函数，lkXx ，并且有分解，并且有分解 kNkBkxxx，0 kBx。若。若 kNkBkppp由下式确定由下式确定，

20、 kNkkkBkBkikikikikikikNpNBpIirrxrrpp1 0 0 ,: (*) 则则 （1） 当当0 kp时，时，kp是是 f 在点在点kx处关于处关于lX的可行下降方向；的可行下降方向； （2） 0 kp的充要条件是的充要条件是kx是问题是问题(4.5.12)的的 K-T 点。点。 0 , | xbAxRxXnl第第41页页Wolfe法步骤法步骤第第 1步步 选选取取初初始始可可行行点点lXx 0，给给定定终终止止误误差差0 e e，令令 k:=0; 第第 2步步 设设kBI是是kx的的 m个个最最大大分分量量的的下下标标集集，对对矩矩阵阵 A进进行行相相应应分分解解 ),

21、(kkNBA 第第 3步步 计计算算 )()()(kNkBkxfxfxf，然然后后，计计算算简简约约梯梯度度 )()()(1kNkBTkkkNxfxfNBr 记记kNr的的第第)(kBIii 个个分分量量为为kir； 第第 4步步 按按(*)式式构构造造可可行行下下降降方方向向kp。若若e e kp，停停止止迭迭代代，输输出出kx； 否否则则进进行行第第 5步步； 第第 5步步 进进行行有有效效一一维维搜搜索索，求求解解 )(minmax0kktttpxfk 得得到到最最优优解解kt，其其中中 00 0min0 1maxkkkikikinikkppppxpt或或者者， 令令kkkkptxx 1

22、，k:=k+1，转转第第 2步步 第第42页页惩罚函数法惩罚函数法思想思想：利用问题中的约束函数做出适当的带有：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数上加参数的惩罚函数，然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数，把上惩罚函数构造出带参数的增广目标函数，把(MP)问题的求解转换为求解一系列无约束非线问题的求解转换为求解一系列无约束非线性规划问题。性规划问题。罚函数法罚函数法障碍函数法障碍函数法第第43页页罚函数法罚函数法 qjxhpixgtsxfji,.,1, 0)( ,.,1, 0)( .)( min qjxhpixgRxXjin,.,1,

23、0)(,.,1, 0)(设法适当地加大不可行点处对应的目标设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约函数值，使不可行点不能成为相应无约束极小化问题的最优解。束极小化问题的最优解。 qjjpiicxhcxgcxp1212)(2)0),(max()(罚函数罚函数)( minxFc)()()(xpxfxFcc第第44页页实际应用中，选取一个实际应用中，选取一个递增且趋于无穷的正罚递增且趋于无穷的正罚函数参数列函数参数列 qjjkpiikcxhcxgcxpk1212)(2)0),(max()(其中其中*)()()( minxpxfxFkkcc *罚函数法罚函数法第第45页页罚函数法计算步骤罚函数法计算步骤第第 1 步步 选取初始点选取初始点0 x，罚参数列，罚参数列,.)2 , 1( kck， 给出检验终止条件的误差给出检验终止条件的误差0 e e，令令 k:=1； 第第 2 步步 按按(*)构造函数构造函数)(xpkc，再按，再按(*)构造构造(MP) 的增广目标函数，即的增广目标函数，即)()()(xpxfxFkkcc 第第 3