Lecture2-6 nonlinear最優(yōu)性條件-凸函數(shù)

1、最優(yōu)化方法最優(yōu)化方法 Operations Research第二第二四講四講非線性規(guī)劃的最優(yōu)性條件非線性規(guī)劃的最優(yōu)性條件無(wú)約束優(yōu)化問(wèn)題的最優(yōu)性條件無(wú)約束優(yōu)化問(wèn)題的最優(yōu)性條件nExtsxf.)(min定義定義:00,(0, ),()( )( )nxEdf xdf xdf xx設(shè)是任給一點(diǎn)，若存在對(duì)任意有 ，則稱(chēng) 為在點(diǎn) 處的下降方向。必要條件必要條件1 ()( )( )0.f xxxf x定理 ：設(shè)函數(shù)在點(diǎn) 處可微，若 是局部極小點(diǎn)，則一階必要條件2()0()0,()() ()|() |00,(0,)()()TTfxdfxfxdfxfxfxfxdfxx 證 明 ： 設(shè)， 取則 有由 引 理 ，

2、存 在使 當(dāng)時(shí) ， 有與是 局 部 極 小 點(diǎn) 矛 盾 。定義：定義：( )*( *)0*( )(stationary point)(saddle point)f xxf xxf x若在點(diǎn)可微，并且，則稱(chēng)為的一個(gè)或者平穩(wěn)點(diǎn)，。既不是極小點(diǎn)，也不是極大點(diǎn)的駐點(diǎn)稱(chēng)為駐點(diǎn)鞍點(diǎn)。例：例：12( ), *(0, 0)*( )Tf xx xxxf x對(duì)于二次函數(shù)是它的駐點(diǎn)，但是該點(diǎn)既不是極小點(diǎn)，也不是極大點(diǎn)，所以是的鞍點(diǎn)。22( )( )0( )f xxxf xHessianf x定理 ：設(shè)在 處二階可微，若 是局部極小點(diǎn)，二階必則，且矩陣是要條件半正定的。.)(0)(,0)()(,|,0),(,0),(

3、|)(21)()(),(|)(21)()()(, 0)(,)(. 0)(1222222222為半正定的即有時(shí)當(dāng)必有充分小時(shí)當(dāng)是局部極小點(diǎn)時(shí)其中當(dāng)且處二階可微在維非零向量，是任意一個(gè)設(shè)，證明：由定理xfdxfdxfdxfxdxdxddxfdxfdxfdxddxfddxfxfdxfxfxxfndxfTTTT23( )( ) 0,( )Hessianxxxf xff x矩定理 ：設(shè)函數(shù)在點(diǎn) 處二次可微，若梯度且正定，則 是嚴(yán)格局部陣極小點(diǎn)。.,)()(0),(|)(21,), 0(, 0, 0)(. 0),(lim),(|)(21)()(0)()(, 0,2222202222是嚴(yán)格局部極小點(diǎn)知的任意

4、性由有時(shí)使得當(dāng)存在其中，處二階可微且在證明：對(duì)任意的xdxfdxfdxddxfddxfddxdxddxfdxfdxfxfxxfdEdTTTn223( )( )0,( )( )f xxf xHessianxxxf xxf x定理 ：設(shè)函數(shù)在點(diǎn) 的鄰域內(nèi)二次可微，若梯度且半矩陣在該鄰域內(nèi)正定，則 是局部極小點(diǎn)。特別地，對(duì)于鄰域內(nèi)的任意點(diǎn)，若是正定矩陣，則 是一個(gè)嚴(yán)格的局部極小點(diǎn).問(wèn)題的提出問(wèn)題的提出 例例: :某公司經(jīng)營(yíng)兩種設(shè)備。第一種設(shè)備每件售價(jià)為某公司經(jīng)營(yíng)兩種設(shè)備。第一種設(shè)備每件售價(jià)為30元，元，第二種設(shè)備每件售價(jià)為第二種設(shè)備每件售價(jià)為450元。且知，售出第一、二種設(shè)元。且知，售出第一、二種設(shè)

5、備分別需時(shí)為每件約備分別需時(shí)為每件約0.5小時(shí)和（小時(shí)和（2+0.25x2）小時(shí)，其中）小時(shí)，其中x2為第二種設(shè)備售出數(shù)量。公司的總營(yíng)業(yè)時(shí)間為為第二種設(shè)備售出數(shù)量。公司的總營(yíng)業(yè)時(shí)間為800小時(shí)。小時(shí)。求：公司為獲取最大營(yíng)業(yè)額（銷(xiāo)售額）的最優(yōu)營(yíng)業(yè)計(jì)劃求：公司為獲取最大營(yíng)業(yè)額（銷(xiāo)售額）的最優(yōu)營(yíng)業(yè)計(jì)劃 解解設(shè)公司應(yīng)經(jīng)營(yíng)銷(xiāo)售第一、二種設(shè)備數(shù)額分別為設(shè)公司應(yīng)經(jīng)營(yíng)銷(xiāo)售第一、二種設(shè)備數(shù)額分別為x1件件和和x2件，則有件，則有 max：f(X) =30 x1+450 x2 s.t. 0.5x1+2x2+0.25x22800 x10，x20min( )min( ). .( )0,1,2,( )0,1,2,.nx

6、 Eijf xf xstg xilh xjm無(wú)約束優(yōu)化 非線性規(guī)劃約束優(yōu)化約束優(yōu)化問(wèn)題數(shù)學(xué)模型： 復(fù)習(xí)概念復(fù)習(xí)概念定義定義：設(shè)：設(shè)f(x)為目標(biāo)函數(shù)，為目標(biāo)函數(shù)，S為可行域，為可行域，x0S，若對(duì)若對(duì) xS, ,有有f(x)f(x0), ,則則x0稱(chēng)為極小化問(wèn)題稱(chēng)為極小化問(wèn)題minminf(x)， xS的（全局）最優(yōu)解的（全局）最優(yōu)解定義定義：設(shè)設(shè)f(x)為目標(biāo)函數(shù)，為目標(biāo)函數(shù)，S為可行域，若存為可行域，若存在在x0的的鄰域鄰域 使得對(duì)使得對(duì) xSN(x0)，有有f(x)f(x0), ,則則x0稱(chēng)為稱(chēng)為極小化問(wèn)題極小化問(wèn)題minminf(x)， xS的局部最優(yōu)解的局部最優(yōu)解00() |,0Nx

7、xxx 顯然，與直線顯然，與直線AB相切的相切的點(diǎn)必為最優(yōu)解點(diǎn)必為最優(yōu)解。圖中圖中D點(diǎn)即為最優(yōu)點(diǎn)，點(diǎn)即為最優(yōu)點(diǎn)，此時(shí)目標(biāo)函數(shù)值為：此時(shí)目標(biāo)函數(shù)值為：f(x*)=2，x1*=x*2=3A f(x)=4f(x)=2x1x263202 36BCD例例求解下述非線性規(guī)劃求解下述非線性規(guī)劃 min f(x)=(x12)2+(x22)2 h(x)=x1+x26=0例例非線性規(guī)劃為非線性規(guī)劃為min f(x)=(x12)2+(x22)2 h(x)=x1+x260最優(yōu)解為最優(yōu)解為x1*=x2*=2 ，f(x*)=0，該點(diǎn)落在可行域內(nèi)部，該點(diǎn)落在可行域內(nèi)部，其邊界約束失去作用。其邊界約束失去作用。結(jié)論結(jié)論: :

8、非線性規(guī)劃的最優(yōu)解（如果存在）可在其可行非線性規(guī)劃的最優(yōu)解（如果存在）可在其可行域上任一點(diǎn)達(dá)到。域上任一點(diǎn)達(dá)到。求下列約束問(wèn)題的解：求下列約束問(wèn)題的解：221222122min. .14010 xxstxxx (-1,0)T(3,0)T約束優(yōu)化問(wèn)題的最優(yōu)性條件約束優(yōu)化問(wèn)題的最優(yōu)性條件可行集或可行域等式約束不等式約束ljxhmixgxSExljxhmixgtsxfjinji,2, 1,0)(,2, 1,0)(.,2, 1,0)(,2, 1,0)(.)(min思路：思路：幾何幾何- 代數(shù)代數(shù)直觀直觀- 抽象抽象簡(jiǎn)單簡(jiǎn)單- 復(fù)雜復(fù)雜？ Start with some basic concepts/k

9、nowledge定義定義:,0,(0,)nSExclS dxdSdSx設(shè)集合為非零向量，若存在數(shù)使得對(duì)任意，都有則稱(chēng) 為集合 在 的可行方向(feasible direction)。SdxclSxddD有), 0(, 0, 0 x可行方向處的錐(集):定義定義:min( )00(0, ),()( )( )nnx Ef xxEdf xdf xdf xx對(duì)，設(shè)是任給一點(diǎn)，若存在，使得對(duì)任意的有，則稱(chēng) 為在點(diǎn) 處的下降方向(descent direction)。0( )0TFdf xdx下降點(diǎn) 處的方向集：TANGENT CONE AND CONSTRAINT QUALIFICATIONSwe ne

10、ed to make assumptions about the nature of the constraints that are active at x to ensure that the linearized approximation is similar to the feasible set, near x. Constraint qualifications are assumptions that ensure similarity of the constraint set and its linearized approximation, in a neighborho

11、od of x .We lay the groundwork in this section by characterizing the directions in which we can step away from x while remaining feasible. A tangent is a limiting direction of a feasible sequence.The constraint qualification most often used in the design of algorithms is the subject of the next defi

12、nition.例：考慮如下約束優(yōu)化問(wèn)題：例：考慮如下約束優(yōu)化問(wèn)題：122212min( ). .( )10f xxxstg xxx f(x)=0( )0g x x1x2x1x212.xDR對(duì)于任意內(nèi)點(diǎn) ，可行方向錐221( 1,0) ,|0.TxDdRd 對(duì)于邊界點(diǎn)可行方向錐 一般約束問(wèn)題的最優(yōu)性條件一般約束問(wèn)題的最優(yōu)性條件ljxhmixgt sxfNPji, 2, 10)(, 2, 10)(. .)(min)(1122( )( )min( )( )( ). .( )0( ), ( )( )=0( )( )mlg xh xf xg xh xstg xg xh xh xgxh x01m in(

13、). .( )nfxs txSSExSfxxxFD 定 理（最 優(yōu) 性 條 件 ） ： 考 慮 問(wèn) 題設(shè)是的 非 空 集 合 ，在處 可 微 ，若是 局 部 最 優(yōu) 解 ， 則幾 何。為局部最優(yōu)解矛盾。與，且有則當(dāng)取有對(duì)有對(duì)則證明：設(shè)存在的xxfdxfSdxSdxDdxfdxfFdDdFdDFd)()(), 0(),min(.), 0(, 0,);()(), 0(, 0,.,212211000定義：定義：( ),( ) |,1,( )0( )2,0,ijxxIgxhxiI jlg xxxh設(shè) 為可行點(diǎn)，不等式約束中在 起作用約束下標(biāo)集記為 ，如果向量組線性無(wú)關(guān)約束和，則稱(chēng) 為的正則點(diǎn)。定義：定

14、義：0101( ) | ( )0,( ( )0.d ( )( )d.xx ttttSx h xttth x txSxT xtx ttSx稱(chēng)點(diǎn)集為曲面上的一條曲線，如果對(duì)所有均有如果導(dǎo)數(shù)存在，則稱(chēng)曲線是可微的.曲面 上在點(diǎn) 處所有可微曲線的切向量組成的集合，稱(chēng)為，曲面 在點(diǎn) 的切平面記為定義子空間定義子空間:|( )0THdh xd12( )( ),( ),( )Tlh xh xh xh x 其中結(jié)論：結(jié)論：0)(|)(dxhdHdxTdT，則有若向量.0)(|)(0)(|dxhdHxTxhxSxT上的一個(gè)正則點(diǎn)，則是曲面定理：設(shè)1,()0,.(, )(0, 0).0()()0( )(0)0),

15、()( )0( )=()( ),( )(0)(0lTdHhxtdhxytRyRy tthyJacobihxhxtyy tyhxtdhxy tx txtdhxy tx tSxx 證 明 ： 設(shè)考 慮 非 線 性 方 程 組其 中該 方 程 組 有 解在處 ，關(guān) 于的矩 陣 為由 隱 函 數(shù) 定 理 ， 在的 鄰 域 ， 存 在 連 續(xù) 可 微 函 數(shù)使成 立令則為 曲 面上 過(guò)的 一 條曲 線 。 在 點(diǎn))=(0)=()(0)()()()(0)0()= 0()()(0)= 0(0)=().TTTTxxdhxyhxdhxhxydHhxdxhxhxyxddTx ， 切 向 量 為又而，是 正 則 點(diǎn)

16、 ，可 逆 ，000000 | ( )0( )( )()( )()(1,2, )(),|( )0 ,|( )0,|( )0,1,2, .iijTTiTjxS f xg x iIxg x iIxh jlxxxNPxFGHFdf x dGdg x diIHdh xxdSjhlx設(shè)，和在 處可微，在 處連續(xù)，在 處連續(xù)可微，且 是。如果 是問(wèn)題的局部最優(yōu)解，則在 處，有定理：的正則中點(diǎn)其., 0,0)()()(), 2 , 1()(,)(), 2 , 1()()(),(,0)(|,)( 10100IiwwxhvxgwxfwljvIiwwNPxxljhxIixgxIixgxfxgiISxJohnFri

17、tziljjjIiiijijiii使得和不全為零的數(shù)的局部最優(yōu)解，則存在題是問(wèn)處連續(xù)可微，若在連續(xù)，處在處可微，在設(shè)條件定理., 2 , 1, 0, 2 , 1, 0)(0)()()(), 2 , 1()(,)(), 2 , 1()(),(,0)(|,)( 101100miwwmixgwxhvxgwxfwljvIiwwNPxxljhxxgxfxgiISxJohnFritziiiljjjmiiijijii使得和在不全為零的數(shù)的局部最優(yōu)解，則存是問(wèn)題續(xù)可微，若處連在處可微，在設(shè)條件定理min( )2(. .( )0,1,( )0,1, |( )0. ,()()(1, )( )( )|,1, ,(1

18、, )(ijiiijijijf xKKTstg ximhxjlxIi g xf g iIxg iIxhjlxg xhxiI jlxw iIvjlf定理必要條件）考慮問(wèn)題設(shè) 為可行點(diǎn)在 處可微，在 連續(xù)，在 連續(xù)可微，向量集，線性無(wú)關(guān)，若 是局部最優(yōu)解，則存在數(shù)和，使得1)( )( )0.0().liijji Ijixwg xvhxwiI1min( )2(. .( )0,1,( )0,1, |( )0. ,(1, )( )( ) |,1, ,(1, )( )( )ijiijijijmiiif xKKTs tgximhxjlxIi gxf gxhjlxgxhxiI jlxw iIvjlf xwgx

19、定理必要條件）考慮問(wèn)題設(shè) 為可行點(diǎn)在 處可微，在 連續(xù)可微，向量集，線性無(wú)關(guān)，若 是局部最優(yōu)解，則存在數(shù)和，使得1( )0( )0,1,2,01,2,.ljjjiiivhxw gximwim定義定義 廣義的廣義的Lagrange函數(shù)函數(shù):.)(,),()()(,),()(),(),()()()()()()(),(11212111TlTmTlTmTTljjjmiiixhxhxhxgxgxgvvvvwwwwxhvxgwxfxhvxgwxfvwxL其中乘子向量乘子向量min( )2(. .( )0,1,( )0,1, |( )0. ,(1, )( )( )|,1, 0, ,( , )0ijiijij

20、xf xKKTstg ximh xjlxIi g xf gxhjlxg xh xiI jlxwvL x w v定理必要條件）考慮問(wèn)題設(shè) 為可行點(diǎn)在 處可線性無(wú)微，在 連續(xù)可微，向量集，若 是局部最優(yōu)解，則存在乘子向量使關(guān)得一般情形的一階必要條件一般情形的一階必要條件(KKT必要條件必要條件)可表示為可表示為:miwljxhmixgmixgwvwxLijiiix, 2 , 1, 0, 2 , 1, 0)(, 2 , 1, 0)(, 2 , 1, 0)(0),(1()NPxSxKKT推 論 ： 設(shè)是的 凸 規(guī) 劃 ，線 性 約 束則是 整 體 最 優(yōu) 解是點(diǎn) 。0,0*0)*(00*,*,0. .

21、min2vwxvbAxwvAwcxbAxRvRwxxbAxtscxTTTTnm使得存在是最優(yōu)解則：?jiǎn)栴}推論：求解下列線性規(guī)劃問(wèn)題0,6224.2min32132132121xxxxxxxxxtsxx0,062204. .2min32132132121xxxxxxxxxtsxx由由KKT條件條件,得得123124125112321233 142531231232012020(4)0(226)0(1)(2)(3)(4)(5)(6)(7)(8)(0000,04022609)iiwwwwwwwwww xxxwxxxw xw xw xwxxxxxxx (6, 0, 0) .TKKT得到點(diǎn)為整體最優(yōu)解。T

22、)0 , 0 , 6(00102.)1()1(min2112212221xxxxxxtsxxf用用KKT條件解下列問(wèn)題條件解下列問(wèn)題:12123( )2(1), 2(1)( )( 1,1)( )(1,0)( )(0,1)( )( 1,1)TTTTTf xxxg xgxgxh x 11221312211211221321232(1)( 1)( 1)02(2)( 1)0201,0(2)000,0 xwwvxwwvxxxxxxwxxw xw xwwwKKT條件為：條件為：1 3*,2 2TxKKT為點(diǎn).min( )( )( )*12if xg xh xxf因?yàn)闉橥购瘮?shù)，為線性函數(shù)，所以本問(wèn)題為凸規(guī)劃

