拉格朗日對偶性
在約束最優化問題中，常用拉格朗日對偶性將原始問題轉換為對偶問題求解。
廣義拉格朗日函數
稱最優化問題
$\begin{equation} \begin{array}{lcl} \min\limits_{x\in R^n} f(x)\\ \begin{aligned} \text{s.t.}\;\;&c_i(x) \le 0,\;\;i=1,2,…,k \\ &h_j(x)=0,\;\;j=1,2,…,l \end{aligned} \end{array} \end {equation}$
為原始最優化問題。使用以上優化問題構造廣義拉格朗日函數：
$L(x,\alpha,\beta) = f(x)+\sum\limits_{i=1}^k\alpha_ic_i(x)+\sum\limits_{j=1}^l\beta_jh_j(x)$
其中$\alpha_i\ge 0,\beta_j\in R$是拉格朗日乘子。可以發現，對於違反原始問題約束的$x$，即存在某個$c_i(x)>0$，或某個$h_j(x)\ne 0$，有：
$\max\limits_{\alpha\ge 0,\beta}L(x,\alpha,\beta) = +\infty$
因此有：
$\begin{equation} \max\limits_{\alpha\ge 0, \beta}L(x,\alpha,\beta) = \left\{ \begin{aligned} &f(x),\;\;x滿足原始條件約束\\ &+\infty,\;\;else \end{aligned} \right. \end {equation}$
因此原始問題的最優值可以表示為：
$p^* = \min\limits_{x}\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)$
從而將約束條件與待優化問題結合到了一起，稱為廣義拉格朗日函數的極小極大問題。
對偶問題以及KKT條件
對偶問題
將極小極大交換一下，得到
$d^* = \max\limits_{\alpha\ge 0 , \beta}\min\limits_{x}L(x,\alpha,\beta)$
即為原始問題的對偶問題的最優值。對偶問題轉換為帶條件的形式就是：
$\begin{aligned} &\max\limits_{\alpha,\beta}\min\limits_{x} L(x,\alpha,\beta)\\ &\;\text{s.t.}\;\;\alpha_i\ge 0, \;\; i=1,2,…,k \\ \end{aligned}$
如果原始問題與對偶問題都有最優值，$p^*$和$d^*$，則：
$d^*= \max\limits_{\alpha\ge 0 , \beta}\min\limits_{x}L(x,\alpha,\beta)\le \min\limits_{x}\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)= p^*$
這是因為，對於任意$x,\alpha,\beta$，有：
$\min\limits_{x}L(x,\alpha,\beta)\le L(x,\alpha,\beta)\le\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)$
也就是左邊關於$\alpha,\beta$的函數，總是小於等於右邊關於$x$的函數。所以有$d^*\le p^*$。
KKT條件
某些情況下，對偶問題與原始問題有相等的最優值，即$d^* = p^*$，這時解對偶問題可以替代原始問題，條件如下：
1、$f(x)$和$c_i(x)$是凸函數；
2、$h_j(x)$是仿射函數，即一次函數；
3、不等式約束$c_i(x)$是嚴格可行的，即存在$x$，對所有$i$有$c_i(x)<0$。如果不存在這樣的$x$的話，實際上就是等式約束了。這是因為，每個$x$都會使某個不等式約束取等號，也就可以僅使用等式約束來表示這些$x$了。
此時有：
$p^*=d^*=L(x^*,\alpha^*,\beta^*)$
且算出$x^*,\alpha^*,\beta^*$的充要條件是（KKT條件）：
$\left\{ \begin{aligned} &\nabla_xL(x^*,\alpha^*,\beta^*) = 0 \\ &\alpha^*c_i(x^*) = 0, \;\; i=1,2,…,k \\ &c_i(x^*) \le 0, \;\; i=1,2,…,k \\ &\alpha_i^*\ge 0, \;\; i=1,2,…,k \\ &h_j(x^*) = 0, \;\; i=1,2,…,l \\ \end{aligned} \right.$
直觀理解
上圖顯示了優化的一個情況。等高線表示的是待優化函數$f(x)$（$x$二維），越向中心，值越小，是個標準的凸函數。紅圈表示不等式約束（內部），是個凸函數。藍線表示等式約束（線上），是仿射函數。則$x$可取的值在紅圈與其內部的藍線上。可觀察有如下幾個符合KKT條件的事實：
1、三個白色箭頭分別表示三個函數的梯度方向，此時有三個梯度的加權矢量和為0，與KKT條件中的1式吻合。
2、因為最優點在紅圈上，因此不等式約束取等為0，有2式。
3、3式和5式是原本的約束條件。
4、觀察三個梯度的方向，因為$f(x)$的方向不能改變（1式梯度前沒係數），所以為了矢量和為0，$\alpha$必須大於0。而由於等式約束的仿射函數取反後約束不變，而梯度方向卻變反了，因此$\beta$沒有正負的限制。
