拉格朗日對偶

0.簡介

在凸優(yōu)化研究中，數(shù)學(xué)優(yōu)化問題遵循以下形式：

? ??\bullet ?x \in \mathbb{R}^n是一個稱為優(yōu)化變量的向量

? ??\bullet f:\mathbb{R}^n\rightarrow \mathbb{R} 是一個我們想要最小化的凸函數(shù)

? ??\bullet C\subseteq \mathbb{R}^n是一套凸集，描述了一組可行（能夠完成或執(zhí)行）的解決方案

x^* \in \mathbb{R}^n作為問題(1)的全局最優(yōu)的充分必要條件是\bigtriangledown_xf(x^*) =0。

然而，在具有約束的凸優(yōu)化問題的更一般設(shè)置中，這種簡單的最優(yōu)性條件不起作用。對偶理論的一個主要目標(biāo)是以數(shù)學(xué)上嚴格的方式表征凸程序的最優(yōu)點。

在這里，我們提出了一種通用可微凸優(yōu)化問題的形式，如：

? ??\bullet x \in \mathbb{R}^n是優(yōu)化變量

? ??\bullet f:\mathbb{R}^n\rightarrow \mathbb{R}?和g_i:\mathbb{R}^n\rightarrow \mathbb{R}是可微的凸函數(shù)

? ??\bullet h_i:\mathbb{R}^n\rightarrow \mathbb{R}是仿射函數(shù)

? ??????????\circ 對于a \in \mathbb{R}^n，b \in \mathbb{R}的仿射函數(shù)形式f(x)=a^Tx+b

1.拉格朗日

給定形式（OPT）的凸約束最小化問題，（廣義）拉格朗日是一個函數(shù)L:\mathbb{R}^n\times \mathbb{R}^m\times \mathbb{R}^p\rightarrow \mathbb{R}，定義為

? ??\bullet x \in \mathbb{R}^n是拉格朗日的原始變量

? ??\bullet \alpha \in \mathbb{R}^m?和\beta \in \mathbb{R}^p是拉格朗日的對偶變量，也叫做拉格朗日乘子

直觀地，拉格朗日可以被認為是原始凸優(yōu)化問題（OPT）的目標(biāo)函數(shù)的修改版本，其解釋了每個約束。拉格朗日乘數(shù)\alpha_i和\beta _i可以被認為是違反約束的懲罰。拉格朗日對偶理論背后的關(guān)鍵直覺如下：

對于任何凸優(yōu)化問題，總是存在對偶變量的設(shè)置，使得拉格朗日關(guān)于原始變量的無約束最小值（保持對偶變量固定）與原始約束最小化問題的解一致。

當(dāng)我們在第6節(jié)中描述KKT條件時，我們將這種直覺形式化。

2.原始問題和對偶問題

為了顯示拉格朗日和原始凸優(yōu)化問題（OPT）之間的關(guān)系，我們引入了與拉格朗日相關(guān)的“原始問題”和“對偶問題”的概念：

原始問題

原始目標(biāo)函數(shù)

然后是無約束的最小化問題

被稱為原始問題。

? ??\bullet 一般來說，如果g_i(x)\leq 0和h_i(x)= 0成立，我們說x \in \mathbb{R}^n是原始可行的

? ??\bullet 我們通常使用向量x^* \in \mathbb{R}^n表示可以使（P）最小化的輸入，我們讓p^* = \theta p(x^*)表示原始目標(biāo)的最優(yōu)值

對偶問題

通過切換上面的最小化和最大化的順序，我們獲得了完全不同的優(yōu)化問題。

然后是約束最大化問題

被稱為對偶問題。

? ??\bullet 一般來說，如果\alpha_i(x)\geq 0成立，我們說(\alpha,\beta)是對偶可行的

3.解釋原始問題

4.解釋對偶問題

對偶目標(biāo)，\theta_D(\alpha,\beta),是\alpha和\beta的凹函數(shù)。為了解釋對偶問題，首先我們做出以下觀察：

論點1：如果(\alpha,\beta)是對偶可行，那么\theta_D(\alpha,\beta) \leq p^*。

論點2（弱對偶性）：

論點3（強對偶性）：對于滿足某些稱為約束條件的技術(shù)條件的原始和對偶問題， d^*=p^*

5.互補松弛

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容