Lagrange duality

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

\begin{aligned} \min\limits_{x\in\mathbf{R}^n} \quad & f(x) \\ s.t. \quad & c_i(x)\leq 0, i=1,2,\cdots,k \\ & h_{j}(x)=0, j=1,2,\cdots,l \end{aligned}

称此最优化问题为原始最优化问题或原始问题。

首先，引入广义拉格朗日函数（generalized Lagrange function） $$ L(x,\alpha,\beta)=f(x)+\sum_{i=1}^{k}\alpha_{i}c_{i}(x)+\sum_{j=1}^{l}\beta_{j}h_{j}(x) $$

这里， $x=(x^{(1)},x^{(2)},\cdots,x^{(n)})^T\in\mathbf{R}^n,\alpha_i,\beta_j$ 是# 拉格朗日乘子， $\alpha_i\geq0$ 。考虑 $x$ 的函数：

$$ \theta_{P}(x) = \max_{\alpha,\beta:\alpha\geq0}L(x,\alpha,\beta) $$

这里， $P$ 表示原始问题。 $\max$ 下标只有 $\alpha,\beta$ ，可以理解为， 先保持 $x$ 不变， $\alpha,\beta$ 是使得 $L$ 最大的参数。

假设给定某个 $x$ 。如果 $x$ 违反原始问题的约束条件，即存在某个 $i$ 使得 $c_i(x)>0$ 或者存在某个 $j$ 使得 $h_{j}(x)\neq0$ ，那么就有： $$ \theta_{P}(x)=\max_{\alpha,\beta:\alpha_i\geq0}\left[ f(x)+\sum_{i=1}^{k}\alpha_{i}c_{i}(x)+\sum_{j=1}^{l}\beta_{j}h_{j}(x) \right]=+\infty $$

因为如果某个 $i$ 使约束 $c_{i}(x)>0$ ，则可令 $\alpha_{i}\rightarrow+\infty$ ； 若某个 $j$ 使 $h_{j}(x)\neq0$ ，则可令 $\beta_{j}$ 使 $\beta_{j}h_{j}(x)\rightarrow+\infty$ ， 而将其余各 $\alpha_i,\beta_j$ 均取 0 。

相反地，如果 $x$ 满足约束条件，则此问题和原始问题等价。即：

\begin{aligned} \theta_{P}(x)= \quad & f(x), &x s.t. Constrain \\ &+\infty, & others \\ \end{aligned}

所以，如果考虑极小化问题

$$ \min_{x}\theta_{P}(x)=\min_{x}\max_{\alpha,\beta:\alpha_{i}\geq0}L(x,\alpha,\beta) $$

它是与原始问题等价的，即它们有相同的解。 问题 $\min_{x}\max_{\alpha,\beta:\alpha_{i}\geq0}L(x,\alpha,\beta)$ 称为广义拉格朗日函数的极小极大问题。 为了方便，定义原始问题的最优值

$$ p^{*}=\min_{x}\theta_{P}(x) $$

称为原始问题的值。

定义 $$ \theta_{D}(\alpha,\beta)=\min_{x}L(x,\alpha,\beta) $$

这里 $\theta_{D}$ 是关于 $\alpha,\beta$ 的函数， $\min$ 的下标为 $x$ 可以理解为在给定 $\alpha,\beta$ 不变的条件下， $x$ 是使得 $L$ 最小的参数。 再考虑极大化 $\theta_D$ ，即 $$ \max_{\alpha,\beta:\alpha_{i}\geq0}\theta_{D}(\alpha,\beta)=\max_{\alpha,\beta:\alpha_{i}\geq0}\min_{x}L(x,\alpha,\beta) $$

此问题被称为广义拉格朗日函数的极大极小问题。

定义对偶问题的最优值 $$ d^{*}=\max_{\alpha,\beta:\alpha_{i}\geq0}\theta_{D}(\alpha,\beta) $$

称为对偶问题的值。