最優(yōu)化模型與算法-基于Python實(shí)現(xiàn) 教案 ch04 對偶理論

對偶理論1．考慮如下優(yōu)化問題 (4.5.1)其中變量。(1)分析原問題，給出可行集、最優(yōu)值以及最優(yōu)解。(2)畫出目標(biāo)函數(shù)關(guān)于的圖像，并在圖像上畫出可行集、最優(yōu)值以及最優(yōu)解。畫出時，Lagrange函數(shù)關(guān)于的圖像，驗(yàn)證下界性質(zhì)：對成立。推導(dǎo)并畫出Lagrange對偶函數(shù)。（1）找出可行集：要使約束條件成立，需要滿足(x-1)(x-5)≤0。這意味著x的取值范圍為[1,5]。求解最優(yōu)值：我們需要找到在可行集內(nèi)使目標(biāo)函數(shù)最小的點(diǎn)。首先，我們可以計算目標(biāo)函數(shù)的導(dǎo)數(shù)：f'(x)=2x-2。將其置零求解：2x-2=0，得到x=1。檢查臨界點(diǎn)和可行集邊界上的目標(biāo)函數(shù)值：當(dāng)x=1時，f(x)=12-2(1)+1=0。確定最優(yōu)解：目標(biāo)函數(shù)在x=1處取得最小值，滿足約束條件(x-1)(x-5)≤0。因此，可行集為[1,5]，最優(yōu)值為f(x)=0，在x=1處取得最小值。綜上所述，原問題的可行集為[1,5]，最優(yōu)值為0，在x=1處取得最優(yōu)解。（2）略。2．考慮如下凸分段線性函數(shù)最小化問題 (4.5.2)其中變量。(1)考慮等式問題 (4.5.3)其中變量，推導(dǎo)出Lagrange對偶問題。(2)將分段線性問題(4.5.1)表述為LP問題并寫出LP問題的對偶問題。將LP對偶與(1)中所求得的對偶問題聯(lián)系起來。（1）略。（2）略。3．設(shè)有若干二分類問題的觀測樣本，考慮線性支持向量機(jī)模型： (4.5.4)其中，為參數(shù)，為樣本點(diǎn)的經(jīng)驗(yàn)損失，對應(yīng)于Hinge損失函數(shù)，函數(shù)為判別函數(shù)。(1)將線性支持向量機(jī)模型化為凸二次規(guī)劃模型，并寫出該規(guī)劃模型的對偶問題；(2)結(jié)合凸二次規(guī)劃模型的最優(yōu)性條件，說明哪些樣本對模型起作用，哪些不起作用.(1)將線性支持向量機(jī)模型化為凸二次規(guī)劃模型，并寫出該規(guī)劃模型的對偶問題：我們可以將線性支持向量機(jī)模型寫成如下的凸二次規(guī)劃形式：minimize1/2||w||2+C∑i=1^mξisubjecttoyi(w'xi+b)≥1-ξi,i=1,2,...,mξi≥0,i=1,2,...,m其中，變量為w∈R?，b∈R，ξi≥0，i=1,2,...,m。對應(yīng)的拉格朗日函數(shù)為：L(w,b,ξ,α,μ)=1/2||w||2+C∑i=1^mξi-∑i=1^mαi[yi(w'xi+b)-1+ξi]-∑i=1^mμiξi其中，αi≥0，i=1,2,...,m，μi≥0，i=1,2,...,m是拉格朗日乘子。接下來，我們需要對拉格朗日函數(shù)進(jìn)行最小化來得到對偶問題。首先，對w、b和ξi分別求導(dǎo)數(shù)并令其等于零，得到：?L/?w=w-∑i=1^mαiyixi=0，解得w=∑i=1^mαiyixi?L/?b=-∑i=1^mαiyi=0，解得∑i=1^mαiyi=0?L/?ξi=C-αi-μi=0，解得αi+μi=C，且αi≥0，μi≥0，i=1,2,...,m將上述結(jié)果代入拉格朗日函數(shù)，得到對偶問題：maximizeL(w*,b*,α)=∑i=1^mαi-1/2∑i=1^m∑j=1^mαiαjyiyjxi'xjsubjectto∑i=1^mαiyi=0,αi≥0,i=1,2,...,m其中，w*=∑i=1^mαiyixi，b*=yi-w'xi(其中i是任意一個滿足αi>0的樣本點(diǎn))，變量為α∈R?，n為樣本數(shù)。注意，這是一個凸二次規(guī)劃問題，而且這個問題的解又可以用來求解原始問題中的最優(yōu)解。(2)結(jié)合凸二次規(guī)劃模型的最優(yōu)性條件，說明哪些樣本對模型起作用，哪些不起作用。根據(jù)凸二次規(guī)劃模型的最優(yōu)性條件，我們可以得出以下結(jié)論：對于所有的正常樣本（即yi=+1的樣本），當(dāng)其對應(yīng)的Lagrange乘子αi>0時，它們將成為決策邊界上的支持向量。對于所有的負(fù)樣本（即yi=-1的樣本），當(dāng)其對應(yīng)的Lagrange乘子αi>0時，它們也將成為決策邊界上的支持向量。對于那些滿足0<αi<C的樣本，它們不在決策邊界上，但會被誤分類點(diǎn)所影響，并且起到一定的支持作用。對于那些對應(yīng)的Lagrange乘子αi=0的樣本，它們既不在決策邊界上，也不對支持向量產(chǎn)生影響。對于那些對應(yīng)的Lagrange乘子αi=C的樣本，它們可能是異常樣本或噪音點(diǎn)。因此，模型中僅有支持向量對模型起作用，非支持向量則不需要考慮。同時，異常樣本或噪音點(diǎn)可能會干擾模型的訓(xùn)練，需要特別處理。4．通過引入新變量以及等式約束，推導(dǎo)出下式的對偶問題 (4.5.5)其中。略。5．考慮Lasso模型 (4.5.6)其中，假設(shè)模型有唯一解，證明該模型的最優(yōu)解關(guān)于是分片線性的。略。6．考慮QCQP問題 (4.5.7)其中變量。(1)寫出最優(yōu)點(diǎn)和最優(yōu)值。(2)寫出KKT條件。(3)求解Lagrange對偶問題，并說明強(qiáng)對偶性是否成立。(1)最優(yōu)點(diǎn)x和最優(yōu)值P：最優(yōu)點(diǎn)x為(x?,x?)=(2,1)，最優(yōu)值P為2。(2)KKT條件：KKT條件是解凸優(yōu)化問題的一組必要條件。對于該問題，KKT條件如下：a.平穩(wěn)性條件（StationarityCondition）：?f(x)+∑?λ??h?(x)+∑?μ??g?(x)=0其中，?f(x)表示目標(biāo)函數(shù)f(x)關(guān)于變量x的梯度；?h?(x)表示約束條件h?(x)關(guān)于變量x的梯度；?g?(x)表示不等式約束條件g?(x)關(guān)于變量x的梯度；λ?和μ?分別是約束條件h?(x)和g?(x)對應(yīng)的拉格朗日乘子。b.約束條件滿足性條件（PrimalFeasibility）：h?(x)≤0，i=1g?(x)≤0，j=1,2c.對偶互補(bǔ)條件（DualComplementarity）：λ?≥0，μ?≥0λ?h?(x)=0，i=1μ?g?(x)=0，j=1,2d.KKT對偶互補(bǔ)條件（ComplementarySlackness）：λ?(h?(x)+0)=0，i=1μ?(g?(x)+0)=0，j=1,2(3)求解Lagrange對偶問題和強(qiáng)對偶性說明：根據(jù)最優(yōu)值P的定義，我們可以得到Lagrange函數(shù)：L(x,λ,μ)=f(x)+∑?λ?h?(x)+∑?μ?g?(x)對于原始問題的約束條件h?(x)≤0(i=1)和g?(x)≤0(j=1,2)，可以分別引入拉格朗日乘子λ?和μ?、μ?。根據(jù)Lagrange函數(shù)，我們可以得到Lagrange對偶問題：maximizeD(λ,μ)=min_xL(x,λ,μ)subjecttoλ?≥0,μ?≥0,μ?≥0將原始問題代入Lagrange函數(shù)，可以得到：L(x,λ,μ)=(x?2+x?3-4)+λ?[(x?-1)2+(x?-1)2-4]+μ?(-x?)+μ?(-x?)最小化Lagrange函數(shù)相當(dāng)