【机器学习之数学】03 有约束的非线性优化问题——拉格朗日乘子法、KKT条件、投影法

时间:2024-01-24 21:15:16


梯度下降法、最速下降法、牛顿法等迭代求解方法,都是在无约束的条件下使用的,而在有约束的问题中,直接使用这些梯度方法会有问题,如更新后的值不满足约束条件。

那么问题来了,如何处理有约束的优化问题?大致可以分为以下两种方式:

  1. 将有约束的问题转化为无约束的问题,如拉格朗日乘子法和KKT条件;
  2. 对无约束问题下的求解算法进行修改,使其能够运用在有约束的问题中,如对梯度下降法进行投影,使得更新后的值都满足约束条件。

1 将有约束问题转化为无约束问题

1.1 拉格朗日法

仅含等式约束的优化问题

\[\begin{array}{cl}{\text { minimize }} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{h}(\boldsymbol{x})=\mathbf{0}}\end{array} \]

其中,\(x \in \mathbb{R}^n\)\(f : \mathbb{R}^{n} \rightarrow \mathbb{R}\)\(\boldsymbol{h} : \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}, \boldsymbol{h}=\left[h_{1}, \ldots, h_{m}\right]^{\top}, \text { and } m \leq n\)

该问题的拉格朗日函数为:

\[l(\boldsymbol{x}, \boldsymbol{\lambda})=f(\boldsymbol{x})+\boldsymbol{\lambda}^{\top} \boldsymbol{h}(\boldsymbol{x}) \]

FONC:对拉格朗日函数 \(l(\boldsymbol{x}, \boldsymbol{\lambda})\) 求偏导数,令偏导数都等于 0,求得的解必然满足原问题的等式约束,可以从这些解里面寻找是否有局部最优解。这是求得局部最优解的一阶必要条件。

拉格朗日条件:(分别对 \(\bm x\)\(\bm \lambda\) 求偏导)

\[\begin{array}{l}{D_{x} l\left(\boldsymbol{x}^{*}, \boldsymbol{\lambda}^{*}\right)=\mathbf{0}^{\top}} \\ {D_{\lambda} l\left(\boldsymbol{x}^{*}, \boldsymbol{\lambda}^{*}\right)=\mathbf{0}^{\top}}\end{array} \]

上式中,对 \(\lambda\) 求偏导数得到的就是等式约束。

拉格朗日条件是必要而非充分条件,即满足上述方程的点 \(\boldsymbol x^{*}\) 不一定是极值点。

1.1.1 KKT条件

既含等式约束又含不等式约束的优化问题:

\[\begin{array}{rl}{\operatorname{minimize}} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{h}(\boldsymbol{x})=\mathbf{0}} \\ {} & {\boldsymbol{g}(\boldsymbol{x}) \leq \mathbf{0}}\end{array} \]

其中,\(f : \mathbb{R}^{n} \rightarrow \mathbb{R}\)\(\boldsymbol{h} : \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}, m \leq n\),并且 \(\boldsymbol{g} : \mathbb{R}^{n} \rightarrow \mathbb{R}^{p}\)

将该问题转化为拉格朗日形式:

\[l(\boldsymbol{x}, \boldsymbol{\lambda})=f(\boldsymbol{x})+\boldsymbol{\lambda}^{\top} \boldsymbol{h}(\boldsymbol{x}) +\boldsymbol{\mu}^{\top} \boldsymbol{g}(\boldsymbol{x}) \]

\(\bm x^{*}\) 是原问题的一个局部极小点,则必然存在 \(\bm{\lambda}^{* \top} \in \mathbb{R}^m\)\(\bm{\mu}^{* \top} \in \mathbb{R}^p\),使得下列KKT条件成立:

  1. \(\bm {\mu}^{*} \geq 0\)
  2. \(D f\left(\boldsymbol{x}^{*}\right)+\boldsymbol{\lambda}^{* \top} D \boldsymbol{h}\left(\boldsymbol{x}^{*}\right)+\boldsymbol{\mu}^{* \top} D \boldsymbol{g}\left(\boldsymbol{x}^{*}\right)=\mathbf{0}^{\top}\)
  3. \(\boldsymbol{\mu}^{* \top} \boldsymbol{g}\left(\boldsymbol{x}^{*}\right)=0\)
  4. \({\boldsymbol{h}(\boldsymbol{x}^*)=\mathbf{0}}\)
  5. \({\boldsymbol{g}(\boldsymbol{x}^*) \leq \mathbf{0}}\)

KKT条件中,\(\bm{\lambda}^{*}\) 是拉格朗日乘子向量,\(\bm{\mu}^{*}\) 是KKT乘子向量,\(\bm{\lambda}^{*}\)\(\bm{\mu}^{*}\) 的元素分别称为拉格朗日乘子和KKT乘子。

1.1.2 拉格朗日法更新方程

将含约束的优化问题转化为拉格朗日形式后,我们可以用更新方程对该问题进行迭代求解。

这也是一种梯度算法,但拉格朗日乘子、KKT 乘子的更新和自变量 \(\bm x\) 的更新不同,自变量 \(\bm x\) 继续采用梯度下降法更新,而拉格朗日乘子、KKT 乘子的更新方程如下:

