最优化理论与方法：弱对偶定理与强对偶定理详解
最优化理论与方法：弱对偶定理与强对偶定理详解
最优化理论是运筹学和数学规划中的一个重要分支，主要研究如何在给定的约束条件下寻找最优解。在最优化问题中，原问题和对偶问题是一对密切相关的概念，它们之间的关系由弱对偶定理和强对偶定理来描述。本文将详细介绍这两个定理及其相关概念。
1. 弱对偶定理
设 $v(P)$ 是原问题 $(P)$ 的最优值，$v(D)$ 是对偶问题 $(D)$ 的最优值，则有：
$$
v(D) \le v(P)
$$
我们知道对于 $f(x)$ 来说，其最小值为 $v(P)$，可得：$v(P) \le f(x)$，因为对于对偶问题 $d(\lambda, \mu)$ 来说，其最大值为 $v(D)$，所以可得：$d(\lambda, \mu) \le v(D)$
整理可得恒等式：
$$
d(\lambda, \mu) \le v(D) \le v(P) \le f(x)
$$
1.1 推论1
假设在原问题的定义域内存在一个 $\bar{x} \in S$，在对偶问题中的定义域内存在一对参数 $(\bar{\lambda}, \bar{\mu})$，$\bar{\lambda} \ge 0$，满足如下条件：
$$
d(\bar{\lambda}, \bar{\mu}) = f(\bar{x})
$$
那么可得，且这个点同时为原问题和对偶问题的最优解：
$$
v(D) = v(P)
$$
解释：因为满足弱对偶定理和前后相等可得：
$$
d(\bar{\lambda}, \bar{\mu}) \le v(D) \le v(P) \le f(\bar{x}), d(\bar{\lambda}, \bar{\mu}) = f(\bar{x}) \to v(D) = v(P)
$$
1.2 推论2
- 如果 $v(P) = -\infty$，则可得 $d(\lambda, \mu) = -\infty, \forall (\lambda, \mu), \lambda \ge 0$
- 如果 $v(D) = +\infty$，则可得 $v(P) = +\infty$，原问题 $P$ 无可行解
2. 对偶间隙
2.1 定义
我们定义对偶间隙表示原问题的最优值减去对偶问题的最优值如下：
$$
\text{duality gap} = v(P) - v(D)
$$
2.2 约束问题
假设我们有如下约束优化问题：
原问题：
$$
\begin{aligned}
&(P) \quad \min {x_1^2 + x_2^2} \
&\text{st.} \quad -x_1 - x_2 \le -\frac{1}{2}, x \in \mathbb{Z}_+^2
\end{aligned}
$$
根据图形可得，当 $x_1 = 0, x_2 = 1$ 时可以得到最小值，则 $v(P) = 1$
拉格朗日函数如下：
$$
d(x, \lambda) = x_1^2 + x_2^2 + \lambda \left(\frac{1}{2} - x_1 - x_2\right)
$$
对偶问题如下：
$$
\max_{\lambda} \min_{(x_1, x_2)} {d(x, \lambda)} = \max_{\lambda} \min_{(x_1, x_2)} \left{x_1^2 + x_2^2 + \lambda \left(\frac{1}{2} - x_1 - x_2\right)\right}
$$
化简如下：
$$
\max_{\lambda} \min_{(x_1, x_2)} {d(x, \lambda)} = \max_{\lambda} \min_{(x_1, x_2)} \left{(x_1 - \frac{\lambda}{2})^2 + (x_2 - \frac{\lambda}{2})^2 + \frac{\lambda}{2} - \frac{\lambda^2}{2}\right}
$$
也就是说，当 $\lambda$ 确定时，内部的最小值指的是坐标点 $P(x_1, x_2)$ 与 $Q\left(\frac{\lambda}{2}, \frac{\lambda}{2}\right)$ 的最短距离，那我们就分类讨论 $\frac{\lambda}{2}$ 在坐标轴哪？
- 当 $\frac{1}{2} < \frac{\lambda}{2} < \frac{3}{2}$ 时，最短的点为 $P = (1, 1)$
$$
\min_{(x_1, x_2)} {d(x, \lambda)} = \min_{(x_1, x_2)} \left{x_1^2 + x_2^2 + \lambda \left(\frac{1}{2} - x_1 - x_2\right)\right} = 2 - \frac{3}{2}\lambda
$$
- 当 $\frac{3}{2} < \frac{\lambda}{2} < \frac{5}{2}$ 时，最短的点为 $P = (2, 2)$
$$
\min_{(x_1, x_2)} {d(x, \lambda)} = \min_{(x_1, x_2)} \left{x_1^2 + x_2^2 + \lambda \left(\frac{1}{2} - x_1 - x_2\right)\right} = 8 - \frac{7}{2}\lambda
$$
- 当 $k - \frac{1}{2} < \frac{\lambda}{2} < k + \frac{1}{2}$ 时，最短的点为 $P = (k, k)$
$$
\min_{(x_1 = k, x_2 = k)} {d(x, \lambda)} = \min_{(x_1 = k, x_2 = k)} \left{2k^2 + \lambda \left(\frac{1}{2} - 2k\right)\right}, k = 1, 2, \cdots, n
$$
将 $k = 1, 2, \cdots, n$ 代入可得，根据 $k - \frac{1}{2} < \frac{\lambda}{2} < k + \frac{1}{2}$
$$
\max_{\lambda} \min_{(x_1, x_2)} {d(x, \lambda)} = \frac{1}{2}
$$
综上所示，$v(D) = \frac{1}{2}, v(P) = 1$，可得：
$$
\text{duality gap} = v(P) - v(D) = 1 - \frac{1}{2} = \frac{1}{2}
$$
3. 强对偶定理
3.1 概述
- 假设：
- 集合 $X$ 为非空凸集，$f(x)$ 及 $g_i(x), i = 1, 2, \cdots, m$ 是凸函数，$h_i(x), i = 1, 2, \cdots, l$ 均为线性函数。
- 假设存在 $\hat{x} \in X$ 使得 $g_i(\hat{x}) < 0, i = 1, \cdots, m, h_i(\hat{x}) = 0, i = 1, \cdots, l$，且
$0 \in \text{int} ; h(X)$，其中 $h(X) = {[h_1(x), h_2(x), \cdots, h_l(x)]^T \mid x \in X}$，则
强对偶成立，即：
$$
\min {f(x) \mid x \in S} = \max {d(\lambda, \mu) \mid \lambda \ge 0, \mu}
$$
- 假设1保证了 $G$ 是一个凸函数集
- 假设2保证了图集 $G$ 在
- $y$
- 处有阴影
- 基于如下讨论最优化理论与方法-第十讲-约束优化，可得原问题 $P$ 的最小值和对偶问题的最大值一致
3.2 证明：
由于 $\hat{x}$ 的存在，则原问题 $(P)$ 有可行解
若 $v(P) = -\infty$，根据弱对偶定理推论可得：$d(\lambda, \mu) = -\infty, \forall (\lambda, \mu), \lambda \ge 0$
若 $v(P) = v$，根据弱对偶定理推论可得：不存在 $x \in X$，使得 $f(x) < v, g_i(x) \le 0, i = 1, \cdots, m, h_i(x) = 0, i = 1, \cdots, l$
定义 $H$ 函数如下：
$$
H = \left{\begin{pmatrix}p\q\r\end{pmatrix} \in \mathbb{R}^{1+m+l} \mid f(x) - v < p, g_i(x) \le q_i, i = 1, \cdots, m; h_i(x) = r_i, i = 1 \cdots, l, x \in X\right}
$$
可知：$H$ 是凸函数，且 $\begin{pmatrix}0\0\0\end{pmatrix} \notin H$，根据凸集分离定理，则
存在
$\begin{pmatrix}\lambda_0\\lambda\\mu\end{pmatrix} \neq 0$，使得：
$$
\begin{pmatrix}\lambda_0\\lambda\\mu\end{pmatrix}^T \begin{pmatrix}p\q\r\end{pmatrix} \ge 0, \forall \begin{pmatrix}p\q\r\end{pmatrix} \in \text{d}(H)
$$
整理可得：$\lambda_0, q$ 为实数，不是向量，不需要转置
$$
\lambda_0 p + \lambda^T q + \mu^T r \ge 0 \to \lambda_0 \ge 0, \lambda_i \ge 0, i = 1, \cdots, m
$$
由图可得对于任意的 $x \in X$ 来说，都在超平面上方，所以可得：
$$
\forall x \in X, \lambda_0 \ge 0, \lambda_0[f(x) - v] + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{i=1}^l \mu_i h_i(x) \ge 0
$$
3.3 证明 $\lambda_0 \neq 0$
- 我们可以设 $\lambda_0 = 0, x = \hat{x}$ 代入可得：
$$
\sum_{i=1}^m \lambda_i g_i(\hat{x}) + \sum_{i=1}^l \mu_i h_i(\hat{x}) \ge 0; g_i(\hat{x}) \le 0, h_i(\hat{x}) = 0
$$
- 只要有一个 $\lambda_i > 0$，那么必然有 $\sum_{i=1}^m \lambda_i g_i(\hat{x}) < 0$，矛盾，所以只能都等于0
$$
\lambda_i = 0
$$
- 代入到通项可得：
$$
\forall x \in X, \sum_{i=1}^l \mu_i h_i(x) \ge 0
$$
- 由于已知 $0 \in \text{int} ; h(X)$，其中 $h(X) = {[h_1(x), h_2(x), \cdots, h_l(x)]^T \mid x \in X}$，则存在一个 $\tilde{x}, \epsilon \to 0$，使得：
$$
\begin{pmatrix} h_1(\tilde{x}) \ \vdots \ h_l(\tilde{x}) \end{pmatrix} = \epsilon \begin{pmatrix} -\mu_1 \ \vdots \ -\mu_l \end{pmatrix}
$$
- 代入可得：
$$
\forall x \in X, \epsilon > 0, -\epsilon \sum_{i=1}^l \mu_i^2 \ge 0 \to \mu_i = 0
$$
- 综上所述可得：
$$
\lambda_0 = 0, \lambda_i = 0, \mu_i = 0 与题目 \begin{pmatrix}0\0\0\end{pmatrix} \notin H, 矛盾，所以 \lambda_0 = 0 是错误的结论
$$
- 可得：
$$
\lambda_0 > 0
$$
- 我们可以整理公式20可得：
$$
[f(x) - v] + \sum_{i=1}^m \frac{\lambda_i}{\lambda_0}g_i(x) + \sum_{i=1}^l \frac{\mu_i}{\lambda_0}h_i(x) \ge 0; \forall x \in X
$$
- 为了方便后续，我们定义 $\frac{\lambda_i}{\lambda_0} = \bar{\lambda_i} \ge 0, \frac{\mu_i}{\lambda_0} = \bar{\mu_i}$
$$
[f(x) - v] + \sum_{i=1}^m \bar{\lambda_i}g_i(x) + \sum_{i=1}^l \bar{\mu_i}h_i(x) \ge 0; \forall x \in X
$$
- 移项可得：
$$
f(x) + \sum_{i=1}^m \bar{\lambda_i}g_i(x) + \sum_{i=1}^l \bar{\mu_i}h_i(x) \ge v; \forall x \in X
$$
- 左边其实就是对偶问题，其中参数为 $\bar{\lambda}, \bar{\mu}$
$$
d(\bar{\lambda}, \bar{\mu}) \ge v = v(P); \forall x \in X
$$
- 因为根据弱对偶定理可得：
$$
d(\lambda, \mu) \le v = v(P); \forall x \in X
$$
- 综上所述可得：
$$
d(\bar{\lambda}, \bar{\mu}) = v(P); 强对偶成立
$$