【正文】 +1→ k。返回收斂性檢驗(yàn)。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 準(zhǔn)牛頓法v 牛頓法算法的優(yōu)點(diǎn)是收斂速度快 (利用了 Hesse矩陣)。但使用 Hesse矩陣的不足之處是計(jì)算量大，Hesse矩陣可能非正定等，準(zhǔn)牛頓法 (QuasiNewton method)是對牛頓法的改進(jìn)，目前被公認(rèn)為是比較有效的無約束優(yōu)化方法。v 基本思想 ：在迭代過程中只利用目標(biāo)函數(shù) f(x)和梯度 g(x)的信息，構(gòu)造 Hesse矩陣的近似矩陣，由此獲得一個(gè)搜索方向，生產(chǎn)新的迭代點(diǎn)。具體內(nèi)容請參考相關(guān)書籍。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f(x)v Matlab提供了兩個(gè)求解無約束非線性規(guī)劃的函數(shù)? [x,fval] = fminunc(fun,x0)? [x,fval] = fminsearch(fun,x0)v 用法相似，算法內(nèi)部的搜索策略不同。 fun為 f(x)的函數(shù)形式， x0為初始解向量。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x)f = f(x)。? 然后調(diào)用 fminunc或 fminsearch并指定初始搜索點(diǎn)。 x0=[x1,x2,…,xn] [x,fval] = fminunc(myfun,x0) 或 [x,fval] = fminsearch(myfun,x0)決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 例 ： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)v 解 ：? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x)f =exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1)。? 調(diào)用無約束非線性規(guī)劃函數(shù) x0 = [1,1]。 % Starting guess options = optimset(39。LargeScale39。,39。off39。)。 [x,fval] = fminunc(myfun,x0,options)。或者 [x,fval] = fminsearch(myfun,x0,options)。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v fminunc結(jié)果：? x =[ ]? fval = ? iterations: 8? algorithm: 39。mediumscale: QuasiNewton line search‘v fminsearch結(jié)果：? x =[ ]? fval =? iterations: 46? algorithm: 39。NelderMead simplex direct search39。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 標(biāo)準(zhǔn)型v 其中 f(x)是目標(biāo)函數(shù)， gi(x)和 hj(x)為約束函數(shù) (約束條件 )。 S={x|gi(x)?0 ? hj(x)=0}為可行域。v 有約束非線性規(guī)劃問題 (COP)是指 f(x),gi(x),hj(x)至少有一個(gè)是非線性的，且 I或 ??至少有一個(gè)為非空。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個(gè)概念v 積極 (active)約束 ：設(shè) x0是 COP問題的一個(gè)可行解，則它必須滿足所有約束條件。對于 gi(x0)?0，或者等號成立，或者大于號成立。稱等號成立的約束為積極約束 (有效約束 )，此時(shí)， x0處于該約束條件形成的可行域邊界上；稱大于號成立的約束為非積極(inactive)約束 (無效約束 )，此時(shí)， x0不在該約束條件形成的可行域邊界上。顯然所有 hj(x0)約束均是積極約束。記 J={j|gj(x0)=0?hj(x0)=0}，稱為積極約束指標(biāo)集。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個(gè)概念v 可行方向 。設(shè) x0為 COP問題的任一可行解，對某一方向 d來說，若 ???00使得對于任意 ??[0,?0]，均有 x0+?d?S，稱 d為x0的一個(gè)可行方向。顯然若 d滿足 dT?gi(x)?0， dT?hj(x)=0，則 d一定是可行方向。（可用一階 Taylor公式分析）。v 下降方向 。 設(shè) x0?S，對某一方向 d來說，若 ???00使得對于任意 ??[0,?0]，均有 f(x0+?d)f(x0)，則稱 d為 x0點(diǎn)的一個(gè)下降方向。由 f(x0+?d)=f(x0)+?(?f(x0))Td+o(?)可知：若 d滿足dT?f(x0)0，有 f(x0+?d)f(x0)，則 d一定是下降方向。v 可行下降方向 。若 x0的某一方向 d既是可行方向又是下降方向則稱其為可行下降方向。 這個(gè)方向就是我們從 x0出發(fā)尋求最優(yōu)解的搜索方向！決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個(gè)概念v 例： min f(x)=x1+x2 . g(x)=1x12x22?0v 圖描述了該問題的相關(guān)概念。x1x2決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 一階必要條件? 幾何特征 ：若 x*是 COP問題的局部極小點(diǎn)且函數(shù) f(x), gi(x), hj(x)在 x*處可微，則 dT?f(x*)?0。 d為 x*的任意可行方向。f(x*+?d)=f(x*)+?(?f(x*))Td+o(?)? 代數(shù)特征 (KKT定理 )： 若 x*是 COP問題的局部極小點(diǎn)且函數(shù) f(x), gi(x), hj(x)在 x*處可微，則存在實(shí)數(shù) ?i?0(i?I), ?j?R(j??)，使得：?f(x*)=?i?gi(x*)?i+?j?hj(x*)?j；gi(x*)?i=0； ?i?0， ?i?I? 若 x*滿足 KKT條件，則稱 x*為 COP問題的一個(gè) KKT點(diǎn)，?i, ?j稱為 x*處的拉格朗日乘子。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 一階充分條件? 設(shè) x*?S，若 函數(shù) f(x), gi(x), hj(x)在 x*處可微，且對于 x*的任意可行方向 d，有 dT?f(x*)0，則 x*為 COP問題的一個(gè)嚴(yán)格局部極小點(diǎn)。? (凸規(guī)劃問題 )設(shè) f(x)為凸函數(shù)， gi(x)為凹函數(shù)， hj(x)為線性函數(shù)。對于 x*?S，若 函數(shù) f(x), gi(x)在 x*處可微，且 KKT條件成立，則 x*為 COP問題的全局最小點(diǎn)。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 二階必要條件? 設(shè) x*是 COP問題的局部極小點(diǎn)且滿足 KKT條件。若函數(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)的拉格朗日乘子向量。v 二階充分條件? 設(shè) x*是 COP問題的 KKT點(diǎn)。 ?*,?*分別為對應(yīng)于 g(x)和 h(x)的拉格朗日乘子向量，且 函數(shù) f(x), gi(x), hj(x)在 x*處二階可微，若 dT?xx2L(x*,?*,?*)d0,則 x*為 COP問題的一個(gè)嚴(yán)格局部極小點(diǎn)。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 例： min f(x)=x12+x22 . x1+x2?4 x1,x2?0v 解： g1(x)=x1+x24?0。g2(x)=x1?0。g3(x)=x2?0?f(x)=[2x1,2x2]T,?g1(x)=[1,1]T,?g2(x)=[1,0]T,?g3(x)=[0,1]T,得到：? 2x1=?1+?2? 2x2=?1+?3又 (x1+x24)?1=0； x1?2=0； x2?3=0； ?i?0v 若 ?1=0，則 x1=x2=0，與題意不符；v 若 ?10，則 x1+x24=0， x10, x20。因此有 ?2=?3=0，所以x1=x2=?1/2，得 x1=x2=2， x*=[2,2]T為該問題的唯一 KKT點(diǎn)。v 根據(jù)凸規(guī)劃充分條件知 x*為全局最小點(diǎn)。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法v 上面例題介紹了通過求解 KKT方程獲得問題解的方法，但 KKT方程并不總是很好求解。下面介紹幾種約束優(yōu)化的求解方法：可行方向法、序列無約束化法和 SQP法。v 可行方向法的應(yīng)用條件 ：要求所有約束均