一、Lagrange 对偶函数

(1) Lagrange

对于标准形式的优化问题：

优化问题的最优解是$p^*$，这里没有假设问题是凸优化问题。

定义该优化问题的Lagrange函数$L :\mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \rightarrow \mathbb{R}$为：

其中：

• $\lambda_i$称为第$i$个不等式约束$f_i(x) \leq 0$对应的Lagrange乘子；
• $v_i$称为第$i$个等式约束$h_i(x) = 0$对应的Lagrange乘子。
• 向量$\lambda$和$v$称为对偶变量或者是优化问题的Lagrange乘子向量

(2) Lagrange 对偶函数

定义Lagrange对偶函数$g : \mathbb{R}^m \times \mathbb{R}^p \rightarrow \mathbb{R}$为Lagrane函数关于$x$取到的最小值：即对$\lambda \in \mathbb{R}^m, v \in \mathbb{R}^p$，有

如果Lagrange函数关于$x$无下界，则对偶函数取值为$-\infty$。由于对偶函数是一簇关于$(\lambda, v)$的仿射函数的逐点下确界，所以对偶函数$g$一定是凹函数。

(3) 最优值下界

对偶函数构成了原问题最优值$p^*$的下界：即对任意$\lambda \succeq 0$和$v$下式成立

设$\tilde{x}$是原问题中的一个可行点，即$f_i(\tilde{x}) \leq 0$且$h_i(\tilde{x}) = 0$。根据假设，$\lambda \succeq 0$，我们有

$$\sum_{i = 1}^m \lambda_i f_i(\tilde{x}) + \sum_{i = 1}^p v_ih_i(\tilde{x}) \leq 0,$$

因此

$$L(\tilde{x}, \lambda, v) = f_0(\tilde{x}) + \sum_{i = 1}^m \lambda_if_i(\tilde{x}) + \sum_{i = 1}^p v_ih_i(\tilde{x}) \leq f_0(\tilde{x})$$

因此

$$g(\lambda, v) = \inf_{x \in \mathcal{D}} L(\tilde{x}, \lambda, v) \leq L(\tilde{x}, \lambda, v) \leq f_0(\tilde{x}).$$

由于每一个可行点$\tilde{x}$都满足$g(\lambda, v) \leq f_0(\tilde{x})$，因此不等式$(3)$成立。

只有当$\lambda \succeq 0$且$(\lambda , v) \in \textbf{dom} g$即$g(\lambda ,v) > - \infty$时，对偶函数才能给出$p^*$的一个非平凡下界。称满足$\lambda \succeq 0$以及$(\lambda , v) \in \textbf{dom} g$的$(\lambda, v)$是对偶可行的。

(4) Lagrange 对偶函数和共轭函数

共轭函数和Lagrange对偶函数紧密相关，考虑问题

该问题的Lagrange函数为$L(x, v) = f(x) + v^Tx$，其对偶函数为

更一般地考虑一个优化问题，具有线性不等式和等式约束，

利用$f_0$的共轭函数，我们可以将优化问题的对偶函数表述为

(5) 例子

1. 标准形式 LP

Lagrange 函数为：

$$\begin{aligned} L(x, \lambda, v) &= c^Tx + v^T(Ax - b) - \lambda^T x\\ &= (c^T + v^TA - \lambda^T)x - v^Tb \end{aligned}$$

因此其对偶函数为：

$$g(\lambda, v) = L(x, \lambda, v) = \begin{cases} -v^Tb, & c^T + v^TA - \lambda^T = 0\\ -\infty, & else \end{cases}$$

$g$在仿射域$\{(\lambda, v) |A^Tv - \lambda^T + c^T = 0\}$上是线性的，因此是凹的。

2. 等式约束范数最小化

3. 两向划分

二、 Lagrange 对偶问题

对于任意一组$(\lambda, v)$，其中$\lambda \succeq 0$，Lagrange 对偶函数给出了原优化问题的最优值$p^*$的一个下界。那么一个自然的问题是：从Lagrange函数能够得到的最好下界是什么？

