广义不等式

本章讲授的 Lagrange 对偶理论可以推广至具有广义不等式约束的问题中，即

$$\begin{array}{rl}\mathrm{minimize}& f_0(x)\\ \mathrm{subject}\mathrm{to}& f_i(x){⪯}_{K_i}0,i=1,\cdots ,m\\ & h_i(x)=0,i=1,\cdots ,p\end{array}$$

其中 $K_i\subseteq {\mathbf{R}}^{k_i}$ 是正常锥（闭、凸、尖且有非空内部），并约定

$$u{⪯}_{K_i}v⟺v-u\in K_i.$$

因此，约束 $f_i(x){⪯}_{K_i}0$ 等价于 $-f_i(x)\in K_i$。本节推导广义不等式对应的乘子约束，并用半定规划说明如何构造对偶问题。

对偶锥与 Lagrange 对偶函数

锥 $K$ 的对偶锥定义为

$$K^{\ast }=\{z\mid z^{\mathrm{\top }}u⩾0,\mathrm{\forall }u\in K\}.$$

若 $f_i(x){⪯}_{K_i}0$，则 $-f_i(x)\in K_i$。对任意 ${\lambda }_i\in K_i^{\ast }$，由对偶锥定义可得 ${\lambda }_i^{\mathrm{\top }}{f}_i(x)⩽0$。所以广义不等式的 Lagrange 乘子必须满足 ${\lambda }_i\in K_i^{\ast }$。

令 $h(x)=(h_1(x),\dots ,h_p(x))$，Lagrange 函数和对偶函数分别为

$$\begin{array}{rl}L(x,\lambda ,\nu )& =f_0(x)+\sum _{i=1}^m{\lambda }_i^{\mathrm{\top }}{f}_i(x)+{\nu }^{\mathrm{\top }}h(x),\\ g(\lambda ,\nu )& =\underset{x\in D}{inf}L(x,\lambda ,\nu ),\end{array}$$

其中 $D$ 是原问题的定义域。对任意原问题可行点 $\tilde{x}$ 及满足 ${\lambda }_i\in K_i^{\ast }$ 的乘子，等式约束项为零，广义不等式项非正，因此

$$g(\lambda ,\nu )⩽L(\tilde{x},\lambda ,\nu )⩽f_0(\tilde{x}).$$

对所有原问题可行点取下确界，便得到弱对偶关系 $g(\lambda ,\nu )⩽p^{\ast }$。相应的 Lagrange 对偶问题为

$$\begin{array}{rl}\mathrm{maximize}& g(\lambda ,\nu )\\ \mathrm{subject}\mathrm{to}& {\lambda }_i\in K_i^{\ast },i=1,\dots ,m.\end{array}$$

记其最优值为 $d^{\ast }$，则始终有 $d^{\ast }⩽p^{\ast }$。这与普通不等式对偶的结构相同，区别在于标量乘子的非负约束被对偶锥约束取代。

Slater 条件与强对偶

考虑等式约束为仿射形式 $Ax=b$ 的问题。假设 $f_0$ 为凸函数，每个 $f_i$ 关于锥 $K_i$ 凸，并且存在 $x$ 满足

$$x\in \mathrm{relint}D,Ax=b,f_i(x){\prec }_{K_i}0,i=1,\dots ,m,$$

其中 $u{\prec }_{K}v$ 表示 $v-u\in \mathrm{int}K$。这就是广义 Slater 条件。若满足该条件且原问题最优值有限，则强对偶成立，且对偶最优值能够取到。对半定锥 ${\mathbf{S}}_{+}^k$，严格不等式表示矩阵负定；对二阶锥，则表示 $-f_i(x)$ 严格位于锥内部。关于向量值函数的锥凸性，另见广义不等式下的凸性。

例子：半定规划的对偶

考虑半定规划

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& F(x)=\sum _{i=1}^n{x}_i{F}_i+G⪯0,\end{array}$$

其中 $F_i,G\in {\mathbf{S}}^k$，约束锥为半正定锥 ${\mathbf{S}}_{+}^k$。该锥关于矩阵内积 $⟨X,Y⟩=\mathrm{tr}(XY)$ 自对偶，因此乘子是满足 $Z⪰0$ 的对称矩阵。Lagrange 函数为

$$\begin{array}{rl}L(x,Z)& =c^{\mathrm{\top }}x+\mathrm{tr}(F(x)Z)\\ & =\sum _{i=1}^n{x}_i(c_i+\mathrm{tr}(F_{i}Z))+\mathrm{tr}(GZ).\end{array}$$

对自由变量 $x$ 取下确界：只要某个 $c_i+\mathrm{tr}(F_{i}Z)\ne 0$，Lagrange 函数就沿相应方向无界，故 $g(Z)=-\mathrm{\infty }$；若这些系数全为零，则 $g(Z)=\mathrm{tr}(GZ)$。于是对偶问题为

$$\begin{array}{rl}\mathrm{maximize}& \mathrm{tr}(GZ)\\ \mathrm{subject}\mathrm{to}& \mathrm{tr}(F_{i}Z)+c_i=0,i=1,\dots ,n,\\ & Z⪰0.\end{array}$$

只要原问题可行，任意对偶可行矩阵 $Z$ 都给出原问题最优值的一个下界；若进一步满足适当的广义 Slater 条件，则原始和对偶最优值相等。关于半定规划的建模形式和其他例子，另见广义不等式约束。