凸函数的对偶问题是解决最优化的有效方法。

Lagrange对偶函数

Lagrange${p_{207}}$

考虑标准形式的优化问题：

$\min \space f_o(x)$

$s.t. \space f_i(x)\le 0,i=1,...,m$

$h_i(x) = 0,i=1,...,p$

注意这里并没有假设问题是凸优化问题。

Lagrange对偶的基本思想是在目标函数中考虑问题的约束条件，即添加约束条件的加权和，得到目标的增广函数。

上述函数的Lagrange函数为：

$L(x, \lambda, v)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} v_{i} h_{i}(x)$

其中$\lambda_i$、$v_i$为对应的Lagrange乘子。 向量$<$称为对偶变量或问题的Lagrange乘子向量。

Lagrange对偶函数

定义Lagrange对偶函数为Lagrange函数关于$x$取得的最小值，即：

$g(\lambda, v)=\inf _{x \in D} L(x, \lambda, v)=\inf _{x \in D}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} v_{i} h_{i}(x)\right)$

若Lagrange函数关于$x$无下界，则对偶函数取值$- \infty$。

因为对偶函数是一簇关于$(\lambda,v)$的仿射函数的逐点下确界，所以即使原问题不是凸的，对偶函数也是凹函数。

最优值的下界

很容易验证，对偶函数构成了原问题最优值$p^\star$的下界，即对于任意$\lambda \succeq 0$，有下式成立：

$g(\lambda,v)\le p^\star$

例子

线性方程组的最小二乘解${p_{210}}$

$\min \space x^Tx$

$s.t.\space Ax = b$

这个问题没有不等式约束，有$p$个线性等式约束。其Lagrange函数是：

$L(x,v) = x^Tx + v^T (Ax-b)$

对偶问题是：

$g(v) = \inf _x L(x,v)$

因为$L(x,v)$是$x$的二次凸函数，因此可以通过求解以下最优性条件得到函数的最小值（无约束条件）：

$\bigtriangledown_xL(x,v) = 2x +A^Tv = 0$

在点$x = -(1/2)A^Tv$处Lagrange函数达到最小值。

标准形式的线性规划

$\min c^Tx$

$s.t. \space Ax = b$

$x \succeq 0$

转化为Lagrange函数为：

$L(x,\lambda,v) = c^Tx - \sum\limits_{i=1}^n\lambda_ix_i + v^T(Ax -b) = -b^Tv + (c + A^Tv - \lambda)^Tx$

对偶函数为：

$g(\lambda,v) = \inf_xL(x,\lambda,v) = -b^Tv + \inf_x(c + A^Tv - \lambda)^Tx$

因为线性函数只有在恒为零时才有下界，因此，当$c + A^Tv - \lambda=0$时，$g(\lambda,v) = -b^Tv$，其余情况下$g(\lambda,v) = - \infty$。

Lagrange对偶函数和共轭函数${p_{212}}$

回忆共轭函数定义为：

$f^\star(y) = \sup\limits_{x\in dom f} (y^Tx - f(x))$

事实上，共轭函数与Lagrange对偶函数密切相关。我们可以考虑一个优化问题：

$\min f_0(x)$

$s.t. \space Ax \preceq b$

$Cx = d$

利用共轭函数，可以将问题的对偶函数表示为：

$\begin{aligned} g(\lambda, v) &=\inf _{x}\left(f_{0}(x)+\lambda^{T}(A x-b)+v^{T}(C x-d)\right) \\ &=-b^{T} \lambda-d^{T} v+\inf _{x}\left(f_{0}(x)+\left(A^{T} \lambda+C^{T} v\right)^{T} x\right) \\ &=-b^{T} \lambda-d^{T} v-f_{0}^{\star}\left(-A^{T} \lambda-C^{T} v\right) \end{aligned}$

熵的最大化${p_{214}}$

考虑熵的最大化问题：

$\min \space f_0(x) = \sum\limits_{i=1}^nx_i\log x_i$

$s.t. \space Ax \preceq b$

$1^Tx = 1$