Lagrange对偶问题可表述为优化问题：

称解$(\lambda^*, v^*)$是对偶最优解或者最优解Lagrange乘子，如果它是对偶问题的最优解。

这是一个凸优化问题，因为极大化的目标函数是凹函数，且约束集合是凸集。

(1) 对偶问题的产生

1. 问题的对偶表述

• 一个问题的等价表述可能导致非常不同的对偶
• 当对偶难以推导或无意义时，重新表述原始问题可能得出有用的对偶问题

2. 常见的重新表述

• 引入新的变量和等式约束
• 将显示约束隐式化或反之
• 替换目标函数或约束函数，例如用凸增函数$\phi(f_0(x))$代替$f_0(x)$

例题1

引入新变量和等式约束

1. 对偶函数是常数：$g = \inf_{x} L(x) = \inf_{x} f_0(Ax + b) = p^*$
2. 具有强对偶性，但对偶问题相当无用

重新表述的问题及其对偶问题：

因此得：

故优化问题为

例题2

范数逼近问题

重新表述的问题及其对偶问题：

因此得：

其中

故优化问题为

例题3

带框约束$LP$问题

用框约束隐式化改写：

对偶函数：

对偶问题：

例题4

找出以下分段线性最小化问题的LP公式和对偶LP：

LP问题是

拉格朗日函数为：

对偶函数为：

因此对偶问题为

(2) 弱对偶性

Lagrange 对偶问题的最优值，我们用$d^*$表示，根据定义这是通过 Lagrange 函数得到的原问题的最优值$p^*$的最好下界。因此我们有下面简单但非常重要的不等式：

这个性质称为弱对偶性。

定义差值$p^* - d^*$是原问题的最优对偶问题。它给出了原问题最优值以及通过 Lagrange 对偶函数所能得到的最好上界之间的差值。

(3) 强对偶性和 Slater 约束准则

如果等式

成立，即最优对偶间隙为零，那么强对偶性成立，说明 Lagrange 对偶函数得到的最好下界是紧的。

对于一般情况，强对偶性不成立。但是如果优化问题是凸问题，即可表述成如下形式：

其中，函数$f_0, \cdots, f_m$是凸函数，强对偶性通常成立。强对偶性成立的条件称为约束准则。

Slater约束准则

对于以下凸问题

如果它是严格可行的，即

强对偶性成立。

三、对偶问题的几何解释

四、相关例题

例题5

因此对偶函数为

问题转化为

1. 根据$Slater$条件：$p^* = d^*$，如果存在$A \tilde{x} \prec d$对于某些$\tilde{x}$
2. 实际上，$p^* = d^*$对于线性规划是基本上成立的，除非原始问题和对偶问题都是不可行的。

例题6

因此对偶函数为

对式子进行求导有：

故最优的$x$关于$\lambda$的表达式为：

因此

问题转化为

1. 根据Slater条件：$p^* = d^*$，如果$A\tilde{x} \prec b$对于某些$\tilde{x}$成立
2. 实际上，$p^* = d^*$总是成立（对于凸二次规划问题，只要原问题可行，则$p^*=d^*$）

五、最优性条件

(1) 次优解认证和终止准则

如果能找到一个对偶可行解$(\lambda, v)$，就对原问题的最优值建立了一个下界：$p^* \geq g(\lambda, v)$。因此对偶可行解点$(\lambda, v)$为表达式$p^* \geq g(\lambda, v)$的成立提供了一个证明或认证。

对偶间隙

定义原问题和对偶问题目标函数的差值：

为原问题可行解$x$和对偶可行解$(\lambda, v)$之间的对偶间隙。一对原对偶问题的可行点$x, (\lambda, v)$将原问题的最优值限制在一个区间上：

区间长度即为对偶间隙。

