前言

笔者在学习机器学习时遇到了凸规划的有关问题，故查阅资料形成此文

本文资料绝大部分来自网络，但也不乏笔者自己的理解，文章为解释性，有些许证明不严谨的地方，敬请谅解

其次，对于函数凹凸性问题的定义，国内其实并不统一，例如同济教材与数分对于函数凹凸性的定义是相反的，这里我们采用国际上对于函数凹凸性的定义，在国内匹配的是数分定义

无约束优化

在无约束优化问题中，如果一个函数f是凸函数，那么可以直接通过令f的各阶偏导（或梯度）等于0来求得全局最小值点
为了避免陷入局部最优，人们尽可能使用凸函数作为优化问题的目标函数。

约束优化

定义

考虑带约束的优化问题，可以描述为如下形式
::: align-center
\begin{aligned} &\min f(x)\\ &s.t.\space g_i(x)\le0,i=1,2,\cdots,q\\ &h_j(x)=0,j=q+1,\cdots,m\\ &x\in D \end{aligned}

:::
其中f(x)是目标函数，g(x)为不等式约束，h(x)为等式约束

若f(x),g(x),h(x)三个函数都是线性函数，则该优化问题称为线性规划。若任意一个是非线性函数，则称为非线性规划，若目标函数为二次函数，约束全为线性函数，称为二次规划。

若f(x)为凸函数，g(x)为凸函数，h(x)为线性函数，则该问题称为凸优化。注意这里不等式约束g(x)\le 0则要求g(x)为凸函数，若g(x)\ge 0则要求g(x)为凹函数。凸优化的任一局部极值点也是全局极值点，局部最优也是全局最优。

等式约束

考虑一个简单的问题：
目标函数为f(x)=x_1+x_2，等式约束为h(x)=x_1^2+x_2^2-2，求解极小值点

f(x)在二维平面上的等高线（Contour，同济教材又称等值线）是一条条斜率相同的直线，h(x)=0在二维平面上画出等高线就是一个圆，如下图所示。

此时h(x)=0的区域又称为可行域（Feasible Region）

可以明显的看出，在圆h(x)的限制下，直线f(x)的最小值为-2，在左下角直线x_1+x_2=2和圆的交点上。

::: align-center
但是为什么？

:::
读者可能会问到这个问题，事实上我们也肯定不能单纯的用这张图片来解释，它是很难让人信服的

在学习完多元函数后，读者可能会想到，可以描述函数增长最快的量—梯度，事实上，我们不妨从梯度入手

在无约束条件下，指向f(x)值减小最快的方向是它的负梯度-\nabla_xf(x)（其中\nabla为向量微分算子）

在没有约束的情况下，往这个左下角的方向走，我们就可以获得尽可能小的值

但是此时我们们有了等式h(x)=0的约束，这意味着我们走的路径只能是在这个圆上，也就是说，现在约束条件下的极值点也只能在这个圆上

我们不妨再考虑h(x)的梯度，h(x)的梯度应该指向它的值尽可能大的方向，对于这个题来说，h(x)的梯度应该指向四周，也就是下面图片红色细箭头的方向

此时我们再考虑当我们走到极值点时会发生什么

很显然，对于函数而言，要走到极值点，肯定要尽可能的“挣脱”约束条件的束缚，所以我们也倾向于往跟h(x)梯度方向有关的方向走

终于，二者在极值点达成了共识：

很明显，我们会发现：此时两个函数的梯度是共线的，在一般问题中，我们也可以类似的得到两个函数梯度的共线的点应是极值点

用数学语言描述，我们在讨论在极小值点x^*，应有
::: align-center
\begin{aligned} &\max\mu^*\\ &s.t.-\nabla_{x}f(x^*)=\mu^*\nabla_{x}h(x^*)\\ &h(x^*)=0 \end{aligned}

:::
那么我们该如何求解这个问题呢？

事实上，我们不妨考虑构造一个多元函数，使得上述等式约束优化的问题转化为求这个多元函数极值点的问题

我们不妨设函数为
::: align-center
\mathcal{L}(x,\mu)=f(x)+\mu h(x)

:::
此时若读者求此函数关于x,\mu的偏导数，并令其等于零，就会得到-\nabla_{x}f(x)=\mu\nabla_xh(x)和h(x)=0

至此，求解这个等式约束的问题，转化为了求L(x,\mu)驻点的问题

上面的函数L(x,\mu)又称拉格朗日函数，其中f(x)称为目标函数，\mu h(x)又称罚项，因为我们在通过“最大化惩罚”来使得两函数梯度“共线的程度”\mu尽可能远离0来获得最优的极值点，而将问题转化为对拉格朗日函数求极值问题，这就是拉格朗日乘数法

注意：若次优化问题是凸优化问题，通过上图两个条件求得的解就是极小值点（而且是全局极小）。若不是凸优化问题，这两个条件只是极小值点的必要条件，还需要附加Hessian正定条件决定函数的凹凸性才能得到充分性。

不等式约束

对于不等式约束g(x)\le0，和等式约束h(x)=0不同，h(x)=0可以在平面上画出一条等高线，而g(x)\le 0是一个区域，是由很多个等高线堆叠而成的一块可行域。

不等式约束应分两种情况来讨论

1. （不考虑可行域限制时的）极小值点落在可行域内（不包含边界）
2. （不考虑可行域限制时的）极小值点落在可行域外（包含边界）。

下面举两个例子来解释这两种情况，然后总结两种情况给出转换求解。

极小值点落在可行域内（不包含边界）

考虑如下问题：
目标函数f(x)=x_1^2+x_2^2，不等式约束g(x)=x_1^2+x_2^2-1\le0，求解f(x)在约束条件下的极小值点

