对偶理论
对于一般的约束优化问题:
$$ \begin{aligned} \min \quad & f(x) \\ \text{s.t.} \quad & c_i(x) \leq 0, \quad i \in \mathcal{I} \\ & c_i(x) = 0, \quad i \in \mathcal{E} \end{aligned} $$Lagrange 函数为:
$$ L(x, \lambda, \nu) = f(x) + \sum_{i \in \mathcal{I}} \lambda_i c_i(x) + \sum_{i \in \mathcal{E}} \nu_i c_i(x) $$其中 $\lambda_i \ge 0$.
定义
Lagrange 对偶函数 $g: \mathbb{R}_+^m \times \mathbb{R}^p \to [-\infty, +\infty)$ 定义为:
$$ g(\lambda, \nu) = \inf_{x \in \mathbb{R}^n} L(x, \lambda, \nu) $$定理弱对偶原理
若 $\lambda \ge 0$, 则 $g(\lambda, \nu) \le p^\ast$.
证明
对 $x_0 \in \mathcal{X}$, 有:
$$ g(\lambda, \nu) = \inf_{x \in \mathbb{R}^n} L(x, \lambda, \nu) \le L(x_0, \lambda, \nu) \le f(x_0) $$对 $x_0$ 取 $\inf$ 得到
$$ g(\lambda, \nu) \le \inf_{x \in \mathcal{X}} f(x) = p^\ast $$定义
Lagrange 对偶问题 形式如下:
$$ \max_{\lambda \ge 0, \nu} g(\lambda, \nu)= \max_{\lambda \ge 0, \nu} \inf_{x \in \mathbb{R}^n} L(x, \lambda, \nu) $$称 $\lambda, \nu$ 为对偶变量, 设最优值为 $q^\ast$. $q^\ast$ 是 $p^\ast$ 的最优下界, 称 $p^\ast-q^\ast$ 为 对偶间隙.
示例: 线性规划问题
$$ \begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \ge 0 \end{aligned} $$Lagrange 函数为:
$$ \begin{aligned} L(x, \lambda, \nu) &= c^T x + \lambda^T (Ax - b) - \nu^T x \\ &= -b^T \lambda + (c + A^T \lambda - \nu)^T x \end{aligned} $$对偶函数:
$$ g(\lambda, \nu) = \inf_{x \ge 0} L(x, \lambda, \nu) = \begin{cases} -b^T \lambda, & c + A^T \lambda - \nu = 0 \\ -\infty, & \text{otherwise} \end{cases} $$对偶问题:
$$ \begin{aligned} \max \quad & -b^T \lambda \\ \text{s.t.} \quad & c + A^T \lambda - \nu = 0 \\ & \nu \ge 0 \end{aligned} $$可以计算证明, 线性规划问题和对偶问题互为对偶.
示例: 范数最小化问题
$$ \begin{aligned} \min \quad & \|x\| \\ \text{s.t.} \quad & Ax = b \end{aligned} $$对偶函数:
$$ g(\nu) = \inf_x(\|X\| - \nu^T (Ax - b)) = \begin{cases} b^T\nu, & \|A^T \nu\|_* \le 1 \\ -\infty, & \text{otherwise} \end{cases} $$其中 $\|v\|_*=\sup_{\|x\|\le 1} x^T v$ 为 $v$ 的对偶范数 (关于为什么自证). 因此对偶问题:
$$ \begin{aligned} \max \quad & b^T \nu \\ \text{s.t.} \quad & \|A^T \nu\|_* \le 1 \end{aligned} $$示例: 最大割问题
上回说到, 最大割问题可以写成:
$$ \begin{aligned} \max \quad & x^T W x \\ \text{s.t.} \quad & x_i^2 = 1 \end{aligned} $$首先加负号变成 $\min$, Lagrange 函数为:
$$ \begin{aligned} L(x, y) &= -x^T W x + \sum_{i=1}^n y_i (x_i^2 - 1) \\ &= x^T(\text{diag}(y) - W) x - \mathbf{1}^T y \end{aligned} $$对偶函数:
$$ g(y) = \inf_x L(x, y) = \begin{cases} -\mathbf{1}^T y, & \text{diag}(y) - W \succeq 0 \\ -\infty, & \text{otherwise} \end{cases} $$对偶问题:
$$ \begin{aligned} \max \quad & -\mathbf{1}^T y \\ \text{s.t.} \quad & \text{diag}(y) - W \succeq 0 \end{aligned} $$再来考虑这个对偶问题的对偶问题.
对偶函数:
$$ \begin{aligned} g(X)&=\inf_y(\mathbf{1}^Ty) - \left<\text{diag}(y) - W, X\right> \\ &= \inf \left(\sum_{i=1}^n (1-X_{ii})y_i + \left< W, X \right> \right) \\ &= \begin{cases} \left< W, X \right>, & X_{ii} = 1, i = 1, \ldots, n \\ -\infty, & \text{otherwise} \end{cases} \end{aligned} $$对偶问题:
$$ \begin{aligned} \max \quad & \left< W, X \right> \\ \text{s.t.} \quad & X_{ii} = 1, i = 1, \ldots, n \\ & X \succeq 0 \end{aligned} $$示例: 共轭函数
$$ \begin{aligned} \min \quad & f(x) \\ \text{s.t.} \quad & Ax \le b \\ & Cx = d \end{aligned} $$对偶函数:
$$ \begin{aligned} g(\lambda, \nu) &= \inf_x(f(x) + \lambda^T (Ax - b) + \nu^T (Cx - d)) \\ &=\inf_x(f(x) + (A^T \lambda + C^T \nu)^T x - b^T \lambda - d^T \nu) \\ &=-f^\ast(-A^T \lambda - C^T \nu) - b^T \lambda - d^T \nu \end{aligned} $$其中 $f^\ast(v) = \sup_x(x^T v - f(x))$ 为 $f$ 的共轭函数.
对偶性
定义
- 弱对偶性: $d^\ast \le p^\ast$. 对一般约束优化问题成立.
- 强对偶性: $d^\ast = p^\ast$, 且若一个线性规划问题有最优解, 则其对偶问题有最优解, 且最优值相等. 一般不成立, 但通常对凸优化问题成立.
称保证凸问题强对偶性成立的条件为 约束品性.
考虑下面这个不满足强对偶性的例子.
$$ \begin{aligned} \min \quad & x_0-x_1 \\ \text{s.t.} \quad & x_0 \ge \sqrt{x_1^2+1} \end{aligned} $$显然, $x_0-x_1 > 0$, 但当 $x_0 \to \infty$ 时, $x_0-x_1 \to 0$, 因此 $p^\ast = 0$, 但是不可达. 而对偶问题是:
$$ \begin{aligned} \max \quad & \lambda \\ \text{s.t.} \quad & 1 \ge \sqrt{1 + \lambda^2} \end{aligned} $$因此 $\lambda \le 0$, $d^\ast = 0$. 虽然 $d^\ast = p^\ast$, 但原问题是没有最优解的.
当然, 也有使得 $p^\ast \ne d^\ast$ 的例子.
改写问题形式
当对偶问题难以推导或没有价值时, 可以尝试改写原问题的形式.
- 引入新变量与等式约束;
- 将显式约束隐式化或将隐式约束显式化;
- 改变目标函数或者约束函数的形式. 例如, 用 $\phi(f(x))$ 取代 $f(x)$, 其中 $\phi$ 是凸的增函数.
先来看几个引入等式约束的例子.
示例: 函数值最小化问题
$$ \min f(Ax+b) $$直接做对偶是常数, 没有意义. 可以改写为:
$$ \begin{aligned} \min \quad & f(y) \\ \text{s.t.} \quad & y = Ax + b \end{aligned} $$对偶问题:
$$ \begin{aligned} \max \quad & b^T \nu-f^\ast(\nu) \\ \text{s.t.} \quad & A^T \nu = 0 \end{aligned} $$示例: 范数逼近问题
$$ \min \|Ax-b\|_2 $$改写成:
$$ \begin{aligned} \min \quad & \|y\| \\ \text{s.t.} \quad & y = Ax - b \end{aligned} $$对偶函数:
$$ \begin{aligned} g(\nu) &= \inf_{x,y}(\|y\| + \nu^Ty - \nu^TAx + \nu^Tb) \\ &= \begin{cases} \nu^T b + \inf_y(\|y\| + \nu^Ty), & A^T \nu = 0 \\ -\infty, & \text{otherwise} \end{cases} \\ &= \begin{cases} \nu^T b, & A^T \nu = 0, \|\nu\|_* \le 1 \\ -\infty, & \text{otherwise} \end{cases} \end{aligned} $$对偶问题:
$$ \begin{aligned} \max \quad & \nu^T b \\ \text{s.t.} \quad & A^T \nu = 0 \\ & \|\nu\|_* \le 1 \end{aligned} $$示例: L1 正则化问题
$$ \min_{x\in \mathbb{R}^n} \frac{1}{2}\|Ax-b\|^2 + \mu \|x\|_1 $$改写成:
$$ \begin{aligned} \min \quad & \frac{1}{2}\|r\|^2 + \mu \|x\|_1 \\ \text{s.t.} \quad & r = Ax - b \end{aligned} $$对偶函数:
$$ \begin{aligned} g(\nu) &= \inf_{x,r}\left(\frac{1}{2}\|r\|_2^2 + \mu \|x\|_1 + \lambda^T(r-Ax+b)\right) \\ &= \inf_{x,r}\left(\frac{1}{2}\|r\|^2 + \lambda^Tr + \mu \|x\|_1 - (A^T\lambda)^Tx + b^T\lambda\right) \\ &= \begin{cases} b^T \lambda - \frac{1}{2} \| \lambda \|^2, & \| A^T \lambda \|_{\infty} \le \mu \\ -\infty, & \text{otherwise} \end{cases} \end{aligned} $$对偶问题:
$$ \begin{aligned} \max \quad & b^T \lambda - \frac{1}{2} \| \lambda \|^2 \\ \text{s.t.} \quad & \| A^T \lambda \|_{\infty} \le \mu \end{aligned} $$现在考虑显式和隐式约束转化的例子.
示例: 带边界约束的线性规划问题
$$ \begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & -\mathbf{1} \le x \le \mathbf{1} \end{aligned} $$我们把边界要求隐藏在目标函数中:
$$ \begin{aligned} \min \quad & f(x) =\begin{cases} c^T x, & -\mathbf{1} \le x \le \mathbf{1} \\ +\infty, & \text{otherwise} \end{cases} \\ \text{s.t.} \quad & Ax = b \end{aligned} $$对偶函数:
$$ \begin{aligned} g(\nu) &= \inf_{-\mathbf{1} \le x \le \mathbf{1}}(c^Tx+\nu^T(Ax-b)) \\ &= -b^T \nu - \|A^T \nu + c\|_1 \end{aligned} $$对偶问题:
$$ \begin{aligned} \max \quad & -b^T \nu - \|A^T \nu + c\|_1 \\ \text{s.t.} \quad & \nu \ge 0 \end{aligned} $$示例: 广义不等式约束优化问题
$$ \begin{aligned} \min \quad & f(x) \\ \text{s.t.} \quad & c_i(x) \preceq_{K_i} 0, \quad i \in \mathcal{I} \\ & c_i(x) = 0, \quad i \in \mathcal{E} \end{aligned} $$其中对于 $i \in \mathcal{I}$, $c_i: \mathbb{R}^n \to \mathbb{R}^{k_i}$ 是向量值函数, $K_i$ 是适当锥. 对于 $i \in \mathcal{E}$, $c_i: \mathbb{R}^n \to \mathbb{R}$ 是标量函数. 实际上这种情况下, 其 Lagrange 函数为:
$$ L(x, \lambda, \nu) = f(x) + \sum_{i \in \mathcal{I}} \left<\lambda_i, c_i(x)\right> + \sum_{i \in \mathcal{E}} \nu_i c_i(x), \quad \lambda_i \in K_i^\ast $$这里 $K_i^\ast$ 是 $K_i$ 的对偶锥. 此时也依然满足 $L(x, \lambda, \nu) \le f(x)$. 对偶问题依然是 $\max_{\lambda \in K_i^\ast, \nu} g(\lambda, \nu)$.
示例: 半定规划问题
$$ \begin{aligned} \min \quad & \left< C, X \right> \\ \text{s.t.} \quad & \left< A_i, X \right> = b_i, \quad i = 1, \ldots, m \\ & X \succeq 0 \end{aligned} $$对偶函数:
$$ \begin{aligned} g(\lambda, \nu) &= \inf_X \left( \left< C, X \right> + \sum_{i=1}^m \lambda_i (\left< A_i, X \right> - b_i) - \left<\nu,X\right> \right) \\ &= \begin{cases} b^T\lambda, & \sum_{i=1}^m \lambda_i A_i - C +\nu \succeq 0 \\ -\infty, & \text{otherwise} \end{cases} \end{aligned} $$对偶问题:
$$ \max \quad b^T\lambda \\ \text{s.t.} \quad \sum_{i=1}^m \lambda_i A_i - C +\nu \succeq 0 $$可以证明, 半定规划问题和对偶问题互为对偶.
带约束凸优化问题的最优性理论
综合来看, 前面的问题其实都可以写成如下的形式:
$$ \begin{aligned} \min \quad & f(x) \\ \text{s.t.} \quad & Ax = b \\ & c_i(x) \le 0, i=1, \ldots, m \end{aligned} $$其中 $f(x)$ 为适当的凸函数, $c_i(x)$ 也是凸函数且 $\text{dom} c_i = \mathbb{R}^n$.
定义
给定集合 $\mathcal{D}$, 设其仿射包为 $\text{affine} \mathcal{D}$, 则其 相对内点集 定义为:
$$ \text{relint} \mathcal{D} = \{x \in \mathcal{D} \mid \exists r > 0, B(x,r) \cap \text{affine} \mathcal{D} \subset \mathcal{D}\} $$定义
若对于凸优化问题
$$ \begin{aligned} \min \quad & f(x) \\ \text{s.t.} \quad & Ax = b \\ & c_i(x) \le 0, i=1, \ldots, m \end{aligned} $$存在 $x \in \text{relint} \mathcal{D}$, 使得
$$c_i(x) < 0, i=1, \ldots, m$$则称对于该问题 Slater 约束品性 成立. 该品性也称为 Slater 条件.
注意: 如果某个不等式约束是仿射函数时, Slater 可以对这个不等式约束放宽到 $c_i(x) \le 0$.
定理
若 Slater 约束品性成立, 则强对偶性成立.
证明
这里假设 $\mathcal{D}$ 内部非空, $A$ 是行满秩的 (否则可以去掉冗余约束), $p^\ast$ 是有限的. 要证明当 $d^\ast > -\infty$ 时, 存在对偶可行解 $(\lambda^\ast, \nu^\ast)$ 使得 $g(\lambda^\ast, \nu^\ast) = d^\ast=p^\ast$.
定义集合
$$ \begin{aligned} \mathbb{A}&= \{(u,v,t) \mid \exists x \in \mathcal{D}, c_i(x) \le u_i (i=1, \ldots, m), Ax-b=v, f(x) \le t\} \\ \mathbb{B}&= \{(0,0,s) \mid s \le p^\ast\} \end{aligned} $$若 $(0,0,t) \in \mathbb{A} \cap \mathbb{B}$, 则 $f(x) \le t< p^\ast$ 矛盾. 因而两集合不交. 由于两者都是凸集, 由超平面分离定理, 存在 $(\lambda, \nu, \mu) \ne 0$ 和 $\alpha$ 使得
$$ \begin{aligned} \lambda^Tu + \nu^Tv + \mu t &\ge \alpha, \quad \forall (u,v,t) \in \mathbb{A} \\ \lambda^Tu + \nu^Tv + \mu t &\le \alpha, \quad \forall (u,v,t) \in \mathbb{B} \end{aligned} $$显见, $\lambda \ge 0, \mu \ge 0$, 否则可以让 $\mu_i, t \to +\infty$ 使得集合 $\mathbb{A}$ 上不等式左侧无下界. 由 $\mathbb{B}$ 的不等式, 立得 $\mu p^\ast \le \alpha$.
对于 $(u,v,t)=(c_i(x), Ax-b, f(x))$, 代入有
$$ \sum_{i=1}^m \lambda_i c_i(x) + \nu^T(Ax-b) + \mu f(x) \ge \alpha \ge \mu p^\ast $$若 $\mu > 0$, 则上式恰好对应 Lagrange 函数:
$$ L(x, \frac{\lambda}{\mu}, \frac{\nu}{\mu}) \ge p^\ast $$故 $g(\frac{\lambda}{\mu}, \frac{\nu}{\mu}) \ge p^\ast$, 再结合弱对偶性, $g(\frac{\lambda}{\mu}, \frac{\nu}{\mu}) = p^\ast$. 则此情况下强对偶性成立, 且最优解可达.
若 $\mu=0$, 可以得到对于所有 $x \in \mathcal{D}$, 有
$$ \sum_{i=1}^m \lambda_i c_i(x) + \nu^T(Ax-b) \ge 0 $$令 $x_S$ 为满足 Slater 条件的点, $Ax_S=b, c_i(x_S) < 0$, 但 $\lambda \ge 0$ 则必须 $\lambda = 0$. 因此
$$ \nu^T(Ax-b) \ge 0, \quad \forall x \in \mathcal{D} $$$x_S$ 恰好是谷底的 $0$, 四周全部都 $\ge 0$ 不太可能. 更具体地, 由于 $(\lambda, \nu, \mu) \ne 0$, 则 $\nu \ne 0$. $A$ 是行满秩的, 则 $A^T \nu \ne 0$, 因为 $x_S \in \text{int}\mathcal{D}$, 则存在微扰 $e$ 使得
$$\widetilde{x} = x_S + e \in \mathcal{D}, \quad v^TAe < 0$$但是
$$ v^TAe = v^TA(\widetilde{x}-x_S) = v^T(A\widetilde{x} - b) \ge 0$$矛盾. 因此 $\mu > 0$, 强对偶性成立.
现在假设 Slater 成立, $x^\ast, \lambda^\ast$ 是原问题和对偶问题的最优解. 由强对偶性,
$$ \begin{aligned} f(x^\ast) = g(\lambda^\ast) &= \inf_{x} f(x) + \sum_{i \in \mathcal{I}} \lambda_i c_i(x) + \sum_{i \in \mathcal{E}} \lambda_i c_i(x) \\ &\le f(x^\ast) + \sum_{i \in \mathcal{I}} \lambda_i c_i(x^\ast) + \sum_{i \in \mathcal{E}} \lambda_i c_i(x^\ast) \\ &\le f(x^\ast) \end{aligned} $$因此等号要成立, 即 $\lambda_i c_i(x^\ast) = 0, i \in \mathcal{I}$, 这称为互补条件 (complementary slackness).
定理凸优化问题的一阶充要条件
对于凸优化问题, 用 $a_i$ 表示矩阵 $A^T$ 的第 $i$ 列, 如 果 Slater 条件成立, 那么$x^\ast, \lambda^\ast$ 分别是原始, 对偶全局最优解当且仅当
- 稳定性条件: $ 0 = \nabla f(x^\ast) + \sum_{i \in \mathcal{I}} \lambda_i^\ast \nabla c_i(x^\ast) + \sum_{i \in \mathcal{E}} \lambda_i^\ast a_i$
- 原始可行性条件: $Ax^\ast = b, i \in \mathcal{E}; c_i(x^\ast) \le 0, i \in \mathcal{I}$
- 对偶可行性条件: $\lambda_i^\ast \ge 0, i \in \mathcal{I}$
- 互补松弛条件: $\lambda_i^\ast c_i(x^\ast) = 0, i \in \mathcal{I}$
证明
必要性已知, 只证明充分性.
考虑 Lagrange 函数
$$ L(x, \lambda) = f(x) + \sum_{i \in \mathcal{I}} \lambda_i c_i(x) + \sum_{i \in \mathcal{E}} \lambda_i (a_i^T x - b_i) $$固定 $\lambda = \bar{\lambda}$, 易见 $L$ 是关于 $x$ 的凸函数. 由凸函数全局最优点的一阶充要性可知, 此时 $\bar{x}$ 就是全局的极小点. 由 Lagrange 对偶函数的定义, 有
$$ L(\bar{x}, \bar{\lambda}) = \inf_x L(x, \bar{\lambda}) = g(\bar{\lambda}) $$又由原始可行性条件和互补松弛条件, 有
$$ L(\bar{x}, \bar{\lambda}) = f(\bar{x}) $$由弱对偶性
$$ L(\bar{x}, \bar{\lambda}) = f(\bar{x}) \ge p^\ast\ge d^\ast \ge g(\bar{\lambda}) = L(\bar{x}, \bar{\lambda}) $$因此等号成立, $p^\ast = d^\ast$, 强对偶性成立, $\bar{x}, \bar{\lambda}$ 是全局最优解.
例子: 仿射空间的投影问题
$$ \begin{aligned} \min \quad & \|x - y\|^2 \\ \text{s.t.} \quad & Ax = b \end{aligned} $$Lagrange 函数为
$$ L(x, \lambda) = \|x - y\|^2 + \lambda^T(Ax - b) $$Slater 条件成立, 由一阶充要条件, 有
$$ \begin{aligned} x^\ast - y + A^T \lambda^\ast &= 0 \\ Ax^\ast &= b \end{aligned} $$解之
$$ \begin{aligned} \lambda^\ast &= (AA^T)^{-1}(Ay-b) \\ x^\ast &= y - A^T(AA^T)^{-1}(Ay-b) \end{aligned} $$显然, $x^\ast$ 是 $y$ 在 $Ax=b$ 上的投影.
例子: 基追踪问题
$$ \begin{aligned} \min \quad & \|x\|_1 \\ \text{s.t.} \quad & Ax = b \end{aligned} $$这个函数实际是不光滑的. 把 $x$ 写作 $x^+-x^-$, 再令 $y=[x^+, x^-]$, 等价于
$$ \begin{aligned} \min \quad & \mathbf{1}^T y \\ \text{s.t.} \quad & [A, -A] y = b \\ & y \ge 0 \end{aligned} $$按照 KKT 条件, 有
$$ \begin{aligned} \mathbf{1} + [A, -A]^T \lambda^\ast - \nu^\ast &= 0 \\ [A, -A] y^\ast &= b \\ y^\ast &\ge 0 \\ \nu^\ast &\ge 0 \\ \nu^\ast \odot y^\ast &= 0 \end{aligned} $$直接推导也得到相应结果, 二者实际上是等价的. (利用 $x^\ast=y_i^\ast-y_{i+n}^\ast$, 代入验证最优点处方向导数为 $0$ 即可)
最优化问题解的存在性
定理推广的 Weierstrass 定理
如果函数 $f: \mathcal{X} \to (-\infty, +\infty]$ 适当且闭, 且以下条件中至少一个成立:
- $\text{dom} f = \{ x\in \mathcal{X}: f(x) < +\infty \} $ 是有界的;
- 存在一个常数 $\bar{\g `2amma}$ 使得下水平集 $C_{\bar{\gamma}} = \{ x \in \mathcal{X}: f(x) \le \bar{\gamma} \}$ 是非空且有界的;
- $f$ 是强制的, 即对于任一满足 $\| x^k \| \to +\infty$ 的点列 $\{ x^k \} \subset \mathcal{X}$, 都有 $\lim_{k \to \infty} f(x^k) = +\infty$
则函数 $f$ 的最小值点集 $\{x \in \mathcal{X} \mid f(x) \le f(y), \forall y \in \mathcal{X}\}$ 非空且紧.
证明
第二个: 又有