凸優(yōu)化理論與應(yīng)用-對偶問題課件

1凸優(yōu)化理論與應(yīng)用第四章對偶問題2優(yōu)化問題的拉格朗日函數(shù)設(shè)優(yōu)化問題：拉格朗日(Lagrangian)函數(shù)：對固定的，拉格朗日函數(shù)為關(guān)于和的仿射函數(shù)。3拉格朗日對偶函數(shù)拉格朗日對偶函數(shù)(lagrangedualfunction)：若拉格朗日函數(shù)沒有下界，則令拉格朗日對偶函數(shù)為凹函數(shù)。對和，若原最優(yōu)化問題有最優(yōu)值，則4對偶函數(shù)的例Least-squaressolutionoflinearequationsStandardformLPTwo-waypartitioningproblem5Least-squaressolutionoflinearequations原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：6StandardformLP原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：7Two-waypartitioningproblem原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：8對偶函數(shù)與共軛函數(shù)共軛函數(shù)共軛函數(shù)與對偶函數(shù)存在密切聯(lián)系具有線性不等式約束和線性等式約束的優(yōu)化問題：對偶函數(shù)：9Equalityconstrainednormminimization問題描述：共軛函數(shù)：對偶函數(shù)：10Entropymaximization原始問題：共軛函數(shù)：對偶函數(shù)：11Minimumvolumecoveringellipsoid原始問題：對偶函數(shù)：共軛函數(shù)：12拉格朗日對偶問題拉格朗日對偶問題的描述：對偶可行域最優(yōu)值最優(yōu)解13LP問題的對偶問題標(biāo)準(zhǔn)LP問題對偶函數(shù)對偶問題等價(jià)描述14弱對偶性定理（弱對偶性）：設(shè)原始問題的最優(yōu)值為，對偶問題的最優(yōu)值為，則成立。optimaldualitygap可以利用對偶問題找到原始問題最優(yōu)解的下界。15強(qiáng)對偶性強(qiáng)對偶性并不是總是成立的。定義（強(qiáng)對偶性）：設(shè)原始問題的最優(yōu)值為，對偶問題的最優(yōu)值為。若成立，則稱原始問題和對偶問題之間具有強(qiáng)對偶性。凸優(yōu)化問題通常（但并不總是）具有強(qiáng)對偶性。Slater定理：若凸優(yōu)化問題存在嚴(yán)格可行解，即存在，滿足 則優(yōu)化問題具有強(qiáng)對偶性。該條件稱為Slater條件。16強(qiáng)對偶性 存在，滿足弱化的Slater條件：若不等式約束條件的前個(gè)為線性不等式約束條件，則Slater條件可以弱化為：17Least-squaressolutionoflinearequations原問題：對偶問題：具有強(qiáng)對偶性18LagrangedualofQCQPQCQP：拉格朗日函數(shù)：對偶函數(shù)：19LagrangedualofQCQP對偶問題：Slater條件：存在，滿足20Entropymaximization原始問題：對偶函數(shù)：對偶問題：21Entropymaximization弱化的Slater條件：存在，滿足22Minimumvolumecoveringellipsoid原始問題：對偶函數(shù)：對偶問題：23Minimumvolumecoveringellipsoid弱化的Slater條件總成立，因此該優(yōu)化問題具有強(qiáng)對偶性。弱化的Slater條件：存在，滿足Mixedstrategiesformatrixgames雙人零和博弈玩家1可以從種策略中選擇；玩家2可以從種策略中選擇；玩家1對玩家2回報(bào)組成回報(bào)矩陣；玩家1希望回報(bào)值越小越好，而玩家2希望回報(bào)值越大越好；玩家1和玩家2以一定的概率分布選擇各種策略，即24Mixedstrategiesformatrixgames玩家1對玩家2的期望回報(bào)為：玩家1的策略分布選擇問題轉(zhuǎn)換為LP問題25Mixedstrategiesformatrixgames對偶問題玩家2的策略分布選擇問題26Mixedstrategiesformatrixgames等價(jià)問題由于優(yōu)化問題具有強(qiáng)對偶性，因此玩家1的優(yōu)化問題和玩家2的優(yōu)化問題完全等價(jià)。2728對偶可行解的不等式對于一優(yōu)化問題，若為一可行解，為對偶問題可行解，則有如下不等式： 為次優(yōu)解，其中不等式可以用于對次優(yōu)解的精度估計(jì)29互補(bǔ)松弛條件 所以設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，若兩者具有強(qiáng)對偶性，則 即30KKT優(yōu)化條件 因此，是的最優(yōu)解。設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，若兩者具有強(qiáng)對偶性，則 可得31KKT優(yōu)化條件設(shè)優(yōu)化問題中，函數(shù)可微。設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性，則滿足如下條件：KKT條件為必要條件！32凸優(yōu)化問題的KKT條件 可微。設(shè)滿足KKT條件，則為原始問題的最優(yōu)解，而為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性。設(shè)原始問題為凸優(yōu)化問題中，函數(shù)例33原始凸優(yōu)化問題KKT條件KKT條件構(gòu)成線性方程組系統(tǒng)34例原始凸優(yōu)化問題

KKT條件35例 其中

解得36凸優(yōu)化問題的對偶求解 存在唯一解。若為原始問題的可行解，則即為原始問題的最優(yōu)解；若不是原始問題的可行解，則原始問題不存在最優(yōu)解。設(shè)原始優(yōu)化問題與對偶問題具有強(qiáng)對偶性，且為對偶問題的最優(yōu)解。存在唯一的最小解，即例37原始凸優(yōu)化問題對偶問題：假設(shè)原問題存在可行解，即有，

則弱Slater條件滿足，原問題與對偶問題具有強(qiáng)對偶性。例38假設(shè)對偶問題的最優(yōu)解為，則原問題可求解可得39擾動問題擾動問題：當(dāng)時(shí)即為原始問題。若為正，則第個(gè)不等式約束被放寬；若為負(fù)，則第個(gè)不等式約束被收緊。記為擾動問題的最優(yōu)解。若擾動問題無最優(yōu)解，則記40靈敏度分析設(shè)對偶問題存在最優(yōu)解，且與原始問題具有強(qiáng)對偶性，若非干擾問題的最優(yōu)對偶解為，則有若在處可微，則41選擇定理設(shè)原始問題的約束條件：關(guān)于約束條件的優(yōu)化問題描述：最優(yōu)值：選擇定理42對偶問題的不等式組對偶問題對偶問題的最優(yōu)值：選擇定理43原問題與對偶問題的最優(yōu)值原問題的約束條件與對偶不等式組具有弱選擇性。定義（弱選擇性）：若兩個(gè)不等式（等式）系統(tǒng)，至多有一個(gè)可解，則稱這兩個(gè)系統(tǒng)具有弱選擇性。44選擇定理對偶不等式組設(shè)原始問題的嚴(yán)格不等式約束條件：原始問題的嚴(yán)格不等式約束條件與對偶不等式組具有弱選擇性。45定義（強(qiáng)選擇性）：若兩個(gè)不等式（等式）系統(tǒng)，恰有一個(gè)可解，則稱這兩個(gè)系統(tǒng)具有強(qiáng)選擇性。選擇定理對偶不等式組設(shè)原始問題為凸優(yōu)化問題，其嚴(yán)格不等式約束條件為：若存在，滿足，則上述兩不