1 基本概念

标准形式的优化问题可以表达成:

在接下来的讨论中，我们假设原优化问题的最优解为

1.1 拉格朗日函数

在原目标函数的基础上添加约束条件的加权和，得到增广目标函数。其中称为第个不等式约束对应的Lagrange乘子，称为第个等式约束对应的Lagrange乘子。

1.2 拉格朗日对偶函数

$$g(\lambda, \nu)=\inf {x \in \mathcal{D}} L(x, \lambda, \nu)=\inf {x \in \mathcal{D}}\left(f_0(x)+\sum{i=1}^m \lambda_i f_i(x)+\sum{i=1}^p \nu_i h_i(x)\right)$$
对拉格朗日函数取下确界, 得到拉格朗日对偶函数, 它有以下性质：

• 即使原问题为非凸的，对偶函数也是凸的
• 对任意和,

1.3 对偶问题

当原问题为非凸时, 考虑到拉格朗日对偶函数的特殊性质, 我们可以去求解它的对偶问题. 假设对偶问题的最优解为, 那么恒成立。

1.4 对偶性

• 弱对偶性: 满足, 总是成立；
• 强对偶性: 满足, 并非总是成立, 需要满足一定的约束准则. 如果原问题时凸优化问题, 强对偶性通常(但不总是)成立.

2 强对偶性和SCQ

SCQ: Slater Constraint Qualification
当1）原问题是凸优化问题且2）SCQ满足的话，强对偶性成立。正式表述如下:
对于凸优化问题:

若存在可行解,使得

强对偶性成立。

• 如果不等式约束中有一些事彷射函数, 那么对这些彷射函数不要求严格小于, 小于等于即可