非線性規(guī)劃ppt課件

1、非線性規(guī)劃非線性規(guī)劃根底知識根底知識直線搜索問題直線搜索問題無約束問題無約束問題不等式約束問題不等式約束問題等式和不等式約束問題等式和不等式約束問題拉格朗日對偶問題拉格朗日對偶問題主要內(nèi)容主要內(nèi)容根底知識根底知識非線性規(guī)劃的普通方式非線性規(guī)劃的普通方式其中其中 ljXgmiXhXfji, 2 , 1, 0, 2 , 1, 0 s.t.minnTnRxxxX,21定義可行集定義可行集上述普通方式可簡寫成上述普通方式可簡寫成 1010lj,Xgm,i,XhRXjin XfX min XXfXfX,全局最優(yōu)解全局最優(yōu)解 ： XfXfX的的 鄰域：鄰域： ,XXRXXBnXX部分最優(yōu)解部分最優(yōu)解 ：

2、,XBXXfXf，且存在，且存在 滿足滿足0X假設(shè)在上面的定義中用假設(shè)在上面的定義中用 交換交換 ，那么稱那么稱 為嚴厲部分最優(yōu)解和嚴厲全局最優(yōu)解為嚴厲部分最優(yōu)解和嚴厲全局最優(yōu)解 f Xf XXX)(Xf部分最優(yōu)解部分最優(yōu)解全局最優(yōu)解全局最優(yōu)解鄰域鄰域標量函數(shù)求偏導數(shù)梯度標量函數(shù)求偏導數(shù)梯度nTTxXfxXfxXfXXfXf)(,)(,)()()(21nxXfxXfxXfXXfXf)()()()()(21向量函數(shù)求偏導數(shù)向量函數(shù)求偏導數(shù)TmXfXfXfXF)(,),(),()(21mnmmnmTXfXfXfXXfXXfXXfXXF)(,),(),()(,)(,)()(2121nmmTTTnmT

3、mTTTXfXfXfXXfXXfXXfXXF)()()()()()()(2121海賽海賽Hesse矩陣矩陣2221 112122222 122222212()()()()()()()()()()nnTnnnnf Xf Xf Xx xx xx xf Xf Xf Xf Xx xx xx xf XXf Xf Xf Xx xx xx x對向量函數(shù)的點積求偏導數(shù)對向量函數(shù)的點積求偏導數(shù)TmXfXfXfXF)(,),(),()(21TmXgXgXgXG)(,),(),()(21)()()()()()(XFXXGXGXXFXXGXFTTTTTTTTTXXFXGXXGXFXXGXF)()()()()()(對常

4、數(shù)矩陣和向量函數(shù)的乘積求偏導數(shù)對常數(shù)矩陣和向量函數(shù)的乘積求偏導數(shù)TmXfXfXfXF)(,),(),()(21mmRATTTTTAXXFXAXFXXAF)()()(TTXXFAXXAF)()(對二次函數(shù)求偏導數(shù)對二次函數(shù)求偏導數(shù) mmTRAAAXXAAXXAXAXXXXAXXTTTT2AXAAXXXAXXAXXXAXXTTTTTTTTT2一元函數(shù)在原點的二階泰勒一元函數(shù)在原點的二階泰勒Taylor展開展開221)(21)0()(tctcgtgt0其中其中tdttgdc222)()(0)(1tdttdgct0221)(21)()(tctcXftDXf多元函數(shù)在給定點沿給定方向的二階泰勒展開多元函

5、數(shù)在給定點沿給定方向的二階泰勒展開其中其中DDXfDtdttDXfdcT)()(2222DXftdttDXdfcT)(0)(1221()()()()2TTf XtDf Xf X DtDf XD Dt無約束優(yōu)化問題最優(yōu)性條件無約束優(yōu)化問題最優(yōu)性條件 XfnRXmin1 是部分最優(yōu)解的必要條件：是部分最優(yōu)解的必要條件： *X, 0, 0)()(*tXftDXf0)(*Xf)(*XfD0)(*Xf理由：理由：DtDXfDXftDtDXfDtXfXftDXfTTTT)(21)()(21)()()(*22*2*22*X不是部分最優(yōu)解不是部分最優(yōu)解2 是嚴厲部分最優(yōu)解的充分條件：是嚴厲部分最優(yōu)解的充分條件

6、：*XnTRDDtDXfDXftDXf,)(21)()(2*2*0)(*Xf0)(*2XfnTRDDXf, 0)(*理由：理由： 0)(*Xf0)(*2Xf, 0, 0)(*2DXf, 0,),()(*tRDXftDXfn,),()(XBXXfXf凸集上的凸函數(shù)和凹函數(shù)凸集上的凸函數(shù)和凹函數(shù)設(shè)設(shè) 是定義在集合是定義在集合 上的函數(shù)，假設(shè)上的函數(shù)，假設(shè)是凸集，并且對是凸集，并且對 中恣意兩點中恣意兩點 以及閉區(qū)間以及閉區(qū)間 中恣意一點中恣意一點 都滿足都滿足nR21,XX1, 0 212111XfXfXXf那么稱那么稱 是凸集是凸集 上的凸函數(shù)，假設(shè)上的凸函數(shù)，假設(shè)是凸集是凸集 上的凸函數(shù)，那么

7、稱上的凸函數(shù)，那么稱 是凸集是凸集上的凹函數(shù)，此時在上面的條件下應滿足上的凹函數(shù)，此時在上面的條件下應滿足)(Xf)(Xf)(Xf)(Xf 212111XfXfXXf一元凸凹函數(shù)的圖象一元凸凹函數(shù)的圖象1X2X1Xf2Xf211XX211XXf 211XfXf1X2X1Xf2Xf211XX211XXf 211XfXf凸函數(shù)凸函數(shù)凹函數(shù)凹函數(shù)一元可導凸凹函數(shù)的充要條件一元可導凸凹函數(shù)的充要條件2Xf1X2X1Xf1121fXfXXX凸函數(shù)凸函數(shù)凸函數(shù)凸函數(shù)11212fXfXXXfX 凹函數(shù)凹函數(shù)11212fXfXXXfX 多元可導凸凹函數(shù)的一階充要條件多元可導凸凹函數(shù)的一階充要條件 211212

8、1,XXXfXfXXXfT必要性：必要性：21211)(21)()()(DDXfDDXfXfXfTTDDXfDDXfXfXfXfXfXfTT)(21)()()()()()1 ()(121212121112,(1),DXXXXDXX利用二階泰勒展開可得利用二階泰勒展開可得記記令令 充分小，由凸凹性可得上面的不等式充分小，由凸凹性可得上面的不等式充分性：充分性：用用 和和 分別乘以上兩式再相加，再利用分別乘以上兩式再相加，再利用 2112121,XXXfXfXXXfT可得可得0)1 (21XXXX記記 ，那么，那么 ，利用給定條件，利用給定條件21)1 (XXXX XfXfXXXfXfXfXXXf

9、TT22111可得可得 211XfXfXf凸凹函數(shù)的二階充分條件凸凹函數(shù)的二階充分條件 XXf,002XXDXXDXXX221121,)1 (2222222)(5 . 0)()()(DDXfDDXfXfXfTT1112111)(5 . 0)()()(DDXfDDXfXfXfTT0)1 ()1 (2121XXXDD212111122222()(1) ()()0.5()0.5(1)()TTf Xf Xf XDf XD DDf XD D記記由于由于 )()()1 ()(21XfXfXf假設(shè)假設(shè) 是開集，前面的充分條件也是必要條件是開集，前面的充分條件也是必要條件DZDXfZDXT,00,2假設(shè)存在假

10、設(shè)存在 和和 使得使得 ，必存在充分小的必存在充分小的 滿足滿足 XnRZ 002ZXfZT0ZD取取 滿足滿足 ，利用，利用ZDZDXfZDXfXfDXfTT)(5 . 0)()()(22記記 ，由以上條件可得，由以上條件可得XXDXX,12 2112121,XXXfXfXXXfT和前面證明的凸凹函數(shù)的充要條件矛盾和前面證明的凸凹函數(shù)的充要條件矛盾凸性對優(yōu)化問題的根本作用凸性對優(yōu)化問題的根本作用 XfX min假設(shè)假設(shè) 是凸集，是凸集， 是其上的延續(xù)凸函數(shù)，稱是其上的延續(xù)凸函數(shù)，稱 Xf解，那么它也是該問題的全局最優(yōu)解解，那么它也是該問題的全局最優(yōu)解是凸規(guī)劃問題是凸規(guī)劃問題*X假設(shè)假設(shè) 是凸

11、規(guī)劃問題的恣意一個部分最優(yōu)是凸規(guī)劃問題的恣意一個部分最優(yōu)證明：假設(shè)存在證明：假設(shè)存在 滿足滿足接近接近 ，闡明，闡明 不是部分最優(yōu)解，矛盾不是部分最優(yōu)解，矛盾X10),()1 ()()1 (*XfXfXXf又由于又由于*()(),0f Xf X*X)()(*XfXf10),()1 (*XfXXf由于對充分小的由于對充分小的 ， 可以充分可以充分0*)1 (XX*X可行下降方向可行下降方向?qū)τ趦?yōu)化問題對于優(yōu)化問題 ，給定可行解，給定可行解 以以 XfX min稱為可行下降方向稱為可行下降方向X稱稱 是是 處的可行方向，假設(shè)存在處的可行方向，假設(shè)存在 滿足滿足及向量及向量 ，假設(shè)存在，假設(shè)存在 滿足滿足nRDtttDX0,DX0tttXftDXf0),(稱稱 是是 處的下降方向，既可行又下降的方向處的下降方向，既可行又下降的方向DX0tX)(Xf的等值線的等值線可行不下降方向可行不下降方向可行下降方向可行下降方向不可