\[\boldsymbol{\lambda}^{(k+1)}=\boldsymbol{\lambda}^{(k)}+\beta_{k} \boldsymbol{h}\left(\boldsymbol{x}^{(k)}\right), \\ \boldsymbol{\mu}^{(k+1)}=\left[\boldsymbol{\mu}^{(k)}+\beta_{k} \boldsymbol{g}\left(\boldsymbol{x}^{(k)}\right)\right]_{+} \]

其中,\([\cdot]_{+}=\max \{\cdot, 0\}\)

1.1.3 凸优化问题下的拉格朗日法

拉格朗日乘子法和KKT条件在一般的含约束条件的优化问题中,都只是一阶必要条件,而在凸优化问题中,则变成了充分条件。

凸优化问题指的是目标函数是凸函数,约束集是凸集的优化问题。线性规划、二次规划(目标函数为二次型函数、约束方程为线性方程)都可以归为凸优化问题。

凸优化问题中,局部极小点就是全局极小点。极小点的一阶必要条件就是凸优化问题的充分条件。

1.2 罚函数法

考虑一般形式的有约束优化问题:

\[\begin{array}{cl}{\operatorname{minimize}} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{x} \in \Omega}\end{array} \]

将问题变为如下无约束的形式:

\[\operatorname{minimize} f(\boldsymbol{x})+\gamma P(\boldsymbol{x}) \]

其中,\(\gamma\) 是惩罚因子,\(P : \mathbb{R}^{n} \rightarrow \mathbb{R}\) 是罚函数。求解该无约束优化问题,把得到的解近似作为原问题的极小点。

罚函数需要满足以下 3 个条件:

  1. \(\bm P\) 是连续的;
  2. 对所有 \(\bm x \in \mathbb{R}^n\)\(P(\boldsymbol{x}) \ge 0\) 成立;
  3. \(P(\boldsymbol{x})=0\),当且仅当 \(\bm x\) 是可行点(即 \({\bm{x} \in \Omega}\))。

2 对梯度算法进行修改,使其运用在有约束条件下

2.1 投影法

梯度下降法、最速下降法、牛顿法等优化算法都有通用的迭代公式:

\[\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)} \]

其中,\(\boldsymbol{d}^{(k)}\) 是关于梯度 \(\nabla f(\bm x^{(k)})\) 的函数,如在梯度下降法中,\(\boldsymbol{d}^{(k)} = -\nabla f(\bm x^{(k)})\)

考虑优化问题:

\[\begin{array}{cl}{\operatorname{minimize}} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{x} \in \Omega}\end{array} \]

在上述有约束的优化问题中,\(\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)}\) 可能不在约束集 \(\Omega\) 内,这是梯度下降等方法无法使用的原因。

而投影法做的是,如果 \(\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)}\) 跑到约束集 \(\Omega\) 外面去了,那么将它投影到约束集内“最接近”的点;如果 \(\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)} \in \Omega\),那么正常更新即可。

投影法的更新公式为:

\[\boldsymbol{x}^{(k+1)}=\boldsymbol{\Pi}\left[\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(k)}\right] \]

其中 \(\bm \Pi\) 为投影算子,\(\bm \Pi[\bm x]\) 称为 \(\bm x\)\(\Omega\) 上的投影。

2.1.1 梯度下降法 to 投影梯度法

梯度下降法的迭代公式为:

\[\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}-\alpha_{k} \nabla f\left(\boldsymbol{x}^{(k)}\right) \]

将投影算法引入梯度下降法,可得投影梯度法,迭代公式如下:

\[\boldsymbol{x}^{(k+1)}=\boldsymbol{\Pi}\left[\boldsymbol{x}^{(k)}-\alpha_{k} \nabla f\left(\boldsymbol{x}^{(k)}\right)\right] \]

2.1.2 正交投影算子

含线性约束优化问题的投影梯度法可以利用正交投影算子来更新 \(\bm x^{(k)}\)

含线性约束的优化问题如下所示:

\[\begin{array}{cl}{\operatorname{minimize}} & {f(\boldsymbol{x})} \\ {\text { subject to }} & {\boldsymbol{A x}=\boldsymbol{b}}\end{array} \]

其中,\(f : \mathbb{R}^{n} \rightarrow \mathbb{R}\)\(\boldsymbol{A} \in \mathbb{R}^{m \times n}, m<n\)\(\operatorname{rank} \boldsymbol{A}=m, \boldsymbol{b} \in \mathbb{R}^{m}\),约束集 \(\Omega=\{\boldsymbol{x} :\boldsymbol{A} \boldsymbol{x}=\boldsymbol{b} \}\)

这种情况下,正交投影算子矩阵 \(\bm P\) 为:

\[\boldsymbol{P}=\boldsymbol{I}_{n}-\boldsymbol{A}^{\top}\left(\boldsymbol{A} \boldsymbol{A}^{\top}\right)^{-1} \boldsymbol{A} \]

正交投影算子 \(\bm P\) 有两个重要性质:

  1. \(P=P^{\top}\).
  2. \(P^{2}=P\).

在投影梯度算法中,可以按照如下公式更新 \(\bm x^{(k)}\)

\[\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}-\alpha_{k} \boldsymbol{P} \nabla \boldsymbol{f}(\boldsymbol{x}^{(k)}) \]

References

Edwin K. P. Chong, Stanislaw H. Zak-An Introduction to Optimization, 4th Edition

相关博客

【机器学习之数学】01 导数、偏导数、方向导数、梯度
【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法
【机器学习之数学】03 有约束的非线性优化问题——拉格朗日乘子法、KKT条件、投影法