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

1、最優(yōu)化方法最優(yōu)化方法 Operations Research第二第二四講四講非線性規(guī)劃的最優(yōu)性條件非線性規(guī)劃的最優(yōu)性條件無約束優(yōu)化問題的最優(yōu)性條件無約束優(yōu)化問題的最優(yōu)性條件nExtsxf.)(min定義定義:00,(0, ),()( )( )nxEdf xdf xdf xx設(shè)是任給一點(diǎn)，若存在對任意有 ，則稱 為在點(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)可微，并且，則稱為的一個(gè)或者平穩(wěn)點(diǎn)，。既不是極小點(diǎn)，也不是極大點(diǎn)的駐點(diǎn)稱為駐點(diǎn)鞍點(diǎn)。例：例：12( ), *(0, 0)*( )Tf xx xxxf x對于二次函數(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)存在其中，處二階可微且在證明：對任意的xdxfdxfdxddxfddxfddxdxddxfdxfdxfxfxxfdEdTTTn223( )( )0,( )( )f xxf xHessianxxxf xxf x定理 ：設(shè)函數(shù)在點(diǎn) 的鄰域內(nèi)二次可微，若梯度且半矩陣在該鄰域內(nèi)正定，則 是局部極小點(diǎn)。特別地，對于鄰域內(nèi)的任意點(diǎn)，若是正定矩陣，則 是一個(gè)嚴(yán)格的局部極小點(diǎn).問題的提出問題的提出 例例: :某公司經(jīng)營兩種設(shè)備。第一種設(shè)備每件售價(jià)為某公司經(jī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è)時(shí)間為為第二種設(shè)備售出數(shù)量。公司的總營業(yè)時(shí)間為800小時(shí)。小時(shí)。求：公司為獲取最大營業(yè)額（銷售額）的最優(yōu)營業(yè)計(jì)劃求：公司為獲取最大營業(yè)額（銷售額）的最優(yōu)營業(yè)計(jì)劃 解解設(shè)公司應(yīng)經(jīng)營銷售第一、二種設(shè)備數(shù)額分別為設(shè)公司應(yīng)經(jīng)營銷售第一、二種設(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無約束優(yōu)化 非線性規(guī)劃約束優(yōu)化約束優(yōu)化問題數(shù)學(xué)模型： 復(fù)習(xí)概念復(fù)習(xí)概念定義定義：設(shè)：設(shè)f(x)為目標(biāo)函數(shù)，為目標(biāo)函數(shù)，S為可行域，為可行域，x0S，若對若對 xS, ,有有f(x)f(x0), ,則則x0稱為極小化問題稱為極小化問題minminf(x)， xS的（全局）最優(yōu)解的（全局）最優(yōu)解定義定義：設(shè)設(shè)f(x)為目標(biāo)函數(shù)，為目標(biāo)函數(shù)，S為可行域，若存為可行域，若存在在x0的的鄰域鄰域 使得對使得對 xSN(x0)，有有f(x)f(x0), ,則則x0稱為稱為極小化問題極小化問題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á)到。求下列約束問題的解：求下列約束問題的解：221222122min. .14010 xxstxxx (-1,0)T(3,0)T約束優(yōu)化問題的最優(yōu)性條件約束優(yōu)化問題的最優(yōu)性條件可行集或可行域等式約束不等式約束ljxhmixgxSExljxhmixgtsxfjinji,2, 1,0)(,2, 1,0)(.,2, 1,0)(,2, 1,0)(.)(min思路：思路：幾何幾何- 代數(shù)代數(shù)直觀直觀- 抽象抽象簡單簡單- 復(fù)雜復(fù)雜？ Start with some basic concepts/k

9、nowledge定義定義:,0,(0,)nSExclS dxdSdSx設(shè)集合為非零向量，若存在數(shù)使得對任意，都有則稱 為集合 在 的可行方向(feasible direction)。SdxclSxddD有), 0(, 0, 0 x可行方向處的錐(集):定義定義:min( )00(0, ),()( )( )nnx Ef xxEdf xdf xdf xx對，設(shè)是任給一點(diǎn)，若存在，使得對任意的有，則稱 為在點(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)化問題：例：考慮如下約束優(yōu)化問題：122212min( ). .( )10f xxxstg xxx f(x)=0( )0g x x1x2x1x212.xDR對于任意內(nèi)點(diǎn) ，可行方向錐221( 1,0) ,|0.TxDdRd 對于邊界點(diǎn)可行方向錐 一般約束問題的最優(yōu)性條件一般約束問題的最優(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) 性 條 件 ） ： 考 慮 問 題設(shè)是的 非 空 集 合 ，在處 可 微 ，若是 局 部 最 優(yōu) 解 ， 則幾 何。為局部最優(yōu)解矛盾。與，且有則當(dāng)取有對有對則證明：設(shè)存在的xxfdxfSdxSdxDdxfdxfFdDdFdDFd)()(), 0(),min(.), 0(, 0,);()(), 0(, 0,.,212211000定義：定義：( ),( ) |,1,( )0( )2,0,ijxxIgxhxiI jlg xxxh設(shè) 為可行點(diǎn)，不等式約束中在 起作用約束下標(biāo)集記為 ，如果向量組線性無關(guān)約束和，則稱 為的正則點(diǎn)。定義：定

14、義：0101( ) | ( )0,( ( )0.d ( )( )d.xx ttttSx h xttth x txSxT xtx ttSx稱點(diǎn)集為曲面上的一條曲線，如果對所有均有如果導(dǎo)數(shù)存在，則稱曲線是可微的.曲面 上在點(diǎn) 處所有可微曲線的切向量組成的集合，稱為，曲面 在點(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ù)使成 立令則為 曲 面上 過的 一 條曲 線 。 在 點(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ù)可微，且 是。如果 是問題的局部最優(yōu)解，則在 處，有定理：的正則中點(diǎn)其., 0,0)()()(), 2 , 1()(,)(), 2 , 1()()(),(,0)(|,)( 10100IiwwxhvxgwxfwljvIiwwNPxxljhxIixgxIixgxfxgiISxJohnFri

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

18、, )(ijiiijijijf xKKTstg ximhxjlxIi g xf g iIxg iIxhjlxg xhxiI jlxw iIvjlf定理必要條件）考慮問題設(shè) 為可行點(diǎn)在 處可微，在 連續(xù)，在 連續(xù)可微，向量集，線性無關(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、定理必要條件）考慮問題設(shè) 為可行點(diǎn)在 處可微，在 連續(xù)可微，向量集，線性無關(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定理必要條件）考慮問題設(shè) 為可行點(diǎn)在 處可線性無微，在 連續(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)解則：問題推論：求解下列線性規(guī)劃問題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條件解下列問題條件解下列問題: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ù)，所以本問題為凸規(guī)劃

23、問題，為全局最優(yōu)解例例:考慮問題考慮問題221222112124min29. .06,0 xxstxxxxx x是全局最優(yōu)解。）證明（成立。必要條件，并驗(yàn)證在點(diǎn)寫出*24923*) 1 (xxKKTT111234221212123142221121212349221100410112(2)()0(6)000060,0KKTxxwwwwxw xxwxxw xw xxxxxx xw www必要條件為2212min( ). .( )0f xxstg xxxKKT點(diǎn)應(yīng)滿足方程組點(diǎn)應(yīng)滿足方程組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è)不是問題的嚴(yán)格局部極小點(diǎ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) 展開，再令得到同理可證利用利用KKT條件條件, 得到得到 1( )( )( )0,lTTTiiji Ijf

27、xdwgxdvh xd( )0.Tf xd因此因此, ( )0,0Tiig xdiI w.Gd ( )( )0TTiii If xdwg xd由于( )kxS由由Taylor展開公式展開公式, 有有( )( )( )( )( )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ī)劃問題的求下列非線性規(guī)劃問題的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è) 為滿足條件的點(diǎn)，則有21211222min( )(1). .( )20( )0f xxxstg xxxgxxKKT 例：給定非線性規(guī)劃問題求滿足條件的點(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è) 為滿足條件的點(diǎn)，則有，即點(diǎn)為為整體極小點(diǎn)。條件成立，則處且在連續(xù)，在點(diǎn)可微，在點(diǎn)和。，為可行域，是凹函數(shù)，是凸函數(shù)，中，設(shè)問題一階充分條件定理xKKTxxIigxIigfxgiISxSmigfmixgtsxfiiiii)()(0)(|), 2 , 1(, 2 , 10)(. .)(min)(3,( )()() ()(1),(),0()()(2)(1)( )()() ()(3),( )()() ()(TiiiiiITiiiIiTiiiiSxSfxxSfxfxfxxxxKKTwiIwfxwgxfxfxwgxxxgiIgxgxgxxxg 證 明 ： 顯

31、然為 凸 集為 凸 函 數(shù) 且 在 可 微對又 點(diǎn) 處條 件 成 立 所 以 存 在使 得代 入得是 凹 函 數(shù)當(dāng)有) ()( )()( )0(4)(4)(3),( )().Tiiixxxgxgxgxfxfxx 將代 入得是 整 體 最 優(yōu) 解求約束極值問題求約束極值問題例例 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若若?？煽傻玫糜捎?0)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

