約束優(yōu)化二次規(guī)劃與SQP課件

約束優(yōu)化問題可行域：

特殊問題可行方向法－線性約束問題次梯度優(yōu)化－對(duì)偶問題

一般問題逐步二次規(guī)劃法懲罰函數(shù)法內(nèi)點(diǎn)法(原對(duì)偶內(nèi)點(diǎn)法)－凸規(guī)劃常用方法1約束優(yōu)化問題可行域：特殊問題第10章：約束優(yōu)化：二次規(guī)劃與逐步二次規(guī)劃法

ConstrainedOptimization:QuadraticProgrammingandSQP

2第10章：約束優(yōu)化：二次規(guī)劃與逐步二次規(guī)劃法

Constr解的情況：無(wú)可行解、無(wú)界、有解其中G是n階對(duì)稱方陣，ai,d是n

維常向量有解時(shí)：⊙

G半正定：KKT點(diǎn)即為全局極小點(diǎn)⊙

G正定：有惟一的極小點(diǎn)⊙

G不定：局部解有可能不是全局解，此時(shí)找全局解是NP-難問題G半正定凸二次規(guī)劃3解的情況：無(wú)可行解、無(wú)界、有解其中G是n階對(duì)稱方陣，有價(jià)證券的組合優(yōu)化⊙投資組合：設(shè)對(duì)第i項(xiàng)投資的資金投放比例為xi⊙問題：對(duì)收益與風(fēng)險(xiǎn)的折衷進(jìn)行建模投資集合{1,…,n}，可能收益為ri

假定II所有資金均投資，不允許賣空

假定I

設(shè)

