前言
本章我们介绍Lagrange函数、对偶函数、对偶问题。
系列文章
1、Lagrange对偶函数
1.1：Lagrange对偶函数的基本概念
定义4.1.1：优化问题的Lagrange对偶函数
设有优化问题：
$$ \begin{align} &\text{minimize}\ \ f_0(\boldsymbol{x})\\ &subject\ to\ f_i(\boldsymbol{x})\leq 0,\ i=1,\cdots,m\\ &\qquad\qquad\ \ h_i(\boldsymbol{x})=0,\ i=1,\cdots,p \end{align}\tag{*} $$
该问题不一定是凸问题。自变量$\boldsymbol{x}\in\mathbb{R}^n$，问题的域：$\mathcal{D}=\bigcap_{i=1}^m \text{dom}f_i\cap\bigcap_{i=1}^p \text{dom}h_i\cap\text{dom}f_0$。设问题（*）的最优值为$p^*$。设有函数：$L:\mathbb{R}^n\times \mathbb{R}^m\times \mathbb{R}^p\to \mathbb{R}$，其形式为：
$$ L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\nu})=f_0(\boldsymbol{x})+\sum_{i=1}^m \lambda_i f_i(\boldsymbol{x})+\sum_{i=1}^p \nu_i h_i(\boldsymbol{x}) $$
称函数$L$为问题（*）的Lagrange函数，$\text{dom}L=\mathcal{D}\times \mathbb{R}^m\times \mathbb{R}^p$。向量$\boldsymbol{\lambda},\boldsymbol{\nu}$为Lagrange乘子向量。
同时称函数$g:\mathbb{R}^m\times \mathbb{R}^p\to \mathbb{R}$：
$$ g(\boldsymbol{\lambda},\boldsymbol{\nu})=\inf_{x\in\mathcal{D}} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\nu}) $$
为问题（*）的Lagrange对偶函数。
定理4.1.1：Lagrange对偶函数的性质
（1）对偶函数一定为凹函数
（2）$\forall \boldsymbol{\lambda}\succcurlyeq \boldsymbol{0},\forall \boldsymbol{\nu},g(\boldsymbol{\lambda},\boldsymbol{\nu})\leq p^*$
我们来看对偶函数的几个例子。
例1.设有优化问题：
$$ \begin{aligned} \min \ & \boldsymbol{x}^T\boldsymbol{x},\boldsymbol{x}\in \mathbb{R}^n \\ s.t. \ & \boldsymbol{Ax}=\boldsymbol{b},\boldsymbol{A}\in \mathbb{R}^{p\times n},\boldsymbol{b}\in \mathbb{R}^p\\ \end{aligned} $$
该问题的Lagrange函数为：$L(\boldsymbol{x},\boldsymbol{\nu})=\boldsymbol{x}^\top\boldsymbol{x}+\boldsymbol{\nu}^\top(\boldsymbol{Ax}-\boldsymbol{b})$。而对偶函数：
$$ g(\boldsymbol{\nu})=\inf_{x\in\mathbb{R}^n}L(\boldsymbol{x},\boldsymbol{v})=\inf_{\boldsymbol{x}\in\mathbb{R}^n} \boldsymbol{x}^\top\boldsymbol{x}+\boldsymbol{\nu}^\top\boldsymbol{Ax}-\boldsymbol{\nu}^\top\boldsymbol{b} $$
由：$\frac{\partial g(\boldsymbol{\nu})}{\partial \boldsymbol{x}}=2\boldsymbol{x}+\boldsymbol{A\nu}^\top$，令其为零代回$g(\boldsymbol{\nu})$，从而：
$$ g(\boldsymbol{\nu})=-\frac{\boldsymbol{\nu}^\top\boldsymbol{AA}^\top\boldsymbol{\nu}}{4}-\boldsymbol{b}^\top\boldsymbol{\nu} $$
例2.设有优化问题：
$$ \begin{aligned} \min \ & \boldsymbol{c}^T\boldsymbol{x},\boldsymbol{c}\in \mathbb{R}^n \\ s.t. \ & \boldsymbol{Ax}=\boldsymbol{b},\boldsymbol{A}\in \mathbb{R}^{p\times n},\boldsymbol{b}\in \mathbb{R}^p\\ & \boldsymbol{x}\succcurlyeq \boldsymbol{0} \end{aligned} $$
Lagrange函数为：$L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\nu})=\boldsymbol{c}^\top\boldsymbol{x}-\boldsymbol{\lambda}^\top\boldsymbol{x}+\boldsymbol{\nu}^\top(\boldsymbol{Ax}-\boldsymbol{b})$，对偶函数：
$$ g(\boldsymbol{\lambda},\boldsymbol{\nu})=\inf_{x\in\mathbb{R}^n}L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{v})=\begin{cases} -\boldsymbol{b}^\top\boldsymbol{\nu},&\boldsymbol{c}+\boldsymbol{A}^\top\boldsymbol{\nu}-\boldsymbol{\lambda}=\boldsymbol{0}\\ -\infty,&else \end{cases} $$
$f(\boldsymbol{\lambda},\boldsymbol{\nu})=-\boldsymbol{b}^\top\boldsymbol{\nu}$既凸又凹，显然$g$是$f$的扩展。
例3.设有优化问题：
$$ \begin{aligned} \min \ & \boldsymbol{x}^T\boldsymbol{W}\boldsymbol{x},\boldsymbol{W}\in \mathbb{R}^{n\times n} \\ s.t. \ & x_i^2-1=0 \end{aligned} $$
显然这不是一个凸问题。其Lagrange函数为：
$$ \begin{align}L(\boldsymbol{x},\boldsymbol{\nu})&=\boldsymbol{x}^\top\boldsymbol{Wx}+\sum_{i=1}^n \nu_i(x_i^2 -1)\\ &=\boldsymbol{x}^\top\left(\boldsymbol{W}+\text{diag}(v_1,\cdots,v_n)\right)\boldsymbol{x} -\boldsymbol{1}^\top\boldsymbol{v} \end{align} $$
所以：
$$ g(\boldsymbol{\nu})=\begin{cases} -\boldsymbol{1}^\top\boldsymbol{v},&\boldsymbol{W}+\text{diag}(\boldsymbol{\nu})\succeq 0\\ -\infty,&else \end{cases} $$
1.2：Lagrange对偶问题
定义4.1.2：Lagrange对偶问题
对于问题，设其Lagrange对偶函数为$g(\boldsymbol{\lambda},\boldsymbol{\nu})$，构造以下优化问题：
$$ \begin{aligned} \max \ & g(\boldsymbol{\lambda},\boldsymbol{\nu}) \\ s.t. \ & \boldsymbol{\lambda}\succcurlyeq \boldsymbol{0} \end{aligned}\tag{**} $$
我们称问题（*）为原问题（*）的对偶问题。设（*）的最优值为$d^*$，显然地，由定理4.1（2）知，$d^*\leq p^*$。此外，由于对偶函数为凹函数，则对偶问题为一凸问题！设对偶问题的最优解为$(\boldsymbol{\lambda}^*,\boldsymbol{\nu}^*)$，称之为对偶最优解或最优Lagrange乘子。
我们来看上文例2的对偶问题。设有优化问题：
$$ \begin{aligned} \min \ & \boldsymbol{c}^T\boldsymbol{x},\boldsymbol{c}\in \mathbb{R}^n \\ s.t. \ & \boldsymbol{Ax}=\boldsymbol{b},\boldsymbol{A}\in \mathbb{R}^{p\times n},\boldsymbol{b}\in \mathbb{R}^p\\ & \boldsymbol{x}\succcurlyeq \boldsymbol{0} \end{aligned} $$
我们在上文中已经分析了其对偶函数为：
$$ g(\boldsymbol{\lambda},\boldsymbol{\nu})=\begin{cases} -\boldsymbol{b}^\top\boldsymbol{\nu},&\boldsymbol{c}+\boldsymbol{A}^\top\boldsymbol{\nu}-\boldsymbol{\lambda}=\boldsymbol{0}\\ -\infty,&else \end{cases} $$
所以，原问题的对偶问题为：
$$ \begin{aligned} \max \ & -\boldsymbol{b}^\top\boldsymbol{\nu}\\ s.t. \ & \boldsymbol{c}+\boldsymbol{A}^\top\boldsymbol{\nu}\succcurlyeq \boldsymbol{0}\\ \end{aligned} $$
我们可以看出，我们将原始的含有$p$个约束的$n$维优化问题转化为了含有$n$个约束的$p$维优化问题，这便是“对偶”的含义。
2、强对偶性
定义4.2.1：弱对偶性
我们在定理4.1（2）与定义4.2中都说明了：对于原问题的最优值$p^*$与其对偶问题的最优值$d^*$，恒有：
$$ d^*\leq p^* $$
这也被称为弱对偶性原理。称$p^*-d^*$为最优对偶间隙。特别地，若有$d^*=p^*$，则称该对偶问题具有强对偶性。
定义4.2.2：相对内部
设有集合$\boldsymbol{D}$，其仿射包为$\text{aff}\ D$，其相对内部定义为集合：
$$ \text{relint}\ \boldsymbol{D}=\{\boldsymbol{x}\in\boldsymbol{D}|\exists r>0,\mathcal{B}(\boldsymbol{x},r)\cap\text{aff}\ \boldsymbol{D}\subseteq \boldsymbol{D} \} $$
定理4.2.1：Slater条件
设有凸问题：
$$ \begin{aligned} \min \ & f_0(\boldsymbol{x}) \\ s.t. \ & f_i(\boldsymbol{x})\leq 0,i=1,\cdots,m \\ & \boldsymbol{Ax}=\boldsymbol{b}, \boldsymbol{A}\in\mathbb{R}^{p\times n},\boldsymbol{b}\in\mathbb{R}^n \end{aligned} $$
若$\exists \boldsymbol{x}\in\text{relint}\ \mathcal{D}$，使得：
$$ f_i(\boldsymbol{x})<0,i=1,\cdots,m\quad \boldsymbol{Ax}=\boldsymbol{b} $$
成立时，强对偶性成立。此时$\boldsymbol{x}$也被称为严格可行。注意，Slater条件是强对偶性成立的充分条件，反过来是不成立的。
定理4.2.2：弱化的Slater条件
若在定理4.2中的凸问题的不等式约束中，有$k$个是仿射的：$f_1,\cdots,f_k$，则若$\exists \boldsymbol{x}\in\text{relint}\ \mathcal{D}$，使得：
$$ f_i(\boldsymbol{x})\leq0,i=1,\cdots,k\\ f_j(\boldsymbol{x})<0,j=k+1,\cdots,m \\ \boldsymbol{Ax}=\boldsymbol{b} $$
成立时，强对偶性成立。
特别地，若该问题的不等式约束全为仿射的（即原问题为线性规划问题），则只要其可行，则强对偶性成立。
例4.QCQP问题
设有优化问题：
$$ \begin{aligned} \min \ & \frac{1}{2}\boldsymbol{x}^\top\boldsymbol{P}_0\boldsymbol{x}+\boldsymbol{q}_0^\top\boldsymbol{x}+r_0 \\ s.t. \ & \frac{1}{2}\boldsymbol{x}^\top\boldsymbol{P}_i\boldsymbol{x}+\boldsymbol{q}_i^\top\boldsymbol{x}+r_i\leq 0,i=1,\cdots,m \\ where:\ &\boldsymbol{P}_j\in\mathbb{R}^{n\times n},\boldsymbol{q}_j\in\mathbb{R}^n,r_j\in\mathbb{R} \end{aligned} $$
其中，$\boldsymbol{P}_0\in\boldsymbol{S}^n_{++},\boldsymbol{P}_i\in\boldsymbol{S}^n_+,i=1,\cdots,m$，其Lagrange函数为：
$$ \begin{align}L(\boldsymbol{x},\boldsymbol{\lambda})&=\frac{1}{2}\boldsymbol{x}^\top\boldsymbol{P}_0\boldsymbol{x}+\boldsymbol{q}_0^\top\boldsymbol{x}+r_0+\sum_{i=10}^m\left(\frac{1}{2}\lambda_i\boldsymbol{x}^\top\boldsymbol{P}_i\boldsymbol{x}+\lambda_i\boldsymbol{q}_i^\top\boldsymbol{x}+\lambda_ir_i\right)\\ &=\frac{1}{2}\boldsymbol{x}^\top\underbrace{\left(\boldsymbol{P}_0+\sum_{i=1}^m \lambda_i\boldsymbol{P}_i \right)}_{\boldsymbol{P}(\boldsymbol{\lambda})}\boldsymbol{x}+\underbrace{\left(\boldsymbol{q}_0+\sum_{i=1}^m \lambda_i\boldsymbol{q}_i\right)^\top}_{\boldsymbol{q}(\boldsymbol{\lambda})}\boldsymbol{x}+\underbrace{\left(r_0+\sum_{i=1}^m \lambda_i r_i \right)}_{r(\boldsymbol{\lambda})} \end{align} $$
则其对偶问题为：
$$ \begin{aligned} \max \ & g(\boldsymbol{\lambda})=\inf_{\boldsymbol{x}\in\mathbb{R}^n}\{\frac{1}{2}\boldsymbol{x}^\top\boldsymbol{P}(\boldsymbol{\lambda})\boldsymbol{x}+\boldsymbol{q}(\boldsymbol{\lambda})^\top\boldsymbol{x}+r(\boldsymbol{\lambda}) \} \\ s.t. \ & \boldsymbol{\lambda}\succcurlyeq \boldsymbol{0}\\ \end{aligned} $$
由于$\boldsymbol{\lambda}\succcurlyeq \boldsymbol{0}$，所以$\boldsymbol{P}(\boldsymbol{\lambda})=\boldsymbol{P}_0+\sum_{i=1}^m \lambda_i\boldsymbol{P}_i$一定正定，所以：
$$ \nabla_\boldsymbol{x}L(\boldsymbol{x},\boldsymbol{\lambda})=\boldsymbol{P}(\boldsymbol{\lambda})\boldsymbol{x}+\boldsymbol{q}(\boldsymbol{\lambda}) $$
令其为零，并将$\boldsymbol{x}$代回原式，则对偶问题的形式变为：
$$ \begin{aligned} \max \ & -\frac{1}{2}\boldsymbol{q}(\boldsymbol{\lambda})^\top\boldsymbol{P}(\boldsymbol{\lambda})^{-1}\boldsymbol{q}(\boldsymbol{\lambda})+r(\boldsymbol{\lambda}) \\ s.t. \ & \boldsymbol{\lambda}\succcurlyeq \boldsymbol{0}\\ \end{aligned} $$
我们考虑一种极端情况：$q_j\equiv \boldsymbol{0},r_j\equiv 0,j=0,\cdots,m$，此时的不等式约束$\frac{1}{2}\boldsymbol{x}^\top\boldsymbol{P}_i\boldsymbol{x}\leq 0$显然只有平凡解$\boldsymbol{x}=\boldsymbol{0}$，此时我们知道Slater条件是不满足的，因为$\boldsymbol{P}_i$半正定。而另一方面，我们将平凡解代入原问题，知$p^*=0$，对偶问题的最优值显然为$d^*=0=p^*$，因此这便为我们说Slater条件是刻画强对偶性的一个充分条件提供了一个例子。
3、强对偶性的理解（TODO）
设有优化问题：
$$ \begin{aligned} \min \ & f_0(\boldsymbol{x}) \\ s.t. \ & f_i(\boldsymbol{x})\leq 0,i=1,\cdots,m \end{aligned}\tag{P} $$
3.1：几何解释
我们简化一下问题（P）：
$$ \begin{aligned} \min \ & f_0(\boldsymbol{x}) \\ s.t. \ & f_1(\boldsymbol{x})\leq 0 \end{aligned}\tag{P1} $$
我们定义集合：$\boldsymbol{G}=\{(f_1(\boldsymbol{x}),f_0(\boldsymbol{x}))|\boldsymbol{x}\in\mathcal{D} \}$，记$p^*=\inf\{t|(u,t)\in\boldsymbol{G},u\leq 0 \}$，定义函数：$g(\lambda)=\inf\{\lambda u+t|(u,t)\in\boldsymbol{G} \}$。
4、最优性条件
我们重新考虑问题（*）：
$$ \begin{align} &\text{minimize}\ \ f_0(\boldsymbol{x})\\ &subject\ to\ f_i(\boldsymbol{x})\leq 0,\ i=1,\cdots,m\\ &\qquad\qquad\ \ h_i(\boldsymbol{x})=0,\ i=1,\cdots,p \end{align}\tag{*} $$
该问题不一定是凸问题。其对偶函数：
$$ g(\boldsymbol{\lambda},\boldsymbol{\nu})=\inf_{\boldsymbol{x}\in \mathcal{D}}\big\{f_0(\boldsymbol{x})+\sum_{i=1}^m \lambda_i f_i(\boldsymbol{x})+\sum_{i=1}^p \nu_i h_i(\boldsymbol{x}) \big\} $$
对偶问题：
$$ \begin{aligned} \max \ & g(\boldsymbol{\lambda},\boldsymbol{\nu}) \\ s.t. \ & \boldsymbol{\lambda}\succcurlyeq \boldsymbol{0} \end{aligned}\tag{**} $$
如果我们假设：
- 强对偶性成立：$p^*=d^*$
- 所有函数均可微
设原问题最优解为$\boldsymbol{x}^*$，对偶问题最优解为$\boldsymbol{\lambda}^*,\boldsymbol{\mu}^*$，则有：
$$ \begin{align}f_i(\boldsymbol{x}^*)&\leq 0,i=1,\cdots,m\\ h_i(\boldsymbol{x}^*)&=0,i=1,\cdots,p\\ \boldsymbol{\lambda}^*&\succcurlyeq\boldsymbol{0} \end{align} $$
此外还有：
$$ \begin{align}f_0(\boldsymbol{x}^*)=g(\boldsymbol{\lambda}^*,\boldsymbol{\nu}^*)&=\inf_{\boldsymbol{x}\in \mathcal{D}}\left\{f_0(\boldsymbol{x})+\sum_{i=1}^m \lambda_i^* f_i(\boldsymbol{x})+\sum_{i=1}^p \nu^*_i h_i(\boldsymbol{x}) \right\}\\ &\leq f_0(\boldsymbol{x}^*)+\sum_{i=1}^m \lambda_i^* f_i(\boldsymbol{x}^*)+\underbrace{\sum_{i=1}^p \nu^*_i h_i(\boldsymbol{x}^*)}_{=0}\\ \end{align} $$
注意到$f_1(\boldsymbol{x}^*)\leq 0$，$\lambda_i^*\geq 0$，从而$\lambda_i^* f_i(\boldsymbol{x}^*)\leq0$。又因为$f_0(\boldsymbol{x}^*)=g(\boldsymbol{\lambda}^*,\boldsymbol{\nu}^*)$，所以必有$\sum_{i=1}^m \lambda_i^* f_i(\boldsymbol{x}^*)=0$，从而$\lambda_i^* f_i(\boldsymbol{x}^*)=0$。所以我们有：
$$ \begin{cases} \lambda_i>0\Rightarrow f_i(\boldsymbol{x}^*)=0\\ f_i(\boldsymbol{x}^*)<0\Rightarrow \lambda_i=0 \end{cases} $$
这也被称为互补松弛性。
同时又注意到：
$$ \begin{align}d^*=g(\boldsymbol{\lambda}^*,\boldsymbol{\nu}^*)&= \inf_{\boldsymbol{x} \in\mathcal{D}} L\left(\boldsymbol{x}, \boldsymbol{\lambda}^{*}, \boldsymbol{\nu}^{*}\right)\\&=\inf _{\boldsymbol{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\} \\ &=L\left(\boldsymbol{x}^{*}, \boldsymbol{\lambda}^{*}, \boldsymbol{\nu}^{*}\right) \end{align} $$
又每个函数可微，则必有：
$$ \frac{\partial L\left(\boldsymbol{x}, \boldsymbol{\lambda}^{*}, \boldsymbol{\nu}^{*}\right)}{\partial \boldsymbol{x}}\Bigg| _{\boldsymbol{x}=\boldsymbol{x}^*}=\boldsymbol{0} $$
从而:
$$ {\nabla f_{0}\left(\boldsymbol{x}^{*}\right)+\sum_{i=1}^{m} \lambda_{i}^{*} \nabla f_{i}\left(\boldsymbol{x}^{*}\right)+\sum_{i=1}^{p} \nu_{i}^{*} \nabla h_{i}\left(\boldsymbol{x}^{*}\right)=\boldsymbol{0}} $$
这也被称为稳定性。综上，我们有：
定理4.4.1：KKT条件必要性定理
设有问题（*）与其对偶问题（**），若各个函数可微，对偶间隙为零，则当原问题最优解为$\boldsymbol{x}^*$，对偶问题最优解为$\boldsymbol{\lambda}^*,\boldsymbol{\mu}^*$时，必有：
$$ \begin{align} &(1)原问题可行:&f_i(\boldsymbol{x}^*)\leq 0,i=1,\cdots,m\\ &&h_i(\boldsymbol{x}^*)=0,i=1,\cdots,p\\ &(2)对偶问题可行:&\boldsymbol{\lambda}^*\succcurlyeq\boldsymbol{0}\\ &(3)互补松弛:&\lambda_i^* f_i(\boldsymbol{x}^*)=0\\ &(4)稳定性:&{\nabla f_{0}\left(\boldsymbol{x}^{*}\right)+\sum_{i=1}^{m} \lambda_{i}^{*} \nabla f_{i}\left(\boldsymbol{x}^{*}\right)+\sum_{i=1}^{p} \nu_{i}^{*} \nabla h_{i}\left(\boldsymbol{x}^{*}\right)=\boldsymbol{0}} \end{align} $$
上述四个条件也被称为KKT条件。
定理4.4.2：凸问题KKT条件充要性定理
设有凸问题（*）与其对偶问题（**），若有$\boldsymbol{\tilde x}$，与$(\boldsymbol{\tilde \lambda},\boldsymbol{\tilde \nu})$满足：
$$ \begin{align} &(1)原问题可行:&f_i(\boldsymbol{\tilde x})\leq 0,i=1,\cdots,m\\ &&h_i(\boldsymbol{\tilde x})=0,i=1,\cdots,p\\ &(2)对偶问题可行:&\boldsymbol{\tilde \lambda}\succcurlyeq\boldsymbol{0}\\ &(3)互补松弛:&\tilde \lambda_i f_i(\boldsymbol{\tilde x})=0\\ &(4)稳定性:&{\nabla f_{0}\left(\boldsymbol{\tilde x}\right)+\sum_{i=1}^{m} \tilde \lambda_{i} \nabla f_{i}\left(\boldsymbol{\tilde x}\right)+\sum_{i=1}^{p} \tilde \nu_{i} \nabla h_{i}\left(\boldsymbol{\tilde x}\right)=\boldsymbol{0}} \end{align} $$
则原问题最优解为$\boldsymbol{\tilde x}$，对偶问题最优解为$\boldsymbol{\tilde \lambda},\boldsymbol{\tilde \mu}$，且对偶间隙为零。
