一、简介

约束优化问题的原问题（Primal Problem）的一般形式如下：

求解约束优化问题需要用到拉格朗日乘子法，定义拉格朗日函数：

然后原问题可以转化为以下优化问题，这两个优化问题具有同样的解：

可以说明一下为什么上述约束优化问题可以求得原问题的最优解：

也就是说虽然拉格朗日函数对 没有约束，但是在求解过程中会过滤掉不符合原问题 的约束的 。

二、对偶关系证明

原问题的对偶问题为

可以看到原问题是关于 的函数，对偶问题是关于 的函数。有如下定理：

这个关系可以简单地得到证明：

三、对偶性的几何解释

对于上述约束优化问题，可以写出它的拉格朗日函数：

然后表示出原问题和对偶问题的最优解

接着定义集合G：

集合G在二维坐标系下表示的空间假设为下图：

因此 可以表示为：

在图中可以表示为：

                                               p*

                                         g(λ)

在某些特殊情况下可以使得强对偶关系成立，在图中表示如下：

                                                   强对偶关系

四、Slater条件

有以下两点说明：

①对于大多数凸优化问题，Slater条件是成立的；

②放松的Slater条件： 中的仿射函数可以不用验证。因为在定义域内寻找一个满足所有 的点是比较困难的，因此放松的Slater条件会减少一些复杂度。

五、KKT条件

对于原问题：

以及其对偶问题：

如果原问题和对偶问题满足强对偶关系，则原问题和对偶问题具有相同的最优解，另外它们还天然地满足KKT条件（Karush-Kuhn-Tucker条件）。假设原问题最优解 ，对偶问题最优解对应 ，则KKT条件为：

可以进行以下证明：