【正文】 q,lb,ub,x0)vx0定義初始可行解 (可選 )決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 首先要將目標(biāo)函數(shù)轉(zhuǎn)換成二次規(guī)劃標(biāo)準(zhǔn)型，從而得到 H和f兩個(gè)矩陣。[x,fval]=fmincon(objfun,x0,[],[],[],[],[],[],confun,options)? 運(yùn)行結(jié)果 ：x =[ ]fval =iterations: 8algorithm: 39。LargeScale39。 x(1)*x(2) 10]。lb。A。? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x)c = c(x)。設(shè)給定迭代點(diǎn)(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 對(duì)于非線性約束優(yōu)化 (COP)問(wèn)題，v 若 x*是 COP問(wèn)題的一個(gè)局部最優(yōu)解，則它對(duì)應(yīng)一個(gè)純等式約束優(yōu)化問(wèn)題決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 因此如果事先知道積極約束指標(biāo)集，那么帶有不等式約束優(yōu)化問(wèn)題就可以轉(zhuǎn)化為純等式約束優(yōu)化問(wèn)題，并可用準(zhǔn)牛頓法求解，這就是逐次二次規(guī)劃(Sequential Quadratic Programming， SQP)法。我們僅討論凸二次規(guī)劃問(wèn)題，因?yàn)榉峭苟我?guī)劃的 Q存在負(fù)特征根，求解很困難。? 該方法的適用性： COP問(wèn)題僅包含不等式約束函數(shù)，且可行域存在內(nèi)點(diǎn)。這種轉(zhuǎn)換隱含著某種懲罰，即 x偏離約束條件越遠(yuǎn)，受到的懲罰越大。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法vZoutendijk可行方向法：其核心思想是通過(guò)求解下列線性規(guī)劃問(wèn)題，在可行方向的某個(gè)范圍內(nèi)獲得目標(biāo)函數(shù)的最速下降方向。v 可行方向法的應(yīng)用條件 ：要求所有約束均為線性約束（稱(chēng)為線性約束的優(yōu)化問(wèn)題， LCO）。因此有 ?2=?3=0，所以x1=x2=?1/2，得 x1=x2=2， x*=[2,2]T為該問(wèn)題的唯一 KKT點(diǎn)。 ?*,?*分別為對(duì)應(yīng)于 g(x)和 h(x)的拉格朗日乘子向量，且 函數(shù) f(x), gi(x), hj(x)在 x*處二階可微，若 dT?xx2L(x*,?*,?*)d0,則 x*為 COP問(wèn)題的一個(gè)嚴(yán)格局部極小點(diǎn)。對(duì)于 x*?S，若 函數(shù) f(x), gi(x)在 x*處可微，且 KKT條件成立，則 x*為 COP問(wèn)題的全局最小點(diǎn)。 d為 x*的任意可行方向。v 可行下降方向 。（可用一階 Taylor公式分析）。記 J={j|gj(x0)=0?hj(x0)=0}，稱(chēng)為積極約束指標(biāo)集。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個(gè)概念v 積極 (active)約束 ：設(shè) x0是 COP問(wèn)題的一個(gè)可行解，則它必須滿(mǎn)足所有約束條件。NelderMead simplex direct search39。 [x,fval] = fminunc(myfun,x0,options)。LargeScale39。? 然后調(diào)用 fminunc或 fminsearch并指定初始搜索點(diǎn)。具體內(nèi)容請(qǐng)參考相關(guān)書(shū)籍。返回收斂性檢驗(yàn)。則f(x)=f(xk+p)≈f(xk)+g(xk)Tp+1/2pTG(xk)p=?k(p)v 由于 ?k(p)的最小點(diǎn)滿(mǎn)足 g(xk)+G(xk)p=0，得p=xxk=G1(xk)g(xk)v 因此，可近似得到迭代關(guān)系：xk+1=xkG1(xk)g(xk)決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 牛頓法v 牛頓迭代法步驟? 初始化 ：給定一個(gè)初始點(diǎn) x0以及參數(shù) e0；記 k=0。設(shè) f(x)是可微凸函數(shù)，則 x*是 f(x)的全局最小點(diǎn)，當(dāng)且僅當(dāng)梯度 ?f(x*)=0。設(shè) x*是 f(x)的局部極小點(diǎn)，則? 當(dāng) f(x)在 x*點(diǎn)可微時(shí)，梯度 ?f(x*)=0；? 當(dāng) f(x)在 x*點(diǎn)二階可微時(shí)， Hesse矩陣 ▽ 2f(x*)是半正定 的，即 ??d?Rn，有 dT?2f(x*)d?0。2 1] [x, fval] = linprog(f,A,b,[],[],lb) x=[0。 b=[40。x=beqlb≤x≤ub? 其中： f, x, b, beq, lb和 ub均為向量； A和 Aeq為矩陣。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法可行域內(nèi)點(diǎn)初始基可行解基可行解目標(biāo)函數(shù)目標(biāo)函數(shù)最速下降方向決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法v 投影尺度算法? 如何穿過(guò)可行域的內(nèi)部快速達(dá)到最優(yōu)解呢？ Karmarkar發(fā)現(xiàn)： (1)如果一個(gè)內(nèi)點(diǎn)位于可行域 (多胞形、多面體 )的中心，那么目標(biāo)函數(shù)的最速下降方向是比較好的方向；(2)存在一個(gè)適當(dāng)?shù)淖儞Q，能夠?qū)⒖尚杏蛑薪o定的內(nèi)點(diǎn)置于變換后的可行域的中心。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法v 內(nèi)點(diǎn)算法的思想? 已知線性規(guī)劃問(wèn)題的可行域是一個(gè)多面體，最優(yōu)點(diǎn)在多面體的某個(gè)極點(diǎn)取到。v 單純形算法的基本思想? 從某個(gè)極點(diǎn)開(kāi)始獲得一個(gè)可行解；? 判斷該可行解是不是目標(biāo)解。已知第 j種食物中包含第 i種營(yíng)養(yǎng)成分的量為 aij個(gè)單位。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化問(wèn)題分類(lèi)v 整數(shù)規(guī)劃 ：當(dāng)決策變量的取值均為整數(shù)時(shí)稱(chēng)為整數(shù)規(guī)劃；若某些變量取值為整數(shù)，而另一些變量取值為實(shí)數(shù)，則成為混合整數(shù)規(guī)劃。決策理論與方法 (2) —— 優(yōu)化決策理論與方法合肥工業(yè)大學(xué)管理學(xué)院Wednesday, April 07, 2023確定性決策v 確定性決策 ：指未來(lái)狀態(tài)是確定的（即只有一種狀態(tài)）一類(lèi)決策問(wèn)題，每一個(gè)行動(dòng)方案對(duì)應(yīng)著一個(gè)確定的結(jié)果值，此時(shí)決策函數(shù)僅依賴(lài)于決策變量。? 最優(yōu)化問(wèn)題的一般形式為：決策理論與方法 優(yōu)化決策理論與方法優(yōu)化問(wèn)題分類(lèi)v 可行點(diǎn) 與 可行域 ：滿(mǎn)足約束條件的 x稱(chēng)為可行點(diǎn)，所有可行點(diǎn)的集合稱(chēng)為可行域，記為 S；v 約束優(yōu)化 與 無(wú)約束優(yōu)化 ：當(dāng) S?Rn時(shí)，稱(chēng)為約束優(yōu)化；當(dāng) S=Rn時(shí)，稱(chēng)為無(wú)約束優(yōu)化；v 多目標(biāo)優(yōu)化 ：若 f是多個(gè)目標(biāo)函數(shù)構(gòu)成的一個(gè)向量值函數(shù)，則稱(chēng)為多目標(biāo)規(guī)劃；v 線性規(guī)劃 與 非線性規(guī)劃 ：當(dāng) f,g,h均為線性函數(shù)時(shí)稱(chēng)為線性規(guī)劃，否則稱(chēng)為非線性規(guī)劃。人體正?；顒?dòng)過(guò)程中需要 m種基本的營(yíng)養(yǎng)成分，且每人每天至少需要攝入第 i種營(yíng)養(yǎng)成分 bi個(gè)單位。極點(diǎn)向量中，至少有 nm個(gè) 0分量 )處取極值。那么是否存在求解線性規(guī)劃問(wèn)題的多項(xiàng)式時(shí)間算法？v1984年， N. Karmarkar提出了一種 投影尺度算法 ，其計(jì)算效果能夠同單純形法相比較，掀起了線性規(guī)劃 內(nèi)點(diǎn)算法 的熱潮。 N. Karmarkar的 投影尺度算法 就是一種典型的內(nèi)點(diǎn)算法。x≤bAeq2]。 A=[1 1。對(duì)于任意點(diǎn)x*?Rn, 它是函數(shù) f的最小點(diǎn) (或局部極小點(diǎn) )嗎？v 例如： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 復(fù)習(xí)v 梯度向量 vHesse矩陣vTaylor展開(kāi)決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 極小值存在條件v 必要條件 。v 充要條件 。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — 牛頓法v 設(shè) xk是第 k次迭代結(jié)果，記 gk=g(xk)=?f(xk)；Gk=G(xk)=?2f(xk)。k+1→ k。v 基本思想 ：在迭代過(guò)程中只利用目標(biāo)函數(shù) f(x)和梯度 g(x)的信息，構(gòu)造 Hesse矩陣的近似矩陣，由此獲得一個(gè)搜索方向，生產(chǎn)新的迭代點(diǎn)。決策理論與方法 優(yōu)化決策理論與方法無(wú)約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x)f = f(x)。 % Starting guess options = optimset(39。)。mediumscale: QuasiNewton line search‘v fminsearch結(jié)果：? x =[ ]? fval =? iterations: 46? algorithm: 39。v 有約束非線性規(guī)劃問(wèn)題 (COP)是指 f(x),gi(x),hj(x)至少有一個(gè)是非線性的，且 I或 ??至少有一個(gè)為非空。顯然所有 hj(x0)約束均是積極約束。顯然若 d滿(mǎn)足 dT?gi(x)?0， dT?hj(x)=0，