凸优化学习笔记 11：对偶原理

前面讲了凸优化问题的定义，以及一些常见的凸优化问题类型，这一章就要引入著名的拉格朗日函数和对偶问题了。通过对偶问题，我们可以将一些非凸问题转化为凸优化问题，还可以求出原问题的非平凡下界，这对复杂优化问题是很有用的。

1. 拉格朗日函数

考虑凸优化问题
$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { subject to } \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &h_{i}(x)=0, \quad i=1, \ldots, p \end{aligned}$ minimize  subject to ​f0​(x)fi​(x)≤0,i=1,…,mhi​(x)=0,i=1,…,p​
假设 $x\in R^n$x∈Rn，定义域为 $\mathcal{D}$D，最优解为 $p^\star$p⋆。

我们定义**拉格朗日函数(Lagrangian)**为 $L:R^n\times R^m\times R^p\to R$L:Rn×Rm×Rp→R，$\text{dom}L=\mathcal{D}\times R^m\times R^p$domL=D×Rm×Rp
$L(x,\lambda,\nu)=f_0(x)+\lambda^Tf(x)+\nu^Th(x)$L(x,λ,ν)=f0​(x)+λTf(x)+νTh(x)

再取下确界得到拉格朗日对偶函数(Lagrange dual function) $g:R^m\times R^p\to R$g:Rm×Rp→R
$g(\lambda,\nu)=\inf_{x\in\mathcal{D}}\left(f_0(x)+\lambda^Tf(x)+\nu^Th(x)\right)$g(λ,ν)=x∈Dinf​(f0​(x)+λTf(x)+νTh(x))

这个拉格朗日对偶函数可不得了啦！他有两个很重要的性质：

1. $g(\lambda,\nu)$g(λ,ν) 是凹函数（不论原问题是否为凸问题）
2. 如果 $\lambda\succeq 0$λ⪰0，那么 $g(\lambda,\nu)\le p^\star$g(λ,ν)≤p⋆（对任意 $\lambda\succeq0,\nu$λ⪰0,ν 都成立）

Remarks：上面两个性质为什么重要呢？首先由于 $g(\lambda,\nu)\le p^\star$g(λ,ν)≤p⋆，这可以给出原问题最优解的一个不平凡下界，这意味着如果原问题很难求解的时候，我们可以转变思路，求解一个新的优化问题：
$\begin{aligned} \text { maximize } \quad& g(\lambda,\nu)\\ \text { subject to } \quad& \lambda\succeq0 \end{aligned}$ maximize  subject to ​g(λ,ν)λ⪰0​

另一方面，由于不论原函数是否为凸优化问题，新的问题都是凸的，因此可以方便求解。下面举几个例子。

例子 1：原问题为
$\begin{aligned} \text { maximize } \quad& x^Tx\\ \text { subject to } \quad& Ax=b \end{aligned}$ maximize  subject to ​xTxAx=b​

那么可以很容易得到拉格朗日函数为 $L(x,\nu)=x^Tx+\nu^T(Ax-b)$L(x,ν)=xTx+νT(Ax−b)，对偶函数为 $g(\nu)=-(1/4)\nu^TAA^T\nu-b^T\nu$g(ν)=−(1/4)νTAATν−bTν，也即

$p^\star\ge g(\nu)$p⋆≥g(ν)。

例子 2：标准形式的线性规划(LP)
$\begin{aligned} \text { maximize } \quad& c^Tx\\ \text { subject to } \quad& Ax=b,\quad x\succeq0 \end{aligned}$ maximize  subject to ​cTxAx=b,x⪰0​

按照定义容易得到对偶问题为
$\begin{aligned} \text { maximize } \quad& -b^T\nu\\ \text { subject to } \quad& A^T\nu+c\succeq0 \end{aligned}$ maximize  subject to ​−bTνATν+c⪰0​

例子 3：原问题为最小化范数
$\begin{aligned} \text { maximize } \quad& \Vert x\Vert\\ \text { subject to } \quad& Ax=b \end{aligned}$ maximize  subject to ​∥x∥Ax=b​

