北邮最优化理论与算法PPT课件：7_最优性条件

1、最优化理论与算法7， 最优性条件第七章 最优性条件 无约束问题的极值条件 约束极值问题的最优性条件 对偶及鞍点7.17.1无约束问题的极值条件无约束问题的极值条件考虑非线性规划问题1，无约束极值问题min ( ), nf xxe ( )nf xe其中是定义在上的实值函数称为无约束极值问题（unlp）7. 最优性条件-无约束17. 最优性条件-无约束2th7.1.1(非极小点的充分条件) 设f(x)在点x*处可微,若存在方向d( 0) rn,使得 f(x*)d0,使得对任意 (0, ),有f(x*+ d)f(x*).此时,我们称d 为f(x)在x*的一个下降方向下降方向.证明证明. 由 f(x)

2、 在 x* 可微, 则 f(x*+d)=f(x*) + f(x*)d+|d|(x*;d), 其中 (x*;d) 0(当 0). 2，必要条件，必要条件7. 最优性条件-无约束3移项且两边同除以移项且两边同除以 ( 0),得（f(x*+d)f(x*)）/ f(x*)d+|d|(x*;d)由于 f(x*)d 0 使得对 任意(0, ), f(x*)d+|d|(x*;d)0 .定理立明.定理定理7.1.2-3(极小点的必要条件)设x*处是问题(unlp)的局部极小点.(1)当 f(x) 在 x*可微时,则梯度 f(x*)=0.(2) 当f(x) 在 x*二次可微时. 则 f(x*)=0 且 hess

3、ian 矩阵 h(x*) 是半正定的7. 最优性条件-无约束4(2). 给定任意向量 d. 由 f(x) 在 x*的二次可微性，有f(x*+d)=f(x*) +f(x*)d+ dh(x*)d/2+ |d| (x*;d) (i), 其中 (x*;d) 0( 0). 由（1）的证明有 f(x*)=0. 移项整理并两端除以 , 得 =dh(x*)d/2+|d| (x*;d) (ii).因 x* 局部极小, 对充分小 有f(x*+d)f(x*) 2222 f(x*+d)f(x*)22证明证明(1). 若f(x*)0, 作 d=f(x*). 则有 f(x*) d 0 使得 f(x*+d)f(x*)， (

4、0, ), 此与 x* 为局部极小相矛盾，故 f(x*)=0.7. 最优性条件-无约束5dh(x*)d/2+|d| (x*;d)0 2由(ii), 显见对充分小的 成立 , 对 0取极限, 则有 dh(x*)d 0, 从而,h(x*) 半正定定义定义1 若f(x)在点x*处可微,且 f(x*)=0,则称x*为f(x)的一个驻点驻点或平稳点平稳点.d( 0) rn, 既不是极大点也不是极小点的驻点称为鞍点鞍点.th7.1.4 (二阶充分条件二阶充分条件). 假设 f(x) 在 x*点二次可微,若 f(x*)=0 且 hessian 矩阵 h(x*) 是正定的,则 x* 是(unlp)的一个(严格

5、)局部极小点3，二阶充分条件，二阶充分条件7. 最优性条件-无约束6证明证明. 因 f 在 x* 二次可微,故对任意 x, 有 f(x)=f(x*)+f(x*)(x-x*)+(x-x*)h(x*)(x-x*)/2+|x- x*| (x*; x- x*), 这里 (x*; x- x*) 0,当 xx*. 假设命题不真， x* 不是局部极小, 则存在序列 xk 收敛到 x* 并使得 f(xk) 0 使得 f(x*+d)f(x*)（ (0, )）,则 d 称为 f(x) 在 x*的下降方向(decedent direction)设 f(x) 在 x*可微. 若存在向量 d 满足 f(x*)d0, 则

6、 由th7.1.1, d 是 f(x) 在 x*.的下降方向。记所有这样的向量集合为0( *)0fdf xd cl ,00, ,7 2 2.,ssd0,0,.fd x s(0, ), nxs drxdsdxxxdd dxclsxds设设若若使使得得则则称称 为为集集合合 在在点点 的的一一个个集集合合 在在 点点的的所所有有可可s s使使得得对对行行方方向向集集合合称称为为 在在 点点的的, ,记记可可行行方方向向可可行行方方向向为为 ( (或或( , )( , )有有) )锥锥定定义义 . . . . 7. 最优性条件-有约束3由可行方向定义和下降方向知，可行方向定义和下降方向知， 从点 x

7、*, 沿可行方向 dd(x*) 作一个很小的移动还是可行点. 进一步，由 th 7.1.1, 若 f(x*)d0 ，则d 是f在 x*的下降方向。下面定理将说明 若 x* 是局部最优且 f(x*)d0, 则 dd(x*).即不是可行方向。theorem 7.2.1. (必要条件必要条件) 考虑极小化问题考虑极小化问题： min f(x) ，subject to xs,其中其中 s 是是 rn 中非空集合中非空集合，设设 f(x) 在在 x*可微。若可微。若 x* 是局部极是局部极小点，则小点，则 f0(x*)d=,其中其中 f0(x*)=d |f(x*)d0, f(x*+ d)0， x*+ d

