拉格朗日乘子法

拉格朗日乘子法是一种寻找非线性多元函数在一组等式约束下的极值的方案，在引入了 KKT 条件后，拉格朗日乘子法被泛化到了有不等式约束的一般形式。拉格朗日乘子法可以将多个等式约束的优化问题转化为无约束的拉格朗日函数优化问题，也可以将多个不等式约束的优化问题转化为 KKT 条件下拉格朗日函数的优化问题。

等式约束的优化问题

对于如上的单个约束的优化问题，可以将看做一个维曲面，存在两条结论：

对于约束曲面上的任意点，该店的梯度正交于约束曲面。这是因为，可以看做函数的一个等值面，而一个等值面上的任意一点梯度都与等值面垂直。
在最优点，目标函数在该店的梯度正交于约束曲面，这是因为，此时使增大的方向与约束曲面垂直，假如不垂直，则可以沿着约束曲面与向梯度的反方向移动，从而让的值变小。

由此可知，在最优点处，梯度和梯度的方向相同或者相反，即存在，使得

为拉格朗日乘子，定义拉格朗日函数

此时分别求拉格朗日函数对和对的偏导数和，分别令它们等于令可以得到上述限制以及原问题约束。于是，原约束优化问题可转化为对拉格朗日函数的无约束优化问题。

对于多个等式约束的情况，梯度的方向是所有梯度方向的线性组合，故如下定义拉格朗日函数，然后对和所有的求偏导置零即可。

不等式约束的优化问题

现将最初的优化问题改为一个不等式约束。仍然可以写出相应的拉格朗日函数，现在对该优化问题的最优解分类讨论，推导出某个解是最优解需要满足的必要条件。

当时，说明是的一个极值点，满足，那么将拉格朗日函数中的置零，必然满足。
当时，与等式约束的情况类似，不同的是，和的方向必须相反，因为如果它们方向相同，沿梯度的反方向移动，则和都变小，与“在边界上取最优解的讨论情况矛盾”，也即存在常数使得。

整合这两种情况，必须满足。

因此，在约束下最小化可以转化为在如上约束下最小化拉格朗日函数的问题。

如上可以将该思路推广到个等式约束和个不等式约束，且可行域非空的优化问题。

引入拉格朗日乘子和，则拉格朗日函数如下。

$𝕩$

由不等式引入的 KKT 条件如下。

对偶问题

“对偶问题”一般而言是指“拉格朗日对偶问题”（Lagrangian dual problem）。最优化问题可以用两种观点来看待的理论，两种观点分别是“原始问题”（primal problem）及“对偶问题”（dual problem）。对偶问题的解提供了原始问题（假设是最小化问题）的下限。

拉格朗日函数

$𝕩$

任何一个优化问题都存在相应的拉格朗日函数。

拉格朗日对偶函数

定义拉格朗日对偶函数如上，对于任何一组给定的拉格朗日乘子，输出在可行域内拉格朗日函数值的下确界。

拉格朗日对偶问题

令原问题中最优解对应的目标函数值为，对偶问题中最优解对应的目标函数值为，则定义原问题和对偶问题的对偶性如下。

弱对偶性（Weak Duality）：
强对偶性（Strong Duality）：

任何优化问题的原始问题和其对偶问题都满足弱对偶性。

强对偶性满足的一个充分条件是：原优化问题是一个凸优化问题，且原优化问题满足 Slater 条件。

拉格朗日对偶问题一定是凸优化问题。

对偶问题将原来的个函数约束变为了个简单的约束，当原问题和对偶问题满足强对偶性是，可以通过求解对偶问题来求解原问题，很多场景下对偶问题比原问题容易求解。

概念

凸集

凸集（Convex set）是一个点集合，其中每两点之间的线段点都落在该点集合中。

凸函数

维某实向量空间的凸子集，若实值函数对任意以及任意，皆满足上式，则称为凸函数（Convex function）。即在的图像上，任意两点的连线不低于中间的曲线。

凸优化

$其中为凸函数$

凸优化可以表示为如上的标准型。

令为一凸集，且为一凸函数。凸优化（Convex Optimization）就是要找出一点满足。其中称为可行域，称为目标函数，称为全局最优解。

如果存在等式约束，可以表示为两个符号相反的不等式约束，这两个凸的不等式约束，可以表示一个仿射函数的等式约束。

KKT 条件

KKT 条件（Karush–Kuhn–Tucker conditions）是最优化（特别是非线性规划）领域最重要的成果之一，是判断某点是极值点的必要条件。

对于以上优化问题，存在相应的拉格朗日函数。

则其对应的 KKT 条件如下。

$稳定性条件原始可行性条件补松驰条件对偶可行性条件原始可行性条件$

Slater 条件

若对凸优化问题

存在满足

则称对此问题满足 Slater 条件。