对偶函数为
$g(\nu)=\inf_{x} (\Vert x\Vert+\nu^T(b-Ax)) =\begin{cases}b^T\nu & \Vert A^T\nu\Vert_* \le1 \\ -\infty & o.w.\end{cases}$g(ν)=xinf​(∥x∥+νT(b−Ax))={bTν−∞​∥ATν∥∗​≤1o.w.​

这个推导过程中用到了共轭函数的知识。实际上上面三个例子都是线性等式约束，这种情况下，我们应用定义推导过程中可以很容易联想到共轭函数。（实际上加上线性不等式约束也可以）

例子 4：(原问题非凸)考虑 Two-way partitioning (不知道怎么翻译了…)
$\begin{aligned} \text { maximize } \quad& x^TWx\\ \text { subject to } \quad& x_i^2=1,\quad i=1,...,n \end{aligned}$ maximize  subject to ​xTWxxi2​=1,i=1,...,n​

对偶函数为
$\begin{aligned} g(\nu)=\inf_{x}\left( x^{T}(W+\operatorname{diag}(\nu)) x \right)-\mathbf{1}^{T} \nu =\left\{\begin{array}{ll} -\mathbf{1}^{T} \nu & W+\operatorname{diag}(\nu) \succeq 0 \\ -\infty & \text { otherwise } \end{array}\right. \end{aligned}$g(ν)=xinf​(xT(W+diag(ν))x)−1Tν={−1Tν−∞​W+diag(ν)⪰0 otherwise ​​

于是可以给出原问题最优解的下界为 $p^\star\ge-\mathbf{1}^{T} \nu$p⋆≥−1Tν if $W+\operatorname{diag}(\nu) \succeq 0$W+diag(ν)⪰0。这个下界是不平凡的，比如可以取 $\nu=-\lambda_{\min}(W)\mathbf{1}$ν=−λmin​(W)1，可以给出 $p^\star\ge n\lambda_{\min}(W)$p⋆≥nλmin​(W)。

2. 对偶问题

上面已经多次提到**对偶问题(Lagrange dual problem)**了
$\begin{aligned} \text { maximize } \quad& g(\lambda,\nu)\\ \text { subject to } \quad& \lambda\succeq0 \end{aligned}$ maximize  subject to ​g(λ,ν)λ⪰0​

假如对偶问题的最优解为 $d^\star=\max g(\lambda,\nu)$d⋆=maxg(λ,ν)，那么我们有 $p^\star \ge d^\star$p⋆≥d⋆。

现在我们当然想知道什么情况下可以取等号，也即 $p^\star = d^\star$p⋆=d⋆，此时我们只需要求解对偶问题就可以获得原问题的最优解了。在此之前，我们先引入两个概念：强对偶和弱对偶。

弱对偶(weak duality)：满足 $p^\star \ge d^\star$p⋆≥d⋆，原问题不论是否为凸，弱对偶总是成立；

强对偶(strong duality)：满足 $p^\star = d^\star$p⋆=d⋆，强对偶并不总是成立，如果原问题为凸优化问题，一般情况下都成立。在凸优化问题中，保证强对偶成立的条件为被称为 constraint qualifications。

有很多种不同的 constraint qualifications，常用到的一种为 Slater’s constraint qualification(SCQ)，其表述为

SCQ：对于凸优化问题
$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { subject to } \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &Ax=b \end{aligned}$ minimize  subject to ​f0​(x)fi​(x)≤0,i=1,…,mAx=b​

如果存在可行解 $x\in\text{int}\mathcal{D}$x∈intD，使得
$Ax=b,\quad f_i(x)<0,\quad,i=1,...,m$Ax=b,fi​(x)<0,,i=1,...,m

那么就能保证强对偶性。

Remarks：

• 由于存在线性等式约束，因此实际定义域可能不存在内点，可以将这一条件放松为相对内点 $x\in\text{relint}\mathcal{D}$x∈relintD；
• 如果不等式约束中存在线性不等式，那么他也不必严格小于0。也即如果 $f_i(x)=C^Tx+d$fi​(x)=CTx+d，则只需要满足 $f_i(x)\le0$fi​(x)≤0 即可。

下面再举几个例子，看一看他们的 SCQ 条件是什么。

例子 1：还是考虑线性规划(LP) 或者二次规划(QP)
$\begin{aligned} \text { minimize } \quad& c^Tx \quad(\text{ or }x^TPx)\\ \text { subject to } \quad& Ax\preceq b \end{aligned}$ minimize  subject to ​cTx( or xTPx)Ax⪯b​

那么根据 SCQ 可以得到，如果想得到强对偶性，应该有 $\exist x, \text{ s.t. } Ax\preceq b$∃x, s.t. Ax⪯b。

例子 2：(原问题非凸) Trust Region Methods
$\begin{aligned} \text { minimize } \quad& x^TAx+2b^Tx\\ \text { subject to } \quad& x^Tx\le1 \end{aligned}$ minimize  subject to ​xTAx+2bTxxTx≤1​

其中 $A\nsucceq 0$A⋡0，因此原问题不是凸的。他的对偶函数就是
$g(\lambda)=\inf_x\left(x^T\left(A+\lambda I\right)x+2b^Tx-\lambda\right) =\begin{cases}-b^T(A+\lambda I)^\dagger b-\lambda & A+\lambda I\succeq0,b\in \mathcal{R}(A+\lambda I) \\ -\infty & o.w. \end{cases}$g(λ)=xinf​(xT(A+λI)x+2bTx−λ)={−bT(A+λI)†b−λ−∞​A+λI⪰0,b∈R(A+λI)o.w.​

注意如果不满足 $A+\lambda I\succeq0$A+λI⪰0 或 $b\in \mathcal{R}(A+\lambda I)$b∈R(A+λI)，则 $g(\lambda)\to-\infty$g(λ)→−∞。那么就可以得到对偶问题为
$\begin{aligned} \text {maximize} \quad& -b^{T}(A+\lambda I)^{\dagger} b -\lambda\\ \text {subject to} \quad& A+\lambda I \succeq 0\\ &b \in \mathcal{R}(A+\lambda I) \end{aligned}$maximizesubject to​−bT(A+λI)†b−λA+λI⪰0b∈R(A+λI)​

也可以等价转换为 SDP
$\begin{aligned} \text {maximize} \quad& -t-\lambda\\ \text {subject to}\quad& \left[\begin{array}{cc}A+\lambda I & b \\ b^{T} & t\end{array}\right] \succeq 0 \end{aligned}$maximizesubject to​−t−λ[A+λIbT​bt​]⪰0​

Remarks：这里用到了舒尔补(Schur complement)的知识。考虑矩阵
$X = \left[\begin{array}{cc}A & B \\ B^{T} & C\end{array}\right]$X=[ABT​BC​]

其中 $\det A\ne0,S=C-B^TA^{-1}B$detA​=0,S=C−BTA−1B。那么有以下及条性质：

• $X\succ0 \iff A\succ0,S\succ0$X≻0⟺A≻0,S≻0
• 若 $A\succ0$A≻0，则 $X\succeq0 \iff S\succeq 0$X⪰0⟺S⪰0
• $X\succeq0 \iff A\succeq0,(I-AA^\dagger)B=0,S=C-B^TA^{\dagger}B\succeq0$X⪰0⟺A⪰0,(I−AA†)B=0,S=C−BTA†B⪰0

关于第 3 条中的第二个要求 $(I-AA^\dagger)B=0$(I−AA†)B=0，对 $A$A 进行奇异值分解，有 $A=U\Sigma V$A=UΣV，那么我们对任意 $v$v，有 $(I-AA^\dagger)Bv=(I-UU^T)Bv=0$(I−AA†)Bv=(I−UUT)Bv=0，而 $UU^T$UUT 实际上就是向 $\mathcal{R}(A)$R(A) 的投影矩阵，因此就要求 $Bv\in\mathcal{R}(A)$Bv∈R(A)。

3. SCQ 几何解释

前面给出的是 SCQ 的代数描述，那么如何证明呢？另外如何从几何角度直观理解呢？

首先我们可以考虑最简单的优化问题
$\begin{aligned} \text { minimize } \quad& f_0(x)\\ \text { subject to } \quad& f_1(x) \end{aligned}$ minimize  subject to ​f0​(x)f1​(x)​

定义集合 $\mathcal{G}=\{(f_1(x),f_0(x))|x\in\mathcal{D}\}$G={(f1​(x),f0​(x))∣x∈D}，那么对偶函数为
$g(\lambda)=\inf_{(u,t)\in\mathcal{G}}(t+\lambda u)$g(λ)=(u,t)∈Ginf​(t+λu)

如果我们画出下面这张图，阴影部分就是可行区域 $\mathcal{G}$G，而 $(\lambda,1)^T$(λ,1)T 则正好定义了一个支撑超平面，$g(\lambda)$g(λ) 就等于 $t$t 轴的交点。通过取不同的 $\lambda$λ 我们就可以得到不同的支撑超平面，也可以得到不同的 $g(\lambda)$g(λ)，最终会有某一个 $\lambda^\star$λ⋆ 对应的是 $d^\star=g(\lambda^\star)$d⋆=g(λ⋆)。还需要注意这里的支撑超平面永远不可能是竖直的。

$(\lambda,1)^T$(λ,1)T 正好定义了一个支撑超平面	每个 $\lambda$λ 对应一个支撑超平面

那么 $p^\star$p⋆ 体现在哪个点呢？由于对于原优化问题，我们有 $f_1(x)\le0$f1​(x)≤0，因此体现在这个图里面就是 $u\le0$u≤0，也就是上面左图当中的红色区域，而 $p^\star=\min f_0(x)=\min t$p⋆=minf0​(x)=mint。

理解了这张图，我们现在开始证明两件事：

1. 证明弱对偶性，也即 $p^\star \ge d^\star$p⋆≥d⋆；
2. 证明强对偶性条件 SCQ。

注：在此之前，我们不妨加入等式约束，也即 $g(\lambda,\mu)=\inf_{(u,v,t)\in\mathcal{G}}(t+\lambda^T u+\mu^T v)$g(λ,μ)=inf(u,v,t)∈G​(t+λTu+μTv)。

弱对偶性的证明：我们有 $\lambda\ge0$λ≥0
$\begin{aligned} p^\star &= \inf\{t|(u,v,t)\in\mathcal{G},u\le0,v=0\} \\ &\ge \inf\{t+\lambda^Tu+\mu^Tv|(u,v,t)\in\mathcal{G},u\le0,v=0\} \\ &\ge \inf\{t+\lambda^Tu+\mu^Tv|(u,v,t)\in\mathcal{G}\} \\ &= g(\lambda,\mu) \end{aligned}$p⋆​=inf{t∣(u,v,t)∈G,u≤0,v=0}≥inf{t+λTu+μTv∣(u,v,t)∈G,u≤0,v=0}≥inf{t+λTu+μTv∣(u,v,t)∈G}=g(λ,μ)​

强对偶性条件 SCQ 的证明：由 $g(\lambda,\mu)=\inf_{(u,v,t)\in\mathcal{G}}(t+\lambda^T u+\mu^Tv)$g(λ,μ)=inf(u,v,t)∈G​(t+λTu+μTv) 可以得到
$(\lambda,\mu,1)^T(u,v,t)\ge g(\lambda,\mu),\quad \forall (u,v,t)\in\mathcal{G}$(λ,μ,1)T(u,v,t)≥g(λ,μ),∀(u,v,t)∈G

这实际上定义了 $\mathcal{G}$G 的一个超平面。特别的有 $(0,0,p^\star)\in\text{bd}\mathcal{G}$(0,0,p⋆)∈bdG，因此也有
$(\lambda,\mu,1)^T(0,0,p^\star)\ge g(\lambda,\mu)$(λ,μ,1)T(0,0,p⋆)≥g(λ,μ)

这个不等式可以自然地导出弱对偶性，当“=”成立时则可以导出强对偶性。那么什么时候取等号呢？点 $(0,0,p^\star)$(0,0,p⋆) 为支撑点的时候！也就是说

如果在边界点 $(0,0,p^\star)$(0,0,p⋆) 处存在一个非竖直的支撑超平面，那么我们就可以找到 $\lambda,\mu$λ,μ 使得上面的等号成立，也就是得到了强对偶性。

注意前面的分析中我们并没有提到 SCQ，那么 SCQ 是如何保证强对偶性的呢？注意 SCQ 要求存在 $x\in\mathcal{D}$x∈D 使得 $f(x)<0$f(x)<0，这也就意味着 $\mathcal{G}$G 在 $u< 0$u<0 半平面上有点，因此如果支撑超平面存在的话，就一定不是垂直的。

但这又引出另一个问题，那就是支撑超平面一定存在吗？答案是一定存在，这是由原问题的凸性质决定的。为了证明这一点，我们可以引入一个类似于 epigraph 的概念：
$\begin{aligned} \mathcal{A} &= \mathcal{G} + (R^m_+\times \{0\}\times R_+) \\ &= \left\{(u,v,t) |\ \exist x\in\mathcal{D},s.t. f(x)\le u,h(x)=v,f_0(x)\le t\right\} \end{aligned}$A​=G+(R+m​×{0}×R+​)={(u,v,t)∣ ∃x∈D,s.t.f(x)≤u,h(x)=v,f0​(x)≤t}​

由于原优化问题为凸的，可以应用定义证明集合 $\mathcal{A}$A 也是凸的，同时 $(0,0,p^\star)\in\text{bd}\mathcal{A}$(0,0,p⋆)∈bdA，那么集合 $\mathcal{A}$A 在 $(0,0,p^\star)$(0,0,p⋆) 点就一定存在一个支撑超平面。又由 SCQ 可知这个支撑超平面一定不是竖直的，因此就可以得到强对偶性了。

注：$(\lambda,\mu,1)^T(u,v,t)\ge g(\lambda,\mu),\quad \forall (u,v,t)\in\mathcal{A}$(λ,μ,1)T(u,v,t)≥g(λ,μ),∀(u,v,t)∈A 也成立。

最后给我的博客打个广告，欢迎光临
https://glooow1024.github.io/
https://glooow.gitee.io/