【文章內(nèi)容簡(jiǎn)介】 線性約束（稱為線性約束的優(yōu)化問題， LCO）。v 可行方向法的基本思想 ：當(dāng)某個(gè)可行方向同時(shí)也是目標(biāo)函數(shù)的下降方向時(shí)，沿此方向移動(dòng)一定會(huì)在滿足可行性的情況下改進(jìn)迭代點(diǎn)的目標(biāo)函數(shù)值。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法x1x2決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法v LCO問題： Min f(x) . aiTx?bi, i?I ajTx=bj, j??v 設(shè) x0是 LCO的一個(gè)可行解，若 d是可行域在 x0點(diǎn)的 可行方向 ，則 d滿足 AI(x0)d?0(I(x0)={i|aiTx0=bi,i?I})，A?d=0。v 設(shè) x0是 LCO的一個(gè)可行解，若 d是可行域在 x0點(diǎn)的 下降方向 ，則 d滿足 dT?f(x0)0。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 可行方向法vZoutendijk可行方向法：其核心思想是通過求解下列線性規(guī)劃問題，在可行方向的某個(gè)范圍內(nèi)獲得目標(biāo)函數(shù)的最速下降方向。Min dT?f(x0). AI(x0)d?0, I(x0)={i|aiTx0=bi,i?I} A?d=0 ||d||∞?1v 可以證明：當(dāng) x0取得 KKT點(diǎn)時(shí)當(dāng)且僅當(dāng) dT?f(x0)的最優(yōu)值為零。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 求解約束優(yōu)化的一類重要方法是用一個(gè)無約束優(yōu)化問題的序列 逼近 約束優(yōu)化問題，通過無約束優(yōu)化問題的最優(yōu)解序列逼近約束優(yōu)化問題的最優(yōu)解。v 基本思想： 將約束條件通過某種轉(zhuǎn)換與目標(biāo)函數(shù)合并形成一個(gè)無約束優(yōu)化問題。這種轉(zhuǎn)換隱含著某種懲罰，即 x偏離約束條件越遠(yuǎn)，受到的懲罰越大。因此也將此類方法稱為 罰函數(shù)法 ，所形成的無約束優(yōu)化函數(shù)成為 罰函數(shù) 。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 二次罰函數(shù)法 ：? 罰函數(shù)：? 其中 (gi)=max{0,gi}， ?稱為罰參數(shù)，且當(dāng) ?→0 時(shí)， Q(x,?)的極小值趨于 f(x)的極小值。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 例 ： min f=x1+x2 . x1x22=0v 解：對(duì)于 ?0，定義二次罰函數(shù)Min Q(x,?)=x1+x2+(2?)1(x1x22)2Q’x1=1+(x1x22)/?=0Q’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決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 對(duì)數(shù)障礙函數(shù)法 ：? 障礙函數(shù)：? 其中 ?稱為障礙參數(shù)，且當(dāng) ?→0 時(shí)， P(x,?)的極小值趨于f(x)的極小值。? 該方法的適用性： COP問題僅包含不等式約束函數(shù)，且可行域存在內(nèi)點(diǎn)。即 S0={x|g(x)0}≠?決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 例 ： min{f=x/2|x?1}v 解：構(gòu)造對(duì)數(shù)障礙函數(shù) P(x,?)=x/2?ln(x1)? P’x=1/2?/(x1)=0，得 x?*=1+2?， P*=1/2+??ln2?? 當(dāng) ?→0 時(shí)得 x*=1， f*=1/2決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 標(biāo)準(zhǔn)型v 若有約束非線性規(guī)劃的目標(biāo)函數(shù)是決策變量 x的二次函數(shù)且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃 (Quadratic Programming, QP)問題。其標(biāo)準(zhǔn)型為：決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 標(biāo)準(zhǔn)型v 其中 Q=QT?Rnn（ n階對(duì)稱方陣）；以 aiT(i?I)為行向量的矩陣記為 AI?RIn；以 ajT(j??)為行向量的矩陣記為 A??R?n；對(duì)應(yīng)的向量記為 bI, b?。若目標(biāo)函數(shù)的 Hesse矩陣 Q是半正定 (或正定 )的，則 QP問題為 (嚴(yán)格 )凸二次規(guī)劃 (CQP)。我們僅討論凸二次規(guī)劃問題，因?yàn)榉峭苟我?guī)劃的 Q存在負(fù)特征根，求解很困難。決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 極小點(diǎn)存在條件v 充要條件? 可行點(diǎn) x*是 QP問題的局部極小點(diǎn)當(dāng)且僅當(dāng) x*為一個(gè) KKT點(diǎn)且對(duì)于任意非零可行方向 d，有 dTQd?0。? 對(duì)于凸二次規(guī)劃， x*為全局極小點(diǎn)當(dāng)且僅當(dāng) x*為局部極小點(diǎn)，當(dāng)且僅當(dāng) x*為 KKT點(diǎn)。? 二次規(guī)劃的 KKT定理形式為：Qx*+c=AIT?*+A?T?*(AIx*bI)?*=0v 二次規(guī)劃的求解本質(zhì)上就是求解上述 KKT方程。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 對(duì)于非線性約束優(yōu)化 (COP)問題，v 若 x*是 COP問題的一個(gè)局部最優(yōu)解，則它對(duì)應(yīng)一個(gè)純等式約束優(yōu)化問題決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 因此如果事先知道積極約束指標(biāo)集，那么帶有不等式約束優(yōu)化問題就可以轉(zhuǎn)化為純等式約束優(yōu)化問題，并可用準(zhǔn)牛頓法求解，這就是逐次二次規(guī)劃(Sequential Quadratic Programming， SQP)法。v 基本思想 ：在迭代點(diǎn)處構(gòu)造一個(gè)二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個(gè)改進(jìn)迭代點(diǎn)；不斷重復(fù)此過程，直到求出滿足一定要求的迭代點(diǎn)。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 對(duì)于等式約束優(yōu)化問題Min f(x). h(x)=0v 拉格朗日函數(shù)記為 L(x,?)=f(x)?Th(x)v 則 ?L(x,?)=(?f(x)?h(x)?, h(x))T=0，顯然問題的最優(yōu)解(x*,?*)滿足此式。v 設(shè) (xk,?k)是第 k次迭代結(jié)果，根據(jù)牛頓法，有：決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 上述迭代過程等價(jià)于如下的二次規(guī)劃的迭代。設(shè)給定迭代點(diǎn)(xk,?k)，則決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f(x). c(x)?0 ceq(x)=0 Ax?b Aeqx=beq lb?x?ubv [x,fval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)v fun定義目標(biāo)函數(shù) ,x0定義初始可行解， nonlcon定義 c(x)和ceq(x)。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 用法? 創(chuàng)建一個(gè) matlab文件，如 function f = myfun(x)f = f(x)。? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x)c = c(x)。 ceq = ceq(x)。? 調(diào)用 fmincon并指定初始搜索點(diǎn)以及其他向量、矩陣。x0=[x1,x2,…,xn]。A。b。Aeq。beq。lb。ub。[x,fval]=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,confun)決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v 例 ： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1) . x1x2x1x2? x1x2?10v 解 ：? 創(chuàng)建一個(gè) 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)。? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x)c = [ + x(1)*x(2) x(1) x(2)。 x(1)*x(2) 10]。ceq = []。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用? 調(diào)用有約束非線性規(guī)劃函數(shù)x0 = [1,1]。 % Starting guessoptions = optimset(39。LargeScale39。,39。off39。)。[x,fval]=fmincon(objfun,x0,[],[],[],[],[],[],confun,options)? 運(yùn)行結(jié)果 ：x =[ ]fval =iterations: 8algo