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\ge 0$ 。考虑 $x$ 的函数：

$${\theta }_P(x)=\underset{\alpha ,\beta :\alpha \ge 0}{\max }L(x,\alpha ,\beta )$$

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

假设给定某个 $x$ 。如果 $x$ 违反原始问题的约束条件，即存在某个 $i$ 使得 $c_i(x)>0$ 或者存在某个 $j$ 使得 $h_j(x)\ne 0$ ，那么就有：

$${\theta }_P(x)=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }\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\to +\infty$ ； 若某个 $j$ 使 $h_j(x)\ne 0$ ，则可令 ${\beta }_j$ 使 ${\beta }_j{h}_j(x)\to +\infty$ ， 而将其余各 ${\alpha }_i,{\beta }_j$ 均取 0 。

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

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

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

$$\underset{x}{\min }{\theta }_P(x)=\underset{x}{\min }\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )$$

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

$$p^{\text{*}}=\underset{x}{\min }{\theta }_P(x)$$

称为原始问题的值。

对偶问题

定义

$${\theta }_D(\alpha ,\beta )=\underset{x}{\min }L(x,\alpha ,\beta )$$

这里 ${\theta }_D$ 是关于 $\alpha ,\beta$ 的函数， $\min$ 的下标为 $x$ 可以理解为在给定 $\alpha ,\beta$ 不变的条件下， $x$ 是使得 $L$ 最小的参数。 再考虑极大化 ${\theta }_D$ ，即

$$\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }{\theta }_D(\alpha ,\beta )=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }\underset{x}{\min }L(x,\alpha ,\beta )$$

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

定义对偶问题的最优值

$$d^{\text{*}}=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }{\theta }_D(\alpha ,\beta )$$

称为对偶问题的值。

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

若原始问题和对偶问题都有最优值，则

$$d^{\text{*}}=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }\underset{x}{\min }L(x,\alpha ,\beta )\le \underset{x}{\min }\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )=p^{\text{*}}$$

易知：

$${\theta }_D(\alpha ,\beta )=\underset{x}{\min }L(x,\alpha ,\beta )\le L(x,\alpha ,\beta )\le \underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )={\theta }_P(x)$$

即 ${\theta }_D(\alpha ,\beta )\le {\theta }_P(x)$

由于原始问题和对偶问题均有最优值，所以，

$$\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }{\theta }_D(\alpha ,\beta )\le \underset{x}{\min }{\theta }_P(x)$$

即

$$d^{\text{*}}=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }\underset{x}{\min }L(x,\alpha ,\beta )\le \underset{x}{\min }\underset{\alpha ,\beta :{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )=p^{\text{*}}$$

定理

考虑原始问题和对偶问题。假设函数 $f(x)$ 和 $c_i(x)$ 是凸函数， $h_j(x)$ 是仿射函数； 并且假设不等式约束 $c_i(x)$ 是严格执行的，即存在 $x$ ，对所有 $i$ 有 $c_i(x)<0$ ， 则存在 $x^{\text{*}},{\alpha }^{\text{*}},{\beta }^{\text{*}}$ ，使 $x^{\text{*}}$ 是原始问题的解， ${\alpha }^{\text{*}},{\beta }^{\text{*}}$ 是对偶问题的解， 并且

$$p^{\text{*}}=d^{\text{*}}=L(x^{\text{*}},{\alpha }^{\text{*}},{\beta }^{\text{*}})$$

KKT 条件

对原始问题和对偶问题，假设函数 $f(x)$ 和 $c_i(x)$ 是凸函数， $h_j(x)$ 是仿射函数， 并且不等式约束 $c_i(x)$ 是严格执行的，则 $x^{\text{*}},{\alpha }^{\text{*}},{\beta }^{\text{*}}$ 被称为是原始问题和对偶问题的解 的充分必要条件是其满足：

\begin{align} \nabla_xL(x^*,\alpha^*,\beta^*)=0 \\ \alpha_i^*c_i(x^*)=0 \\ c_i(x^*)\leq0 \\ \alpha_i^*\geq0 \\ h_j(x^*)=0 \\ \end{align}