目录
将有约束问题转化为无约束问题
拉格朗日法
KKT 条件
拉格朗日法更新方程
凸优化问题下的拉格朗日法
罚函数法
对梯度算法进行修改, 使其运用在有约束条件下
投影法
梯度下降法 to 投影梯度法
正交投影算子
References
相关博客
梯度下降法, 最速下降法, 牛顿法等迭代求解方法, 都是在无约束的条件下使用的, 而在有约束的问题中, 直接使用这些梯度方法会有问题, 如更新后的值不满足约束条件.
那么问题来了, 如何处理有约束的优化问题? 大致可以分为以下两种方式:
将有约束的问题转化为无约束的问题, 如拉格朗日乘子法和 KKT 条件;
对无约束问题下的求解算法进行修改, 使其能够运用在有约束的问题中, 如对梯度下降法进行投影, 使得更新后的值都满足约束条件.
将有约束问题转化为无约束问题
拉格朗日法
仅含等式约束的优化问题
\[ \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^{*}\) 不一定是极值点.
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 条件成立:
- \(\bm {
- \mu
- }^{
- *
- } \geq 0\)
- \(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
- }\)
- \(\boldsymbol{
- \mu
- }^{
- * \top
- } \boldsymbol{
- g
- }\left(\boldsymbol{
- x
- }^{
- *
- }\right)=0\)
- \({
- \boldsymbol{
- h
- }(\boldsymbol{
- x
- }^*)=\mathbf{
- 0
- }
- }\)
- \({
- \boldsymbol{
- g
- }(\boldsymbol{
- x
- }^*) \leq \mathbf{
- 0
- }
- }\)
KKT 条件中,\(\bm{\lambda}^{*}\) 是拉格朗日乘子向量,\(\bm{\mu}^{*}\) 是 KKT 乘子向量,\(\bm{\lambda}^{*}\) 和 \(\bm{\mu}^{*}\) 的元素分别称为拉格朗日乘子和 KKT 乘子.
拉格朗日法更新方程
将含约束的优化问题转化为拉格朗日形式后, 我们可以用更新方程对该问题进行迭代求解.
这也是一种梯度算法, 但拉格朗日乘子, 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\}\).
凸优化问题下的拉格朗日法
拉格朗日乘子法和 KKT 条件在一般的含约束条件的优化问题中, 都只是一阶必要条件, 而在凸优化问题中, 则变成了充分条件.
凸优化问题指的是目标函数是凸函数, 约束集是凸集的优化问题. 线性规划, 二次规划 (目标函数为二次型函数, 约束方程为线性方程) 都可以归为凸优化问题.
凸优化问题中, 局部极小点就是全局极小点. 极小点的一阶必要条件就是凸优化问题的充分条件.
罚函数法
updating...
对梯度算法进行修改, 使其运用在有约束条件下
投影法
梯度下降法, 最速下降法, 牛顿法等优化算法都有通用的迭代公式:
\[ \boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}+\alpha_{k} \boldsymbol{d}^{(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\) 上的投影.
梯度下降法 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] \]
正交投影算子
updating...
References
Edwin K. P. Chong, Stanislaw H. Zak-An Introduction to Optimization, 4th Edition
相关博客
[机器学习之数学] 01 导数, 偏导数, 方向导数, 梯度
[机器学习之数学] 02 梯度下降法, 最速下降法, 牛顿法, 共轭方向法, 拟牛顿法
来源: https://www.cnblogs.com/wuliytTaotao/p/11077353.html