是隨機(jī)變量4有價(jià)證券的組合優(yōu)化⊙投資組合：設(shè)對(duì)第i項(xiàng)投資的資金投放有價(jià)證券的組合優(yōu)化(續(xù))⊙證卷組合：證卷組合的利潤(rùn)：證卷組合的期望收益和方差：G是半正定矩陣！⊙證卷組合優(yōu)化(portfoliooptimization)：5有價(jià)證券的組合優(yōu)化(續(xù))⊙證卷組合：證卷組合的利潤(rùn)：證卷組有價(jià)證券的組合優(yōu)化(續(xù))Markowitz引入風(fēng)險(xiǎn)容許參數(shù)(risktoleranceparameter)找出“最優(yōu)的”證券投資組合！⊙參數(shù)，設(shè)定值依賴于投資者的個(gè)人偏好保守型投資者：大的參數(shù)取值冒險(xiǎn)性投資者：小的參數(shù)取值6有價(jià)證券的組合優(yōu)化(續(xù))Markowitz引入風(fēng)險(xiǎn)容許參數(shù)(

等式約束二次規(guī)劃積極集法逐步二次規(guī)劃法7等式約束二次規(guī)劃7等式約束二次規(guī)劃8等式約束二次規(guī)劃8等式約束二次規(guī)劃其中假定:線性無(wú)關(guān)核心思想：消元法(基本、廣義)其中，A1可逆9等式約束二次規(guī)劃其中假定:代入q(x)等式約束二次規(guī)劃－基本消元法消去x310代入q(x)等式約束二次規(guī)劃－基本消元法消去x310等式約束二次規(guī)劃－基本消元法(續(xù))找A的可逆子矩陣A1，進(jìn)行消元如果正定，解方程組可得惟一解11等式約束二次規(guī)劃－基本消元法(續(xù))找A的可逆子矩陣A1等式約束二次規(guī)劃－廣義消元法令Y和Z分別是n×m與n×(n-m)矩陣，滿足考察方程組ATx=b:Yb是特解；通解x=Yb+s，其中s是齊次線性方程組ATs=0的解任一可行解均可表示為:x=Yb+Zy如果ZTGZ正定，則原問題有惟一解，解方程組12等式約束二次規(guī)劃－廣義消元法令Y和Z分別是n×m等式約束二次規(guī)劃－廣義消元法(續(xù))構(gòu)造Y和Z的正交分解法對(duì)矩陣A進(jìn)行QR分解，即13等式約束二次規(guī)劃－廣義消元法(續(xù))構(gòu)造Y和Z的正交分解等式約束二次規(guī)劃－廣義消元法(續(xù))14等式約束二次規(guī)劃－廣義消元法(續(xù))14實(shí)用二次規(guī)劃算法綜述⊙經(jīng)典積極集法(classicalactive-setmethods)求解凸和非凸二次規(guī)劃問題－－中小規(guī)模(幾百個(gè)變量！)⊙梯度投影法(gradient-projectionmethods)界約束QP(BoxQP)!⊙內(nèi)點(diǎn)法(interior-pointmethods)大規(guī)模凸二次規(guī)劃！15實(shí)用二次規(guī)劃算法綜述⊙經(jīng)典積極集法(classicala積極集法16積極集法16技術(shù)注記：此處用線性約束規(guī)范代替LICQ!故二次規(guī)劃的任一解x*均滿足KKT條件其中G是n階對(duì)稱方陣，ai,d是n

維常向量解的情況：無(wú)可行解、無(wú)界、有解G半正定凸二次規(guī)劃積極集法－問題最優(yōu)積極集！17技術(shù)注記：此處用線性約束規(guī)范代替LICQ!故二次規(guī)劃的任積極集法－算法的動(dòng)機(jī)(motivation)如果提前知道，求解對(duì)最優(yōu)積極集進(jìn)行猜測(cè)，并不斷修正，直到得到正確的！考慮第k次迭代：x(k)是可行點(diǎn)，Wk

是工作集(由等式約束和部分或全部積極不等式約束組成)其中18積極集法－算法的動(dòng)機(jī)(motivation)如果提前知道積極集法－算法的原理◎x(k)不是當(dāng)前等式約束問題的解，即s(k)≠0:⊙x(k)+s(k)滿足其它約束：，工作集保持不變⊙x(k)+s(k)不滿足某些約束，找阻滯約束和步長(zhǎng)：稱取到最小值的指標(biāo)p對(duì)應(yīng)的約束為阻滯(blocking)約束無(wú)阻滯約束時(shí)，工作集不變；否則給工作集添加一個(gè)阻滯約束19積極集法－算法的原理◎x(k)不是當(dāng)前等式約束問題的解，即積極集法－算法的原理(續(xù))⊙乘子中與不等式約束對(duì)應(yīng)的分量非負(fù)：

x(k)是原問題的KKT點(diǎn)，進(jìn)而是全局解◎x(k)是當(dāng)前等式約束問題的解，即s(k)=0：設(shè)當(dāng)前等式約束問題的Lagrange乘子是⊙否則，存在通常取指標(biāo)q滿足：20積極集法－算法的原理(續(xù))⊙乘子中與不等式約束對(duì)應(yīng)的分量積極集法－算例21積極集法－算例21積極集法－算例(續(xù))作業(yè)中用同樣的初始點(diǎn)和不同的初始工作集進(jìn)行迭代求解22積極集法－算例(續(xù))作業(yè)中用同樣的初始點(diǎn)和不同的初始工作集進(jìn)積極集法－算法算法10.2.1求解凸二次規(guī)劃的積極集法23積極集法－算法算法10.2.1求解凸二次規(guī)劃的積極集法23定理10.2.2

假設(shè)s(k)

是關(guān)于增量的等式約束二次規(guī)劃子問題的最優(yōu)解，且滿足該問題的二階充分條件，則p(k)=s(k)

是原目標(biāo)函數(shù)的下降方向.積極集法－理論分析線搜索法、每個(gè)迭代點(diǎn)都可行定理10.2.1

設(shè)x(k)

是等式約束二次規(guī)劃子問題的最優(yōu)解，是對(duì)應(yīng)的乘子.假設(shè)約束的梯度向量線性無(wú)關(guān)，且存在指標(biāo)使得.考慮問題設(shè)該問題的解為s’.則s’是第j個(gè)約束的可行方向，即

.此外，如果s’滿足二階充分條件，則.24定理10.2.2假設(shè)s(k)是關(guān)于增量的等式約束二次規(guī)⊙存在許多技術(shù)確定初始點(diǎn)－－比如人工變量法！⊙在恰當(dāng)?shù)募俣ㄏ驴勺C明－－算法有限步找到解！⊙可以推廣來(lái)求解非凸二次規(guī)劃積極集法－進(jìn)一步說明⊙初試點(diǎn)相同，但初始工作集不同，則后面的迭代不同；即使初始工作集相同，后面的迭代也可能不同⊙迭代次數(shù)有可能超過不等式約束的個(gè)數(shù)⊙選取初試工作集的額外要求：所選約束的梯度線性無(wú)關(guān)25⊙存在許多技術(shù)確定初始點(diǎn)－－比如人工變量法！⊙在恰當(dāng)?shù)募僦鸩蕉我?guī)劃法SuccessiveQuadraticProgrammingMethod26逐步二次規(guī)劃法26假設(shè)和記號(hào)

