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