优化问题的标准形式：
$$ minimize \quad f_0(x) \quad $$
$$ s.t. \quad f_i(x) \leqslant 0, \quad i=1,…,m $$
$$ \quad \quad h_i(x) = 0, \quad i=1,…,p $$
引入拉格朗日因子来去掉约束条件有拉格朗日函数： $$L(x, \lambda, \upsilon) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \upsilon_ih_i(x) $$
$$ s.t. \quad \lambda_i \geqslant 0, \quad i=1,…m $$
$$\quad \quad \upsilon_i \geqslant 0, \quad i=1,…p$$
在可行域范围内\(f_i(x) \leqslant 0, h_i(x) = 0\)，必有拉格朗日函数\(L \leqslant f_0(x)\)，若\(f_0(x)\)的最小值无法直接取得，可通过求拉格朗日函数的下确界来近似求得，若拉格朗日函数的下确界取得时恰巧满足\(f_i(x) = 0\)，则拉格朗日函数的下确界即原目标函数\(f_0(x)\)的最小值，因此求\(f_0(x)\)的最小值，可转为
$$ maximize_{\lambda_i, \upsilon_i}\quad g(\lambda, \upsilon) $$
$$ s.t. \quad g(\lambda, \upsilon) = minimize_x \quad f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \upsilon_ih_i(x) $$
$$\quad \lambda_i \geqslant 0, \quad i=1,…m $$
$$\quad \quad \upsilon_i \geqslant 0, \quad i=1,…p$$
这个优化问题即为最开始部分的标准优化问题的拉格朗日对偶问题，开始部分的问题则被成为原问题， 当拉格朗日函数关于x无下界时，对偶函数取值为\(-\infty \)，此时意义不大，只有\(g(\lambda, \upsilon) > -\infty \)时，对偶函数才能给出一个非平凡下界，此时是对偶可行的。
如前所述\(maximize_{\lambda_i, \upsilon_i}\quad g(\lambda, \upsilon) \leqslant minimize \quad f_0(x)\)当等号成立时，叫做强对偶，否则是弱对偶
重新将原问题描述为无约束问题：
$$minimize \quad f_0(x) + \sum_{i=1}^m I_{-} (f_i(x)) + \sum_{i=1}^p I_0(h_i(x))$$
其中：
$$I_-(u) = 0\quad if \quad u\leqslant 0$$
$$I_-(u) = \infty\quad if \quad u > 0$$
$$I_0(u) = 0\quad if \quad u = 0$$
$$I_0(u) = \infty\quad if \quad u \neq 0$$
\(I_-\)和\(I_0\)都是示性函数，可以理解为我们对约束条件的不满意程度，当约束条件满足时，不满意程度为0，当约束条件被打破时，不满意程度为无穷大。
$$L(x, \lambda, \upsilon) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \upsilon_ih_i(x) $$
$$s.t. \quad \lambda_i \geqslant 0, \quad i=1,…m $$
$$\quad \quad \upsilon_i \geqslant 0, \quad i=1,…p$$
在拉格朗日函数的表达中，使用\(\lambda\)和\(\upsilon\)代替里\(I_-\)和\(I_0\)，\(\lambda\)和\(\upsilon\)都是大于零的整数，可以理解为不满意函数为柔性的，不再是无穷大，而是随着越来越违背约束条件，就越来越不满意。
线性规划的一般形式：
$$ minimize \quad c^{T}x $$
$$s.t.\quad Ax \leqslant b $$
$$\quad \quad x \geqslant 0$$
构建拉格朗日函数：
$$ L(x) = c^Tx + \lambda^T(Ax - b)$$
$$ s.t. \quad \lambda_i \geqslant 0 $$
$$ \quad \quad x \geqslant 0$$
构建对偶函数： $$ maximize_\lambda \quad minimize_x\quad c^Tx + \lambda^T(Ax - b) $$
$$ \quad \quad \quad\quad\quad\quad\quad\quad \quad =(c^T + \lambda^TA)x - \lambda^Tb $$
$$ s.t. \quad \lambda_i \geqslant 0 $$
$$ \quad \quad x \geqslant 0 $$
分情况讨论：
1）当\(c^T + \lambda^TA < 0\)时，\(g(\lambda) = minimize_x\ \ (c^T + \lambda^TA)x - \lambda^Tb = -\infty\)对偶不可行，无意义
2）当\(c^T + \lambda^TA = 0\)时，\(g(\lambda) = minimize_x\ \ (c^T + \lambda^TA)x - \lambda^Tb = -\lambda^Tb\)
3）当\(c^T + \lambda^TA > 0\)时，\(g(\lambda) = minimize_x\ \ (c^T + \lambda^TA)x - \lambda^Tb\) ，为取得最小值，x必然等于0，进而有，\(g(\lambda) = -\lambda^Tb\)
因此对偶问题规约为：
$$ maximize_\lambda -\lambda^Tb $$
$$ s.t. \quad c_i + \sum_j \lambda_iA_{i,j} \geqslant 0 $$
$$ \quad \quad \lambda_i \geqslant 0 $$
为了推导简单，这里只讨论支持向量机，线性可分的场景，其余的使用核函数或不可分场景并无本质区别。
定义分类界面\(f(x) = w^Tx - b\)，支撑向量到分类界面的距离正比于\(\frac{1}{||w||^2}\)，优化问题目标为最大化支撑向量到分类界面的距离，约束是每个点的正确分类。
$$ minimize_w \quad \frac{1}{2}||w||^2 $$
$$ s.t. \quad y_i(w^Tx_i-b) \geqslant 1 \quad \forall i $$
其中\(y_i\)表示样本\(x_i\)的标签。
构建拉格朗日函数：
$$ L(w,b) = \frac{1}{2}||w||^2 + \sum_i \alpha_i[1 - y_i(w^Tx_i-b)] $$
$$ s.t.\quad \alpha_i \geqslant 0 $$
为取得拉格朗日函数极值，参数位于对参数求导等于0处，对w,b求导，得到：
$$ \frac{dL(w,b)}{db} = - \sum_i \alpha_iy_i = 0 $$
$$ \frac{dL(w,b)}{dw} = w - \sum_i \alpha_iy_ix_i = 0 $$
$$ w = \sum_i \alpha_iy_ix_i $$ 将\(w = \sum_i \alpha_iy_ix_i \)和\(\sum_i \alpha_iy_i = 0\)带入拉格朗日函数，并构建对偶问题：
$$ maximize_\alpha \quad minimize_{w,b}\quad\frac{1}{2}||w||^2 + \sum_i \alpha_i[1 - y_i(w^Tx_i-b)] $$
$$ \Rightarrow \frac{1}{2}(\sum_i \alpha_iy_ix_i) (\sum_j \alpha_jy_jx_j ) + \sum_i\alpha_i - \sum_i \alpha_iy_i((\sum_j \alpha_jy_jx_j) x_i -b) $$
$$ \Rightarrow \sum_i\alpha_i - \frac{1}{2}(\sum_i \alpha_iy_ix_i) (\sum_j \alpha_jy_jx_j ) $$
$$ \Rightarrow \sum_i\alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j x_i x_j $$
$$ s.t.\quad \alpha_i \geqslant 0 $$
当原问题不知道如何求解的时候，解对偶问题至少可以得到一个原问题的下界
有些问题的原问题很难求解或者无法求解，而对偶问题缺可以比较方便的求解，如上面示例的支持向量机优化对偶问题催生了SMO方法，这个方法要比直接去优化原问题的二次规划问题方便的多
对偶问题sensitivity analysis会更容易。如果对原问题的约束条件进行变化，很可能之前求的解就不再可行范围里了，但是对于对偶问题，只是优化目标发生了变化，原来的解还是可行的（很可能距离新的最优解也不远）
原问题的最小值可能根本无法求得，通过对偶问题可以发现这一点。
https://en.wikipedia.org/wiki/Duality_(optimization)
《凸优化》第五章