优化-6-对偶

带约束的优化问题

在本章中，我们主要考虑一类带约束的优化问题，即

$$\begin{aligned} \textbf{minimize} & \qquad f(x) & \\ \textbf{subject to} & \qquad g_i(x) \leq 0, & i=1,\cdots,m \\ & \qquad h_j(x) = 0, & j=1,\cdots,p \end{aligned}$$

乘子法 Lagrange Multiplier Method

在前面的章节中我的提到，可以使用指示函数来将带约束的优化问题转化为无约束的优化问题。构造指示函数

$$I_{-}(x) = \begin{cases} 0, & x \leq 0 \\ \infty, & x > 0 \end{cases} \qquad I_{0}(x) = \begin{cases} 0, & x = 0 \\ \infty, & x \not= 0 \end{cases}$$

于是原优化目标可以转化为其无约束形式

$$\textbf{minimize} \qquad f(x) + \sum_{i=1}^m I_{-}(g_i(x)) + \sum_{j=1}^p I_{0}(h_j(x))$$

我们可以使用线性函数 来近似 ; 类似地，使用 来近似 。

于是我们得到

$$\textbf{minimize} \qquad f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x)$$

我们称上式为 Lagrangian, 其中 被称为拉格朗日乘子。记

$$L(x, \lambda, \mu) := f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x)$$

通过 最小化 ，得到

$$D(\lambda, \mu) := \inf_x L(x, \lambda, \mu)$$

于是我们得到拉格朗日对偶优化问题

$$\begin{aligned} \textbf{maximize} & \qquad D(\lambda, \mu) & \\ \textbf{subject to} & \qquad \lambda_i \geq 0, & i=1,\cdots,m \\ \end{aligned}$$

由于 且 对任意的 都成立，因此对偶问题的解是原问题的解的下界，并且对偶问题永远是凹的（当 确定后，对偶问题无外乎若干个线性函数的和），因此可以得到一个良好的求解性质。

矩阵分解 Matrix Factorization

一类常见的带约束的优化问题是矩阵分解问题，即

$$\begin{aligned} \textbf{minimize} & \qquad f(UV^T) \\ \textbf{subject to} & \qquad U \in C_U \subseteq \mathbb{R}^{d \times K} \\ & \qquad V \in C_V \subseteq \mathbb{R}^{n \times K} \end{aligned}$$

其中 。

Example: K-means

K-means 聚类也可以被描述为一个矩阵分解问题，即

$$\begin{aligned} \textbf{minimize} & \qquad \| X-UV^T\|_F^2 = \sum_{i,j} (X_{ij} - u_i^T v_j)^2 \\ \textbf{subject to} & \qquad U \in \mathbb{R}^{d \times K} \\ & \qquad V \in \{ V \in \mathbb{R}^{n \times K}_{\geq 0} \mid \sum_j V_{ij}=1, v_k^Tv_h=0\ \textbf{for}\ k\not= h\} \end{aligned}$$

非凸

矩阵分解问题是非凸的。举一个最简单的例子，不妨设 且 ，则优化目标

$$f(u,v) = uv$$

是非凸的，其图像为沿着两个变量的鞍函数。

对偶梯度上升 Dual Gradient Ascent

类似梯度下降法，凹的对偶问题可以使用梯度上升法求解。对于 的约束，使用投影法，因此我们可以得到迭代式

$$\begin{aligned} x_t &= \arg\inf_x L(x, \lambda_t, \mu_t) \\ \lambda_{t+1}^i &= \Phi_{\geq 0}(\lambda_t^i + \gamma g_i(x_t))\\ \mu_{t+1}^j &= \mu_t^j + \gamma h_j(x_t) \end{aligned}$$

作为次梯度算法，其收敛率为

共轭函数 Fenchel Conjugate

定义

我们首先给出共轭函数的定义：

$$f^\star(y) := \sup_{x} \{y^T x - f(x)\}$$

性质

