凸優(yōu)化理論與應(yīng)用對(duì)偶問題

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

KKT條件34整理課件例 其中

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

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