33、KT 2,2對偶向量形式對偶向量形式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)的乘子為對約束的右端項(xiàng)進(jìn)行擾動對約束的右端項(xiàng)進(jìn)行擾動min( ). .( )1, 2,( )1, 2,iijjf xs tg ximh xjl

34、擾動問題擾動問題11,ml令 *,*, *,= 0,0* 0,0*,* 0 , * 0*, * .xLagrangewvxxwvw v 設(shè)擾動問題的局部最優(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è)是擾動問題的局部最優(yōu)解，是相應(yīng)的乘子向量，則有 1222121212221081834122xxxxx xxx例：某企業(yè)預(yù)算以 千元作為廣告費(fèi)，根據(jù)以

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

36、當(dāng) 增加時(shí)，下降，即上升，即當(dāng)廣告費(fèi)增加后，銷售金額也隨著增加，而且銷售金額的增加大約是廣告費(fèi)的 倍，可見適當(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ù)，如果對于每一對對于每一對x1，x2 S及每一個(gè)及每一個(gè)a，0a1,都都有有f(ax1+(1a)x2)a f(x1)+(1a)f(x2)則稱函數(shù)則稱函數(shù)f(x)為為S上的上

37、的凸函數(shù)上式中，若凸函數(shù)上式中，若變?yōu)樽優(yōu)?，則，則稱為嚴(yán)格凸函數(shù)。稱為嚴(yán)格凸函數(shù)。 若若-f(x)為為S的凸函數(shù)，則稱的凸函數(shù)，則稱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ù)，則對任意的上的凸函數(shù)，則對任意的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ù)，對每一個(gè)實(shí)數(shù)上的凸函數(shù)，對每一個(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)，既存在 的鄰域使得對，有。若 不是整體極小點(diǎn)，則使，是凸集，對有，是 上的凸函數(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è) 是中非空開凸集，是定義在 上的函數(shù)，則為凸函數(shù)的充要條件是對任意兩點(diǎn)，有；為嚴(yán)格凸函數(shù)的充要條件是對任意互不相同兩點(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ù)，則對及，有

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í)，對是”當(dāng)“是凸函數(shù)。有及由假設(shè)，對。，則，令。，有設(shè)對”“fxxfyfyxxyfyfxfxfyxyfyfxfyxyfyfxf