如果原对偶可行对$x, (\lambda, v)$的对偶间隙为零，即$f_0(x) = g(\lambda, v)$，那么$x$是原问题最优解，且$(\lambda, v)$是对偶问题的最优解。此时我们可以认为$(\lambda, v)$是证明$x$为最优解的一个认证。

非启发式停止准则

设某个算法给出一系列原问题可行解$x^{(k)}$以及对偶问题可行解$(\lambda^{(k)}, v^{(k)})$，$k = 1, 2, \dots,$给定要求的绝对精度$\epsilon_{abs} > 0$，那么停止准则

保证当算法终止时，$x^{(k)}$是$\epsilon_{abs} -$次优。

给定相对精度$\epsilon_{rel} > 0$，可以推导类似的条件保证$\epsilon-$次优。如果

成立，或者

成立，那么$p^* \neq 0$，且可以保证相对误差

小于等于$\epsilon_{rel}$。

(2) 互补松弛性

设原问题和对偶问题的最优值都可以达到且相等，令$x^*$是原问题的最优解，$(\lambda^*, v^*)$是对偶问题的最优解，这表明

重要结论 —— 互补松弛性

该性质对任意原问题最优解$x^*$以及对偶问题最优解$(\lambda^*, v^*)$都成立。我们可以把互补松弛条件写成

或

这个式子意味着在最优点处，除了第$i$个约束起作用的情况，最优Lagrange乘子的第$i$项都为零。

(3) KKT最优性条件

现在假设函数$f_0, \dots, f_m, h_1, \dots, h_p$是可微的，但是并不假设这些是凸函数。

以下四个条件称为 KKT 条件

1. 原问题可行性： $f_i(x) \leq 0, h_i(x) = 0$
2. 对偶问题可行性：$\lambda \succeq 0$
3. 互补松弛性条件：$\lambda_if_i(x) = 0$
4. 一阶最优条件：$\nabla f_0(x) + \sum_{i = 1}^m \lambda_i \nabla f_i(x) + \sum_{i = 1}^p v_i \nabla h_i(x) = 0$

1. 非凸问题的KKT条件

令$x^*$是原问题的最优解，$(\lambda^*, v^*)$是对偶问题的最优解，对偶间隙为0。因为$L(x, \lambda^*, v^*)$关于$x$求极小在$x^*$处取得最小值，因此函数在$x^*$处的导数必须为零，即：

因此有

我们称上式为Karush-Kuhn-Tucker(KKT)条件。

2. 凸问题的KKT条件

当原问题是凸问题时，满足KKT条件的点也是原、对偶最优解。即如果函数$f_i$是凸函数，$h_i$是仿射函数，$\tilde{x}, \tilde{\lambda}, \tilde{v}$是任意满足KKT条件的点，则他们是最优的：

1. 从互补松弛性和原问题可行性：$f_0(\tilde{x}) = L(\tilde{x}, \tilde{\lambda}, \tilde{\mu})$
2. 从第四个条件（以及凸性）：$g(\tilde{\lambda}, \tilde{\mu}) = L(\tilde{x}, \tilde{\lambda}, \tilde{\mu})$

因此$f_0(\tilde{x}) = g(\tilde{\lambda}, \tilde{\mu})$

• 反过来，如果满足slater条件，$x$是最优的当且仅当存在$\lambda, v$满足KKT条件（slater条件意味着强对偶性，并且对偶最优解被达到）
• 本质上，KKT条件推广了无约束问题的最优条件$\nabla f_0(x) = 0$

对于一般的非凸问题，KKT条件只是必要条件，类似无约束优化中的

$$\nabla f_0(x) = 0$$

只表示可能是极值点，不保证是最优点。

但是对于凸问题，则满足KKT条件的点一定是最优点。

六、KKT 条件应用

题目1

写出$KKT$ 条件有：

$$x^* \succeq 0, \quad 1^Tx = 1, \quad \lambda^* \succeq 0, \quad \lambda_i^*x_i^* = 0\\ -\frac{1}{\alpha_i + x_i^*} - \lambda_i^* + v^* = 0$$