关于$x$的负熵函数$u\log u$的共轭函数是$e^{v-1}$（见${p_{86}}$）。因为函数$f_0$是不同变量的负熵函数的和，因此其共轭函数为：

$f^\star _0(y) = \sum\limits_{i=1}^ne^{y_i-1}$

根据之前的结论，可以知道其对偶函数为：

$g(\lambda,v) = -b^T\lambda -v -\sum\limits_{i=1}^n e^{-a_i^T\lambda -v-1}$

其中$a_i$是矩阵$A$的第$i$列向量。

Lagrange对偶问题

定义

对于任意一组（$\lambda,v$），Lagrange对偶函数给出优化问题的最优值的下界。因此，我们关心的是从Lagrange函数中能得到的最好下界是什么？

$\max g(\lambda,v)$

$s.t. \space \lambda \succeq 0$

上述问题为Lagrange对偶问题，是一个凸优化问题（与原问题的凹凸性无关）。

例子

标准形式线性规划的Lagrange对偶

我们之前已经写出了线性规划的对偶函数，因此不难写出该问题的对偶问题：

$\max -b^Tx$

$s.t. A^Tv - \lambda +c = 0$

$\lambda \succeq 0$

我们还可以将$\lambda$去掉，进一步简化问题为：

$\max -b^Tx$

$A^Tv + c \succeq 0$

这是一个不等式形式的线性规划（我们将等式形式的线性规划通过对偶问题转化为不等式）。

不等式形式的线性规划的Lagrange对偶

类似的，我们可以写出不等式形式的线性规划问题：

$\min c^Tx$

$s.t. Ax \preceq b$

其Lagrange函数为：

$L(x,\lambda) = c^Tx + \lambda^T(Ax - b) = -b^T\lambda +(A^T\lambda + c)^Tx$

所以对偶函数为：

$g(\lambda) = \inf_x L(x,\lambda) = -b^T\lambda +\inf _x(A^T\lambda + c)^Tx$

因此，当$A^T\lambda + c = 0$且$\lambda \succeq 0$时，$g(\lambda) = -b^T\lambda$

同样，我们可以写出其Lagrange对偶问题：

$\max -b^T\lambda$

$s.t. A^T\lambda +c = 0$

$\lambda \succeq 0$

很有趣的是，我们发现不等式形式的线性规划问题，通过Lagrange对偶问题可以转化为等式形式。

因此，不等式和等式形式的线性规划与其对偶问题存在着对称性。

弱对偶性

用$d^\star$表示Lagrange对偶问题的最优值，原问题的最优值用$p^\star$表示，很容易，我们可以有以下不等式：

$d^\star \le p^\star$

即使原问题不是凸问题，上述不等式依然成立，这个性质称为弱对偶性。

最优对偶间隙定义为$p^\star - d^\star$，给出了原问题最优值以及通过Lagrange对偶函数所能得到的最好下界之差，总是非负的。

为什么我们要大费周折来求对偶问题呢？这是因为当原问题很难求解时，弱对偶不等式可以给出原问题最优值的一个下界，这是因为对偶问题总是凸问题，更容易求解。

强对偶性与Slater准则

如果等式$d^\star = p^\star$成立，即最优对偶间隙为零，则强对偶性成立。

这是我们愿意看见的情形，因为这样我们可以通过求解对偶问题从而得到原问题的最优解。

凸函数

对于一般情况，强对偶性不成立。但是，如果原问题是凸问题，即可以表述为以下形式：

$\min f_0(x)$

$s.t. f_i(x) \le 0$

$Ax = b$

其中$f_i$都是凸函数，则强对偶性通常（不总是）成立。

Slater条件

一个简单的强对偶性成立的条件，我们称为Slater条件，表述为存在一点$x \in relint (D)$

$f_i(x) < 0, i =1,...,m, \space Ax =b$

即每一个约束条件都严格满足。

Slater定理表明，当条件成立且原问题为凸问题时，强对偶性成立。

同时，当不等式约束$f_i$中有一些仿射函数时，Slater条件可以进一步放宽。如果前$k$个条件约束是仿射的，则若下列弱化的条件成立，强对偶性成立（仿射不等式不需要严格成立）。即：

