深度学习数学基础之约束优化

约束优化

约束优化的形式化表述

$$\begin{array}{rl}{\displaystyle \underset{\mathbf{x}\in {\mathbb{R}}^n}{\min }}& {\displaystyle f(\mathbf{x})}\\ {\displaystyle \text{subject to:}}& {\displaystyle g_i(\mathbf{x})\le 0,i=1,\dots ,m}\\ {\displaystyle }& {\displaystyle h_j(\mathbf{x})=0,j=1,\dots ,p}\end{array}$$

其中：

• （目标函数）$f(\mathbf{x})$ 是我们要最小化的目标函数。
• （优化变量）$\mathbf{x}$ 是 $n$ 维的优化变量。
• $g_i(\mathbf{x})\le 0$ 是 $m$ 个不等式约束。
• $h_j(\mathbf{x})$ 是 $p$ 个等式约束。

注意，这里 $\mathbf{x}$ 一般是向量。

s.t.：subject to 后面是要满足的条件，subject to 也写作 $\text{s.t.}$（使得）。

可行域：所有满足这些约束条件的点 $\mathbb{x}$ 组成的集合被称为可行域，记作 $\mathcal{F}=\{x\in {\mathbb{R}}^n\mid \mathrm{\forall }i,g_i(x)\le 0\text{且}\mathrm{\forall }j,h_j(x)=0\}$。

约束优化就是在 $\mathcal{F}$ 中找到 $\mathrm{arg\hspace{0.17em}min}f(x)$。

LICQ

线性无关约束规范 / 线性独立约束品性。

LICQ 是相对于所有的等式/不等式约束和点 ${\mathbf{x}}^{\ast }$ 说的，它要求向量组

$$\{\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })\mid i\in \mathcal{A}({\mathbf{x}}^{\ast })\}\cup \{\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })\mid j=1,\dots ,p\}$$

线性无关。其中：

• $\mathcal{A}({\mathbf{x}}^{\ast })=\{i\mid g_i({\mathbf{x}}^{\ast })=0\}$ 是所有起作用的不等式的“编号”集合，或者叫积极约束指标集。
• 起作用约束：起作用约束是相对于所有不等式约束和点 ${\mathbf{x}}^{\ast }$ 说的，意思就是 $g_i({\mathbf{x}}^{\ast })=0$。

正则点：能使 LICQ 成立的点叫正则点。

可以将那个向量组看作点 ${\mathbf{x}}^{\ast }$ “碰到”的约束的“法向量”集合，对于不等式约束，法向量指向不可行区域。

拉格朗日乘子法

我们全程不考虑不等式约束。

我们首先考虑只有一个等式约束 $h({\mathbf{x}}^{\ast })=0$ 的情况。在满足等式约束的局部最优解 ${\mathbf{x}}^{\ast }$ 处，$\mathrm{\nabla }f({\mathbf{x}}^{\ast })$ 和 $\mathrm{\nabla }h({\mathbf{x}}^{\ast })$ 必须是平行的。

既然平行，那么肯定 $\mathrm{\exists }\lambda \in \mathbb{R},\mathrm{\nabla }f({\mathbf{x}}^{\ast })=\lambda \mathrm{\nabla }h({\mathbf{x}}^{\ast })$。这个标量 $\lambda$ 就叫拉格朗日乘子

为什么一定平行呢？我们可以用反证法证明： 如果不平行，那么沿着可行域切空间的某个方向移动，目标函数 $f$ 就会减少，从而找到了一个比 ${\mathbf{x}}^{\ast }$ 更好的可行点，这与 ${\mathbf{x}}^{\ast }$ 是局部最优点矛盾。为了消除这种改进的可能性，就必须平行。

如果现在有多个等式约束 $h_j(\mathbf{x})=0,j=1,\dots ,p$ ，并且最优点 ${\mathbf{x}}^{\ast }$ 是正则点（符合 LICQ 的点），那么目标函数梯度向量方向一定和可行域切空间平行。就是说存在一组拉格朗日乘子 ${\lambda }_1,\dots ,{\lambda }_p$，使得和等式约束梯度的线性组合为目标函数梯度，即：

$$\mathrm{\nabla }f({\mathbf{x}}^{\ast })=\sum _{j=1}^p{\lambda }_j\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })$$

移项：

$$\begin{array}{cccc}& \mathrm{\nabla }f({\mathbf{x}}^{\ast })-\sum _{j=1}^p{\lambda }_j\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })=\mathbf{0}& & \text{(1)}\end{array}$$

我们构造拉格朗日函数 $\mathcal{L}$：

$$\mathcal{L}(\mathbf{x},\mathit{\lambda })=f(\mathbf{x})-\sum _{j=1}^p{\lambda }_j{h}_j(\mathbf{x})$$

其中：

• $\mathit{\lambda }$是拉格朗日乘子向量。

我们发现，${\mathrm{\nabla }}_{\mathbf{x}}\mathcal{L}({\mathbf{x}}^{\ast },{\mathit{\lambda }}^{\ast })=\mathbf{0}$ 这个条件等价于上面的 $(1)$ 式，且 $\frac{\mathrm{\partial }\mathcal{L}}{\mathrm{\partial }{\lambda }_j}({\mathbf{x}}^{\ast },{\mathit{\lambda }}^{\ast })=0$ 等价于 $h_j({\mathbf{x}}^{\ast })=0$。这两个条件同时成立时就能还原原来的等式约束条件。

所以，原始的等式约束优化问题的最优性条件通过拉格朗日函数可以转化为求解方程组：

$${\mathrm{\nabla }}_{\mathbf{x}}\mathcal{L}(\mathbf{x},\mathit{\lambda })=0\text{and}{\mathrm{\nabla }}_{\mathit{\lambda }}\mathcal{L}(\mathbf{x},\mathit{\lambda })=0$$

方程解完还没结束，需要判断解是最小值、最大值还是鞍点。

KKT 方法

KKT 方法是拉格朗日乘子法的推广，进一步考虑了不等式约束。

此时最优解可能在可行域边缘（存在一个或多个起作用的不等式约束）或在内部（$\mathrm{\forall }i,g_i(\mathbf{x})<0$）。

如果 ${\mathbf{x}}^{\ast }$ 是局部最优解并且满足正则性条件，则存在一组 KKT 乘子：${\mu }_1,\dots ,{\mu }_m$ 对应不等式约束，${\lambda }_1,\dots ,{\lambda }_p$ 对应等式约束，满足以下四个条件：

稳定性

$$\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{\mu }_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{\lambda }_j\mathrm{\nabla }{h}_i({\mathbf{x}}^{\ast })=0$$

原始可行性

$${\mathbf{x}}^{\ast }\in \mathcal{F}$$

互补松弛性

$${\mu }_i{g}_i({\mathbf{x}}^{\ast })=0$$

表示如果不等式约束不起作用时，需要让 ${\mu }_i=0\text{，}$。

对偶可行性

$${\mu }_i\ge 0$$

稳定性条件表明，局部最优时目标函数的下降方向 $-\mathrm{\nabla }f({\mathbf{x}}^{\ast })$ 是由约束梯度构成的。如果 ${\mu }_i<0$，那么 ${\mu }_i{g}_i({\mathbf{x}}^{\ast })$ 指向可行域内部，可以证明此时存在一个可以让目标函数下降的方向，与 ${\mathbf{x}}^{\ast }$ 是局部最优点矛盾。