7.2约束优化和Lagrange乘子

7.2 约束优化和 Lagrange 乘子

在前一节中，我们讨论了如何求解函数的最小化问题：

其中 f: \mathbb{R}^{D} \rightarrow \mathbb{R}。但在本节中，我们得面对额外的“约束条件”，具体来说，对于实值函数 g_i: \mathbb{R}^{D} \rightarrow \mathbb{R}（i=1,\ldots, m），我们考虑如下的约束优化问题（如图 7.4）：

这里有个值得注意的细节：函数 f 和 g_i 在一般情况下可能非凸（non-convex），不过别急，我们将在下一节讨论凸优化这个“乖孩子”。

一种直观但不太实用的方法是使用 示性函数（indicator function） 将约束问题 (7.17) 转化为无约束形式：

其中

这招儿就像给违反约束的行为判了“无期徒刑”，理论上能给出相同解，但实际优化起来十分困难。我们可以用Lagrangre 乘数法（Lagrange multipliers）解决这个问题：它的妙招是把阶跃函数松弛为线性函数。

我们为问题 (7.17) 引入 Lagrangre 函数（Lagrangian），通过Lagrangre 乘数 \lambda_i \geqslant 0 将每个不等式约束松弛化（Boyd and Vandenberghe, 2004, 第四章）：

这里，我们把所有约束 g_i(x) 打包成一个向量 \boldsymbol{g}(x)，所有乘数也塞进向量，得到 \boldsymbol{\lambda} \in \mathbb{R}^{m}。

现在我们引入 Lagrangre 对偶性 (Lagrangian duality) 。优化中的对偶思想，本质是把原变量（primal variables）\boldsymbol{x} 的问题，转换成另一组对偶变量（dual variables）\boldsymbol{\lambda} 的问题。本节我们聚焦Lagrangre 对偶，除此之外我们将在 7.3.3 节介绍 Legendre-Fenchel 对偶。

定义 7.1 我们称 (7.17) 中的问题

\begin{align}\min\limits_{\boldsymbol{x}}~&~f(\boldsymbol{x})\\\text{subject to}~&~g_{i}(\boldsymbol{x}) \leqslant 0\quad\text{for all}\quad i = 1, \dots, m\end{align} \tag{7.21}

为原问题（primal problem），对应原变量 \boldsymbol{x}。其关联的Lagrangre 对偶问题（Lagrangian dual problem）是

\begin{align}\min\limits_{\boldsymbol{\lambda} \in \mathbb{R}^{m}}~&~\mathfrak{D}(\boldsymbol{\lambda})\\\text{subject to}~&~\boldsymbol{\lambda} \geqslant \boldsymbol{0}.\end{align} \tag{7.22}

其中 \boldsymbol{\lambda} 是对偶变量， \displaystyle \mathfrak{D}(\boldsymbol{\lambda}) = \min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda})。

注释

在定义 7.1 的讨论中，我们用到两个独立有趣的概念（Boyd and Vandenberghe, 2004）

第一个概念叫做 极小极大不等式（minimax inequality）：对任意双变量函数 \varphi(\boldsymbol{x}, \boldsymbol{y})，有

\max\limits_{\boldsymbol{y}}~\min\limits_{\boldsymbol{x}}~\phi(\boldsymbol{x}, \boldsymbol{y}) \leqslant \min\limits_{\boldsymbol{x}}~\max\limits_{\boldsymbol{y}}~\phi(\boldsymbol{x}, \boldsymbol{y}). \tag{7.23}

可以考虑下面的不等式来证明

\forall \boldsymbol{x}, \boldsymbol{y}\quad \min\limits_{\boldsymbol{x}}~\phi(\boldsymbol{x}, \boldsymbol{y}) \leqslant \max\limits_{\boldsymbol{y}}~\phi(\boldsymbol{x}, \boldsymbol{y}).\tag{7.24}

显然，左边的式子对 \boldsymbol{y} 取 \max 就对应 (7.23) 的左边；类似地操作我们也能得到右边。

第二个概念是 弱对偶性（weak duality），这是说我们在 (7.23) 证明了了的 "原问题值总大于等于对偶值"，更多细节见 (7.27)。

回忆一下，(7.18) 中的 J(\boldsymbol{x}) 与Lagrangre 函数的关键区别，是我们把指示函数松弛成了线性函数。因此，当 \boldsymbol{\lambda} \geqslant 0 时，Lagrangre \mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) 是 J(\boldsymbol{x}) 的下界。于是，\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) 对 \boldsymbol{\lambda} 的最大化给出

同时原问题是最小化 J(\boldsymbol{x})

由极小极大不等式 (7.23)，交换最小和最大顺序会得到更小值，也就是所谓的弱对偶性：

其中右侧里面正是对偶目标函数 \mathfrak{D}(\boldsymbol{\lambda})。

与原优化问题（带约束）相比，\displaystyle \min_{\boldsymbol{x} \in \mathbb{R}^{d}} \mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) 对给定 \boldsymbol{\lambda} 是无约束问题。如果这个子问题容易求解，那整体问题就变简单了！观察 (7.20b)，\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) 关于 \boldsymbol{\lambda} 是仿射（affine）的，因此 \displaystyle \min_{\boldsymbol{x} \in \mathbb{R}^{d}} \mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) 是 \boldsymbol{\lambda} 的仿射函数的逐点最小值，故 \mathfrak{D}(\boldsymbol{\lambda}) 是凹函数——即使 f(\cdot) 和 g_i(\cdot) 非凸。外部最大化问题（对 \boldsymbol{\lambda}）是凹函数的最大化，可高效求解

假设 f(\cdot) 和 g_i(\cdot) 可微，我们通过微分Lagrangre 函数求解对偶问题：对 \boldsymbol{x} 求导、设导数为零、解最优值。第7.3.1和7.3.2节将讨论两个具体例子（f 和 g_i 为凸时）。

注释 （等式约束）
考虑 (7.17) 添加等式约束

\begin{align}\min\limits_{\boldsymbol{x}}~&f(\boldsymbol{x})\\\text{subject to}~&~g_{i}(\boldsymbol{x}) \leqslant 0 \quad \forall i = 1, \dots, m\\&~h_{j}(\boldsymbol{x}) = 0\quad \forall j = 1, \dots, n.\end{align} \tag{7.28}

我们可以用两个不等式约束模拟等式约束：对每个 h_j(\boldsymbol{x})=0，等价替换为 h_j(\boldsymbol{x}) \leqslant 0 和 h_j(\boldsymbol{x}) \geqslant 0。结果Lagrangre 乘数将无约束。
因此，在 (7.28) 中，我们仅约束不等式乘数为非负，而等式乘数则没有约束。