23、問(wèn)題，為全局最優(yōu)解例例:考慮問(wèn)題考慮問(wèn)題221222112124min29. .06,0 xxstxxxxx x是全局最優(yōu)解。）證明（成立。必要條件，并驗(yàn)證在點(diǎn)寫(xiě)出*24923*) 1 (xxKKTT111234221212123142221121212349221100410112(2)()0(6)000060,0KKTxxwwwwxw xxwxxw xw xxxxxx xw www必要條件為2212min( ). .( )0f xxstg xxxKKT點(diǎn)應(yīng)滿(mǎn)足方程組點(diǎn)應(yīng)滿(mǎn)足方程組121221220011()000 xww xxxxw 1210wxx*0, 0Tx 不是極小點(diǎn)。lineari

24、zed feasible direction setConstraint qualifications are conditions under which the linearized feasible set F(x) is similar to the tangent cone T_(x). In fact, most constraint qualifications ensure that these two sets are identical. the critical cone2(1,)(1, ),( , , )()( , , )( )0,00( )0,0 .( )0,1,2,

25、ijxTiiTiiTjfg imhjlxw vx w vLML x w vGxg xdiIwGdg xdiIwh xdjl定理（二階充分條件）：設(shè) ，和是二次連續(xù)可微函數(shù)， 為可行解，若存在，使為的解且矩陣在子空間 上是正定的，則 是嚴(yán)格局部極小點(diǎn)。且其中且證明：證明： x( )kxS( )( ),kkxx xx( )()( )kf xf x假設(shè)假設(shè)不是問(wèn)題的嚴(yán)格局部極小點(diǎn)不是問(wèn)題的嚴(yán)格局部極小點(diǎn), 則存在序列則存在序列, 使得使得, 并且并且, 即即( )( )( )()( )( ) ()(|)0.kTkkf xf xf xxxoxx ( )( )( ),|kkkxxdxx( )1,| 1.

26、kkd ()0ikdd( )kdd( ,)dT x S則，( )(1)0Tkf xdok( )0Tdf x記記顯然顯然, 根據(jù)有界序列的性質(zhì)可知根據(jù)有界序列的性質(zhì)可知, 存在一個(gè)收斂子列存在一個(gè)收斂子列不妨假設(shè)不妨假設(shè)令令于是有于是有.因?yàn)橐驗(yàn)? )0Tf x d以下證明()()()()()()( ),()()() ()(|)() ()(|)0 ()()0()()0,1,2,kikTkkiiiTkkiTiTjgxxxxgxgxgxxxoxxgxxxoxxiIgxdiIhxdjl 將在點(diǎn) 展開(kāi)，再令得到同理可證利用利用KKT條件條件, 得到得到 1( )( )( )0,lTTTiiji Ijf

