【正文】 非線性規(guī)劃 — Matlab函數應用 ? fminunc結果： ? x =[ ] ? fval = ? iterations: 8 ? algorithm: 39。off39。 ? 調用無約束非線性規(guī)劃函數 x0 = [1,1]。 fun為 f(x)的函數形式， x0為初始解向量。但使用 Hesse矩陣的不足之處是計算量大，Hesse矩陣可能非正定等，準牛頓法 (QuasiNewton method)是對牛頓法的改進，目前被公認為是比較有效的無約束優(yōu)化方法。 ? 迭代改進 ：計算新的迭代點 xk+1，即 xk+1=xkG1(xk)g(xk)。如果近似誤差比較大，那么可在近似最小點附近重新構造 f(x)的二階 Taylor多項式 (迭代 )，據此尋找新的近似最小點，重復以上過程直到求得滿足一定精度要求的迭代點。 設 f(x)在 x*點二階可微，若梯度 ?f(x*)=0且 Hesse矩陣 ?2f(x*)是正定 的，則 x*是 f(x)的一個嚴格局部極小點。 x?Rn ?其中 f： Rn→R 是一個非線性連續(xù)函數。 lb=zeros(2,1)。 x2≥0 解 ：將 max變?yōu)?min， min –z=x12x2 則： f=[1。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 內點算法 X空間 內點 目標函數 目標函數最速下降方向 Y1空間 中心點 投影尺度變換 1 目標函數最速下降方向 Y2空間 中心點 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — Matlab函數應用 ? Optimization ToolBox Min fTx . A ? 內點算法的思想是從可行域內的任意一點 (任一可行解 )出發(fā)，穿越可行域的內部達到最優(yōu)解。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 內點算法 ? 1972年， V. Klee和 G. L. Minty指出 Dantzig的單純形算法的迭代次數為 O(2n)，是一個指數時間算法，不是優(yōu)良算法。 ? 最優(yōu)解分析 ：在端點 (或稱為極點。人體正常活動過程中需要 m種基本的營養(yǎng)成分，且每人每天至少需要攝入第 i種營養(yǎng)成分 bi個單位。 ? 最優(yōu)化問題的一般形式為： ??????jxhIixgtsxfjiRx n,0)(,0)(..)(m i n2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化問題分類 ?可行點 與 可行域 ：滿足約束條件的 x稱為可行點，所有可行點的集合稱為可行域，記為 S； ?約束優(yōu)化 與 無約束優(yōu)化 ：當 S?Rn時，稱為約束優(yōu)化；當 S=Rn時，稱為無約束優(yōu)化； ?多目標優(yōu)化 ：若 f是多個目標函數構成的一個向量值函數，則稱為多目標規(guī)劃； ?線性規(guī)劃 與 非線性規(guī)劃 ：當 f,g,h均為線性函數時稱為線性規(guī)劃，否則稱為非線性規(guī)劃。決策理論與方法 (2) —— 優(yōu)化決策理論與方法 合肥工業(yè)大學管理學院 2021年 6月 15日 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 確定性決策 ?確定性決策 ：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一類決策問題，每一個行動方案對應著一個確定的結果值，此時決策函數僅依賴于決策變量。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化問題分類 ?整數規(guī)劃 ：當決策變量的取值均為整數時稱為整數規(guī)劃；若某些變量取值為整數，而另一些變量取值為實數，則成為混合整數規(guī)劃。已知第 j種食物中包含第 i種營養(yǎng)成分的量為 aij個單位。極點向量中，至少有nm個 0分量 )處取極值。那么是否存在求解線性規(guī)劃問題的多項式時間算法？ ? 1984年， N. Karmarkar提出了一種 投影尺度算法 ，其計算效果能夠同單純形法相比較，掀起了線性規(guī)劃 內點算法 的熱潮。 N. Karmarkar的 投影尺度算法 就是一種典型的內點算法。x≤b Aeq2]。 A=[1 1。對于任意點x*?Rn, 它是函數 f的最小點 (或局部極小點 )嗎？ ?例如： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — 極小值存在條件 ?必要條件 。 ?充要條件 。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — 牛頓法 ?設 xk是第 k次迭代結果，記 gk=g(xk)=?f(xk)；Gk=G(xk)=?2f(xk)。k+1→k 。 ?基本思想 ：在迭代過程中只利用目標函數 f(x)和梯度 g(x)的信息，構造 Hesse矩陣的近似矩陣，由此獲得一個搜索方向，生產新的迭代點。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數應用 ?用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f = f(x)。 % Starting guess options = optimset(39。)。mediumscale: QuasiNewton line search‘ ? fminsearch結果： ? x =[ ] ? fval = ? iterations: 46 ? algorithm: 39。 ?有約束非線性規(guī)劃問題 (COP)是指 f(x),gi(x),hj(x)至少有一個是非線性的，且 I或 ??至少有一個為非空。顯然所有 hj(x0)約束均是積極約束。顯然若 d滿足 dT?gi(x)?0， dT?hj(x)=0，則 d一定是可行方向。由 f(x0+?d)=f(x0)+?(?f(x0))Td+o(?)可知：若 d滿足dT?f(x0)0，有 f(x0+?d)f(x0)，則 d一定是下降方向。 x1 x2 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ?一階必要條件 ? 幾何特征 ：若 x*是 COP問題的局部極小點且函數 f(x), gi(x), hj(x)在 x*處可微，則 dT?f(x*)?0。 ? (凸規(guī)劃問題 )設 f(x)為凸函數， gi(x)為凹函數， hj(x)為線性函數。 ? 二階充分條件 ? 設 x*是 COP問題的 KKT點。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。下面介紹幾種約束優(yōu)化的求解方法：可行方向法、序列無約束化法和 SQP法。 ?設 x0是 LCO的一個可行解，若 d是可行域在 x0點的 下降方向 ，則 d滿足 dT?f(x0)0。 ?基本思想： 將約束條件通過某種轉換與目標函數合并形成一個無約束優(yōu)化問題。 )(2 1)())((2 1)(),(||12||12 xQxfhgxfxQjjIii ????????? ?????)(m i n)),((m i nl i m 0 xfxQ ?? ??2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?例 ： min f=x1+x2 . x1x22=0 ?解：對于 ?0，定義二次罰函數 Min Q(x,?)=x1+x2+(2?)1(x1x22)2 Q’x1=1+(x1x22)/?=0 Q’x2=12x2(x1x22)/?=0 解得： x?*=(1/4?,1/2)T, Q*=1/4?/2 當 ?→ 0時得， x*=(1/4,1/2)T, f*=1/4 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?對數障礙函數法 ： ? 障礙函數： ? 其中 ?稱為障礙參數，且當 ?→ 0時， P(x,?)的極小值趨于f(x)的極小值。若目標函數的 Hesse矩陣 Q是半正定 (或正定 )的，則 QP問題為(嚴格 )凸二次規(guī)劃 (CQP)。 ? 二次規(guī)劃的 KKT定理形式為： Qx*+c=AIT?*+A?T?* (AIx*bI)?*=0 ?二次規(guī)劃的求解本質上就是求解上述 KKT方程。 ? 設 (xk,?k)是第 k次迭代結果，根據牛頓法，有： ???????? ????????????????????????????????????????????????????)()()(0)()(),()),(()),((121211kkkkTkkkkxxkkkkkkkkkkxhxhxfxhxhxLxxLxLxx???????2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — SQP法 ? 上述迭代過程等價于如下的二次規(guī)劃的迭代。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — Matlab函數應用 ? 用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f = f(x)。 x0=[x1,x2,…,xn]。beq。 ? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x) c = [ + x(1)*x(2) x(1) x(2)。 % Starting guess options = optimset(39。)。x?b AeqA