目录
梯度下降法、最速下降法、牛顿法等迭代求解方法，都是在无约束的条件下使用的，而在有约束的问题中，直接使用这些梯度方法会有问题，如更新后的值不满足约束条件。
那么问题来了，如何处理有约束的优化问题？大致可以分为以下两种方式：
- 将有约束的问题转化为无约束的问题，如拉格朗日乘子法和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，求得的解必然满足原问题的等式约束，可以从这些解里面寻找是否有局部最优解。这是求得局部最优解的一阶必要条件。
拉格朗日条件：
\[
\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}^n\)，使得下列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\)
KKT条件中，\(\bm{\lambda}^{*}\) 是拉格朗日乘子向量，\(\bm{\mu}^{*}\) 是KKT乘子向量，\(\bm{\lambda}^{*}\) 和 \(\bm{\mu}^{*}\) 的元素分别称为拉格朗日乘子和KKT乘子。
凸优化下的等式约束和不等式约束优化问题
拉格朗日乘子法和KKT条件在一般的含约束条件的优化问题中，都只是一阶必要条件，而在凸优化问题中，则变成了充分条件。
凸优化问题指的是目标函数是凸函数，约束集是凸集的优化问题。线性规划、二次规划（目标函数为二次型函数、约束方程为线性方程）都可以归为凸优化问题。
凸优化问题中，局部极小点就是全局极小点。极小点的一阶必要条件就是凸优化问题的充分条件。
对梯度算法进行修改，使其运用在有约束条件下
投影法
梯度下降法、最速下降法、牛顿法等优化算法都有通用的迭代公式：
\[
\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\) 上的投影。
梯度下降法->投影梯度法
梯度下降法的迭代公式为：
\[
\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 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法
【机器学习之数学】03 有约束的非线性优化问题