1. 是凸函数（ 可以不是凸的）
2. Fenchel’s Inequality:
3. 可分性：如果 ，则

计算

一些常见的共轭函数如下：

• 二次函数： () $$f^\star(y) = \frac{1}{2}(y-b)^TA^{-1}(y-b) - c$$
• 负熵： $$f^\star(y) = \sum_i e^{y_i-1}$$
• 负对数： $$f^\star(y) = -\sum_i \log(-y_i) - n$$
• 范数： ( 其对偶范数为 ) $$f^\star(y) = \begin{cases} 0, & \|y\|_* \leq 1 \\ \infty, & \textbf{otherwise} \end{cases}$$

一些常见的性质如下：

• 可分性： $$f^\star(y) = f_1^\star(y_1) + f_2^\star(y_2)$$
• 标量乘性： $$\begin{aligned} f(x) = \alpha g(x) & \Longrightarrow & f^\star(y) = \alpha g^\star(y/\alpha) \\ f(x) = \alpha g(x/\alpha) & \Longrightarrow & f^\star(y) = \alpha g^\star(y) \\ \end{aligned}$$

关于共轭函数计算的更多内容可以参考 Conjugate Functions。

Fenchel Duality

如果 是凸函数， 是凹函数，则

$$\min_x f(x) - g(x) = \max_y g^\star(y) - f^\star(y)$$

证明如下，使用拉格朗日对偶性和共轭函数定义：

$$\begin{aligned} \min_x f(x) - g(x) &= \min_{x=z} \left( f(x) - g(z) \right) \\ &= \max_p\min_{x,z} \left( f(x) - g(z) + p^T(z-x) \right) \\ &= \max_p \left( -\max_x ( -f(x) + p^Tx) + \min_z (-g(z) + p^Tz) \right) \\ &= \max_p (-f^\star(p) + g^\star(p)) \\ \end{aligned}$$

Example: Generalized Linear Model

考虑由凸函数 组成的优化目标

$$\min_{x\in \mathbb{R}^d, w\in \mathbb{R}^n} f(w) + g(x) \quad \textbf{s.t.} \quad Ax = w$$

有拉格朗日对偶函数

$$\begin{aligned} \mathcal{L}(u) & = \min_{x\in \mathbb{R}^d, w\in \mathbb{R}^n} f(w) + g(x) + u^T(Ax-w) \\ & = -f^\star(u) - g^\star(-A^Tu) \end{aligned}$$

于是得到对偶问题

$$\max_{u\in \mathbb{R}^d} -f^\star(u) - g^\star(-A^Tu)$$

Example: Lasso

考虑 Lasso 优化目标

$$\min_{x\in \mathbb{R}^d} \frac{1}{2}\|Ax-b\|_2^2 + \lambda \|x\|_1$$

令

$$f(w):= \frac{1}{2}\|w-b\|_2^2 \\ g(x):= \lambda \|x\|_1$$

，则有共轭函数

$$f^\star(u):= \frac{1}{2}\|u-b\|_2^2 - \frac{1}{2}\|b\|_2^2 \\ g^\star(y):= \begin{cases} 0, & \|y\|_\infty \leq \lambda \\ \infty, & \text{otherwise} \end{cases}$$

应用 Fenchel Duality 的 Generalized Linear Model 形式，得到对偶问题

$$\begin{aligned} & \quad \max_{u\in \mathbb{R}^d} -f^\star(u) - g^\star(-A^T u) \\ \Leftrightarrow & \quad \max_{u\in \mathbb{R}^d} -\frac{1}{2}\|u-b\|_2^2 + \frac{1}{2}\|b\|_2^2 \quad \textbf{s.t.} \quad \|-A^Tu\|_\infty \leq \lambda \\ \Leftrightarrow & \quad \min_{u\in \mathbb{R}^d} \|u-b\|_2^2 \quad \textbf{s.t.} \quad \|A^Tu\|_\infty \leq \lambda \end{aligned}$$