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

痛定思痛。 2021-10-26 13:38 371阅读 0赞

*  1 将有约束问题转化为无约束问题
    
     *  1.1 拉格朗日法
        
         *  1.1.1 KKT条件
         *  1.1.2 拉格朗日法更新方程
         *  1.1.3 凸优化问题下的拉格朗日法
     *  1.2 罚函数法
 *  2 对梯度算法进行修改，使其运用在有约束条件下
    
     *  2.1 投影法
        
         *  2.1.1 梯度下降法 to 投影梯度法
         *  2.1.2 正交投影算子
 *  References
 *  相关博客

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

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

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][Edwin K. P. Chong_ Stanislaw H. Zak-An Introduction to Optimization_ 4th Edition]

# 相关博客 #

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

转载于:https://www.cnblogs.com/wuliytTaotao/p/11077353.html

[Edwin K. P. Chong_ Stanislaw H. Zak-An Introduction to Optimization_ 4th Edition]: https://github.com/wuliytTaotao/Learning-Materials/blob/master/machine%20leanring/Edwin%20K.%20P.%20Chong%2C%20Stanislaw%20H.%20Zak-An%20Introduction%20to%20Optimization%2C%204th%20Edition.pdf
[01]: https://www.cnblogs.com/wuliytTaotao/p/10513371.html
[02]: https://www.cnblogs.com/wuliytTaotao/p/10603576.html
[03 _KKT]: https://www.cnblogs.com/wuliytTaotao/p/11077353.html