【正文】 : ‘mediumscale: activeset(積極約束集方法 )39。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Pareto最優(yōu)解 ?設(shè) x*是可行域 S上的一個(gè)點(diǎn)，對(duì)于 ?x?S，均有：fi(x*)?fi(x)(i=1,…, p)，稱 x*為 MOP問(wèn)題的絕對(duì)最優(yōu)解；若不存在 x?S，使得 fi(x)?fi(x*)(或 fi(x)fi(x*)) (i=1,…, p)，則稱 x*為 MOP問(wèn)題的有效解 (或弱有效解 )。 關(guān)鍵問(wèn)題在于 ：保證最后一個(gè)單目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解是 MOP問(wèn)題的有效解或弱有效解。Aeq。A。minimax SQP, QuasiNewton, line_search‘ 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 解 (2)：用 fgoalattain求解。 ? 解 ： as=(1 1 0 0 0)T； at=(0 0 0 1 1)T。x?b Aeq aij=1(vi為 ej的起點(diǎn) )； aij=1(vi為 ej的終點(diǎn) )； aij=0(其他情形 )。 ? 無(wú)約束。f(p)=f p(x) ? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x) c = c(x)。 ? 調(diào)用 fminimax并指定初始搜索點(diǎn)以及其他向量、矩陣。j?? fk(x)?uk, k=2,…, p ? uk為專家經(jīng)驗(yàn)值。,1(0),1(),1(..m i n111 11 1njmixnjbxmiaxtsxcxdijmijijnjiijminjijijminjijij?????????????????????????? ?? ???? ?? ?2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — 標(biāo)準(zhǔn)型 ?多目標(biāo)規(guī)劃 (multiObjective Programming,MOP)就是指在決策變量滿足給定約束的條件下研究多個(gè)可數(shù)值化的目標(biāo)函數(shù)同時(shí)極小化 (或極大化 )的問(wèn)題。beq=[]。beq。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 調(diào)用有約束非線性規(guī)劃函數(shù) x0 = [1,1]。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)。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無(wú)約束化法 ?二次罰函數(shù)法 ： ? 罰函數(shù)： ? 其中 (gi)=max{0,gi}， ?稱為罰參數(shù)，且當(dāng) ?→ 0時(shí)， Q(x,?)的極小值趨于 f(x)的極小值。g2(x)=x1?0。 設(shè) x0?S，對(duì)某一方向 d來(lái)說(shuō)，若 ???00使得對(duì)于任意 ??[0,?0]，均有 f(x0+?d)f(x0)，則稱 d為 x0點(diǎn)的一個(gè)下降方向。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 無(wú)約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? fminunc結(jié)果： ? x =[ ] ? fval = ? iterations: 8 ? algorithm: 39。但使用 Hesse矩陣的不足之處是計(jì)算量大，Hesse矩陣可能非正定等，準(zhǔn)牛頓法 (QuasiNewton method)是對(duì)牛頓法的改進(jìn)，目前被公認(rèn)為是比較有效的無(wú)約束優(yōu)化方法。 x?Rn ?其中 f： Rn→R 是一個(gè)非線性連續(xù)函數(shù)。 ? 內(nèi)點(diǎn)算法的思想是從可行域內(nèi)的任意一點(diǎn) (任一可行解 )出發(fā)，穿越可行域的內(nèi)部達(dá)到最優(yōu)解。 ? 最優(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ī)劃。極點(diǎn)向量中，至少有nm個(gè) 0分量 )處取極值。2]。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 無(wú)約束非線性規(guī)劃 — 牛頓法 ?設(shè) xk是第 k次迭代結(jié)果，記 gk=g(xk)=?f(xk)；Gk=G(xk)=?2f(xk)。 % Starting guess options = optimset(39。顯然所有 hj(x0)約束均是積極約束。 ? (凸規(guī)劃問(wèn)題 )設(shè) f(x)為凸函數(shù)， gi(x)為凹函數(shù)， hj(x)為線性函數(shù)。 ?設(shè) x0是 LCO的一個(gè)可行解，若 d是可行域在 x0點(diǎn)的 下降方向 ，則 d滿足 dT?f(x0)0。 ? 二次規(guī)劃的 KKT定理形式為： Qx*+c=AIT?*+A?T?* (AIx*bI)?*=0 ?二次規(guī)劃的求解本質(zhì)上就是求解上述 KKT方程。beq。x?b Aeq2 1]。第 i個(gè)倉(cāng)庫(kù)到第 j個(gè)銷售網(wǎng)點(diǎn)的距離為 dij，單位物資的運(yùn)費(fèi)為 cij。 ?基于一個(gè)單目標(biāo)問(wèn)題的方法 ：將原來(lái)的多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化成一個(gè)單目標(biāo)優(yōu)化問(wèn)題，然后利用非線性優(yōu)化算法求解該單目標(biāo)問(wèn)題，所得解作為 MOP問(wèn)題的最優(yōu)解。x?b Aeq??goal c(x)?0 ceq(x)=0 Aub。 ? 給定一個(gè)有限集 N={1,2,…,n} 和權(quán)函數(shù) c:N→R 。 ?線性混合整數(shù)規(guī)劃 (MILP)： max {cTx+hTy|Ax+Gy?b, x?Z+n, y?R+p} ? x,y為決策變量向量，其中 x包含 n個(gè)整數(shù)變量， y包含 p個(gè)實(shí)數(shù)變量； c為 n維向量； h為 p維向量； A為 m n階矩陣，G為 m p階矩陣。 ?整數(shù)規(guī)劃問(wèn)題的可行解一定是松弛問(wèn)題的可行解，但反之不一定。 ? 已經(jīng)證明：求解組合優(yōu)化問(wèn)題的最優(yōu)解是 NP難的。weight [x,fval]=fgoalattain(myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,confun) 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ?例： min {f1,f2,f3,f4,f5} f(1)= 2*x(1)^2+x(2)^248*x(1)40*x(2)+304。x=beq lb?x?ub ? [x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) ? Fun定義目標(biāo)函數(shù)； goal為理想點(diǎn)； x0定義初始可行解；nonlcon定義 c(x)和 ceq(x)。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用 ? 用法 ? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x) f(1) = f1(x)。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — 求解方法 ?線性加權(quán)和法 ： Min ?Tf(x)=?k?kfk(x)， . gi(x)?0。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 — 管理實(shí)例 ?決策目標(biāo)： ? 運(yùn)輸速度最快，可用噸公里數(shù)（ 可觀測(cè)變量 ）最小描述。2。 ? 調(diào)用 quadprog并根據(jù)需要指定初始搜索點(diǎn)以及其他向量、矩陣。ub。 ?基本思想 ：在迭代點(diǎn)處構(gòu)造一個(gè)二次規(guī)劃子問(wèn)題，近似原來(lái)的約束優(yōu)化問(wèn)題；然后通過(guò)求解該二次規(guī)劃子問(wèn)題獲得約束優(yōu)化問(wèn)題的一個(gè)改進(jìn)迭代點(diǎn)；不斷重復(fù)此過(guò)程，直到求出滿足一定要求的迭代點(diǎn)。 Min dT?f(x0) . AI(x0)d?0, I(x0)={i|aiTx0=bi,i?I} A?d=0 ||d||∞?1 ?可以證明：當(dāng) x0取得 KKT點(diǎn)時(shí)當(dāng)且僅當(dāng) dT?f(x0)的最優(yōu)值為零。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ? 二階必要條件 ? 設(shè) x*是 COP問(wèn)題的局部極小點(diǎn)且滿足 KKT條件。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 幾個(gè)概念 ? 可行方向 。,39。 ? 收斂性檢驗(yàn) ：計(jì)算 g(xk)，若 ||g(xk)||≤e，則算法終止；否則計(jì)算 G(xk)。60]。若是，算法結(jié)束；否則尋找下一個(gè)極點(diǎn)（確定 入基變量 和 出基變量 ），直至找到目標(biāo)解。 ?特點(diǎn) ：狀態(tài)是確定的；決策問(wèn)題變?yōu)閮?yōu)化問(wèn)題。 2021年 6月 15日 1時(shí) 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 內(nèi)點(diǎn)算法 ?內(nèi)點(diǎn)算法的思想 ? 已知線性規(guī)劃問(wèn)題的可行域是一個(gè)多面體，最優(yōu)點(diǎn)在多面體的某個(gè)極點(diǎn)取到。2 1] [x, fval] = linprog(f,A,b,[],[],lb) x=[0。返回收斂性檢驗(yàn)。 [x,fval] = fminunc(myfun,x0,options)。（可用一階 Taylor公式分析）。 ?*,?*分別為對(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)。這種轉(zhuǎn)換隱含著某種懲罰，即 x偏離約束條件越遠(yuǎn)，受到的懲罰越大。設(shè)給定迭代點(diǎn)(xk,?k)，則 0)()(..,)(),(21m