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

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

KKT條件35例 其中

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

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