显然，此时f(x)的极小值点在不考虑约束条件时为(0,0)，而这个点落在约束条件的可行域内

此时约束条件并不起作用

极小值点落在可行域内（不包含边界）

现在考虑：
目标函数f(x)=(x_1-2)^2+(x_2-2)^2，不等式约束g(x)=x_1^2+x_2^2-1\le0，求解f(x)在约束条件下的极小值点

现在f(x)的极值点在不考虑约束条件时为(2,2)，而这个点落在可行域外，我们将不得不考虑在可行域内找一个“以次充好”的极小值点

类似的，我们可以知道在可行域内沿着f(x)的负梯度走可以通往极小值点，而这样走我们一定最终会走到g(x)的边界

此时再考虑g(x)的梯度，我们依然可以得到在边界上两个函数梯度共线的点就是极小值点

总结

• 极小值点落在可行域内（不包含边界）时：此时可行域的限制不起作用，相当于没有约束，可直接令f(x)的梯度为0求解
• 极小值点落在可行域外（包含边界）时：可行域的限制起作用，极小值点应该落在可行域边界上，即g(x)=0，此时问题类似于等式约束

总结以上两种情况，可以构造拉格朗日函数来转换求解问题。满足一定条件的极值点x^*就是此约束问题的解

而这个条件就是著名的卡罗什—库恩—塔克条件，又称KKT条件，它整合了上面的两种情况。

注意：若是凸优化问题，KKT条件就是极小值点（而且是全局极小）存在的充要条件。若不是凸优化问题，KKT条件只是极小值点的必要条件，不是充分条件，KKT点是驻点，是可能的极值点。需要附加Hessian正定条件才能补全充分性

卡罗什—库恩—塔克（KKT）条件

对于一个等式一个不等式约束条件下的凸优化问题
::: align-center
\begin{aligned} &\min f(x)\\ &s.t.\space g(x)\le0\\ &h(x)=0\\ &x\in D \end{aligned}

:::
有拉格朗日函数
::: align-center
L(x,\mu,\lambda)=f(x)+\mu h(x)+\lambda g(x)

:::

存在有参数\mu^*,\lambda^*时有极小值点x^*等价于

• \nabla_{x}L(x^*,\mu^*,\lambda^*)=0（基本条件，保证共线）
• \lambda^*>0（可行性条件，保证不等式约束条件不变号）
• \lambda^*g(x^*)=0（松弛互补条件）
  • 当g(x^*)\ne 0时，即第一种情况，此时约束条件不起作用，即\lambda=0
  • 当g(x^*)=0时，即第二种情况

此外实际求解问题时，可能还需要附带约束条件本身

• h(x)=0
• g(x)\le 0

在处理非凸优化问题时可能还需要附带Hessian正定条件

拉格朗日对偶性

在约束优化问题中，常常用拉格朗日对偶性来将原始问题转为对偶问题，通过解对偶问题的解来得到原始问题的解。

首先要明确，对偶问题的解不一定直接等于原问题的解（弱对偶），但是，对偶问题有两点性质：

1. 满足某些条件时，对偶问题直接等于原问题的解（强对偶）
2. 无论原始问题是否是凸的，对偶问题都是凸优化问题

显然，在某些情况下，直接对对偶问题求解可以得到原问题的解，而且对偶问题是凸优化，易于求解。所以利用对偶来求解是很有用的。

例子

原始问题

考虑原始的优化问题如下：
::: align-center
\begin{aligned} &\min f(x)\\ &s.t.\space g_i(x)\le 0,i=1,2,\cdots,q\\ &h_j(x)=0,j=q+1,\cdots,m\\ &x\in D \end{aligned}

:::
先定义拉格朗日函数
::: align-center
L(x,\alpha,\beta)=f(x)+\sum_{i=1}^q\alpha_ig_i(x)+\sum_{j=q+1}^m\beta_jh_j(x)

:::

考虑函数
::: align-center
\Theta_{P}(x)=\max_{\alpha,\beta,\alpha_i\ge 0}L(x,\alpha,\beta)

:::
也就是最大化罚项使得“共线程度”尽可能远离0
那么原始问题等价于
::: align-center
p^*=\min_{x}\Theta_{P}(x)=\min_{x}\max_{\alpha,\beta,\alpha_i\ge 0}L(x,\alpha,\beta)

:::

对偶问题

考虑函数
::: align-center
\Theta_{D}(\alpha,\beta)=\min_{x}L(x,\alpha,\beta)

:::
极大化函数得到
::: align-center
d^*=\max_{\alpha,\beta,\alpha_i\ge 0}\Theta_P(\alpha,\beta)=\max_{\alpha,\beta,\alpha_i\ge0}\min_{x}L(x,\alpha,\beta)

:::
我们把这个极大化问题视为对偶问题

原始问题和对偶问题的关系

可以得知d^*\le p^*，因为p是先求最大的一块区域然后在这块区域求最小，d是先求最小的一块区域然后在这块区域求最大，最大里面的最小，总会比最小里面的最大要大（或等于）

• d^*\le p^*称为弱对偶，它对于所有优化问题成立，这个时候我们可以得到原始问题的一个下界
• d^*=p^*称为强对偶，满足某些条件才成立，这时可以用解对偶问题替代原始问题
  如果原问题是一个凸优化，并且不等式约束g(x)是严格可行的，即存在x对所有i有g_i<0，那么强对偶成立。这里需要注意的是，这里的条件只是强对偶成立的一种情况，对于非凸的问题也有可能是强对偶。更为详细的情况需要查阅Slater条件

强对偶成立时，将拉格朗日函数分别对原变量x，以及对偶变量\alpha和\beta分别求偏导，令偏导数等于零（还需要满足KKT条件），即可求解对偶问题的解，也就求得了原问题的解。