【正文】 復(fù)此過程，直到求出滿足一定要求的迭代點(diǎn)。 ? 二次規(guī)劃的 KKT定理形式為： Qx*+c=AIT?*+A?T?* (AIx*bI)?*=0 ?二次規(guī)劃的求解本質(zhì)上就是求解上述 KKT方程。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — 極小點(diǎn)存在條件 ?充要條件 ? 可行點(diǎn) x*是 QP問題的局部極小點(diǎn)當(dāng)且僅當(dāng) x*為一個 KKT點(diǎn)且對于任意非零可行方向 d，有 dTQd?0。若目標(biāo)函數(shù)的 Hesse矩陣 Q是半正定 (或正定 )的，則 QP問題為(嚴(yán)格 )凸二次規(guī)劃 (CQP)。即 S0={x|g(x)0}≠? ????Iii xgxfxP )(ln)(),( ??2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?例 ： min{f=x/2|x?1} ?解：構(gòu)造對數(shù)障礙函數(shù) P(x,?)=x/2?ln(x1) ? P’x=1/2?/(x1)=0，得 x?*=1+2?， P*=1/2+??ln2? ? 當(dāng) ?→ 0時得 x*=1， f*=1/2 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 — 標(biāo)準(zhǔn)型 ?若有約束非線性規(guī)劃的目標(biāo)函數(shù)是決策變量 x的二次函數(shù)且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃 (Quadratic Programming, QP)問題。 )(2 1)())((2 1)(),(||12||12 xQxfhgxfxQjjIii ????????? ?????)(m i n)),((m i nl i m 0 xfxQ ?? ??2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?例 ： min f=x1+x2 . x1x22=0 ?解：對于 ?0，定義二次罰函數(shù) Min Q(x,?)=x1+x2+(2?)1(x1x22)2 Q’x1=1+(x1x22)/?=0 Q’x2=12x2(x1x22)/?=0 解得： x?*=(1/4?,1/2)T, Q*=1/4?/2 當(dāng) ?→ 0時得， x*=(1/4,1/2)T, f*=1/4 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?對數(shù)障礙函數(shù)法 ： ? 障礙函數(shù)： ? 其中 ?稱為障礙參數(shù)，且當(dāng) ?→ 0時， P(x,?)的極小值趨于f(x)的極小值。因此也將此類方法稱為 罰函數(shù)法 ，所形成的無約束優(yōu)化函數(shù)成為 罰函數(shù) 。 ?基本思想： 將約束條件通過某種轉(zhuǎn)換與目標(biāo)函數(shù)合并形成一個無約束優(yōu)化問題。 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)時當(dāng)且僅當(dāng) dT?f(x0)的最優(yōu)值為零。 ?設(shè) x0是 LCO的一個可行解，若 d是可行域在 x0點(diǎn)的 下降方向 ，則 d滿足 dT?f(x0)0。 ?可行方向法的基本思想 ：當(dāng)某個可行方向同時也是目標(biāo)函數(shù)的下降方向時，沿此方向移動一定會在滿足可行性的情況下改進(jìn)迭代點(diǎn)的目標(biāo)函數(shù)值。下面介紹幾種約束優(yōu)化的求解方法：可行方向法、序列無約束化法和 SQP法。 ? 根據(jù)凸規(guī)劃充分條件知 x*為全局最小點(diǎn)。g3(x)=x2?0 ?f(x)=[2x1,2x2]T,?g1(x)=[1,1]T,?g2(x)=[1,0]T,?g3(x)=[0,1]T,得到： ? 2x1=?1+?2 ? 2x2=?1+?3 又 (x1+x24)?1=0； x1?2=0； x2?3=0； ?i?0 ? 若 ?1=0，則 x1=x2=0，與題意不符； ? 若 ?10，則 x1+x24=0， x10, x20。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ? 例： min f(x)=x12+x22 . x1+x2?4 x1,x2?0 ? 解： g1(x)=x1+x24?0。 ? 二階充分條件 ? 設(shè) x*是 COP問題的 KKT點(diǎn)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ? 二階必要條件 ? 設(shè) x*是 COP問題的局部極小點(diǎn)且滿足 KKT條件。 ? (凸規(guī)劃問題 )設(shè) f(x)為凸函數(shù)， gi(x)為凹函數(shù)， hj(x)為線性函數(shù)。 f(x*+?d)=f(x*)+?(?f(x*))Td+o(?) ? 代數(shù)特征 (KKT定理 )： 若 x*是 COP問題的局部極小點(diǎn)且函數(shù) f(x), gi(x), hj(x)在 x*處可微，則存在實(shí)數(shù) ?i?0(i?I), ?j?R(j??)，使得： ?f(x*)=?i?gi(x*)?i+?j?hj(x*)?j； gi(x*)?i=0； ?i?0， ?i?I ? 若 x*滿足 KKT條件，則稱 x*為 COP問題的一個 KKT點(diǎn)，?i, ?j稱為 x*處的拉格朗日乘子。 x1 x2 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ?一階必要條件 ? 幾何特征 ：若 x*是 COP問題的局部極小點(diǎn)且函數(shù) f(x), gi(x), hj(x)在 x*處可微，則 dT?f(x*)?0。若 x0的某一方向 d既是可行方向又是下降方向則稱其為可行下降方向。由 f(x0+?d)=f(x0)+?(?f(x0))Td+o(?)可知：若 d滿足dT?f(x0)0，有 f(x0+?d)f(x0)，則 d一定是下降方向。 ? 下降方向 。顯然若 d滿足 dT?gi(x)?0， dT?hj(x)=0，則 d一定是可行方向。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 幾個概念 ? 可行方向 。顯然所有 hj(x0)約束均是積極約束。對于 gi(x0)?0，或者等號成立，或者大于號成立。 ?有約束非線性規(guī)劃問題 (COP)是指 f(x),gi(x),hj(x)至少有一個是非線性的，且 I或 ??至少有一個為非空。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 標(biāo)準(zhǔn)型 ?其中 f(x)是目標(biāo)函數(shù)， gi(x)和 hj(x)為約束函數(shù) (約束條件 )。mediumscale: QuasiNewton line search‘ ? fminsearch結(jié)果： ? x =[ ] ? fval = ? iterations: 46 ? algorithm: 39。 或者 [x,fval] = fminsearch(myfun,x0,options)。)。,39。 % Starting guess options = optimset(39。 x0=[x1,x2,…,xn] [x,fval] = fminunc(myfun,x0) 或 [x,fval] = fminsearch(myfun,x0) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ?例 ： min f(x)=ex1(4x12+2x22+4x1x2+2x2+1) ?解 ： ? 創(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)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ?用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f = f(x)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用 ? Optimization ToolBox Min f(x) ? Matlab提供了兩個求解無約束非線性規(guī)劃的函數(shù) ? [x,fval] = fminunc(fun,x0) ? [x,fval] = fminsearch(fun,x0) ?用法相似，算法內(nèi)部的搜索策略不同。 ?基本思想 ：在迭代過程中只利用目標(biāo)函數(shù) f(x)和梯度 g(x)的信息，構(gòu)造 Hesse矩陣的近似矩陣，由此獲得一個搜索方向，生產(chǎn)新的迭代點(diǎn)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — 準(zhǔn)牛頓法 ?牛頓法算法的優(yōu)點(diǎn)是收斂速度快 (利用了 Hesse矩陣 )。k+1→k 。 ? 收斂性檢驗(yàn) ：計(jì)算 g(xk)，若 ||g(xk)||≤e，則算法終止；否則計(jì)算 G(xk)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — 牛頓法 ?設(shè) xk是第 k次迭代結(jié)果，記 gk=g(xk)=?f(xk)；Gk=G(xk)=?2f(xk)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — 復(fù)習(xí) ? 梯度矩陣 ????????????????????????????nxfxfxfxf?21)(??????????????????????????????????????????????22221222222122122122122)(nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxf??????? Hesse矩陣 ? Taylor展開 ),(||