在設(shè)計(jì)和分析算法時(shí)，通常假設(shè)f(x),ci(x)是連續(xù)可微(二階連續(xù)可微)的，且導(dǎo)數(shù)是李普希茲連續(xù)的！27假設(shè)和記號(hào)在設(shè)計(jì)和分析算法時(shí)，通常假設(shè)f(x等式約束問題－Lagrange-Newton法KKT條件：其中28等式約束問題－Lagrange-Newton法KKT條件：其等式約束問題－Lagrange-Newton法KKT條件：其中設(shè)是近似解，則其牛頓校正滿足29等式約束問題－Lagrange-Newton法KKT條件：其等式約束問題－Lagrange-Newton法(續(xù))令，上述方程組即給定初始點(diǎn)，利用上面兩式進(jìn)行迭代解等式約束問題的－Lagrange-Newton法定理假設(shè)x*是等式約束問題的滿足二階充分條件的局部極小點(diǎn),且rank(A*)=m，是惟一的Lagrange乘子.則當(dāng)充分接近時(shí)，Lagrange-Newton法有定義，且由該方法產(chǎn)生的序列二次收斂到.30等式約束問題－Lagrange-Newton法(續(xù))令基本/局部逐步二次規(guī)劃法考慮二次規(guī)劃問題的解和對(duì)應(yīng)的Lagrange乘子，其中二次規(guī)劃的KKT條件31基本/局部逐步二次規(guī)劃法考慮二次規(guī)劃問題的解和對(duì)應(yīng)的Lagr基本/局部逐步二次規(guī)劃法(續(xù))假設(shè)是等式約束問題的滿足二階充分條件的極小點(diǎn)，即這里Z是A*Ts=0的基礎(chǔ)解系組成的矩陣.則s*=0(x*)是下列問題的惟一最優(yōu)解32基本/局部逐步二次規(guī)劃法(續(xù))假設(shè)基本/局部逐步二次規(guī)劃法(續(xù))算法10.3.1基本SQP法33基本/局部逐步二次規(guī)劃法(續(xù))算法10.3.1基本SQP法基本/局部逐步二次規(guī)劃法(續(xù))例34基本/局部逐步二次規(guī)劃法(續(xù))例34基本/局部逐步二次規(guī)劃法(續(xù))優(yōu)點(diǎn)：局部二階收斂存在問題

⊙初始點(diǎn)不好時(shí)，迭代可能發(fā)散

⊙子問題的解可能不存在－無(wú)界或者不可行

⊙需要二階導(dǎo)數(shù)－W(k)35基本/局部逐步二次規(guī)劃法(續(xù))優(yōu)點(diǎn)：局部二階收斂35實(shí)用逐步二次規(guī)劃法全局化策略：使用線搜索策略或者信賴域策略

⊙評(píng)價(jià)函數(shù)法常用的是l1精確罰函數(shù)，迭代中需更新懲罰因子；

⊙濾子(Filter)法

存在問題：具有Martos效應(yīng)，需要采取校正措施近似二階導(dǎo)數(shù)

⊙用近似矩陣B(k)代替W(k)

⊙用近似矩陣代替既約海森矩陣Z(k)TW(k)Z(k)子問題的求解36實(shí)用逐步二次規(guī)劃法全局化策略：使用線搜索策略或者信賴域策略3約束優(yōu)化問題可行域：

特殊問題可行方向法－線性約束問題次梯度優(yōu)化－對(duì)偶問題

一般問題逐步二次規(guī)劃法懲罰函數(shù)法內(nèi)點(diǎn)法(原對(duì)偶內(nèi)點(diǎn)法)－凸規(guī)劃常用方法37約束優(yōu)化問題可行域：特殊問題第10章：約束優(yōu)化：二次規(guī)劃與逐步二次規(guī)劃法

ConstrainedOptimization:QuadraticProgrammingandSQP

38第10章：約束優(yōu)化：二次規(guī)劃與逐步二次規(guī)劃法

Constr解的情況：無(wú)可行解、無(wú)界、有解其中G是n階對(duì)稱方陣，ai,d是n

維常向量有解時(shí)：⊙

G半正定：KKT點(diǎn)即為全局極小點(diǎn)⊙

G正定：有惟一的極小點(diǎn)⊙

G不定：局部解有可能不是全局解，此時(shí)找全局解是NP-難問題G半正定凸二次規(guī)劃39解的情況：無(wú)可行解、無(wú)界、有解其中G是n階對(duì)稱方陣，有價(jià)證券的組合優(yōu)化⊙投資組合：設(shè)對(duì)第i項(xiàng)投資的資金投放比例為xi⊙問題：對(duì)收益與風(fēng)險(xiǎn)的折衷進(jìn)行建模投資集合{1,…,n}，可能收益為ri

假定II所有資金均投資，不允許賣空

假定I

設(shè)

是隨機(jī)變量40有價(jià)證券的組合優(yōu)化⊙投資組合：設(shè)對(duì)第i項(xiàng)投資的資金投放有價(jià)證券的組合優(yōu)化(續(xù))⊙證卷組合：證卷組合的利潤(rùn)：證卷組合的期望收益和方差：G是半正定矩陣！⊙證卷組合優(yōu)化(portfoliooptimization)：41有價(jià)證券的組合優(yōu)化(續(xù))⊙證卷組合：證卷組合的利潤(rùn)：證卷組有價(jià)證券的組合優(yōu)化(續(xù))Markowitz引入風(fēng)險(xiǎn)容許參數(shù)(risktoleranceparameter)找出“最優(yōu)的”證券投資組合！⊙參數(shù)，設(shè)定值依賴于投資者的個(gè)人偏好保守型投資者：大的參數(shù)取值冒險(xiǎn)性投資者：小的參數(shù)取值42有價(jià)證券的組合優(yōu)化(續(xù))Markowitz引入風(fēng)險(xiǎn)容許參數(shù)(

等式約束二次規(guī)劃積極集法逐步二次規(guī)劃法43等式約束二次規(guī)劃7等式約束二次規(guī)劃44等式約束二次規(guī)劃8等式約束二次規(guī)劃其中假定:線性無(wú)關(guān)核心思想：消元法(基本、廣義)其中，A1可逆45等式約束二次規(guī)劃其中假定:代入q(x)等式約束二次規(guī)劃－基本消元法消去x346代入q(x)等式約束二次規(guī)劃－基本消元法消去x310等式約束二次規(guī)劃－基本消元法(續(xù))找A的可逆子矩陣A1，進(jìn)行消元如果正定，解方程組可得惟一解47等式約束二次規(guī)劃－基本消元法(續(xù))找A的可逆子矩陣A1等式約束二次規(guī)劃－廣義消元法令Y和Z分別是n×m與n×(n-m)矩陣，滿足考察方程組ATx=b:Yb是特解；通解x=Yb+s，其中s是齊次線性方程組ATs=0的解任一可行解均可表示為:x=Yb+Zy如果ZTGZ正定，則原問題有惟一解，解方程組48等式約束二次規(guī)劃－廣義消元法令Y和Z分別是n×m等式約束二次規(guī)劃－廣義消元法(續(xù))構(gòu)造Y和Z的正交分解法對(duì)矩陣A進(jìn)行QR分解，即49等式約束二次規(guī)劃－廣義消元法(續(xù))構(gòu)造Y和Z的正交分解等式約束二次規(guī)劃－廣義消元法(續(xù))50等式約束二次規(guī)劃－廣義消元法(續(xù))14實(shí)用二次規(guī)劃算法綜述⊙經(jīng)典積極集法(classicalactive-setmethods)求解凸和非凸二次規(guī)劃問題－－中小規(guī)模(幾百個(gè)變量！)⊙梯度投影法(gradient-projectionmethods)界約束QP(BoxQP)!⊙內(nèi)點(diǎn)法(interior-pointmethods)大規(guī)模凸二次規(guī)劃！51實(shí)用二次規(guī)劃算法綜述⊙經(jīng)典積極集法(classicala積極集法52積極集法16技術(shù)注記：此處用線性約束規(guī)范代替LICQ!故二次規(guī)劃的任一解x*均滿足KKT條件其中G是n階對(duì)稱方陣，ai,d是n

維常向量解的情況：無(wú)可行解、無(wú)界、有解G半正定凸二次規(guī)劃積極集法－問題最優(yōu)積極集！53技術(shù)注記：此處用線性約束規(guī)范代替LICQ!故二次規(guī)劃的任積極集法－算法的動(dòng)機(jī)(motivation)如果提前知道，求解對(duì)最優(yōu)積極集進(jìn)行猜測(cè)，并不斷修正，直到得到正確的！考慮第k次迭代：x(k)是可行點(diǎn)，Wk

是工作集(由等式約束和部分或全部積極不等式約束組成)其中54積極集法－算法的動(dòng)機(jī)(motivation)如果提前知道積極集法－算法的原理◎x(k)不是當(dāng)前等式約束問題的解，即s(k)≠0:⊙x(k)+s(k)滿足其它約束：，工作集保持不變⊙x(k)+s(k)不滿足某些約束，找阻滯約束和步長(zhǎng)：稱取到最小值的指標(biāo)p對(duì)應(yīng)的約束為阻滯(blocking)約束無(wú)阻滯約束時(shí)，工作集不變；否則給工作集添加一個(gè)阻滯約束55積極集法－算法的原理◎x(k)不是當(dāng)前等式約束問題的解，即積極集法－算法的原理(續(xù))⊙乘子中與不等式約束對(duì)應(yīng)的分量非負(fù)：

x(k)是原問題的KKT點(diǎn)，進(jìn)而是全局解◎x(k)是當(dāng)前等式約束問題的解，即s(k)=0：設(shè)當(dāng)前等式約束問題的Lagrange乘子是⊙否則，存在通常取指標(biāo)q滿足：56積極集法－算法的原理(續(xù))⊙乘子中與不等式約束對(duì)應(yīng)的分量積極集法－算例57積極集法－算例21積極集法－算例(續(xù))作業(yè)中用同樣的初始點(diǎn)和不同的初始工作集進(jìn)行迭代求解58積極集法－算例(續(xù))作業(yè)中用同樣的初始點(diǎn)和不同的初始工作集進(jìn)積極集法－算法算法10.2.1求解凸二次規(guī)劃的積極集法59積極集法－算法算法10.2.1求解凸二次規(guī)劃的積極集法23定理10.2.2

假設(shè)s(k)

是關(guān)于增量的等式約束二次規(guī)劃子問題的最優(yōu)解，且滿足該問題的二階充分條件，則p(k)=s(k)

是原目標(biāo)函數(shù)的下降方向.積極集法－理論分析線搜索法、每個(gè)迭代點(diǎn)都可行定理10.2.1

設(shè)x(k)

是等式約束二次規(guī)劃子問題的最優(yōu)解，是對(duì)應(yīng)的乘子.假設(shè)約束的梯度向量線性無(wú)關(guān)，且存在指標(biāo)使得.考慮問題設(shè)該問題的解為s’.則s’是第j個(gè)約束的可行方向，即

.此外，如果s’滿足二階充分條件，則.60定理10.2.2假設(shè)s(k)是關(guān)于增量的等式約束二次規(guī)⊙存在許多技術(shù)確定初始點(diǎn)－－比如人工變量法！⊙在恰當(dāng)?shù)募俣ㄏ驴勺C明－－算法有限步找到解！⊙可以推廣來(lái)求解非凸二次規(guī)劃積極集法－進(jìn)一步說明⊙初試點(diǎn)相同，但初始工作集不同，則后面的迭代不同；即使初始工作集相同，后面的迭代也可能不同⊙迭代次數(shù)有可能超過不等式約束的個(gè)數(shù)⊙選取初試工作集的額外要求：所選約束的梯度線性無(wú)關(guān)61⊙存在許多技術(shù)確定初始點(diǎn)－－比如人工變量法！⊙在恰當(dāng)?shù)募僦鸩蕉我?guī)劃法SuccessiveQuadraticProgrammingMethod62逐步二次規(guī)劃法26假設(shè)和記號(hào)

在設(shè)計(jì)和分析算法時(shí)，通常假設(shè)f(x),ci(x)是連續(xù)可微(二階連續(xù)可微)的，且導(dǎo)數(shù)是李普希茲連續(xù)的！63假設(shè)和記號(hào)在設(shè)計(jì)和分析算法時(shí)，通常假設(shè)f(x等式約束問題－Lagrange-Newton法KKT條件：其中64等式約束問題－Lagrange-Newton法KKT條件：其等式約束問題－Lagrange-Newton法KKT條件：其中設(shè)是近似解，則其牛頓校正滿足65等式約束問題－Lagrange-Newton法KKT條件：其等式約束問題－Lagrange-Newton法(續(xù))令，上述方程組即給定初始點(diǎn)，利用上面兩式進(jìn)行迭代解等式約