8、 s ， (0, 2)此与局部极小矛盾。此与局部极小矛盾。177. 最优性条件-不等式约束1为把最优性的几何条件用代数来表示，引入起作用约束的为把最优性的几何条件用代数来表示，引入起作用约束的概念。问题的约束条件在点概念。问题的约束条件在点x* * s s处有两种情形处有两种情形3 不等式约束的一阶最优性条件不等式约束的一阶最优性条件 min ( ) , ( )0, 1,2,.,s ( )0,1,2,.,iif xs tg ximx g xim考察非线性规划可行域 1，i= i| gi(x*)=0在x*处起作用约束2， gi(x*)0. ii在x*处不起作用约束g0(x*)=d |gi(x*)

9、d0 , ii .187. 最优性条件-不等式约束2证明概要证明概要. 设设 d g0(x*).因因 s 为开集，则存在为开集，则存在 10 使得对使得对 (0, 1)， x* + d s。 另外存在另外存在 20使得使得对对 (0, 2) ，i i. gi(x*+ d)0,最后存在最后存在 30 使得使得对任意对任意 (0, 3) and i i有有gi(x*+ d)gi(x*), 从而从而 d d, d 是是 x*处的可行方向锥处的可行方向锥. 于是于是g(x*) d. 由由th 7.2.1, 立明。立明。th7.2.2. (必要条件必要条件) 考虑极小化问题考虑极小化问题 min f(x

10、) subject to gi(x) 0， i=1, m ，x s, 其中其中 s 是是 rn中的非空开集。中的非空开集。 设设 x* 为可行点，为可行点， i= i| gi(x*)=0. 进一步假设，进一步假设， f(x) 和和 gi(x) （ i i ）在）在 x* 可微，可微， gi （ i i） 在在 x*连续连续. 若若 x* 是局部最优解，则是局部最优解，则 f0(x*) g0(x*)=, 其中其中f0(x*)=d | f(x*)d0， i i .7. 最优性条件-不等式约束3g1(x)=-x - y + 5,g2(x)=-x - y + 3,g3(x)=x,g4(x)=y； i=

11、2f(x)2(x 3),2(y 2) 2 2min (x-3) + (y-2) s.t. x + y 5 x + y 3 x, y 0.2 222f(x*)g2(x*)(9/5, 6/5)f(x*)g(x*). g2(x)g1(x)x*7. 最优性条件-不等式约束4min (x-3) + (y-2) s.t. x + y 5 x + y 3 x, y 0.2 222x*=(2, 1)g1(x*)=(-4, -2),g2(x*)=(-1, -1),f(x*)(-2, -2)f(x*)g1(x*)x* 是最优解g2(x*)(2,1)x*7. 最优性条件-不等式约束5th7.2.3. (fritz

12、john condition, 1948)考虑极小化问题考虑极小化问题 min f(x) subject to gi(x) 0， i=1, m ，x s, 其中其中 s 是是 en.中非空开集中非空开集. 设设 x* 为可行点为可行点, i= i| gi(x*)=0. 进一进一步假设步假设 f(x) 和和 gi(x)( i i )在在 x* 可微可微, gi ( i i) 在在 x*连续连续. 若若 x* 是局部最优解是局部最优解.则则存在一组非负数存在一组非负数 u0 , ui ( ii )使得使得 u0f(x*) - uigi(x*)=0, u0, ui0 for ii and (u0,

13、ui)0.ii进一步进一步, 若若 gi(x) ( ii) 在 x*也可微，则 u0f(x*) uigi(x*)=0, uigi(x*)=0, u0, ui (所有 i ) ，且 (u0, u)0.i=1i=m227. 最优性条件-不等式约束6证明证明. 由由th7.2.2, 不存在向量不存在向量 d 同时满足同时满足 f(x*)d0 和和 gi(x*)d0 ，( i i). 设设 a 是其行由是其行由 f(x*) 和和 gi(x*)(i i)组成的矩阵组成的矩阵. 则则 ad0,可以对约束强加某种限制，这种限制条件叫做约束规格或约束品性( constraint qualifications)

14、.已有很多的约束规格，特别的, karush 1939, ms thesis, dept of math, univ of chicago , kuhn 和 tucker 1951 独立给出的最优性必要条件恰是 fritz john 条件条件加上加上 u00.7. 最优性条件-不等式约束12th7.2.4. (karush-kuhn-tucker 必要条件必要条件)考虑极小化问题考虑极小化问题 min f(x) subject to gi(x) 0， i=1, m ，x s, 其中其中 s 是是 en.中非空开集中非空开集. 设设 x* 为可行点为可行点, i= i| gi(x*)=0. 进一

