本文主要講解有關原問題和拉格朗日對偶問題，以及它們之間的關系，進而引出弱對偶性和強對偶性以及 KKT 條件和 Slater 條件。
原問題
優化問題一般都可以寫為下面的形式：
min f 0 ( x ) , x ∈ R n \min f_0(x),\quad x\in R^n minf0(x),x∈Rn
s . t . f i ( x ) ≤ 0 , i = 1 , 2 , . . . , m s.t.\quad f_i(x)\leq0,\quad i=1,2,...,m s.t.fi(x)≤0,i=1,2,...,m
h j ( x ) = 0 , j = 1 , 2 , . . . , p \quad \quad h_j(x)=0,\quad j=1,2,...,p hj(x)=0,j=1,2,...,p
以上形式被成為原問題，即求解一個滿足 m 個不等式限制和 p 個等式限制的函數 f 0 ( x ) f_0(x) f0(x) 的最小值。實際上我們并不關心最小值是什麼，而是關心最小值在 x 是什麼的時候取得。
上述是一般的優化問題，而凸優化問題在以上形式的基礎上多了幾個限制條件：1. f i ( x ) f_i(x) fi(x) 為凸函數 2. h j ( x ) h_j(x) hj(x) 為仿射函數。将一般的優化問題轉化為凸優化問題的好處是凸優化隻有一個極小值點，也就是說凸優化問題的局部最優解即全局最優解。下面的讨論如果不加以說明都是針對一般的優化問題來說的。
拉格朗日函數
解決帶限制的條件的優化問題的一般解決辦法是拉格朗日乘子法，也就是先寫出拉格朗日函數，再讓拉氏函數對 x 求導得到導數為 0 的點，将這些點帶入原函數，則其中的最大值即為原函數的最大值，最小值即為原函數的最小值。上述凸優化問題的拉氏函數為：
L ( x , u , v ) = f 0 ( x ) + ∑ i = 1 m u i f i ( x ) + ∑ j = 1 p v j h j ( x ) L(x,u,v)=f_0(x)+\sum_{i=1}^mu_if_i(x)+\sum_{j=1}^pv_jh_j(x) L(x,u,v)=f0(x)+i=1∑muifi(x)+j=1∑pvjhj(x)
其中 u i ≥ 0 u_i\geq0 ui≥0， v j ∈ R v_j\in R vj∈R，這是因為在可行域内，因為 f i ( x ) ≤ 0 f_i(x)\leq0 fi(x)≤0，是以當 u i ≥ 0 u_i\geq0 ui≥0 時， ∑ i = 1 m u i f i ( x ) \sum_{i=1}^mu_if_i(x) ∑i=1muifi(x) 的最大值為 0；因為 h j ( x ) = 0 h_j(x)=0 hj(x)=0，是以 ∑ j = 1 p v j h j ( x ) \sum_{j=1}^pv_jh_j(x) ∑j=1pvjhj(x) 恒為0， v j v_j vj 可以取任意值。這樣就保證了 L ( x , u , v ) L(x,u,v) L(x,u,v) 的最大值為原函數 f 0 ( x ) f_0(x) f0(x) ，即 max u , v L ( x , u , v ) = f 0 ( x ) \max_{u,v} L(x,u,v)=f_0(x) maxu,vL(x,u,v)=f0(x)。
對于固定的 x 來說，拉氏函數 L ( x , u , v ) L(x,u,v) L(x,u,v) 為 u u u 和 v 的仿射函數。
拉格朗日對偶函數
由此一來，就把原來的求解帶限制條件的原函數轉換為了不帶限制條件的拉格朗日函數。求解 min x f 0 ( x ) \min_x f_0(x) minxf0(x) 就等價于求解 min x max u , v L ( x , u , v ) \min_x\max_{u,v}L(x,u,v) minxmaxu,vL(x,u,v)。但是該式子并不容易求解，是以引入了拉格朗日對偶函數（注意不是對偶問題），拉格朗日對偶函數就是拉格朗日函數關于 x 取最小值，即：
g ( u , v ) = inf x ∈ D L ( x , u , v ) = inf x ∈ D [ f 0 ( x ) + ∑ i = 1 m u i f i ( x ) + ∑ j = 1 p v j h j ( x ) ] g(u,v)=\inf_{x\in D}L(x,u,v)=\inf_{x\in D}[f_0(x)+\sum_{i=1}^mu_if_i(x)+\sum_{j=1}^pv_jh_j(x)] g(u,v)=x∈DinfL(x,u,v)=x∈Dinf[f0(x)+i=1∑muifi(x)+j=1∑pvjhj(x)]
其中 inf x ∈ D \inf_{x\in D} infx∈D 表示函數逐點對 x 求下确界，也就是對任意的 u u u 和 v 求出一個使得 L ( x , u , v ) L(x,u,v) L(x,u,v) 最小的 x 。當拉氏函數沒有下确界時，定義下确界為 − ∞ -\infty −∞，即 g ( u , v ) = − ∞ g(u,v)=-\infty g(u,v)=−∞； D 是可行域。拉格朗日對偶函數是一個凹函數，也就是說它存在一個唯一的極大值點。
拉氏對偶函數為凹函數證明
先來感性的看一下這個問題，因為是拉氏對偶函數是關于 u 和 v 的仿射函數，是以可以用下面兩張示意圖表示對 x 逐點取最小值的結果：
上圖是随便畫的多個仿射函數，對其逐點取最小值得到下圖：
可以發現結果是一個凹函數。
拉氏對偶函數和原函數的關系
因為 min x f 0 ( x ) = min x max u , v L ( x , u , v ) ≥ max u , v min x L ( x , u , v ) = m a x u , v g ( u , v ) \min_x f_0(x)=\min_x\max_{u,v}L(x,u,v)\geq\max_{u,v}\min_xL(x,u,v)=max_{u,v}g(u,v) minxf0(x)=minxmaxu,vL(x,u,v)≥maxu,vminxL(x,u,v)=maxu,vg(u,v)，是以可以用拉格朗日對偶的最大值去逼近原函數的最小值。下面來證明一下上面式子的正确性：
因為任何函數都不大于其對某個變量求最大值，故：
f ( x , y ) ≤ max x f ( x , y ) f(x,y)\leq\max_x f(x,y) f(x,y)≤xmaxf(x,y)
上式兩邊對 y 求最小值得：
min y f ( x , y ) ≤ min y max x f ( x , y ) \min_yf(x,y)\leq\min_y\max_x f(x,y) yminf(x,y)≤yminxmaxf(x,y)
上式中不等式的前面是一個關于 x 的函數，不妨記為 G(x)，不等式後面是一個定值，不妨記為 A，是以說 G ( x ) ≤ A G(x)\leq A G(x)≤A，是以 G(x) 的最大值也不大于 A：
max x min y f ( x , y ) ≤ min y max x f ( x , y ) \max_x\min_yf(x,y)\leq\min_y\max_x f(x,y) xmaxyminf(x,y)≤yminxmaxf(x,y)
得證。
弱對偶和強對偶
我們用 p ∗ p^* p∗ 表示原問題的最優解，即 p ∗ = min x f 0 ( x ) p^*=\min_xf_0(x) p∗=minxf0(x)；用 d ∗ d^* d∗ 表示拉氏對偶函數的最優解，即 d ∗ = max u , v g ( u , v ) d^*=\max_{u,v}g(u,v) d∗=maxu,vg(u,v)。并定義原問題的最優解與拉氏對偶問題的最優解之間的內插補點為 對偶間隙（dual gap），即 p ∗ − d ∗ p^*-d^* p∗−d∗。
前面我們已經證明了原問題的最優解大于等于對偶問題的最優解，即 p ∗ ≥ d ∗ p^*\geq d^* p∗≥d∗，這個性質被稱作 弱對偶性 ，也可以表示為對偶間隙大于等于 0，即 p ∗ − d ∗ ≥ 0 p^*-d^*\geq 0 p∗−d∗≥0。即使當 p ∗ p^* p∗ 和 d ∗ d^* d∗ 無限時，弱對偶性仍然成立。如果原問題無下界，則對偶問題也無下界；如果對偶問題無上界，則原問題也無上界，即原問題不可行。
如果原問題的最優解和拉氏對偶問題的最優解相等，也就是對偶間隙為 0，則 強對偶性 成立。
一般情況下強對偶性不成立，但是如果原問題是凸優化問題，即原函數和不等式限制 f i ( x ) f_i(x) fi(x) 為凸函數，而等式限制 h j ( x ) h_j(x) hj(x) 為仿射函數，則強對偶性通常（但不總是）成立。而強對偶性成立的條件一般被稱為 限制準則。下面主要講解兩個限制準則—— KKT 條件 和 Slater 條件。
KKT 條件
之前證明了我們可以用拉格朗日對偶的最大值去逼近原函數的最小值的思路是正确的，但是什麼時候兩者的最大值和最小值相等呢？
首先假設函數 f 0 ( x ) , . . . , f m ( x ) , h 1 ( x ) , . . . , h p ( x ) f_0(x),...,f_m(x),h_1(x),...,h_p(x) f0(x),...,fm(x),h1(x),...,hp(x) 都可微，但并不假設這些函數為凸函數，則拉氏對偶函數：
g ( u ∗ , v ∗ ) = inf x [ f 0 ( x ) + ∑ i = 1 m u i ∗ f i ( x ) + ∑ j = 1 p v j ∗ h j ( x ) ] g(u^*,v^*)=\inf_x[f_0(x)+\sum_{i=1}^mu_i^*f_i(x)+\sum_{j=1}^pv_j^*h_j(x)] g(u∗,v∗)=xinf[f0(x)+i=1∑mui∗fi(x)+j=1∑pvj∗hj(x)]
因為一個函數的下确界（最小值）不大于函數本身，故：
≤ f 0 ( x ∗ ) + ∑ i = 1 m u i ∗ f i ( x ∗ ) + ∑ j = 1 p v j ∗ h j ( x ∗ ) \leq f_0(x^*)+\sum_{i=1}^mu_i^*f_i(x^*)+\sum_{j=1}^pv_j^*h_j(x^*) ≤f0(x∗)+i=1∑mui∗fi(x∗)+j=1∑pvj∗hj(x∗)
又因為後兩項的最大值為 0，故：
≤ f 0 ( x ∗ ) \leq f_0(x^*) ≤f0(x∗)
上面三式中， u ∗ u^* u∗、 v ∗ v^* v∗ 和 x ∗ x^* x∗ 分别是拉格朗日對偶函數和原函數的最優解。是以說要想讓拉格朗日對偶函數的最大值和原函數最小值相等，需要讓上面三式中的小于等于号全部取等号。
因為拉格朗日函數在 x ∗ x^* x∗ 處取得極小值，是以拉氏函數在 x ∗ x^* x∗ 處的導數為 0 。是以第一個 ≤ \leq ≤ 取等号的條件是拉氏函數對 x ∗ x^* x∗ 的偏導為 0，即：
∇ f 0 ( x ∗ ) + ∑ i = 1 m u i ∗ ∇ f i ( x ) + ∑ j = 1 p v j ∗ ∇ h j ( x ) = 0 條 件 ( 1 ) \nabla f_0(x^*)+\sum_{i=1}^mu_i^*\nabla f_i(x)+\sum_{j=1}^pv_j^*\nabla h_j(x)=0\quad\quad\quad\quad 條件 (1) ∇f0(x∗)+i=1∑mui∗∇fi(x)+j=1∑pvj∗∇hj(x)=0條件(1)
第二個 ≤ \leq ≤ 取等号的條件是 ∑ i = 1 m u i ∗ f i ( x ∗ ) \sum_{i=1}^mu_i^*f_i(x^*) ∑i=1mui∗fi(x∗) 和 ∑ j = 1 p v j ∗ h j ( x ∗ ) \sum_{j=1}^pv_j^*h_j(x^*) ∑j=1pvj∗hj(x∗) 全部為 0，前面說了，後者恒等于 0，而前者為 0 的條件是：
∑ i = 1 m u i ∗ f i ( x ∗ ) = 0 \sum_{i=1}^mu_i^*f_i(x^*)=0 i=1∑mui∗fi(x∗)=0
但是因為在可行域内，以上求和項的每一項都是非正的，是以以上條件等價于：
u i ∗ f i ( x ∗ ) = 0 條 件 ( 2 ) u_i^*f_i(x^*)=0\quad\quad\quad\quad\quad\quad\quad條件(2) ui∗fi(x∗)=0條件(2)
以上 2 個限制條件，再加上凸優化問題自身的三個限制條件就得到了著名的 KKT 條件，和 KMP 算法的名稱類似，所謂的 KKT 條件的命名其實是三位科學家名字的英文首字母的組合，KKT 條件即：
f i ( x ∗ ) ≤ 0 , i = 1 , . . . , m f_i(x^*)\leq0,\quad i=1,...,m fi(x∗)≤0,i=1,...,m
h i ( x ∗ ) = 0 , i = 1 , . . . , p h_i(x^*)=0,\quad i=1,...,p hi(x∗)=0,i=1,...,p
u i ∗ ≥ 0 , i = 1 , . . . , m u_i^*\geq0,\quad i=1,...,m ui∗≥0,i=1,...,m
∇ f 0 ( x ∗ ) + ∑ i = 1 m u i ∗ ∇ f i ( x ) + ∑ j = 1 p v j ∗ ∇ h j ( x ) = 0 \nabla f_0(x^*)+\sum_{i=1}^mu_i^*\nabla f_i(x)+\sum_{j=1}^pv_j^*\nabla h_j(x)=0 ∇f0(x∗)+i=1∑mui∗∇fi(x)+j=1∑pvj∗∇hj(x)=0
u i ∗ f i ( x ∗ ) = 0 u_i^*f_i(x^*)=0 ui∗fi(x∗)=0
KKT 條件中的條件 (2) u i ∗ f i ( x ∗ ) = 0 u_i^*f_i(x^*)=0 ui∗fi(x∗)=0 也被成為 互補松弛性，我們可以将互補松弛條件等價地改寫為：
u i ∗ > 0 ⇒ f i ( x ∗ ) = 0 u_i^*>0\Rightarrow f_i(x^*)=0 ui∗>0⇒fi(x∗)=0
或者：
f i ( x ∗ ) < 0 ⇒ u i ∗ = 0 f_i(x^*)<0\Rightarrow u_i^*=0 fi(x∗)<0⇒ui∗=0
這是因為在可行域内有 u i ∗ ≥ 0 u_i^*\geq 0 ui∗≥0 并且 f i ( x ∗ ) ≤ 0 f_i(x^*)\leq 0 fi(x∗)≤0。
Slater 條件
如果原始問題為凸優化問題，并且存在一點 x 使得所有的限制條件都小于 0，即：
f i ( x ) < 0 , i = 1 , . . . , m f_i(x)<0,\quad i=1,...,m fi(x)<0,i=1,...,m
則強對偶性成立。
上述條件就是所謂的 Slater 條件，而滿足上述條件的點被稱為 嚴格可行，這是因為不等式限制嚴格成立。
當不等式限制函數 f i ( x ) f_i(x) fi(x) 中有一些函數是仿射函數時，Slater 條件可以進一步改進。我們假設前 k 個不等式限制函數為仿射函數，則強對偶性成立的條件（即改進後的 Slater 條件）為：存在一點 x 使得前 k 個不等式限制函數小于等于 0，而其他不等式限制函數小于 0，即
f i ( x ) ≤ 0 , i = 1 , . . . , k f_i(x)\leq 0,\quad i=1,...,k fi(x)≤0,i=1,...,k
f i ( x ) < 0 , i = k + 1 , . . . , m f_i(x)<0,\quad i=k+1,...,m fi(x)<0,i=k+1,...,m
換句話說，仿射函數不等式不需要嚴格成立。