$f_i(x)\le 0, i=1,...,k \space f_i(x)<0,i=k+1,...,m \space Ax =b$

例子

二次约束二次规划QCQP${p_{220}}$

考虑约束和目标函数都是二次函数的优化问题：

$\min (1/2)x^TP_0x + q_0^Tx + r_0$

$s.t. \space (1/2)x^TP_ix + q_i^Tx + r_i \le0$

其Lagrange函数为：

$L(x,\lambda) = (1/2 )x^TP(\lambda)x + q(\lambda)^Tx + r(\lambda)$

其中$P(\lambda) = P_0 + \sum \lambda_iP_i$，$q(\lambda) = q_0 + \sum \lambda_iq_i$，$r(\lambda) = r_o + \sum \lambda_ir_i$

对于$P(\lambda)\succ 0$，可以表述对偶问题为：

$\max -(1/2)q(\lambda)^TP(\lambda)^{-1}q(\lambda) + r(\lambda)$

$s.t. \lambda \succeq 0$

根据Slater条件，当二次不等式约束严格成立时，即存在一点$x$使得：

$(1/2)x^TP_ix + q_i^Tx + r_i <0$

强对偶性成立。

小结

总的来说，传统的Lagrange函数的作用是使得有约束的问题变为无约束：

通过拉格朗日的办法重新定义一个无约束问题这个无约束问题等价于原来的约束优化问题，从而将约束问题无约束化。

而Lagrange对偶问题则进一步，将最小化最大值问题转化为最大化最小值问题，即最大化Lagrange对偶函数来求得原问题的解的下界（在Slater条件下相等），而对偶函数的好处是它始终是一个凸函数。

对偶性我们可以从之前线性规划的对偶问题看出眉目。

最优性条件${p_{233}}$

互补松弛性

设原问题和对偶问题得到最优值都可以达到且相等（即强对偶性成立）。令$x^\star$是原问题的最优解，$(\lambda ^\star,v^\star)$是对偶问题的最优解，则：

$\begin{aligned} f_{0}\left(x^{\star}\right) &=g\left(\lambda^{\star}, v^{\star}\right) \\ &=\inf _{x}\left(f_{0}(x)+\sum \lambda_{i}^{\star} f_{i}(x)+\sum v_{i}^{\star} h_{i}(x)\right) \\ & \leq f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} f_{i}\left(x^{\star}\right)+\sum v_{i}^{\star} h_{i}\left(x^{\star}\right) \\ & \leq f_{0}\left(x^{\star}\right) \end{aligned}$ 可以得到一个重要的结论：

$\lambda_i^\star f_i(x^\star) = 0$

这个条件被称为互补松弛性。它对任意原问题最优解$x^\star$以及对偶问题的最优解$(\lambda^\star,v^\star)$都成立。可以将互补松弛条件写成：

$\lambda ^\star > 0 \Rightarrow f_i(x^\star) =0$

$f_i(x^\star) < 0 \Rightarrow \lambda^\star = 0$

因此，除了第$i$个约束起作用外，最优Lagrange乘子的第$i$项都为零。

KKT最优性条件

假设函数$f_i$都可微（定义域是开集），但并不假设其为凸函数。

非凸问题的KKT条件${p_{235}}$

当对偶间隙为0时，因为$L(x,\lambda^\star,v^\star)$关于$x$求极小在$x^\star$处取得最小值，因此函数在$x^\star$处的导数必须为零，因此：

$\triangledown f_0(x^\star)+\sum\lambda_i^\star\triangledown f_i(x^\star) + \sum v_i^\star\triangledown h_i(x^\star) = 0$

因此，我们可以得到：

$f_i(x^\star) \le 0$

$h_i(x^\star) = 0$

$\lambda_i^\star \ge 0$

$\lambda_i^\star f_i(x^\star )= 0$

$\triangledown f_0(x^\star)+\sum\lambda_i^\star\triangledown f_i(x^\star) + \sum v_i^\star\triangledown h_i(x^\star) = 0$

