拉格朗日对偶函数及对偶问题

对于一般地约束优化问题：

$$\begin{array}{ll} {\min } & {f(\boldsymbol x)} \qquad\qquad\qquad\qquad\qquad\qquad (A.1)\\ {\text {s.t.}} & {g_{i}(\boldsymbol x) \leq 0 \quad(i=1, \ldots, m)} \\ {} & {h_{j}(\boldsymbol x)=0 \quad(j=1, \ldots, n)} \end{array}$$

其中，自变量$\boldsymbol x\in \mathbb{R}^k$。设优化问题（A.1）的定义域为$D=\boldsymbol{dom} f \cap \bigcap\limits_{i=1}^{m}\boldsymbol{dom} g_i \cap \bigcap\limits_{j=1}^{n}\boldsymbol{dom} h_j $，可行集为$\tilde{D}=\{\boldsymbol x|\boldsymbol x\in D,g_i(\boldsymbol x) \leq 0,h_j(\boldsymbol x) = 0\}$，最优值为$p^*=\min\{f(\tilde{\boldsymbol x})\}$。由拉格朗日函数的定义可知优化问题（A.1）的拉格朗日函数为

$$L(\boldsymbol x,\boldsymbol \mu,\boldsymbol \lambda)=f(\boldsymbol x)+\sum_{i=1}^{m}\mu_i g_i(\boldsymbol x)+\sum_{j=1}^{n}\lambda_j h_j(\boldsymbol x)$$

其中$\boldsymbol \mu=(\mu_1,\mu_2,…,\mu_m)^T,\boldsymbol \lambda=(\lambda_1,\lambda_2,…,\lambda_n)^T$为拉格朗日乘子向量。

拉格朗日对偶函数

定义优化问题（A.1）的拉格朗日对偶函数$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)$为$L(\boldsymbol x,\boldsymbol \mu,\boldsymbol \lambda)$关于$\boldsymbol x$的下确界，也即

$$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)=\mathop{\inf}_{\boldsymbol x∈D}L(\boldsymbol x,\boldsymbol \mu,\boldsymbol \lambda)=\mathop{\inf}_{\boldsymbol x∈D} \left( f(\boldsymbol x)+\sum_{i=1}^{m}\mu_i g_i(\boldsymbol x)+\sum_{j=1}^{n}\lambda_j h_j(\boldsymbol x) \right)$$

对偶函数$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)$有如下重要性质：

• 对偶函数$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)$是一族关于$(\boldsymbol \mu,\boldsymbol \lambda)$的仿射函数的逐点下确界，所以无论优化问题（A.1）是否是凸优化问题，其对偶函数$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)$恒为凹函数（证明参见[1] § 3.2.3）；
• 当$\boldsymbol \mu \succeq 0$时，$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)$构成了优化问题（A.1）最优值$p^*$的下界，也即 $$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)\leq p^*$$ 【证明】：设$\tilde{\boldsymbol x}\in\tilde{D}$是优化问题（A.1）的可行点，那么当$\boldsymbol \mu \succeq 0$时 $$\sum_{i=1}^{n}\mu_i g_i(\tilde{\boldsymbol x})+\sum_{j=1}^{m}\lambda_j h_j(\tilde{\boldsymbol x}) \leq 0$$ 这是因为左边第一项非正而第二项恒为0。根据此不等式可以进一步推得 $$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)=\mathop{\inf}_{\boldsymbol x∈D}L(\boldsymbol x,\boldsymbol \mu,\boldsymbol \lambda) \leq L(\tilde{\boldsymbol x},\boldsymbol \mu,\boldsymbol \lambda) \leq f(\tilde{\boldsymbol x})$$ $$\Gamma (\boldsymbol \mu,\boldsymbol \lambda) \leq \min\{f(\tilde{\boldsymbol x})\}=p^*$$ 所以，当$\boldsymbol \mu \succeq 0$时，$\Gamma (\boldsymbol \mu,\boldsymbol \lambda) \leq p^*$恒成立，证毕。

拉格朗日对偶问题

由以上分析可知，当$\boldsymbol \mu \succeq 0$时，对偶函数$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)$构成了优化问题（A.1）最优值$p^*$的下界，那么对偶函数所能取到的最优下界是多少？这也就引出了求对偶函数最大值的问题。定义求对偶函数最大值的优化问题为拉格朗日对偶问题，也即

$$\begin{array}{ll} {\max } & {\Gamma (\boldsymbol \mu,\boldsymbol \lambda)} \qquad\qquad\qquad\qquad\qquad\qquad (B.1)\\ {\text {s.t.}} & {\boldsymbol \mu \succeq 0} \end{array}$$

设优化问题（B.1）的最优值为$d^*$，显然$d^* \leq p^*$，此时称为“弱对偶性”成立，若$d^* = p^*$，则称为“强对偶性”成立。对偶问题有如下重要性质：