27、xdwgxdvh xd( )0.Tf xd因此因此, ( )0,0Tiig xdiI w.Gd ( )( )0TTiii If xdwg xd由于( )kxS由由Taylor展開(kāi)公式展開(kāi)公式, 有有( )( )( )( )( )1( ,)( )()()()()(,)klkkTkTkiijji IjL x w vf xf xf xw g xv h xL xw v2( ,)0.TxdL x w v d矛盾。( )( )( )2( )( )2(, )( , )( , ) ()1()( , )()(|()| ).2kTkxkTkkxL xw vL x w vL x w vxxxxL x w vxxox

28、x而( )2( )( )21()( ,)()(|()| )0.2kTkkxxxL x w vxxoxx221222min3. .0*(0,0)Txxxs txx最 優(yōu) 解Lagrange函數(shù)為函數(shù)為22221222122( , )3(3)L x vxxxvxxvxx122220( , ),( , )(3)202xL x vL x vvxLagrange函數(shù)不存在極小點(diǎn)。函數(shù)不存在極小點(diǎn)。例例:求下列非線性規(guī)劃問(wèn)題的求下列非線性規(guī)劃問(wèn)題的KKT點(diǎn)點(diǎn).063)(05)(. .101022)(min2122221121222121xxxgxxxgtsxxxxxxxf121211224210( )22

29、1023( )( )21xxf xxxxg xgxx121 121212222112212221212124210230221020(5)0( 36)050360,0 xKKTxxw xwxxw xwwxxwxxxxxxw w設(shè) 為滿(mǎn)足條件的點(diǎn)，則有21211222min( )(1). .( )20( )0f xxxstg xxxgxxKKT 例：給定非線性規(guī)劃問(wèn)題求滿(mǎn)足條件的點(diǎn)。11211211222121221212( )(2(1),1) ,( )( 1, 1) ,( )(0,1)2(1)1001101(2)0020,001,0,0,1(1,0) .TTTTf xxgxgxxKTTxwww

30、xxw xxxw wxxxwwKKT 解：設(shè) 為滿(mǎn)足條件的點(diǎn)，則有，即點(diǎn)為為整體極小點(diǎn)。條件成立，則處且在連續(xù)，在點(diǎn)可微，在點(diǎn)和。，為可行域，是凹函數(shù)，是凸函數(shù)，中，設(shè)問(wèn)題一階充分條件定理xKKTxxIigxIigfxgiISxSmigfmixgtsxfiiiii)()(0)(|), 2 , 1(, 2 , 10)(. .)(min)(3,( )()() ()(1),(),0()()(2)(1)( )()() ()(3),( )()() ()(TiiiiiITiiiIiTiiiiSxSfxxSfxfxfxxxxKKTwiIwfxwgxfxfxwgxxxgiIgxgxgxxxg 證 明 ： 顯

31、然為 凸 集為 凸 函 數(shù) 且 在 可 微對(duì)又 點(diǎn) 處條 件 成 立 所 以 存 在使 得代 入得是 凹 函 數(shù)當(dāng)有) ()( )()( )0(4)(4)(3),( )().Tiiixxxgxgxgxfxfxx 將代 入得是 整 體 最 優(yōu) 解求約束極值問(wèn)題求約束極值問(wèn)題例例 004.866)(min2121212221xxxxtsxxxxxf。點(diǎn)點(diǎn)的的TK 解：解：。Txxxf3,32)(21 2114)(xxxg Txg1,1)(1 。Txgxxg0,1)(,)(212 。Txgxxg1 , 0)(,)(323 條條件件得得由由TK 01001113332121 xx條條件件及及約約束束條

32、條件件得得由由TK 0400043321321212312211312211x,x,xxxx)xx(xx以下分情況討論：以下分情況討論：:0)1(21 xx若若。可可得得由由00)4(1211 xx321 32 矛盾。矛盾。這與這與02 :0,0)2(21 xx若若03 332112 x022 x022 x 矛盾。矛盾。這與這與02 :0,0)3(21 xx若若02 333111 x031 x013 x 矛盾。矛盾。這與這與03 :0,0)4(21 xx若若032 331211 xx21xx 421 xx若若01 321 xx4621 xx矛盾。矛盾。421 xx221 xx11 點(diǎn)點(diǎn)。為為T(mén)

33、KT 2,2對(duì)偶向量形式對(duì)偶向量形式TlTmxhxhxhxgxgxgDxxhxgtsxf)(,),()()(,),()(0)(0)(. .)(min110. .),(maxwtsvw( , )inf( )( )( )|TTw vf xw g xv h xxDLagrange乘子的意義乘子的意義ljxhmixgtsxfNPji, 2, 10)(, 2, 10)(. .)(min)(NP*,*, * , *0.xLagrangew vw 設(shè)的局部最優(yōu)解為相應(yīng)的乘子為對(duì)約束的右端項(xiàng)進(jìn)行擾動(dòng)對(duì)約束的右端項(xiàng)進(jìn)行擾動(dòng)min( ). .( )1, 2,( )1, 2,iijjf xs tg ximh xjl

34、擾動(dòng)問(wèn)題擾動(dòng)問(wèn)題11,ml令 *,*, *,= 0,0* 0,0*,* 0 , * 0*, * .xLagrangewvxxwvw v 設(shè)擾動(dòng)問(wèn)題的局部最優(yōu)解為相應(yīng)的乘子為，則當(dāng)時(shí)，有l(wèi)jxhmixgtsxfNPji, 2, 10)(, 2, 10)(. .)(min)( 00( ),( ),( )*,*.*,*,*.ijfxgxhxxNPwvLagrangexwvfxwfxv 定理：設(shè)具有連續(xù)的二階偏導(dǎo)數(shù)，是的局部最優(yōu)解，是相應(yīng)的乘子向量 假設(shè)是擾動(dòng)問(wèn)題的局部最優(yōu)解，是相應(yīng)的乘子向量，則有 1222121212221081834122xxxxx xxx例：某企業(yè)預(yù)算以 千元作為廣告費(fèi)，根據(jù)以

35、往的經(jīng)驗(yàn)，若以 千元作廣播廣告， 千元作報(bào)紙廣告，銷(xiāo)售金額為千元試問(wèn)：如何分配 千元廣告費(fèi)？廣告費(fèi)預(yù)算作微小改變的影響如何？221212121212min 21081834. .200,0 xxx xxxs txxxx解：最優(yōu)化問(wèn)題為1212121122121212481802083400,020,0KKTxxwvxxwvw xw xxxxxw w相應(yīng)的條件為12*1 1*06TKKTxwwv 點(diǎn)為，廣告費(fèi)作微小改動(dòng)，考慮擾動(dòng)問(wèn)題廣告費(fèi)作微小改動(dòng)，考慮擾動(dòng)問(wèn)題 2212121212120min( )21081834. .20,0*6f xxxx xxxs txxxxdfxvd 有 *6fxfx

36、當(dāng) 增加時(shí)，下降，即上升，即當(dāng)廣告費(fèi)增加后，銷(xiāo)售金額也隨著增加，而且銷(xiāo)售金額的增加大約是廣告費(fèi)的 倍，可見(jiàn)適當(dāng)增加廣告費(fèi)的預(yù)算是有利的。凸規(guī)劃凸規(guī)劃是線性函數(shù)。是凹函數(shù)，凸函數(shù)，其中是)()()(., 2 , 1, 0)(, 2 , 1, 0)(. .)(minxhxgxfljxhmixgtsxfjiji凸函數(shù)凸函數(shù)凸函數(shù)凸函數(shù)：設(shè)設(shè)S是是En中的非空凸集，中的非空凸集， f(x)是定義在是定義在S上的上的實(shí)函數(shù)，如果實(shí)函數(shù)，如果對(duì)于每一對(duì)對(duì)于每一對(duì)x1，x2 S及每一個(gè)及每一個(gè)a，0a1,都都有有f(ax1+(1a)x2)a f(x1)+(1a)f(x2)則稱(chēng)函數(shù)則稱(chēng)函數(shù)f(x)為為S上的上

37、的凸函數(shù)上式中，若凸函數(shù)上式中，若變?yōu)樽優(yōu)?，則，則稱(chēng)為嚴(yán)格凸函數(shù)。稱(chēng)為嚴(yán)格凸函數(shù)。 若若-f(x)為為S的凸函數(shù)，則稱(chēng)的凸函數(shù)，則稱(chēng)f(x)為為S上的上的凹函數(shù)凹函數(shù)(a)嚴(yán)格凸x凸x非凸x(b)(c)凸函數(shù)性質(zhì)凸函數(shù)性質(zhì) (1) 設(shè)設(shè)f1(x)，f2(x)是凸集是凸集S上的凸函數(shù)，則函數(shù)上的凸函數(shù)，則函數(shù)f1(x)+f2(x)在在S上也是凸函數(shù)。上也是凸函數(shù)。(2) 設(shè)設(shè)f(x)是凸集是凸集S上的凸函數(shù)，則對(duì)任意的上的凸函數(shù)，則對(duì)任意的a0，函數(shù)，函數(shù)af(x)是凸的。是凸的。推廣：推廣：設(shè)設(shè)f1(x)，f2(x), , fk(x)是凸集是凸集S上的凸函數(shù)，上的凸函數(shù)，ai0,則則a1f1(

38、x)+a2f2(x)+ + akfk(x)也是凸集也是凸集S S上的凸函上的凸函數(shù)數(shù). .(3) 設(shè)設(shè)f(x)是凸集是凸集S上的凸函數(shù)，對(duì)每一個(gè)實(shí)數(shù)上的凸函數(shù)，對(duì)每一個(gè)實(shí)數(shù)c，則集，則集合合(level set)Scx | x S，f(x) c是凸集。是凸集。(4)設(shè)設(shè)S是是En中的非空凸集，中的非空凸集，f是定義在是定義在S上的凸函數(shù)，上的凸函數(shù)， 則則f在在S上的局部極小點(diǎn)是整體極小點(diǎn)，且極小點(diǎn)上的局部極小點(diǎn)是整體極小點(diǎn)，且極小點(diǎn) 的集合是凸集的集合是凸集凸函數(shù)性質(zhì)凸函數(shù)性質(zhì)證明：證明：(0)(0)(0)(0)(0)(0)0( )( )( )( )( )()(0,1)(1)(1) )()(

39、1) ( )( )(1) ( )( )xfSxNxxSNxf xf xxxSf xf xSxxSfSfxxf xf xf xf xf xx 設(shè) 是 在 中的局部極小點(diǎn)，既存在 的鄰域使得對(duì)，有。若 不是整體極小點(diǎn)，則使，是凸集，對(duì)有，是 上的凸函數(shù)，當(dāng) 取得充分小時(shí)，可使(1)( ) |,( )xSNxxxfSfSSx xS f x，這與 為局部極小點(diǎn)矛盾，是 在 上的整體極小點(diǎn)。在 上的極小值也是它在 上的最小值。極小點(diǎn)集合為，則由性質(zhì)（3），為凸集。凸函數(shù)的判別凸函數(shù)的判別梯度：梯度：Tnxxfxxfxf)(,)()(1Hesse矩陣：矩陣：221222122122122)()()()()

