1 拉格朗日对偶（Lagrange dual）

约束最优化问题的一个解决思路是利用拉格朗日对偶性将原始问题转换为对偶问题，再通过对偶问题得到原始问题的解。

1.1 原始问题与对偶问题

1.1.1 原始问题

假设是定义在上的连续可微函数，一般的带约束最优化问题可表示为以下形式，约束条件中包含等式和不等式

假设此优化问题的约束条件所定义的可行域非空，存在最优值。

1.1.2 拉格朗日函数

Lagrange对偶的基本思想是在目标函数中考虑（2）~（3）约束条件，即添加约束条件的加权和，得到增广的目标函数，如下所示

其中称为拉格朗日乘子，且。

1.1.3 对偶函数

考虑以下关于的最大化问题

若的值满足约束条件，则有。相反，若给定值违反了约束条件，也就是存在或。即存在某个使得时，令对应的乘子，或存在某个使，令其。而其余的乘子则都为0。

因此

我们称为对偶函数（或Lagrange对偶函数），其总是凹函数（证明可参考）。

此时我们考虑以下的极小化问题时

这个问题与原始问题（1）-（3）等价，存在相同的解。我们把（8）称为广义拉格朗日函数的极小极大问题。这样一来，我们将原始的最优化问题转化为一个等价的广义拉格朗日函数极小极大值优化问题了，这也是一个带约束的最优化问题，如下

1.1.4 对偶问题

定义以下最小化问题

关于乘子变量最大化该问题可得

同样，也是一个约束最优化问题

称为原始问题的对偶问题，我们设其最优值为。

1.2 对偶性

1.2.1 下界

定理1 若原始问题和对偶问题的最优值均存在，满足

由于

也就是说

我们知道了的值总是大于或等于的值的，那么当的最小值也必然大于或等于的最大值，即

由于，则对偶问题的解是原始问题的解的下界。

1.2.2 弱对偶性

我们知道Lagrange对偶问题的最优值是原始问题最优值的下界，即。即时原问题并非凸优化问题，该不等式也成立，这个性质称为弱对偶性。当原始问题很难求解时，弱对偶问题可以给出原问题最优值的一个下界，这是因为对偶问题总是凸优化问题。

1.2.3 强对偶性

Slater条件

如果成立，则称为强对偶性，这说明从拉格朗日对偶问题求得的下界是紧的。要使得其成立，可以通过以下的约束准则来判断

Slater条件 存在一点使得下式成立

这里的为相对内点集，对于集合D中的某个点y，以y为中心做半径为r的球B（r>0，且足够小），若球B和A的交集完全落在D内部，则y为D的相对内点。
满足上述条件的点称为严格可行点，这是因为不等式约束严格成立（仅取得不等号）。若原问题是凸问题，且满足Slater条件，则强对偶性可成立。

弱化的Slater条件

当不等式约束中有一部分（）是仿射函数时，如果以下弱化的Slater条件成立，那么强对偶性同样也成立。

松弛Slater条件 存在一点使得下式成立

也就是说对于仿射不等式，不等式约束并不需要严格成立。

注：称从的映射为仿射变换或仿射映射，当m=1时称上述变换为仿射函数，即映射后为一维变量。

1.2.4 同解

当强对偶性成立，我们知道了，那么对应的同时是原始问题和对偶问题的最优解

定理2 若是凸函数，为仿射函数，并且原始问题约束条件定义的定义域非空，那么存在满足

当原始问题很难求解时，利用对偶问题是凸问题的特点，我们可以通过求解对偶问题来找到原问题的解。

1.3 KKT条件

当原问题是凸问题时，则满足KKT条件的点就是原问题和对偶问题的最优解。也就是说

定理3 若是凸函数，为仿射函数，并且原始问题约束条件定义的可行域非空，那么和分别是原始问题、对偶问题的解的充分必要条件时满足下面的KKT条件：

因此，对于凸优化问题，我们通常可以直接利用Lagrange对偶性以及KKT条件来求解。

*1.4 几何理解

作者：彭一洋
链接：https://www.zhihu.com/question/58584814/answer/159863739 以二维情况为例。1. 无约束的优化问题> ，

注意我在图里画了等高线。此时 在局部极小值点 处的梯度必然为0，比较容易理解。这个梯度为零的条件是局部极小值点的必要条件。这样，优化问题的求解变成了对该必要条件解方程组。

2.带等式约束的优化问题

,

s.t. .

