原始问题

假设 $f(x),c_i(x), h_j(x)$ 是定义在 $R^n$ 上的连续可微函数，考虑约束最优化问题
$min_{x \in R^n}f(x)$

$s.t. \qquad c_i(x) \leq 0, \qquad i = 1,2,...,k$

$h_j(x) = 0, \quad j=1,2,...,l$

首先，引入拉格朗日函数：
$L(x, \alpha, \beta) = f(x)+\sum_{i=1}^k \alpha_i c_i(x)+ \sum_{j=1}^l \beta_jh_j(x)$
这里， $x = (x^{(1)},x^{(1)},..., x^{(n)} )^T \in R^n$ ， $\alpha_i, \beta_i$ 是拉格朗日乘子， $\alpha_i \geq 0$ ，考虑x的函数：
$\theta_P(x) = max_{\alpha, \beta: \alpha_i \geq0}L(x, \alpha, \beta)$
考虑极小化问题：
$min_x\theta_P(x)= min_xmax_{\alpha, \beta: \alpha_i \geq0}L(x, \alpha, \beta)$
这与原始最优化问题等价，即它们有着相同的解，将其称为广义拉格朗日函数的极小极大问题。

对偶问题

定义：
$\theta_D(\alpha, \beta) = min_xL(x, \alpha, \beta)$
再考虑极大化 $\theta_D(\alpha, \beta)$ ，即原始最优化问题的对偶问题：
$max_{\alpha, \beta: \alpha_i \geq 0}\theta_D(\alpha, \beta)= max_{\alpha, \beta: \alpha_i \geq 0}min_xL(x, \alpha, \beta)$

$s.t. \qquad \alpha_i \geq 0, \qquad i = 1,2,...,k$

原始问题和对偶问题的关系

若原始问题和对偶问题都有最优值，则：
$max_{\alpha, \beta: \alpha_i \geq 0}min_xL(x, \alpha, \beta) \leq min_xmax_{\alpha, \beta: \alpha_i \geq0}L(x, \alpha, \beta)$
在某些条件下，上式的等号成立，这时可以用解对偶问题替代解原始问题。

对原始问题和对偶问题，假设函数 $f(x)$ 和 $c_i(x)$ 是凸函数， $h_j(x)$ 是仿射函数，并且不等式约束 $c_i(x)$ 是严格可行的，则 $x^{\star}$ 和 $\alpha^{\star}，\beta^{\star}$ 分别是原始问题和对偶问题的解的充分必要条件是 $x^{\star}$ ， $\alpha^{\star}，\beta^{\star}$ 满足下面的Karush-Kuhn-Tucker (KKT)条件：
$\nabla_xL(x^{\star},\alpha^{\star}，\beta^{\star}) = 0$