因此约掉$\lambda^*$后有：

$$x^* \succeq 0, \quad 1^Tx = 1\\ x_i^*(v^* - \frac{1}{\alpha_i + x_i^*}) = 0, i = 1, \dots, n\\ v^* \geq \frac{1}{\alpha_i + x_i^*}, i = 1, \dots, n$$

针对第四个式子，进行讨论：

若$v^* - \frac{1}{\alpha_i} < 0$，则$x^* > 0$，同时$x_i^* = \frac{1}{v^*} - \alpha_i$

若$v^* - \frac{1}{\alpha_i} \geq 0$，那么$x^* \leq 0$，因此$x^* = 0$

故$x_i^* = \max\{0, \frac{1}{v^*} - \alpha_i \}$

结合$1^Tx^* = 1$，确定$v$的最优值，即

$$\sum_{i = 1}^n \max\{0, \frac{1}{v^*} - \alpha_i \} = 1$$

题目2

利用 KKT 条件找到下列集合中最接近$(0, 0)$的点。

该问题可转化为：

$$\begin{aligned} \min & \quad x_1^2 + x_2^2\\ s.t. & \quad x_1 + x_2 \geq 4\\ & \quad 2x_1 + x_2 \geq 5 \end{aligned}$$

拉格朗日函数为：

$$L(x_1, x_2, \lambda_1, \lambda_2) = x_1^2 + x_2^2 + \lambda_1^T(4 - x_1 - x_2) + \lambda_2^T(5 - 2x_1 - x_2)$$

因此 KKT 条件是：

1. 原问题可行性：$4 - x_1 - x_2 \leq 0, \quad 5 - 2x_1 - x_2 \leq 0$
2. 对偶问题可行性：$\lambda_1 \geq 0, \lambda_2 \geq 0$
3. 互补松弛性：$\lambda_1^T(4 - x_1 - x_2) = 0, \quad \lambda_2^T(5 - 2x_1 - x_2) = 0$
4. 一阶最优条件：$2x_1 - \lambda_1^T - 2 \lambda_2^T = 0, \quad 2x_2 - \lambda_1 - \lambda_2 = 0$

分四种情况讨论：

1. $\lambda_1 = \lambda_2 = 0$，因此根据第三个条件可得$x_1 = x_2 = 0$，违背原问题可行性

2. $\lambda_1 = 0, \lambda_2 > 0$，因此$2x_1 + x_2 - 5 = 0$，$x_1 = \lambda_2. x_2 = \frac{\lambda_2}{2}$。

   因此可算得$\lambda_2 = 2， x_1 = 2， x_2 = 1$.原问题仍不可行。

3. $\lambda_2 = 0, \lambda_1 > 0$。

   因此$x_1 + x_2 = 4, \quad x_1 = \frac{\lambda_1}{2}, \quad x_2 = \frac{\lambda_1}{2}$

   可算得：$\lambda_1 = 4, x_1 = x_2 = 2$。满足所有条件，故一个 KKT 点为$(2, 2, 4, 0)$

4. $\lambda_1 > 0, \lambda_2 > 0$.

   因此$x_1 + x_2 = 4, \quad 2x_1 + x_2 = 5$，故$x_1 = 1, x_2 = 3$。

   进一步有$\lambda_1 = 10, \lambda_2 = -4$，违反对偶问题可行性

题目3 下面是一个强对偶性成立的非凸优化问题，如何找到最优解，唯一吗？

求拉格朗日函数为：

$$\begin{aligned} L(x_1, x_2, \lambda_1, \lambda_2) = -2(x_1 - 2)^2 - x_2^2 + \lambda_1(x_1^2 + x_2^2 - 25) - \lambda_2 x_1 \end{aligned}$$

因此 KKT 条件为：