与无约束的问题不同。我们所要求的极小值点被限制在曲线 上，我们将 称为可行域, 解只能在这个可行域里取。如下图所示，曲线 （黑色实曲线）经过无约束极小值点（黑点）附近。那么满足约束的极小值点应该与黑点尽可能近。我们将 的等高线不断放大，直到与曲线 相切，切点即为所求。相切是关键，是极小值点的必要条件。

把 沿着曲线的切线可参数化为 , 。必有 在红点 的梯度方向与 的切线方向垂直，即

。另外，由于 为常数，那么也有复合函数 , 因此 在 t 的导数必为0，根据链式法则有

（内积为0，说明 与 垂直）。

因为 垂直于 ， 垂直于 ，所以 与 共线，有

若为最小值点就必须满足上式和问题中的约束 ,这个必要条件就叫作拉格朗日条件，为了好记，定义一个拉格朗日函数

令其偏导为0，正好就得到拉格朗日条件。

如此，带等式约束的优化问题转化为了无约束的优化问题，只需要对拉格朗日条件解方程组即可。这里λ就是拉格朗日乘子，有多少个等式约束就有多少个拉格朗日乘子。

1. 带不等式约束的优化问题

,

s.t.

.

当只有一个不等式起作用时, 如我们把问题2里的等式约束 改为 ，如下图所示，可行域变成了阴影部分，最小值点还是切点，情况和问题2完全一样，只需要把不等号当做等号去求解即可。

当两个不等式起作用时，那么问题就来了

,

s.t.

,

.

如下图，当 的等高线慢慢扩大时，等高线与可行域(阴影部分)第一次相遇的点是个顶点，2个不等式同时起作用了。满足约束的最小值点从原来的黑点位置(切点)移动到了红点位置，现在跟哪条约束函数曲线都不相切。这时候就需要用到kkt条件了。这里的“条件”是指：某一个点它如果是最小值点的话，就必须满足这个条件（在含不等式约束的优化问题里）。这是个必要条件，前面说的也全部是必要条件。

这个问题的解 应满足的KKT条件为：

1. ， ;

2. ;

3. .

其中，μ叫KKT乘子，有多少个不等式约束就有多少个KKT乘子。加上问题3中的约束部分，就是完整版的KKT条件。对于有等式的情况，你把其中一个不等式约束换成等式，可行域变成了半条曲线，最小值点还是那个红点，和下面这种情况是一样的。

下面看看KKT条件是怎么来的。在问题2中我们知道了约束曲线的梯度方向与曲线垂直，我在上图画出了两条约束曲线的负梯度方向（绿色箭头）和等高线的梯度方向（红色箭头）。如果这个顶点是满足约束的最小值点，那么该点处（红点），红色箭头一定在两个绿色箭头之间( 方向一定指向 减小的方向，即 的那一边)。即 能被 和 线性表出（ ），且系数必非负（ ， ）。也就是kkt条件中的1和2

1. ， ;

2. .

有时候，有的不等式约束实际上不起作用，如下面这个优化问题

,

s.t.

;

;

.

如下图的 是不起作用的

对于最小值点 ,三个不等式约束的不同在于

（起作用）

（起作用）

（不起作用, 最小值点不在 上）

这时，这个问题的KKT条件1，2成了：

1. ， ， ;

2. .

条件2中的 这一项让我们很苦恼啊， 的绿色箭头跟我们的红色箭头没关系。要是能令 就好了。加上条件3：

1. 

恰好能使 。由于 ， ，所以前两项等于0，第三项 , 在条件3的作用下使得 . 正好满足需求。如果再多几项不起作用的不等式约束，比如 。要使

就只能有

同样地， , , 只能出现 或者 和 异号的情况。但注意条件1限制了 ， ，所以只能有 。因此不管加了几个不起作用的不等式约束，条件2都能完美实现：目标函数 的梯度 被起作用的不等式约束函数 的负梯度（ ）线性表出且系数 全部非负（红色箭头被绿色箭头夹在中间）。这样，优化问题的求解就变成对所有KKT条件解方程组。

如果再定义一个拉格朗日函数

令它对x的偏导为0，就是KKT条件中的条件2了。

最后说明一下，以上所有都是局部极小值点的必要条件。据此求得的解不一定是局部极小值点（更别提全局了），原因是上图中我所画的等高线也许根本就不闭合，也就是说我们一直想要靠近的等高线中间的黑点压根就是个鞍点或者近似鞍点。