上述条件为KKT条件，如果强对偶性成立，那么任何一对原问题的最优解和对偶问题的最优解必须满足KKT条件。

凸问题的KKT条件

当原问题是凸问题时，满足KKT条件的点也是原、对偶最优解。即若函数$f_i$是凸函数，$h_i$是仿射函数，$\tilde{x},\tilde{\lambda},\tilde{v}$是任意满足KKT条件的点：

$f_i(\tilde{x}) \le 0$

$h_i(\tilde{x}) = 0$

$\tilde{\lambda_i} \ge 0$

$\tilde{\lambda_i} f_i(\tilde{x})= 0$

$\triangledown f_0(\tilde{x})+\sum\tilde{\lambda_i}\triangledown f_i(\tilde{x}) + \sum \tilde{v_i}\triangledown h_i(\tilde{x}) = 0$

那么$\tilde{x},\tilde{\lambda},\tilde{v}$分别是原问题和对偶问题的最优解。

小结

若原问题为普通优化问题，如果强对偶性成立，那么任何一对原问题的最优解和对偶问题的最优解必须满足KKT条件。

而如果是目标函数和约束函数可微的凸优化问题，任意满足KKT条件的点分别是原问题、对偶问题的最优解。

因此，我们可以通过求解KKT条件，来求解原问题的最优解。

扰动及灵敏度分析

当强对偶性成立时，对原问题的约束进行扰动，对偶问题最优变量为原问题最优值的灵敏度分析提供了很多有用的信息。

扰动问题${p_{241}}$

$\min f_0(x)$

$s.t.\space f_i(x)\le u_i$

$h_i(x)=v_i$

若$u_i$大于0，则我们放松了第$i$个不等式约束；若$u_i$小于0，则我们加强了第$i$个不等式约束。

定义$p^\star(u,v)$为扰动问题的最优值：

$p^\star(u,v) = \inf\{f_o(x)| \exists x\in D ,f_i(x)\le u_i,h_i(x) = v_i\}$

若定义$p^\star$为原始问题的最优解，可以发现$p^\star(0,0) = p^\star$。

全局不等式

假设强对偶性成立且对偶问题的最优值可以达到。我们由如下推导：

$\begin{aligned} p^{\star}(0,0) &=g\left(\lambda^{\star}, v^{\star}\right) \\ & \leq f_{0}(x)+\sum \lambda_{i}^{\star} f_{i}(x)+\sum v_{i}^{\star} h_{i}(x) \\ & \leq f_{0}(x)+\lambda^{\star T} u+v^{\star T} v \end{aligned}$ 因此，对于任意扰动问题的可行解$x$：

$f_0(x) \ge p^\star (0,0) - {\lambda^\star}^T u - {v^\star}^T v$

即$p^\star(u,v) \ge p^\star (0,0) - {\lambda^\star}^T u - {v^\star}^T v$

解释

• 如果$\lambda^\star$较大，我们加强第$i$个约束(选择$u_i < 0$)，则最优值$p^\star(\lambda^\star ,v^\star)$会大幅增加；
• 如果$v^\star$较大且大于0，选择$v< 0$；或者如果$v^\star$较大且小于0，我们选择$v_i > 0$，这两种情况下最优值也会大幅增加；
• 类似，如果$\lambda^\star$较小，我们放松第$i$个约束(选择$u_i > 0$)，则最优值$p^\star(\lambda^\star ,v^\star)$不会减小太多；

然而，这个不等式只能给出扰动之后最优值的一个下界，结论不是对称的。

局部灵敏度分析${p_{243}}$

假设$p^\star(u,v)$在$u = 0$和$v = 0$处可微，假设强对偶性成立，则：

$\lambda^\star_i = -\frac{\partial p^\star(0,0)}{\partial u_i} \quad v^\star_i = -\frac{\partial p^\star(0,0)}{\partial v_i}$

可以发现，最优Lagrange乘子就是最优值关于约束扰动的局部灵敏度。

并且，这种关系是对称的：若稍微加强不等式约束，会使得最优值增大；若稍微放松不等式约束，会使得最优值减小。

Reference

• 拉格朗日对偶问题