1. 原问题可行性：$x_1^2 + x_2^2 - 25 \leq 0, \quad -x_1 \leq 0$
2. 对偶问题可行性：$\lambda_1 \geq 0, \lambda_2 \geq 0$
3. 互补松弛性：$\lambda_1(x_1^2 + x_2^2 - 25) = 0, \quad -\lambda_2x_1 = 0$
4. 一阶最优条件：$-4x_1 + 8 + 2\lambda_1 x_1 - \lambda_2 = 0, \quad -2x_2 + 2\lambda_1 x_2 = 0$

分四种情况进行讨论：

1. $\lambda_1 = \lambda_2 = 0$。

   因此$x_2 = 0, x_1 = 2$，成立，值为$0$

2. $\lambda_1 = 0, \lambda_2 > 0$。

   因此$x_1 = 0$，$\lambda_2 = 8, x_2 = 0$，成立，值为$-8$

3. $\lambda_2 = 0, \lambda_1 > 0$

   有两个解：$(5, 0, \frac{6}{5}, 0)$，值为$-18$；$(4, \pm 3, 1, 0)$，值为$-17$

4. $\lambda_1 > 0, \lambda_2 > 0$

   故$x_1 = 0, x_2 = \pm 5$，因此$\lambda_1 = 1, \lambda_2 = 8$，值为$-33$

综上，最优解为$(0, \pm 5)$，取得最小值为$-33$

题目4 已知下面是一个强对偶性成立的非凸优化问题。分析最优解（充分或必要）条件，以及如何寻找其最优解，可以存在多个最优解吗？

求拉格朗日函数为：

$$L(x_1, x_2, x_3, v) = -3 x_1^2 + x_2^2 + 2x_3^2 + 2(x_1 + x_2 +x_3) + v(1 - x_1^2 - x_2^2 - x_3^2)$$

因此$KKT$ 条件为：

1. 原问题可行性：$x_1^2 + x_2^2 + x_3^2 - 1 = 0$

2. 对偶问题可行性：无

3. 互补松弛性：无

4. 一阶最优条件：

   $$\begin{aligned} -6x_1 + 2 - 2vx_1 = 0\\ 2x_2 + 2 - 2vx_2 = 0\\ 4x_3 + 2 - 2vx_3 = 0 \end{aligned}$$

因此

$$\frac{1}{(v + 3)^2} + \frac{1}{(v - 1)^2} + \frac{1}{(v - 2)^2} = 1$$

解得$v_1 = -3.15, v_2 = 0.22, v_3 = 1.89, v_4 = 4.04$。

四个解对应的$x$值为：……

题目 5 求解一下优化问题

求拉格朗日函数为：

$$L(x, y, \lambda_1, \lambda_2) = (x - 1)^2 + (y - 2)^2 + \lambda_1(x - y) + \lambda_2(x + 2y - 2)$$

因此 KKT 条件为

1. 原问题可行性：$x - y \leq 0, \quad x + 2y - 2 \leq 0$
2. 对偶问题可行性：$\lambda_1 \geq 0, \lambda_2 \geq 0$
3. 互补松弛性：$\lambda_1(x - y) = 0, \lambda_2(x + 2y - 2) = 0$
4. 一阶最优条件：$2x - 2 + \lambda_1 + \lambda_2 = 0, 2y - 4 - \lambda_1 + 2\lambda_2 = 0$

讨论：

1. $\lambda_1 = \lambda_2 = 0$，因此$x = 1, y = 2$，原问题可行性不满足
2. $\lambda_1 = 0, \lambda_2 > 0$，因此$x = \frac{2}{5}, y = \frac{4}{5}, \lambda_2 = \frac{6}{5}$
3. $\lambda_1 > 0, \lambda_2 = 0$，因此$x = y = \frac{3}{2}, \lambda_1 = -1$，不满足
4. $\lambda_1 > 0, \lambda_2 > 0$，因此$x = y = \frac{3}{2}, \lambda_1 = -\frac{4}{9}, \lambda_2 = \frac{10}{9}$，不满足

故唯一解为$(\frac{2}{5}, \frac{4}{5})$。最优值为$\frac{9}{5}$