【正文】 tion [c, ceq] = confun(x)c = c(x)。x=beq lb?x?ubv [x,fval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)v fun定義目標(biāo)函數(shù) ,x0定義初始可行解， nonlcon定義 c(x)和ceq(x)。設(shè)給定迭代點(xk,?k)，則決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f(x). c(x)?0 ceq(x)=0 A決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 對于等式約束優(yōu)化問題Min f(x). h(x)=0v 拉格朗日函數(shù)記為 L(x,?)=f(x)?Th(x)v 則 ?L(x,?)=(?f(x)?h(x)?, h(x))T=0，顯然問題的最優(yōu)解(x*,?*)滿足此式。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 對于非線性約束優(yōu)化 (COP)問題，v 若 x*是 COP問題的一個局部最優(yōu)解，則它對應(yīng)一個純等式約束優(yōu)化問題決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 因此如果事先知道積極約束指標(biāo)集，那么帶有不等式約束優(yōu)化問題就可以轉(zhuǎn)化為純等式約束優(yōu)化問題，并可用準(zhǔn)牛頓法求解，這就是逐次二次規(guī)劃(Sequential Quadratic Programming， SQP)法。? 對于凸二次規(guī)劃， x*為全局極小點當(dāng)且僅當(dāng) x*為局部極小點，當(dāng)且僅當(dāng) x*為 KKT點。我們僅討論凸二次規(guī)劃問題，因為非凸二次規(guī)劃的 Q存在負(fù)特征根，求解很困難。其標(biāo)準(zhǔn)型為：決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 標(biāo)準(zhǔn)型v 其中 Q=QT?Rnn（ n階對稱方陣）；以 aiT(i?I)為行向量的矩陣記為 AI?RIn；以 ajT(j??)為行向量的矩陣記為 A??R?n；對應(yīng)的向量記為 bI, b?。? 該方法的適用性： COP問題僅包含不等式約束函數(shù)，且可行域存在內(nèi)點。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 二次罰函數(shù)法 ：? 罰函數(shù)：? 其中 (gi)=max{0,gi}， ?稱為罰參數(shù)，且當(dāng) ?→0 時， Q(x,?)的極小值趨于 f(x)的極小值。這種轉(zhuǎn)換隱含著某種懲罰，即 x偏離約束條件越遠(yuǎn)，受到的懲罰越大。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 求解約束優(yōu)化的一類重要方法是用一個無約束優(yōu)化問題的序列 逼近 約束優(yōu)化問題，通過無約束優(yōu)化問題的最優(yōu)解序列逼近約束優(yōu)化問題的最優(yōu)解。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法vZoutendijk可行方向法：其核心思想是通過求解下列線性規(guī)劃問題，在可行方向的某個范圍內(nèi)獲得目標(biāo)函數(shù)的最速下降方向。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法x1x2決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法v LCO問題： Min f(x) . aiTx?bi, i?I ajTx=bj, j??v 設(shè) x0是 LCO的一個可行解，若 d是可行域在 x0點的 可行方向 ，則 d滿足 AI(x0)d?0(I(x0)={i|aiTx0=bi,i?I})，A?d=0。v 可行方向法的應(yīng)用條件 ：要求所有約束均為線性約束（稱為線性約束的優(yōu)化問題， LCO）。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法v 上面例題介紹了通過求解 KKT方程獲得問題解的方法，但 KKT方程并不總是很好求解。因此有 ?2=?3=0，所以x1=x2=?1/2，得 x1=x2=2， x*=[2,2]T為該問題的唯一 KKT點。g2(x)=x1?0。 ?*,?*分別為對應(yīng)于 g(x)和 h(x)的拉格朗日乘子向量，且 函數(shù) f(x), gi(x), hj(x)在 x*處二階可微，若 dT?xx2L(x*,?*,?*)d0,則 x*為 COP問題的一個嚴(yán)格局部極小點。若函數(shù)f(x), gi(x), hj(x)在 x*處二階可微，則必有：dT?xx2L(x*,?*,?*)d?0 其中， L(x,?,?)=f(x)g(x)T?h(x)T?, g(x),h(x)分別為由 gi(x)和 hj(x)構(gòu)成的向量值函數(shù)， ?,?分別為對應(yīng)于 g(x)和 h(x)的拉格朗日乘子向量。對于 x*?S，若 函數(shù) f(x), gi(x)在 x*處可微，且 KKT條件成立，則 x*為 COP問題的全局最小點。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 一階充分條件? 設(shè) x*?S，若 函數(shù) f(x), gi(x), hj(x)在 x*處可微，且對于 x*的任意可行方向 d，有 dT?f(x*)0，則 x*為 COP問題的一個嚴(yán)格局部極小點。 d為 x*的任意可行方向。 這個方向就是我們從 x0出發(fā)尋求最優(yōu)解的搜索方向！決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個概念v 例： min f(x)=x1+x2 . g(x)=1x12x22?0v 圖描述了該問題的相關(guān)概念。v 可行下降方向 。 設(shè) x0?S，對某一方向 d來說，若 ???00使得對于任意 ??[0,?0]，均有 f(x0+?d)f(x0)，則稱 d為 x0點的一個下降方向。（可用一階 Taylor公式分析）。設(shè) x0為 COP問題的任一可行解，對某一方向 d來說，若 ???00使得對于任意 ??[0,?0]，均有 x0+?d?S，稱 d為x0的一個可行方向。記 J={j|gj(x0)=0?hj(x0)=0}，稱為積極約束指標(biāo)集。稱等號成立的約束為積極約束 (有效約束 )，此時， x0處于該約束條件形成的可行域邊界上；稱大于號成立的約束為非積極(inactive)約束 (無效約束 )，此時， x0不在該約束條件形成的可行域邊界上。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個概念v 積極 (active)約束 ：設(shè) x0是 COP問題的一個可行解，則它必須滿足所有約束條件。 S={x|gi(x)?0 ? hj(x)=0}為可行域。NelderMead simplex direct search39。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v fminunc結(jié)果：? x =[ ]? fval = ? iterations: 8? algorithm: 39。 [x,fval] = fminunc(myfun,x0,options)。off39。LargeScale39。? 調(diào)用無約束非線性規(guī)劃函數(shù) x0 = [1,1]。? 然后調(diào)用 fminunc或 fminsearch并指定初始搜索點。 fun為 f(x)的函數(shù)形式， x0為初始解向量。具體內(nèi)容請參考相關(guān)書籍。但使用 Hesse矩陣的不足之處是計算量大，Hesse矩陣可能非正定等，準(zhǔn)牛頓法 (QuasiNewton method)是對牛頓法的改進(jìn)，目前被公認(rèn)為是比較有效的無約束優(yōu)化方法。返回收斂性檢驗。? 迭代改進(jìn) ：計算新的迭代點 xk+1，即 xk+1=xkG1(xk)g(xk)。則f(x)=f(xk+p)≈f(xk)+g(xk)Tp+1/2pTG(xk)p=?k(p)v 由于 ?k(p)的最小點滿足 g(xk)+G(xk)p=0，得p=xxk=G1(xk)g(xk)v 因此，可近似得到迭代關(guān)系：xk+1=xkG1(xk)g(xk)決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 牛頓法v 牛頓迭代法步驟? 初始化 ：給定一個初始點 x0以及參數(shù) e0；記 k=0。如果近似誤差比較大，那么可在近似最小點附近重新構(gòu)造 f(x)的二階 Taylor多項式(迭代 )，據(jù)此尋找新的近似最小點，重復(fù)以上過程直到求得滿足一定精度要求的迭代點。設(shè) f(x)是可微凸函數(shù)，則 x*是 f(x)的全局最小點，當(dāng)且僅當(dāng)梯度 ?f(x*)=0。 設(shè) f(x)在 x*點二階可微，若梯度 ?f(x*)=0且 Hesse矩陣 ?2f(x*)是正定 的，則 x*是 f(x)的一個嚴(yán)格局部極小點。設(shè) x*是 f(x)的局部極小點，則? 當(dāng) f(x)在 x*點可微時，梯度 ?f(x*)=0；? 當(dāng) f(x)在 x*點二階可微時， Hesse矩陣 ▽ 2f(x*)是半正定 的，即 ??d?Rn，有 dT?2f(x*)d?0。 x?Rnv 其中 f： Rn→R 是一個非線性連續(xù)函數(shù)。