40、()()(nnnnxxfxxxfxxxfxxxfxxxfxxfxfAxfbAxxfcxbAxxxfTT)()(21)(2方向?qū)?shù)方向?qū)?shù)00000000,0( )()()()lim.(; )nntxEpEpf xxpf xf xtpf xptDf xpfxp 設(shè)，則函數(shù)在點(diǎn) 關(guān)于方向 的方向?qū)?shù)定義為：我們用表示 在點(diǎn) 關(guān)于方向 的方向?qū)?shù)。方向?qū)?shù)通常用下面的公式計(jì)算：方向?qū)?shù)通常用下面的公式計(jì)算：00(; )().TDf xpf xp 凸函數(shù)的充要條件凸函數(shù)的充要條件(1)(2)(2)(1)(1)(2)(1)(1)(2)(2)(1)(1)(2)(1)( )( ),()()() ()( ),

41、()()() ().nTTSEf xSf xxxSf xf xf xxxf xxxSf xf xf xxx設(shè) 是中非空開(kāi)凸集，是定義在 上的函數(shù)，則為凸函數(shù)的充要條件是對(duì)任意兩點(diǎn)，有；為嚴(yán)格凸函數(shù)的充要條件是對(duì)任意互不相同兩點(diǎn)有可，微定理（一階充要條件）定理（一階充要條件）凸性凸性(1)(2)(2)(1)(2)(1)(1)(2)(1)(1)(2)(1)(1)(2)(1)(1)(2)(1)(1)(2)(1),(0,1)(1)()(1) ()()()()()0(;)() (TfSxxSfxxf xf xf xxxf xf xf xffxxxDf xxxf xxx “”設(shè) 是 上的凸函數(shù)，則對(duì)及，有

42、即令，由 的可微性，得 在點(diǎn)關(guān)于方向的方向?qū)?shù)(2)(1)(2)(1)(1)(2)(1)()(),()()() ().Tf xf xf xf xf xxx證證 明明).()()()()()(21)()()()()(21)(21).()()()().(21)(212121)(212121,)1()2()1()1()2()1()2()1()1()1()1()1()2()1()1()1()1()2()1()2()1()2()1()2()1()2()1(xxxfxfxfxxxfxfxyxfxfxfxfxyxfxfyffxfxfxxfyfSxxyxxSxxSfTTTT是凸函數(shù)，且，則取，及上的嚴(yán)格凸函數(shù)時(shí)，對(duì)是”當(dāng)“是凸函數(shù)。有及由假設(shè)，對(duì)。，則，令。，有設(shè)對(duì)”“fxxfyfyxxyfyfxfxfyxyfyfxfyxyfyfxf