15、进一步假设步假设 f(x) 和和 gi(x)( i i )在在 x* 可微可微, gi ( i i) 在在 x*连续连续. gi for ii 线性独立线性独立.若若 x* 是局部最优解是局部最优解.则则存在一组非负数存在一组非负数ui( ii )使使得得 f(x*) uigi(x*)=0, ui 0 ( ii ).ii若还有若还有 gi ( i i )在在 x*可微可微, 则则 f(x*) uigi(x*)=0, uigi(x*)=0, ui0 ， i=1, m.i=1i=m7. 最优性条件-不等式约束13karush-kuhn-tucker 条件可写成向量形式条件可写成向量形式f(x*)-

16、ug(x*)=0, ug(x*)=0, u0.这表明 f(x*) 属于起作用约束的这些约束的梯度所形成的锥中。7. 最优性条件-不等式约1)(2)min (-2). . -0 -001k-t01xxstxxxxxx 例3给定非线性规划 验证下列两点和是否为点7. 最优性条件-不等式约束152212211211211222(1)121( )(-2) ( ) =- ( )-2(-2)11( )( )( )221. ( ) 0( ) 04()0f xxxg xxxg xxxxf xg xgxxxxg xgxf x（ ）记 目标函数和约束函数的梯度是，先验证在这一点，都是起作

17、用约束目标函数和约束函数的梯度分别是111211()()01g xgx （ ）（ ），7. 最优性条件-不等式约束161212141100010400,kktwwwww 设 解此方程组，得 ， 。由于故不是点。(2)12 ( ) 0( ) 0 xg xgx再验证,在这一点，都是起作用约束目标函数和约束函数的梯度分别是:1211()()()221f xg xgx（2）（2）（2）2，7. 最优性条件-不等式约束171212110221002kktwwww 2设 解此方程组，得 ， 。故它是点。347. 最优性条件-不等式约束18th7.2.5. (karush-kuhn-tucker 充分条件充

18、分条件)考虑极小化问题考虑极小化问题 min f(x) subject to gi(x) 0， i=1, m ，x s, 其中其中 s 是是 en.中非空开集中非空开集. 设设 x* 为可行点为可行点, i= i| gi(x*)=0. 设设f(x)和诸和诸 gi 是凸的，是凸的， 进一步假设进一步假设 f(x) 和和 gi(x)( i i )在在 x* 可微可微, gi ( i i) 在在 x*连续连续. 若若 k-k-t条件在条件在 x*成立，则成立，则x*是全局最优是全局最优解解.证明略证明略7. 最优性条件-等与不等式约束11122( )( )( )( )( ), ( )( )( )ml

