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