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