• 对偶问题恒为凸优化问题，因为对偶函数$\Gamma (\boldsymbol \mu,\boldsymbol \lambda)$恒为凹函数（加个负号即可转为凸函数），约束条件$\boldsymbol \mu \succeq 0$恒为凸集。这也就是为什么不直接求解主问题转而去求解对偶问题的主要原因；

• 当主问题（A.1）满足某些充分条件（sufficient conditions）^[2]时，强对偶性成立。常见的充分条件有Slater条件^[3]：“若主问题是凸优化问题，且可行集$\tilde{D}$中存在一点能使得所有不等式约束的不等号成立，则强对偶性成立”（证明参见[1] § 5.3.2）。Slater条件也是KKT条件中的约束限制条件之一；

• Slater条件的“弱化”形式（参见[1] § 5.2.3）：“若主问题是凸优化问题，前$k$个不等式约束为仿射函数，可行集$\tilde{D}$中存在一点能使得第$k+1$至第$m$个不等式约束的不等号成立，则强对偶性成立”。也就是说当不等式约束中有仿射函数时，不要求可行集$\tilde{D}$中存在一点使得这些仿射不等式的不等号成立；

• 设$f(\boldsymbol x),g_i(\boldsymbol x),h_j(\boldsymbol x)$一阶偏导连续，$\boldsymbol x^*,(\boldsymbol \mu^*,\boldsymbol \lambda^*)$分别为主问题（A.1）（注：此时并不要求为凸优化问题）和对偶问题（B.1）的最优解，若强对偶性成立，则$\boldsymbol x^*,\boldsymbol \mu^*,\boldsymbol \lambda^*$一定满足KKT条件，也就是说KK条件是强对偶性成立的必要条件；
  【证明】：因为$\boldsymbol x^*,(\boldsymbol \mu^*,\boldsymbol \lambda^*)$分别为主问题（A.1）和对偶问题（B.1）的最优解，且此时强对偶性成立，那么

  $$\begin{aligned} f(\boldsymbol x^*)&=\Gamma(\boldsymbol \mu^*,\boldsymbol \lambda^*) &(B.2.1)\\ &=\mathop{\inf}_{\boldsymbol x∈D} \left( f(\boldsymbol x)+\sum_{i=1}^{m}\mu_i^* g_i(\boldsymbol x)+\sum_{j=1}^{n}\lambda_j^* h_j(\boldsymbol x) \right) &(B.2.2)\\ &\leq f(\boldsymbol x^*)+\sum_{i=1}^{m}\mu_i^* g_i(\boldsymbol x^*)+\sum_{j=1}^{n}\lambda_j^* h_j(\boldsymbol x^*) &(B.2.3)\\ &\leq f(\boldsymbol x^*)&(B.2.4) \end{aligned}$$

  其中，（B.2.1）是由强对偶性成立推得；（B.2.2）是由$\Gamma(\boldsymbol \mu,\boldsymbol \lambda)$的定义推得；（B.2.3）是由下确界函数的性质推得；（B.2.4）是由$\boldsymbol \mu \succeq 0\Rightarrow\mu_i^*\geq0,g_i(\boldsymbol x^*)\leq0,h_j(\boldsymbol x^*)=0$推得。由于$f(\boldsymbol x^*)=f(\boldsymbol x^*)$，所以此时上式中的两个不等号均可以替换为等号。如果将（B.2.3）中的不等号替换为等号，那么可以推得$\boldsymbol x^*$为$L(\boldsymbol x,\boldsymbol \mu^*,\boldsymbol \lambda^*)$的最小值点，所以$L(\boldsymbol x,\boldsymbol \mu^*,\boldsymbol \lambda^*)$在$\boldsymbol x^*$处的梯度一定为0，也即

  $$\nabla_{\boldsymbol x} L(\boldsymbol x^* ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )=\nabla f(\boldsymbol x^* )+\sum_{i=1}^{m}\mu_i^* \nabla g_i(\boldsymbol x^* )+\sum_{j=1}^{n}\lambda_j^* \nabla h_j(\boldsymbol x^*)=0 \qquad (B.3)$$

  如果将（B.2.4）中的不等号替换为等号，那么可以推得

  $$\left\{ \begin{array}{lcl} \sum_{i=1}^{m}\mu_i^* g_i(\boldsymbol x^*)=0 \\ \mu_i^*\geq0 \\ g_i(\boldsymbol x^*)\leq0\\ \end{array}\right. \Rightarrow \left\{ \begin{array}{lcl} \mu_i^* g_i(\boldsymbol x^*)=0 \\ \mu_i^*\geq0 \\ g_i(\boldsymbol x^*)\leq0\\ \end{array}\right.\qquad (B.4)$$

  此条件称作互补松弛（complementary slackness）。将$h_j(\boldsymbol x^*)=0$和（B.3）、（B.4）整合在一起即可得KKT条件，证毕。

• 若主问题（A.1）为凸优化问题，且$f(\boldsymbol x),g_i(\boldsymbol x),h_j(\boldsymbol x)$一阶偏导连续，如果存在$\boldsymbol x^*,\boldsymbol \mu^*,\boldsymbol \lambda^*$满足KKT条件，那么$\boldsymbol x^*$和$(\boldsymbol \mu^*,\boldsymbol \lambda^*)$一定是主问题（A.1）和对偶问题（B.1）的最优解，且强对偶性成立，也就是说当主问题（A.1）为凸优化问题时，KKT条件是强对偶性成立的充分条件。
  【证明】：已知存在$\boldsymbol x^*,\boldsymbol \mu^*,\boldsymbol \lambda^*$满足KKT条件，也即

  $$\left\{ \begin{aligned} & \nabla_{\boldsymbol x} L(\boldsymbol x^* ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )=\nabla f(\boldsymbol x^* )+\sum_{i=1}^{m}\mu_i^* \nabla g_i(\boldsymbol x^* )+\sum_{j=1}^{n}\lambda_j^* \nabla h_j(\boldsymbol x^*)=0 &(B.5.1) \\ & h_j(\boldsymbol x^*)=0 &(B.5.2) \\ & g_i(\boldsymbol x^*) \leq 0 &(B.5.3) \\ & \mu_i^* \geq 0 &(B.5.4)\\ & \mu_i^* g_i(\boldsymbol x^*)=0 &(B.5.5) \end{aligned} \right.$$

  由（B.5.2）和（B.5.3）可知$\boldsymbol x^*$是可行集$\tilde{D}$中的点；由（B.5.4）可推得$L(\boldsymbol x,\boldsymbol \mu^*,\boldsymbol \lambda^*)$是关于$\boldsymbol x$的凸函数，因为

  $$L(\boldsymbol x ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )= f(\boldsymbol x)+\sum_{i=1}^{m}\mu_i^* g_i(\boldsymbol x )+\sum_{j=1}^{n}\lambda_j^* h_j(\boldsymbol x)$$

  由于此时主问题（A.1）为凸优化问题，所以上式中的$f(\boldsymbol x),g_i(\boldsymbol x)$为凸函数，$h_j(\boldsymbol x)$为仿射函数，显然，当$\mu_i^* \geq 0$时$L(\boldsymbol x ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )$恒为关于$\boldsymbol x$的凸函数；由（B.5.1）可知，$\boldsymbol x^*$是$L(\boldsymbol x ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )$的极值点，由凸函数的性质可知，此极值点必是最小值点，那么可以进一步推得

  $$\begin{aligned} \Gamma(\boldsymbol \mu^*,\boldsymbol \lambda^*)&=\mathop{\inf}_{\boldsymbol x∈D} \left( f(\boldsymbol x)+\sum_{i=1}^{m}\mu_i^* g_i(\boldsymbol x)+\sum_{j=1}^{n}\lambda_j^* h_j(\boldsymbol x) \right) &(B.6.1)\\ &=L(\boldsymbol x^* ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )&(B.6.2)\\ &=f(\boldsymbol x^*)+\sum_{i=1}^{m}\mu_i^* g_i(\boldsymbol x^*)+\sum_{j=1}^{n}\lambda_j^* h_j(\boldsymbol x^*) &(B.6.3)\\ &=f(\boldsymbol x^*)&(B.6.4) \end{aligned}$$

  其中，（B.6.1）是由$\Gamma(\boldsymbol \mu,\boldsymbol \lambda)$的定义推得；（B.6.2）是由

  $$\mathop{\inf}_{\boldsymbol x∈D} \left( f(\boldsymbol x)+\sum_{i=1}^{m}\mu_i^* g_i(\boldsymbol x^*)+\sum_{j=1}^{n}\lambda_j^* h_j(\boldsymbol x) \right)=\min\{L(\boldsymbol x ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )\}=L(\boldsymbol x^* ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )$$

  推得；（B.6.3）是由$L(\boldsymbol x,\boldsymbol \mu,\boldsymbol \lambda)$的定义推得；（B.6.4）是由（B.5.2）和（B.5.5）推得。因此，根据上述对偶函数的第二条性质可知，当$\boldsymbol \mu \succeq 0$时，能找到$\boldsymbol x^*\in \tilde{D}$和$(\boldsymbol \mu^*,\boldsymbol \lambda^*)$使得$\Gamma(\boldsymbol \mu^*,\boldsymbol \lambda^*)=f(\boldsymbol x^*)$成立，那么此时强对偶性成立，且$\boldsymbol x^*$和$(\boldsymbol \mu^*,\boldsymbol \lambda^*)$是主问题（A.1）和对偶问题（B.1）的最优解，证毕。

综合上述最后两条性质可知：若主问题（A.1）为非凸优化问题，KKT条件是强对偶性成立的必要条件，若主问题（A.1）为凸优化问题，那么KKT条件即为强对偶性成立的充要条件。

参考文献：

[1] 王书宁 译.《凸优化》
[2] Strong duality
[3] Slater’s condition