【正文】 。如果近似誤差比較大，那么可在近似最小點(diǎn)附近重新構(gòu)造 f(x)的二階 Taylor多項式 (迭代 )，據(jù)此尋找新的近似最小點(diǎn)，重復(fù)以上過程直到求得滿足一定精度要求的迭代點(diǎn)。但使用 Hesse矩陣的不足之處是計算量大，Hesse矩陣可能非正定等，準(zhǔn)牛頓法 (QuasiNewton method)是對牛頓法的改進(jìn)，目前被公認(rèn)為是比較有效的無約束優(yōu)化方法。 ? 調(diào)用無約束非線性規(guī)劃函數(shù) x0 = [1,1]。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? fminunc結(jié)果： ? x =[ ] ? fval = ? iterations: 8 ? algorithm: 39。稱等號成立的約束為積極約束 (有效約束 )，此時， x0處于該約束條件形成的可行域邊界上；稱大于號成立的約束為非積極(inactive)約束 (無效約束 )，此時， x0不在該約束條件形成的可行域邊界上。 設(shè) x0?S，對某一方向 d來說，若 ???00使得對于任意 ??[0,?0]，均有 f(x0+?d)f(x0)，則稱 d為 x0點(diǎn)的一個下降方向。 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問題的一個嚴(yán)格局部極小點(diǎn)。g2(x)=x1?0。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 可行方向法 x1 x2 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 可行方向法 ? LCO問題： Min f(x) . aiTx?bi, i?I ajTx=bj, j?? ?設(shè) x0是 LCO的一個可行解，若 d是可行域在 x0點(diǎn)的 可行方向 ，則 d滿足 AI(x0)d?0(I(x0)={i|aiTx0=bi,i?I})，A?d=0。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?二次罰函數(shù)法 ： ? 罰函數(shù)： ? 其中 (gi)=max{0,gi}， ?稱為罰參數(shù)，且當(dāng) ?→ 0時， Q(x,?)的極小值趨于 f(x)的極小值。 ? 對于凸二次規(guī)劃， x*為全局極小點(diǎn)當(dāng)且僅當(dāng) x*為局部極小點(diǎn)，當(dāng)且僅當(dāng) x*為 KKT點(diǎn)。x=beq lb?x?ub ? [x,fval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) ? fun定義目標(biāo)函數(shù) ,x0定義初始可行解， nonlcon定義 c(x)和ceq(x)。Aeq。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 調(diào)用有約束非線性規(guī)劃函數(shù) x0 = [1,1]。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min +fTx . Abeq。1 2。beq=[]。 ? 解 ：設(shè)共有 m個倉庫，第 i個倉庫的物資庫存量為 ai噸；有 n個銷售網(wǎng)點(diǎn)，第 j個銷售網(wǎng)點(diǎn)的銷售量為 bj噸。,1(0),1(),1(..m i n111 11 1njmixnjbxmiaxtsxcxdijmijijnjiijminjijijminjijij?????????????????????????? ?? ???? ?? ?2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — 標(biāo)準(zhǔn)型 ?多目標(biāo)規(guī)劃 (multiObjective Programming,MOP)就是指在決策變量滿足給定約束的條件下研究多個可數(shù)值化的目標(biāo)函數(shù)同時極小化 (或極大化 )的問題。下面介紹多目標(biāo)規(guī)劃問題的間接解法，基本思路都是將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為一個或多個單目標(biāo)優(yōu)化問題。j?? fk(x)?uk, k=2,…, p ? uk為專家經(jīng)驗值。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min max {fi(x)} . c(x)?0 ceq(x)=0 A ? 調(diào)用 fminimax并指定初始搜索點(diǎn)以及其他向量、矩陣。 [x,fval]=fminimax(myfun,x0,A,b,Aeq,beq,lb,ub,confun) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Minx,? ? . F(x)weightf(p)=f p(x) ? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x) c = c(x)。lb。 ? 無約束。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 非線性規(guī)劃（約束和非約束） 多目標(biāo)規(guī)劃 組合優(yōu)化與整數(shù)規(guī)劃 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 組合優(yōu)化 — 基本概念 ? 組合優(yōu)化問題 是指從一個有限的可行解集中尋找使某個性能函數(shù)取極值的最優(yōu)解。 aij=1(vi為 ej的起點(diǎn) )； aij=1(vi為 ej的終點(diǎn) )； aij=0(其他情形 )。線性 (混合 )整數(shù)規(guī)劃問題 是指在等式或不等式的線性約束下，極大化 (或極小化 )某個線性函數(shù)，其中要求某些變量必須取整數(shù)。x?b Aeq所以整數(shù)規(guī)劃問題的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解。 ? 解 ： as=(1 1 0 0 0)T； at=(0 0 0 1 1)T。設(shè)計各類 貪婪算法 是求解組合優(yōu)化問題常用的思路。minimax SQP, QuasiNewton, line_search‘ 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 解 (2)：用 fgoalattain求解。 f(2)= x(1)^2 3*x(2)^2。A。 weight為各目標(biāo)的權(quán)重向量。Aeq。f(2)=f2(x)。 關(guān)鍵問題在于 ：保證最后一個單目標(biāo)優(yōu)化問題的最優(yōu)解是 MOP問題的有效解或弱有效解。i?I hj(x)=0。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Pareto最優(yōu)解 ?設(shè) x*是可行域 S上的一個點(diǎn)，對于 ?x?S，均有：fi(x*)?fi(x)(i=1,…, p)，稱 x*為 MOP問題的絕對最優(yōu)解；若不存在 x?S，使得 fi(x)?fi(x*)(或 fi(x)fi(x*)) (i=1,…, p)，則稱 x*為 MOP問題的有效解 (或弱有效解 )?？倗嵐飻?shù)為 ?i?jdijxij； ? 運(yùn)輸費(fèi)用最小。] fval = iterations: 3 algorithm: ‘mediumscale: activeset(積極約束集方法 )39。3]。1 2], f=[2。 x0=[x1,x2,…,xn]。off39。 [x,fval]=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,confun) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 例 ： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1) . x1x2x1x2? x1x2?10 ? 解 ： ? 創(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)用 fmincon并指定初始搜索點(diǎn)以及其他向量、矩陣。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — SQP法 ? 對于等式約束優(yōu)化問題 Min f(x) . h(x)=0 ? 拉格朗日函數(shù)記為 L(x,?)=f(x)?Th(x) ? 則 ?L(x,?)=(?f(x)?h(x)?, h(x))T=0，顯然問題的最優(yōu)解(x*,?*)滿足此式。其標(biāo)準(zhǔn)型為： ????????jbxaIibxatsxcQxxxfQPjTjiTiTTRxn,..21)(m i n)(2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — 標(biāo)準(zhǔn)型 ?其中 Q=QT?Rn n（ n階對稱方陣）；以 aiT(i?I)為行向量的矩陣記為 AI?RI n；以 ajT(j??)為行向量的矩陣記為 A??R? n；對應(yīng)的向量記為 bI, b?。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?求解約束優(yōu)化的一類重要方法是用一個無約束優(yōu)化問題的序列逼近約束優(yōu)化問題，通過無約束優(yōu)化問題的最優(yōu)解序列逼近約束優(yōu)化問題的最優(yōu)解。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 可行方向法 ?上面例題介紹了通過求解 KKT方程獲得問題解的方法，但 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