19、g xh xgxh xg xh xgxh x.4.一般约束问题的一阶最优性条件jcop) min ( ) , ( )0, 1,2,., (7.2.1) ( )0, 1,2,.,nif xxes tg ximh xjl考虑约束优化(记cop) min ( ) , ( )0, (7.2.33) ( )0, nf xxes tg xh x(矩阵形式7. 最优性条件-等与不等式约束20101( )| | ( )0, , ( ( )xx ttttsx h xtt th x t 点集称为曲面上的一条曲线 如果对所有均有定义 ,( ),( )|1,2,.,1,2,., ( )( )7.2.3i

20、jxxig xh xim jlxg xh x设 为可行点，不等式约束中在 点起作用约束下标集记作 若向量组线性无关，则定义称 为约束和的正则点。( ),( ).( )( )( ).s,s,( ).dx ttx tdtx tx tx txxt x显然 曲线上点是参数 的函数 若导数存在则称曲线是可微的曲线的一阶导数是曲线在点处的切向量曲面 上在点 处所有可微曲线的切向量组成的集合 称为曲面 在点 的切平面 记做7. 最优性条件-等与不等式约束31212( )( ),.,( )h( )0( )0( )0( )llh xh xh xh xh xh xxt x可证明，当，线性无关时，等于等式约束 .所

21、定义的超曲面在 处的切平面。h( )0, 1,2,.,jdh x djl定义集合7. 最优性条件-等与不等式约束4证明略127.2.6 | ( )0( )( ),.,( )( ) |( )0.ltthxsx h xh xh xh xxt xhdh xd设 是曲面上一个正则点 即，线性无关 ,则在点 切平面等于子空间120007.2.7(7.2.1), |( )0,(),(),(1,2,., ),( )( ),.,( ), iiijlthxii gxfg iixg iixhjlxh xhxh xxxfgh设在约束极值问题中为可行点和在点 可微在点 连续在点 连续可微 且，线性无关.若 是局部最优

22、解 则在点 处 有7. 最优性条件-等与不等式约束5000 |( )0 |( *)0 () |( *)0 (1,2,., )ttitjfd df xgd dg xiihd dh xjl其其中中 000:,( *)0 ()( *)0 (1,2,., )( )0th( ), | ( )0titjtyfghdg xiidh xjldf xyt xsx h x 证明 反证法 设则同时满足 .由7.2.6,即在曲面上7. 最优性条件-等与不等式约束60112(0)( ),(0).,0, ( ),( ( )( ).,( )(0)( )( )00,0,)( ( )0,.(7.2.39),( ( )0, 存在

23、经过点的可微曲线其切向量下面证明 当充分小时为可行点 且当时 于是当时 当时 因且 在 连续 则ttiiitiiixxx tdxdtytx tf x tf xiidg xdxg xg xydtdttg x tiiiig x tgx20,0,)( ( )0,.(7.2.40) 当时,有 itg x tii7. 最优性条件-等与不等式约束7033123( ( )( )0.0,0,)( ( )( )(7.2.41)min ,0, )(7.2.39-41)( ( )0,0, )( )( ( )( ), 另一方面,由于 当时,有 令,当时,有成立,且 因此 当当时,为可行点且此与 之局部最优性矛盾 故证

24、ttdf x tf xydttf x tf xth x ttx tf x tf xx.7. 最优性条件-等与不等式约束800th(fritz john)(7.2.1), |( )0,(),(),(1,2,., ),0(),(1,2,., )( ),iiijiiijxii g xfg iixg iixhjlxxw wii vr jlwf xwg下面给出一阶必要条件的代数表示.我们有如下定理.7.2.8 条件 设在约束极值问题中 为可行点和在点 可微在点 连续在点 连续可微.若 是局部最优解,则 不全为零的数使得 1( )( )ljji ijxvh x =0 10:( ):1,2,., ,(1,2

25、,., ),( )0().jljjjjih xjlvr jlvh xwwii证明 若线性相关 则 不全为零的数使=0.令显然命题为真7. 最优性条件-等与不等式约束9000( ):1,2,., , ( )0 ()( )0 (1,2,., )(7.2.42)( )0 jtitjth xjlfghdg xiidh xjldf x下设线性无关.由th7.2.7,有即不等式组 . 无解.( )( ) (),( ) (1,2,., ),0()0ttitjaf xg xiibh xjladbd令 是以,-为行组成的矩阵是以为行组成的矩阵 这样上述系统无解即系统 7.2.43 无解.7. 最优性条件-等与不

26、等式约束10现定义两集合1121221212(,) |,(,) |0,0tntsy yyad ybd drsy yyy121212121211222111212,0(,) ,( ,),0.0( ,)00tntttttttts ssspp pdry yclsp adp bdp yp yyypy yclsp adp bd 显然非空 且根据凸集分离定理,存在使得对及每一点成立 (7.2.44)令由于 的每个分量均可为任意负数,故(7.2.44)成立 (7.2.45)再令 () 7.2.467. 最优性条件-等与不等式约束111221212,()00.nttttttdrda pb pa pb pa p

27、b p 由之任意性 取1020010,(),(1,2,., ),)()( )( )( ),0(),(),(1,2,., ).ijliijjii ijijpw w iipvjlwf xwg xvh xw wiipw w ii vjl记 的分量为的分量为则(7.2.47 和 7.2.45 式即为 =0, 注意到 为非零向量,故不全为零7. 最优性条件-等与不等式约束12例:221222121212min . 5, 0, 0, 24(4/5,8/5)fritz johnxxstxxxxxxx验证在处条件成立.11* ( *)(8/5,16/5) ,( *)(1,2)( *)( *)081501625

28、5,8 ttxf xh xw f xv h xwvwv此处只有一个等式约束.注意到在处i= ,因此与不等式相应的乘子为零.于是即有合适解.如取7. 最优性条件-等与不等式约束13例1321321min(1)0,(1)0,xxxxx7. 最优性条件-等与不等式约束1412012012*(1,0) .( *)( 1,0) ,( *)(0,1) ,( *)(0, 1) ,1000110,().*fj. ttttxf xh xh xfjwvvwvva ax此问题只有一个可行解在此点有条件 仅当为任意数 成立故在满足条件1321321min(1)0,(1)0,xxxxx7. 最优性条件-等与不等式约束1

29、5*,()*,()*( *),( *)|,1,2,.,0(),(1,(2,., ),iijijjixsf giixwii vrgiixhxg xh xii jlfjxl理一阶必要条件(karush-kuhn-tucker定理) 代数特征设是问题(7.2.1)的局部极小点,函数在点处可微,在点处连续,在点处连续可微.若 线性无关，则使得 定定7.2 .9(:)7.2 .9(:)*)( *)( *)iijji ij ewg xvh x kkt最优性必要条件（th2.4）加以推广。这是通过增加约束规格来实现的.前面fj条件中w0不一定为正, 在下面定理中。我们将前面提到的7. 最优性条件-等与不等式

30、约束16进一步假设,gi ( ii )在 x*, 连续可微,则 f(x*)+ uigi(x*)+ vjhj(x*) =0, uigi(x*)=0, ui(i=1, m.)i=1i=mo若采用矩阵和向量记号,则kkt可如下简洁表示.ijghgh其其中中 和和 分分别别是是由由 和和组组成成的的向向量量函函数数定义定义lagrange函数为函数为(7.2.48)( , , )( )ttl xf xgh 7. 最优性条件-等与不等式约束17( )( )(,),( )( )(,1,2,., ),( ),( ),jacobitgithjghghxg xjxg iih xjxhjljx jxg hx 记向

31、量值函数 和 在 点的梯度为其中分别是在 点的矩阵.( *)( *)( *) ( *)0, 0 (7.2.49)( *)0, ( *)0 tf xg xh xg xg xh x 则kkt条件可表为7. 最优性条件-等与不等式约束18| |*,kkt(7.2.49),*(cop),*lagrange., ( *).kktniltxrrrxxg x定义若满足条件则称为约束优化问题的一个和 称为处的乘子特别点互补松的0称为弛条件=,1,2,.,0( ,)nkkkkkkxs drdkxdsdddsxsxsfd x s 定义:设若 向量序列和正实数列使得对有,且则称 为 在点 的一个. 在点 的所序列化

32、可行方向序列化可有序列化可行方向的集合,称为,记为行方向锥7. 最优性条件-等与不等式约束19*,*( *)0,( *,)0*.ijtxsf g hxdf xdsfd xsx 理理 充充分分条条件件 设设, ,函函数数在在点点处处可可微微, ,且且 则则为为(cop)(cop)的的严严格格局局部部极极小小点点定定 () ()kktcop,*,*ijijfghxsfg hxx，理理充充分分条条件件 凸凸规规划划情情形形设设 为为凸凸函函数数为为凹凹函函数数为为线线性性函函数数。对对于于若若在在点点处处可可微微, ,并并且且条条件件(7.2.49)(7.2.49)成成立立，则则为为优优化化问问题题

33、（）的的全全局局极极小小点点。定定7.2.10 (:)7.2.10 (:)7. 最优性条件-等与不等式约束202212212,min( ). .( )10f xxxs t g xxx 例例考考虑虑如如下下约约束束优优化化问问题题 *(0,1)( *)1,( *)(0,2)( *)(0,1)*kkt( *),( *),( *),.jtttxi xf xg xxxg xh xii xjei i对对于于可可行行点点, ,易易见见是是条条件件. .此此时时线线性性独独立立约约束束规规格格(licq)(licq)成成立立，即即 线线性性无无关关但但我我们们无无法法利利用用一一阶阶最最优优性性条条件件判判

34、断断是是否否为为问问题题的的局局, ,. .部部极极小小点点。5.二阶条件7. 最优性条件-等与不等式约束21( )( )( )2.3 t=,0,lim()nkkkkkksrxclsdxs xxdxxtsx定义设 是中的一个非空集合，点集合及使得则称 为集合 在点 的切锥。( )( )( )( )( ),limkkkkkkxs xxxxxxdxxdt根据上述定义，如果序列使得则。,.nxclssxtr如果则 在 的切锥为此,我们考虑函数的二阶导数,首先给出如下定义7. 最优性条件-等与不等式约束22例sx7. 最优性条件-等与不等式约束237. 最优性条件-等与不等式约束24现在我们考虑问题(

35、7.2.1).lagrange0,;,1,2,., .( )0,0( )0,0( )0,1,2,.,ijiiiiixwiivjlg xiiwsx g xiiwh xjl设在可行点 ，对应不等式约束中的起作用约束和等式约束的乘子分别为：定义一个集合。且且7. 最优性条件-等与不等式约束25( )0,0( )0,0( )0,1,2,.,iiiiisxtg x diiwgdg x diiwh x djlgt设集合 在点 的切锥为 。再定义一个集合且且容易证明( )( )( )( )( )( )( )( )( )( ), lim()( )( ),()( )( ) ()( ,)()( )( ) ()(

36、,)kkkkkiikkkkiiikkkkjjjdtxsxxdg xh xxg xg xg xxxxxx xxh xxh xxxxxx xx设则存在可行序列和正数列使得把和在 展开 得到h7. 最优性条件-等与不等式约束26( )( )( )( )( )( )( )( )( )( )( )00()0()()( )00( ) ()( ,)00( ) ()( ,)01,2,.,( ) ()kiiikkiijjikkkiikkkikjiig xiiwg xiiwg xh xxiiwg xxxxxx xxiiwg xxxxxx xxjlh xxxx由于当时， ，当且时0，当且 时0，以及h ,故当且时当

37、且时当时有)( )( ,)0kkxx xx7. 最优性条件-等与不等式约束27,( )0,0( )0,0( )1,2,.,.iiiijkg x diiwg x diiwh xjldggt k把以上各式两端乘以令，得且 且d=0,即所以tggt由以上分析知道，切锥 必包含于 ，但是反之不真。下面，在也成立的假设下，给出关于问题(7.2.1)的局部最优解的二阶必要条件。7. 最优性条件-等与不等式约束2811222212.10()(7.2.1),(1,.,)(1,., )(,.,)( ,.,),( , , )0( , , )( )( )iijmlxmxiiitheoremxf g imhjlwww

38、vvvxgtdgdl x w v dl x w vf xwgx 二阶必要条件 设 是问题的局部最优解,和二次连续可微，并存在满足(7.2.43)的乘子和再假设在点约束规格成立，则对每一个向量都有其中21( )lagrange( , , )hessianljjjvhxl x w vxx是函数在点 关于 的矩阵.7. 最优性条件-等与不等式约束29( )( )( )( )2( )2( )( )( )0,., lim()( , , )(, , )( , , )( , , ) ()1()( , , )()( ,)2 kkkkkkkxkkkkxddggtdtxsxxdl x w vxl xw vl x

39、w vl x w vxxxxl x w vxxxxx xx证明：设向量由于约束规格 成立，因此，则存在可行序列和正数列使得将在 展开，则( )( ) (7.2.50)( ,)0kkxxx xx其中当时，。7. 最优性条件-等与不等式约束30( )( )( )( )( ),()0,()lagrange(, , )( , , )( , , )kkkjiikkxxsh xw g xl xw vxl x w vxxl x w v由于故有0.根据函数的定义，有f() (7.2.51)f( ) (7.2.52)将上两式代入(7.2.50),并注意到 是局部最优解，0,则有7. 最优性条件-等与不等式约束3

40、1( )( )2( )2( )( )( )2( )2( )( )( )1()( )()( , , )()2( ,) (7.2.53)()( )k1()( , , )()( ,)02kkkxkkkkkkkxkf xf xxxl x w vxxxxx xxxf xf xxxl x w vxxxxx xx注意到 是局部最优解,当k充分大时必有。因此对充分大的 ，由（7.2.53）得上式两端乘以22( , , )0 xdl x w v d，并去取极限，则证毕。7. 最优性条件-等与不等式约束32为给出局部最优解的二阶充分条件，我们定义集合0( )0,0( )0,0( )0,1,2,.,iiiiidg

41、x diiwgdg x diiwh x djl且且1122.11() 7.2.1,(1,.,)(1,., )(,.,)( ,.,),( , , )0iijmlxtheoremf g imhjlwwwvvvxdgdl x w v dx 二阶充分条件设在问题中，和二次连续可微，并存在满足(7.2.43)的乘子和为可行点，且对每一个向量都有则 是严格的局部最优解。7. 最优性条件-等与不等式约束33j( )( )( )( )( )()( )(0) ,()( ) (7.2.54) (7.2.55).kkkkkkkxxxf xf xxxdxxddd证明：反证法设 不是严格的局部最优解，则存在收敛于 的可

42、行序列使得 令 因为有界序列,故必有收敛子列,设其极限为jjjjj()()()()()( ),()( )( ) ()( ,)( ,)0 (7.2.56)ikkkkiiikjg xxg xg xg xxxxxx xxkx xx 把在 展开 得到其中当时7. 最优性条件-等与不等式约束34jjjjjj()()()()()()(0)(0)( )0()(7.2.56)( ) ()( ,)0( )0,. (7.2.57)( )0,1,., . (7.kkiikkkikjijiig xxg xg xxxxxx xxxxkg x diih x djl 当时 ，又是可行点，0，故由得到上式两端除以，令，则 类

43、似可得(0)2.58)( )0, (7.2.59)f x d 及 7. 最优性条件-等与不等式约束35下面分两种情况讨论(0)(0)(0)(0)1(0)1)g0( )0( )( )( ) ( )0(7.2.59)iiliijji ijiii idgiiwg x dkktf x dwg xvh xdwg x d此时，由(7.2.57)和集合 的定义可知，必存在下标使得和。于是利用条件，必有此与矛盾。7. 最优性条件-等与不等式约束36jjjjjjjjj(0)()()()()22()()()()()1)lagrange( , , )(, , )( , , )( , , ) ()1 ()( , ,

44、)()2 ( ,) (7.2.60)( ,)0kkxkkxkkkkkdgl x w vxl xw vl x w vl x w vxxxxl x w vxxxxx xxxxx xxx此时，把函数在 展开，则其中当时。由于1(,.,)0,lagrangemwww是可行点，根据函数的定义，有7. 最优性条件-等与不等式约束37jjjjjjj()()()()11()()()(, , )()()()(, , )() (7.2.61)( , , )( ) (7.2.62)( , , )(7.2.63)()imlkkkkikkikkkxkl xw vf xw g xv h xl xw vf xl x w v

45、f xl x w vf x故 又知 由假设还有0 ( )(7.2.64)(7.2.61)(7.2.64)(7.2.60)f x 将代入，则jjjj2()()()()21()( , , )()( ,)02kkkkxxxl x w vxxxxx xx7. 最优性条件-等与不等式约束38j()(0)2(0)2 ( , , )0( , , )0()kjxxxxkdl x w v ddl x w v ddg 2上式两端除以，令，则此与的假设相矛盾。7. 最优性条件-等与不等式约束39例7.2.7 考虑下列非线性规划问题12122212min . .3(3)0(3)100 xstxxxx检验以下各点是否为

46、局部最优解(1)(2)(3)(4)24310310,3300 xxxx7. 最优性条件-等与不等式约束40记目标函数和约束函数分别为f(x),g(x),h(x),他们在点x处的梯度分别是1122(3)16(3)( ),( ),( )201xxf xg xh xx lagrange函数是22211212( , , )3(3)(3)10l x w vxwxxv xxlagrange函数关于x的hessian矩阵是262002xwvlv7. 最优性条件-等与不等式约束41(1)(1)(1)(1):162(),(),()016kkt162310.01619380kktxf xg xh xwvwvw 检

47、查是可行点，且两约束都是起作用约束。按照条件，设不存在使的解，故它不是点.7. 最优性条件-等与不等式约束42(2)(2)(2)(1)(2):162(),(),()016kkt162310.0161938kktlagrangehessian10(, , )1019xxf xg xh xwvwvl xw v 2检查是可行点，且两约束都是起作用约束。按照条件，设故它是点,此点函数的矩阵为：7. 最优性条件-等与不等式约束43(2)(2)12120,(6(0,0)26ggwgg xdh xdddddd求集合 中的元素。由于根据 的定义，令)=0,)=00上述方程组即0故 。此情况表明在充分条件中对曲

48、率的要求自然满足，因此该点是局部最优解。后两点请自行验证之7. 最优性条件-等与不等式约束442212212min(-2). .-0(0,0)xxstxxx 其中 为某个实数。讨论点是否为局部最优解。例7.2.8 考虑下列非线性规划问题记目标函数和约束函数分别为f(x), h(x),他们在点x处的梯度分别是00( ),( )41f xf x7. 最优性条件-等与不等式约束45例22212122(0)2(0)000v=441( , )(-2)(-)hessian22002220,02xxvlagrangel x vxxvxxxvlvxl xv设函数为它关于 的矩阵是在点处，有（）7. 最优性条件

49、-等与不等式约束46122112(0)212(0),00(,0) , )2(14 )1/4, )00 0 xxdgdddddddl xv dddgdl xv d(0)求集合 的元素令(0,-1)解得可取任意实数。此时有(当时。对每一个向量有(故x =( ，)是局部最优解。7. 最优性条件-等与不等式约束472(0)2212212221/4, )00 01/4min(-2). ./4-0(-2)0 0 xdgdl xv dxxst xxx(0)(0)2当时。对每一个向量有(此时不满足局部最优解的二阶必要条件，故x =( ，)不是局部最优解。当 时利用二阶条件给不出结论，可用其他方法判断。此时原问

50、题即 利用约束条件，从目标函数中消去一个变量，把问题化为无约束问题min4x +，显见x =( ，)为局部最优解ch7.3 对偶理论1 min ( ) , ( )0 ()(7.3.1) , ( )0, , ijnf xs tg xipih xjexdrinlpe考虑如下形式的约束优化问题其中分别是(7.3.1)d不等式约束和等式约束的指标集。为问题的集合约束.称原始形式为非线性(原规划的问题).7.3.1 对偶形式ch7.3 对偶理论2max ( , ). .0( , )inf ( )( )( )| (7.3lagran().3)s,( , , )( )( )( )pnlpdnlplagran

51、ge,getttts tf xg xh xxdl xf xg xh xxddnlpnlpp 其中目标函数 称为问题的.问题()和()的可行域分别记为 和相应对的函数为偶函数 (7.3.2) (7.3.2)| | |,.ierr,其对偶形式其对偶形式(对偶问题对偶问题)定义如下定义如下ch7.3 对偶理论3112212121212( , )inf()()|inf()l|, 0, plagrangentttntttttntttttdrc xa xba xbxrcaa xbbxrbbcaa 若若取取集集合合约约若若束束则则该该问问题题的的对对为为否否则则偶偶函函数数,例考虑lp问题7.3.1 7.3

52、.1 1122min. . *tnc xs ta xba xbxr于是(lp)问题(*)的对偶形如1212max . . 0 ttttbbs taacch7.3 对偶理论42:1max42. .0s t 于于是是该该问问题题的的对对偶偶问问题题形形如如 22212122221212221112222min4,( , )inf(4)|4inf|0inf|014 , 0 24 , lagrange nfxxxxxrdrxxxxxrxxxxxx s.例:考虑非线性约束优化问题,若取集合约束,则它, 否则函数为 t.的ch7.3 ch7.3 对偶理论对偶理论5 5( , )min( )max ( ,

53、) ? x sf x 7.3.2 对偶定理对偶定理对于上面的两例我们有原问题与对偶问题的最优值相等.对一般形式的非线性规划问题,是否也对?即( , )pnl( )(p)(,) 定理7.3.1(弱对偶定理)设和分别为原问题()和对偶问题的可行解,则 dnf xlpxs1. 1. 弱对偶定理弱对偶定理ch7.3 对偶理论6minmaxminmpnlp(2),inf ( )|sup ( , )|( , )(, )( )( , )( , )( , ),pnl( , )p 推论对于原问题()和对偶问题(dnlp),则下述结论成立:(1)若则 若存在和使得则 和分别是原问题()和对偶问题(dnlp)的最优

54、解.(3)若,则.若sff xxsxsf xxf7.3.1 7.3.1 axpnlp ,则原问题()没有可行解.minmaxf (pnlp)(pnlp)问问题题的的对对偶偶间间隙隙定定义义为为 ch7.3 对偶理论7 | ( )0, ( )0,slater 对于凸规划来说 若相对内点的集合 则称约束函数满足条件.定义 risx h xg xxd2. 2. 凸规划与凸规划与slaterslater约束规格约束规格*( *)0,( *)0 ( *)( *)|( *)0,( *)0 ( *). 设为凸规划的一个最优解,若 在包含 的凸开集 内可微且slater约束规格成立,则存在方向 ,使得,即命题

55、 ttinttixsgsddh xdg xdii xc xdrh xdg xdii xch7.3 对偶理论8,*.( ), *,( *)( )( *)0,( ),( )( *)( *)( *)( )0,( *),( *)0,( *)0tttrisxris dxxh xxris xsh xdh xh xg xiig xg xdg xg xdg xii xg xg xd i ii ii i证证明明: :因因故故可可取取由由是是线线性性函函数数所所以以另另一一方方面面 根根据据的的凹凹性性 有有利利用用且且注注意意到到可可得得 ch7.3 对偶理论9slaterkk,(),*0*,( *, *, *

56、)t. 理 凸规划的一阶必要条件)假设在包含凸规划的可行域的凸开集上函数可微.若函数满足约束规格,且为凸规划的最优解,则存在lagrange乘子向量,使得满足条件isf g iig hxx定定 ( (3. 强对偶定理强对偶定理00:():( )( )0, ( )0, ( )0(, , )0(, )0,( )( )( )0(),ittdfdrg iidrh xxdf xg xh xf xg xh xxd 0 00 0引引理理设设 为为非非空空凸凸集集, ,为为凸凸函函数数, ,为为凹凹函函数数. .为为线线性性函函数数. .对对下下面面的的两两个个不不等等式式系系统统: :(1)(1)存存在在使

57、使得得 (2)(2)存存在在, ,使使得得且且 若若系系统统(1)(1)无无解解, ,则则系系统统(2)(2)有有解解; ;若若系系统统(2)(2)有有满满足足的的解解, ,则则系系统统( (007.3.2 7.3.2 1)1)无无解解. .ch7.3 对偶理论10证明:先证第一部分:(1)无解=(2)有解. 令集合000( , , )|,( ), ( ), ( ).(0,0,0).(, , )0( , , )( ),0.0,0.( ),( ),( )(),ttcp q rxd pf xg xq h xrcp q rcl cpqrpqpf x qg x rh xxd 可可证证c c是是非非空空

58、凸凸集集. .若若(1)(1)无无解解, ,则则由由凸凸集集分分离离定定理理知知, ,存存在在使使得得 分分别别令令, ,则则有有特特别别的的, ,上上式式对对也也成成立立, ,故故(2)(2)有有解解. .再再证证第第二二部部分分:(2:(2000,( )( )( ).(d,)0, ( )0( )0,( )0,0ttxdf xg xh xg xhxxf xf x ) )有有解解(1)(1)无无解解假假设设(2)(2)有有满满足足的的解解, ,由由于于知知对对任任00何何满满足足的的点点由由可可知知即即所所以以(1)(1)无无解解. .ch7.3 对偶理论11minmaxminmax()(),

59、0int()() ( )|)inf ( )|sup ( , )|( , ),( , )( ,slater,). 定理强对偶定理 对于凸规划问题,假设 为非空的凸开集, 为凸函数,为凹函数,为线性函数.若函数满足约束规格,并且,则 此外,若则存在某个使得ijdfg iihjeg hh d h dh xxsff xxsf7.3.3() 7.3.3() min( )( )0特别的.若存在,使得,则互补松施条件成立.txsf xfg xch7.3 对偶理论12min000minm00in( )-0, ( )0, ( )0(, , )0 (, )0,( ( )( )( )0.0,:.d,slater0,( )0,( )0 ttf xfg xh xxdf xfg xh xxdg xhfx证证明明 根根据据弱弱对对偶偶定定理理的的推推论论, ,不不妨妨设设于于是是不不等等式式组组 在在非非空空凸凸集集 内内无无解解, ,由由引引理理(7.3.2)(7.