凸优化之强弱对偶性与Slater准则

弱对偶性

Lagrange ext{Lagrange} Lagrange 对偶问题的最优值, 我们用 d ⋆ d^{star} d⋆ 表示, 根据定义, 这是通过 Lagrange ext{Lagrange} Lagrange 函数 得到的原问题最优值 p ⋆ p^{star} p⋆ 的最好下界(即最大下界). 特别地, 我们有下面简单但是非常重要的不等式 d ⋆ ⩽ p ⋆ ( primal dual ) d^{star} leqslant p^{star} ( ext{primal dual}) d⋆⩽p⋆(primal dual), 即使原问题不是凸问题, 上述不等式亦成立. 这个性质称为弱对偶性. 即使当 d ⋆ d^{star} d⋆ 和 p ⋆ p^{star} p⋆ 无限时, 弱对偶性不等式也成立. 例如, 如果原问题无下界, 即 p ⋆ = − ∞ p^{star}=-infty p⋆=−∞, 为了保证弱对偶性成立, 必须有 d ⋆ = − ∞ d^{star}=-infty d⋆=−∞, 即 Lagrange ext{Lagrange} Lagrange 对偶问题不可行. 反过来, 若对偶问题无上界, 即 d ⋆ = ∞ d^{star}=infty d⋆=∞, 为了保证弱对偶性成立, 必须有 p ⋆ = ∞ p^{star}=infty p⋆=∞,即原问题不可行. 定义差值 p ⋆ − d ⋆ p^{star}-d^{star} p⋆−d⋆ 是原问题的最优对偶间隙. 它给出了原问题最优值以及通过 Lagrange ext{Lagrange} Lagrange 对偶函数所能得到的最好（最大）下界之间的差值. 最优对偶间隙总是非负的. 当原问题很难求解时, 弱对偶不等式可以给出原问题最优值的一个下界, 这是因为对偶问题总是凸问题, 而且在很多情况下都可以进行有效的求解得到 d ⋆ d^{star} d⋆. 如果等式 d ⋆ = p ∗ d^{star}=p^{*} d⋆=p∗ 成立, 即最优对偶间隙为零, 那么强对偶性成立. 这说明从 Lagrange ext{Lagrange} Lagrange 对偶函数得到的最好下界是紧的.

x ∈ r e l i n t    D x in oldsymbol{relint} ; mathcal{D} x∈relintD

强对偶性和 Slater ext{Slater} Slater 约束准则

如果等式 d ⋆ = p ∗ d^{star}=p^{*} d⋆=p∗ 成立, 即最优对偶间隙为零, 那么强对偶性成立. 这说明从 Lagrange ext{Lagrange} Lagrange 对偶函数得到的 对于一般情况, 强对偶性不成立. 但是, 如果原问题是凸问题, 即可以表述为如下形式

minimize f 0 ( x ) subject to f i ( x ) ⩽ 0 , i = 1 , ⋯   , m , A x = b , egin{array}{ll} ext{minimize} & f_{0}(x) \ ext{subject to} & f_{i}(x) leqslant 0, quad i=1, cdots, m, \ &A x=b,& end{array} minimizesubject tof0(x)fi(x)⩽0,i=1,⋯,m,Ax=b,

其中, 函数 f 0 , ⋯   , f m f_{0}, cdots, f_{m} f0,⋯,fm 是凸函数, 强对偶性通常（但不总是）成立. 有很多研究成果给出了强对偶性成立的条件 (除了凸性条件以外). 这些条件称为约束准则. 一个简单的约束准则是 Slater ext{Slater} Slater 条件: 存在一点 x ∈ r e l i n t    D x in oldsymbol{relint} ; mathcal{D} x∈relintD 使得下式成立

f i ( x ) < 0 , i = 1 , ⋯   , m , A x = b egin{aligned} f_{i}(x)&<0, quad i=1, cdots, m, \ A x&=b end{aligned} fi(x)Ax<0,i=1,⋯,m,=b

即在可行域 D mathcal{D} D的内部不等式严格成立,仿射等式成立. 满足上述条件的点有时称为严格可行, 这是因为不等式约束严格成立. Slater ext{Slater} Slater 定理说明, 当 Slater ext{Slater} Slater 条件成立 (且原问题是凸问题）时, 强对偶性成立.

当不等式约束函数 f i f_{i} fi 中有一些是仿射函数时, Slater ext{Slater} Slater 条件可以进一步改进. 如果最前面的 k k k 个约束函数 f 1 , ⋯   , f k f_{1}, cdots, f_{k} f1,⋯,fk 是仿射的, 则若下列弱化的条件成立, 强对偶性成立. 该条件为: 存在一点 x ∈ r e l i n t    D x in oldsymbol{relint} ; mathcal{D} x∈relintD 使得

f i ( x ) ⩽ 0 , i = 1 , ⋯   , k , f i ( x ) < 0 , i = k + 1 , ⋯   , m , A x = b egin{aligned}{} f_{i}(x) &leqslant 0, quad i=1, cdots, k, \ f_{i}(x)&<0, quad i=k+1, cdots, m, \ A x&=b end{aligned} fi(x)fi(x)Ax⩽0,i=1,⋯,k,<0,i=k+1,⋯,m,=b

换言之, 在可行域 D mathcal{D} D的内部, 仿射不等式不需要严格成立. 注意到当所有约束条件都是线性等式或不等式且 dom f 0 ext{dom} f_{0} domf0 是开集时, 改进的 Slater ext{Slater} Slater 条件就是可行性条件.