重庆工商大学数学模型与数学实验课件08非线性规划

1非线性规划（NonlinearProgramming）第一章一般的非线性规划问题§1.1问题概论（模型）minf(x)s.t()0,1,...,()0,1,...,ijgximhxjn2（两类问题）无约束极值问题与约束极值问题（一些基本定义）梯度Hesse矩阵Jaccobi矩阵1()(,...,)Tndfdffxdxdx()Hx1111nmmnffff1()TTnfFxf3§1.2最优解分类（注：不一定存在）定义1.2.1整体（全局）最优解定义1.2.2局部最优解（已有算法基本都是求局部最优解的）§1.3凸集与凸函数定义1.3.1凸集定义1.3.2（严格）凸函数称定义在凸集K上的实值函数f(x)为凸函数，若定义1.3.3凹函数1201xxK，及，有：1212((1))()(1)()fxxfxfx4定义1.3.4凸规划（图集上凸函数的极小化问题）定理1.3.1设、均为凸集，则也是凸集，对任意实数ß，是凸集。（证明）（推广）定理1.3.2有限个凸集的交集必是凸集定理1.3.3（分离定理）K为闭凸集，则定理1.3.4（支撑超平面定理）1K1K12KKyK0min/TTppypxxK，2K5定理1.3.5若均为凸集K上的凸函数，则也是K上的凸函数。（请证明）定理1.3.6设f(x)是凸集K上的凸函数，则实数C，水平集必为凸集。（请证明）定理1.3.7若f(x)在开集K中可微，则f是K上的（严格）凸函数当且仅当1()()rfxfx，，0i=1,,ir，（）1()riiifx{/()}xkfxC,,()()()()TxyKfxfyfxxy均有6证明（充分性）任取，记由条件，（必要性）0,1,xyK(1),zzxyK则()()()()()(1)()()TTfxfzfzxzfzfzxy()()()()()()()TTfyfzfzyzfzfzxy1-()(1)()()((1))()fxfyfzfxyfx第一式乘以，第二式乘以（），相加得故为凸函数,,(0,1),()((1))()(1)()()(()())((1))()()()xyKfxfxyfxfyfyfxfyfxyfyfxfy由凸，可得故7令此即需证。若f(x)两阶可微，则有以下的定理：定理1.3.8设f(x)在开凸集K中二阶连续可微，f为凸函数的充要条件为：证明：（充分性）0,()()()()Tfxxyfxfy得:,()xKfxxn在处的Hesse矩阵H(x)在R中半正定，即()0TyHxy,nxKyR,,()xyKfx由的二阶可微性得1()()()()()(())()2TTfxfyfyxyxyHyxyxy8此处从而，(必要性)任取将在x处展开：(0,1),()KyxyK因为为凸集，故有(())Hyxy()()()()nTRfxfyfyxy在中半正定，故：,,nxKzRxzK因为K是开集，故存在0,使当(0,)时，()fxz22()()()()()2TTfxzfxfxzzHxzo9令得定理1.3.9证明22()()()()2TTfxfxzzHxzo0()0TzHxz(),()nfxxKHesseRfx在开凸集中二阶连续可微，若矩阵在上正定，则是严格凸函数。,,,xyKxy由假设1()()()()()(())()2()()()TTTfxfyfyxyxyHyxyxyfyfyxy10此即说明f是严格凸函数。定理1.3.10证明当充分小时在的邻域中，从而导出矛盾，证毕()()fxKfxK是凸集上的凸函数，则在中的任一局部最优解都是它的整体最优解。**,()()xxRfxfx是一局部最优解但非整体最优解，则使***01()((1))()(1)()()fxfxxfxfxfx（，），由于是凸函数，可得：*(1)xx*x11§1.4最优性条件无约束极小化问题（模型）mins.t（1.4.1)定理1.4.1（一阶必要条件）若是可微函数，是问题（1.4.1)的一个局部最小点的必要条件为：（无约束极小化问题求解）等价于（方程组求解）定理1.4.2（二阶必要条件）设为中的二阶连续可微函数，如果是的一个局部极小点，则()nfxxR()fx*x*()0,1,,phxpt()0fx21mintpphx()fx()fxnR*x12**()0()0TfxyHxy证明：由定理1.4.1，。对任意的由于是局部极小点，故对于充分小的必有此式成立必须有，证毕。*()0fx,nyR根据泰勒公式有2***2()()()()2TfxyfxyHxyo**()()fxfxy*x*()0TyHxy13定理1.4.3（二阶充分条件）设两阶可微，若满足则点的一个严格局部极小点，这里是的两阶Hesse矩阵定理1.4.4（两阶充分条件）设两阶连续可微，若满足证明：任取显然，由假设，，由的任意性，是()fxx()0()0,,0TnfxyFxyyRy且()xfx是()Fx()fx()fxx()0,()fxxVx且存在的一个邻域，使得()0,TyHxy,()nyRxVx有()xfx则必为的局部极小点。1(),()()()(())()2TxVxfxfxxxHxxxxx由()()xxxVx()()fxfxxx()fx的局部极小点，证毕。14定理1.4.5证毕()()nfxRfx若是上的凸函数，则的任意局部极小点均为整体最小解:(),()()()()0,()nTxfxxRfxfxfxxxxfx证设是的任意局部极小点，由凸函数性质此即说明是的整体极小点。15具有等式与不等式约束的极小化问题(NP)mins.t定义1.4.1设x是满足(NP)约束条件的点，记称I为x处不等式约束中的积极约束的下标集合定义1.4.2（积极约束）称约束为x处的积极约束定义1.4.3（正则点）若向量组线性无关，则称x为约束条件的一个正则点。()fx()0()0gxhx()()0,1,,iIxigxim()0,();()0,1,ipgxiIxhxpt()0,();()0,1,ipgxiIxhxpt16定理1.4.5（Kuhn-Tucker条件）设是(NP)的局部极小点且其中x1)(,,)TnxuuuT1n是约束的正则点，则必存在乘子矢量（，，和0,,xu使得和满足11()()()0mtiippipfxgxuhx()0,1,,0,1,,()0,1,,()0,1,,iiiipgximimgximhxpt17例求下面问题的K-T点mins.t解：本问题的K-T条件为2212126618xxxx124xx120,0xx11221311221321212312260260(4)00,04,,0,0xxxxxxxxxx；18（1）若（舍去）若（舍去）（2）（舍去）（3）10,x则上述条件化为1213212322123662(4)0,004;,,0xxxx231402x2120406x212006x1200,xxKT且条件化为19故有求得23112111032(2)026xx11222xx(2,2)Tx20§1.5迭代算法及收敛速度迭代算法记满足要求的点集为（如K-T点集，最优解集等）。算法一般采用迭代方法，即：任给一个初始点步1步2定义1.5.1（全局收敛性）设A是求解问题的一个算法，若对任意初始点在用算法A进行迭代时，或能在有限步求得最优解，或求得一无穷点列，该点列的任意聚点均为需求的点。1()kkkxxAx若停；否则,求一改进点0,:0xk令:1,1kk返回步0x,1,kxk21例1求解问题mins.t算法迭代点列例2求解min算法1nxx1()(1)2Axx111111111(1)122222kkkkxx0x,xxE1(1),12()1,12xxAxxx当当22迭代点列若若定义1.5.1（闭映射）设X何Y分别是两个非空闭集，A是从X到Y的一个点到集的映射，即对任意有。设，且若（例1种的映射是闭的，而例2中的映射则是非闭的）显然，例2的最优解为取算法A为X到X的一个映射：定理1.5.1若对任意取定的：（1）（2）存在在，（3）算法A在外是闭的则算法A必定是全局收敛的。（证明从略）0011,2kkxxx则011kxx则xX()AxY,kkxXyY(),kkyAxk,,()kkxxyyyAx则必有0,{0}x记011,1,1(1),((1))2kxxAA但注01,:0,,()kkkxXkxxAx若则取0,kxXAx由算法求得的点列满足kx是列紧的(),,(),()()fxxyAxfyfx若有,(),()()xyAxfyfx若有23收敛速度定义1.5.2设实数列除有限个外除有限个外其他被称为商收敛因子定理1.5.2仅有以下三种情况之一发生：（1）（2）（3），,0,krrp令10()limkpkkrrQprrkrkrkrrkrr()Qp()0Qp()Qp()Qp()0Qp000,ppp当时0pp当时24定义1.5.3设，我们称为收敛到的阶。也称阶收敛到（对情况1，令，对情况2，令）显然，收敛的阶越大，收敛速度越快。当数列具有一阶收敛速度时越小数列收敛得越快。定义1.5.4若则称数列超线性收敛于例2（1）（2）krr0pkrrr0p00pkr0p010,1,(1)lim11kkpQkk0101(1)0kpQk为超线性收敛，因为且()Qp01()0pQp且krr25第二章一维极值问题的最优化方法在求解极值问题时我们经常会反复采用如下的一元函数求极值步骤：先求出一个搜索方向d，然后沿方向d作一维搜索。为此，我们先来介绍一下一维搜索的一些技巧和方法。问题：mins.t本问题实际上是一个一元函数求极值的问题，为方便起见，以下我们讨论问题：mins.t这里a可以是，b可以是。()()0fxdg()fxaxb26§2.1仅比较函数值的最优化方法定义2.1（下单峰函数）定义2.2（不定区间）包含下单峰函数最小点的区间[a,b]方法：按一定的方法在[a,b]区间中取若干个点，比较这些点上的函数值，不断缩小不定区间。定义2.3（最优搜索策略）总点数相同而能使不定区间缩得最小的搜索方法。（Fibonacci方法）Fibonacci数1，1，2，3，5，8，13，21，34，………()[,](,),fxabxab是上的连续函数，若存在使得当()()xyxfxfy时有;()()()xyxfxfyfx当时有01121,nnnFFFFF:nF27方法：设目前的不定区间为[a,b]，尚有r个试验点。令比较（1）若（2）若（3）若最后，当只剩下还有一个试验点时，不定区间的中点为一试验点，最后一个试验点