对偶问题笔记（2）

4. 凸优化问题之强对偶性的 Slater 条件

一个优化问题是否满足强对偶性是不容易检验的, 所以需要对凸优化问题给出一个方便的检验条件, 即所谓 Slater 条件.

考虑凸优化问题$$\begin{array}{r}?\begin{array}{l}\min f_0(x)\\ \text{s.t}{f}_i(x)\le 0,i=1,?,p,\\ Ax=b,\\ x\in \Omega ,\end{array}\end{array}\text{\hspace{1em}?}$$其中 { f i } i = 0 p \{f_i\}_{i=0}^p {fi?}i=0p? 是凸函数，$A\in {\mathbb{R}}^{q\times n},b\in {\mathbb{R}}^q,\Omega ?{\mathbb{R}}^n$ 是一个凸集. 我们假设约束函数$f_1,...,f_p$ 如下条件满足：$$\begin{array}{r}?\infty <f_i(x)<\infty ,i=0,1,?,p,?x\in \Omega .\end{array}\text{\hspace{1em}?}$$

定义 4.1 (Slater 条件) 对于凸优化问题(5.4.1), 若存在 $x_0\in \mathcal{D}\cap \mathbf{ri}(\Omega )$, 满足$$f_i(x_0)<0,i=1,?,p,$$
定义 4.2 (弱 Slater 条件) 对于本节中的优化问题(1), 若 { f i } i = 1 p \{f_i\}_{i=1}^p {fi?}i=1p? 中非仿射函数 $f_i$ 都存在严格可行点，即存在 $x_i\in \mathcal{D}$ 使得 $f_i(x_i)<0$,且 $\mathcal{D}\cap \mathbf{ri}(\Omega )\ne ?$, 则称其满足弱 $Slater$ 条件.

注：当所有约束函数均为仿射函数且 $\Omega ={\mathbb{R}}^n$ 时，弱 Slater 条件即为 $D\ne ?.$

对于仅含集约束的优化问题$$\{\begin{array}{l}\min f_0(x)\\ \text{s.t}x\in \Omega ,\end{array}$$有 $\mathcal{D}=\Omega$.定义其 Largrane 函数为 $L(x):=f_0(x)$. 相应的对偶函数为$$g(\lambda ,\mu ):=\underset{x\in \Omega }{\inf }L(x)=\underset{x\in \mathcal{D}}{\inf }{f}_0(x)={\xi }^{?}.$$因而对偶问题的最优值为 ${\eta }^{?}={\xi }^{?}$, 强对偶性满足，而且对偶问题是可解的.

定理 4.1 $(\mathrm{Slater})$ 设本小节的凸优化问题$$?\begin{array}{l}\min f_0(x)\\ \text{s.t}{f}_i(x)\le 0,i=1,?,p,\\ Ax=b,\\ x\in \Omega ,\end{array}$$满足$$?\infty <f_i(x)<\infty ,i=0,1,?,p,?x\in \Omega .$$, 且可以满足 定义 4.2 所述的弱 $(\mathrm{Slater})$ 条件，那么强对偶性成立，且对偶问题是可解的.

Emmm，由于这个命题需要证明的引理太多了，我就偷个懒好啦~

虽然没有把证明写出来, 但有点还是需要说明的，即存在不满足强对偶性的凸优化问题，比如下例.

例 4.2 如下优化问题是凸的, 但不满足强对偶性.$$?\begin{array}{l}\min e^{?x}\\ \text{s.t?}{x}^2/y\le 0,\\ (x,y)\in \Omega ,\end{array}$$其中 $\Omega :=\{(x,y)|x\in \mathbb{R},y>0\}$

证. 根据凸函数的定义，可以判断 $x^2/y$ 是凸的，于是该优化问题是凸问题 ，可行集为$$\mathcal{D}=\{(x,y)\in \Omega |x^2\le 0\}=\{(0,y)|y>0\}.$$因而其最优值为 ${\xi }^{?}={\inf }_{(x,y)\in \mathcal{D}}{e}^{?x}=1.$

根据定义可以写出其 Lagrange 函数 $L(x,y,\lambda ):=e^{?x}+\lambda x^2/y$, 所以对偶函数为$$g(\lambda )=\underset{(x,y)\in \Omega }{\inf }L(x,y,\lambda )=\underset{x\in \mathbb{R},y>0}{\inf }(e^{?x}+\lambda x^2/y)=?\begin{array}{ll}0& ?\lambda \ge 0,\\ ?\infty & \lambda <0.\end{array}$$

于是 ${\eta }^{?}={\sup }_{\lambda \ge 0}g(\lambda )=0\ne {\xi }^{?}$. 所以强对偶性不成立.

5. 约束转换对对偶性的影响

优化问题$$\begin{array}{r}?\begin{array}{l}\min f_0(x)\\ s.t{f}_i(x)\le 0,i=1,?,p,\\ h_j(x)=0,j=1,?,q,\\ x\in \Omega ,\end{array}\end{array}\text{\hspace{1em}?}$$的不等式约束和等式约束统称为代数约束, 而称约束 $x\in ?$ 为集
约束. 实际上这两种约束常常可以等价地相互表示, 所得到的优化问题是同解的. 类似地,当优化问题的目标函数 $f_0$ 取值为无穷大时, 可以将之转换为集约束. 这些转换虽然不影响原问题的同解性, 但它们的对偶问题却发生了变化.

将上述的优化问题进行适当变形后可以得到一个新的优化问题，设原问题及其对偶问题的最优值分别为 ${\xi }^{?}$ 和 ${\eta }^{?};$ 设新问题及其对偶问题的最优值分别为 ${\tilde{\xi }}^{?}$ 和 ${\tilde{\eta }}^{?}$. 下面看看 ${\xi }^{?}$ 与 ${\tilde{\xi }}^{?}$ 以及 ${\eta }^{?}$ 与 ${\tilde{\eta }}^{?}$ 有哪些数值关系.

5.1 函数有限值约束转换为集约束

对于优化问题(3)，当 $f_0,f_1,...,f_p$ 的取值范围为 R ∪ { ∞ } \mathbb{R}\cup\{\infty\} R∪{∞} 时，考虑如下优化问题$$\begin{array}{r}?\begin{array}{l}\min f_0(x)\\ \text{s.t?}{f}_i(x)\le 0,i=1,?,p,\\ h_j(x)=0,j=1,?,q,\\ x\in \tilde{\Omega },\end{array}\end{array}\text{\hspace{1em}?}$$

其中 Ω ^ : = { x ∈ Ω ∣ f i ( x ) < ∞ , i = 0 , 1 , . . . , p } . \begin{align}\hat{\Omega}:=\{x\in\Omega|f_i(x)<\infty,i=0,1,...,p\}.\end{align} Ω^:={x∈Ω∣fi?(x)<∞,i=0,1,...,p}.??

根据 $\hat{\Omega }$ 的定义可以知道 $\tilde{\Omega }?\Omega$ 且其可行集为 $\tilde{\mathcal{D}}=\mathcal{D}\cap \mathrm{dom}(f_0).$ 由于$f_0(x)=\infty ,?x\in \mathcal{D}?\mathrm{dom}(f_0)$，所以有
$$\widetilde{{\xi }^{?}}:=\underset{x\in \tilde{\mathcal{D}}}{\inf }{f}_0(x)=\underset{x\in \mathcal{D}}{\inf }{f}_0(x)={\xi }^{?}.$$这说明(4)与原问题(3)同解. 又根据下确界 $\text{inf}$ 的性质有
$$\tilde{g}(\lambda ,\mu ):=\underset{x\in \tilde{\Omega }}{\inf }L(x,\lambda ,\mu )\ge \underset{x\in \Omega }{\inf }L(x,\lambda ,\mu )=g(\lambda ,\mu ).$$所以 ${\tilde{\eta }}^{?}\ge {\eta }^{?}.$

特别地，如果将(5)替换成下式 Ω ~ : = { x ∈ Ω ∣ f 0 ( x ) < ∞ } . \begin{align} \tilde{\Omega}:=\{x\in\Omega|f_0(x)<\infty\}.\end{align} Ω~:={x∈Ω∣f0?(x)<∞}.??那么 $L(x,\lambda ,\mu )=\infty ,?x\in \Omega ?\tilde{\Omega }$, 从而$$g(\lambda ,\mu )=\underset{x\in \Omega }{\inf }L(x,\lambda ,\mu )=\underset{x\in \tilde{\Omega }}{\inf }L(x,\lambda ,\mu )=\tilde{g}(\lambda ,\mu ),$$因而 ${\tilde{\eta }}^{?}={\eta }^{?}$.综上所述，可以得到如下的命题.

命题 5.1.1 设优化问题(3)满足$$\{\begin{array}{ll}?\infty <f_i(x)\le \infty & i=0,1,?,p,\\ ?\infty <h_j(x)<\infty & j=1,?,q,\end{array}?x\in \Omega .$$, 记问题(3)和(4)的对偶函数分别为$g(\lambda ,\mu )$ 和 $\tilde{g}(\lambda ,\mu )$,那么
$${\tilde{\xi }}^{?}:=\underset{x\in \tilde{D}}{\inf }{f}_0(x)=\underset{x\in \mathcal{D}}{\inf }{f}_0(x)={\xi }^{?},\tilde{g}(\lambda ,\mu )\ge g(\lambda ,\mu ),?\lambda \in {\mathbb{R}}_{+}^p,\mu \in {\mathbb{R}}^q.$$因而，${\tilde{\eta }}^{?}\ge {\eta }^{?}$. 特别，若将(5)所定义的 $\tilde{\Omega }$ 替换成(6), 那么 ${\tilde{\eta }}^{?}={\eta }^{?}$.

如果我们回顾第4小节中的Slater 定理可以发现，优化问题(1)中的目标函数 $f_0$ 和约束函数 $f_1,...,f_p$ 都是有限取值，利用上述的命题 5.1.1可以将Slater 定理推广如下：

推论 5.1.2 (Slater 定理的推广) 对凸优化问题(1), 若如下条件满足：

(1) 对任意的 $x\in \Omega$ 有$:?\infty <f_0(x)\le \infty$, 且 $?\infty <f_i(x)<\infty ,i=1,...,p;$

(2) { f i } i = 1 p \left\{f_i\right\}_{i=1}^p {fi?}i=1p? 中非仿射函数 $f_i$ 都存在 $x_i\in \mathcal{D}\cap \mathbf{dom}(f_0)$ 使得 $f_i(x_i)<0$;

(3) $\mathcal{D}\cap \mathbf{ri}(\Omega \cap \mathbf{dom}(f_0))\ne ?$,

则强对偶性成立，且对偶问题的最优值是可解的.

证.考虑如下凸优化问题:$$\begin{array}{r}?\begin{array}{ll}\min f_0(x)& \\ s.t{f}_i(x)\le 0,i=1,?,p,& \\ Ax=b,& \\ x\in \tilde{\Omega },& \end{array}\end{array}\text{\hspace{1em}?}$$其中 $\tilde{\Omega }:=\Omega \cap \mathbf{dom}(f_0)$.记 ${\tilde{\xi }}^{?}$ 和${\tilde{\eta }}^{?}$ 是问题(7)及其对偶问题的最优值. 易见，问题(7)的可行集为 $\tilde{D}=\mathcal{D}\cap \mathbf{dom}(f_0)$. 由此可见问题 (7)满足 Slater 定理 4.1 的全部条件，因而${\tilde{\xi }}^{?}={\tilde{\eta }}^{?}$,并且 (7)的对偶问题的最优值 ${\tilde{\eta }}^{?}$ 是可解的.

根据 命题 5.1.1可以知道，问题(7)和问题(1)是同解的，并且相应的对偶问题也是同解的，于是(1)也是强对偶并且对偶问题是可解的.

5.2 代数约束转换为集约束

对于优化问题(3)，即优化问题$$?\begin{array}{l}\min f_0(x)\\ s.t{f}_i(x)\le 0,i=1,?,p,\\ h_j(x)=0,j=1,?,q,\\ x\in \Omega ,\end{array}$$，设其可行集为 $\mathcal{D}$.如果将该优化问题的一个不等式约束转换为集合约束，便能够得到如下的问题：$$\begin{array}{r}?\begin{array}{l}\min f_0(x)\\ s.t{f}_i(x)\le 0,i=1,?,p?1,\\ h_j(x)=0,j=1,?,q,\\ x\in \tilde{\Omega },\end{array}\end{array}\text{\hspace{1em}?}$$其中 { Ω ~ : = { x ∈ Ω ∣ f p ( x ) ≤ 0 } , D ~ : = { x ∈ Ω ~ ∣ f i ( x ) ≤ 0 , i = 1 , ? ? , p ? 1 ; h j ( x ) = 0 , j = 1 , ? ? , q } = D . \begin{cases}\tilde{\Omega}:=\{x\in\Omega|f_p(x)\leq0\},\\\tilde{\mathcal{D}}:=\{x\in\tilde{\Omega}|f_i(x)\leq0,i=1,\cdots,p-1;h_j(x)=0,j=1,\cdots,q\}=\mathcal{D}.\end{cases} {Ω~:={x∈Ω∣fp?(x)≤0},D~:={x∈Ω~∣fi?(x)≤0,i=1,?,p?1;hj?(x)=0,j=1,?,q}=D.?，由于 $\tilde{\mathcal{D}}=\mathcal{D}$，于是问题(8)与问题(3)是同解的.下面我们来看看这两个问题的对偶问题是否改变了.

根据这两个集合的定义可以知道 $\tilde{\mathcal{D}}?\tilde{\Omega }$，其 Lagrange 函数为
$$\tilde{L}(x,\tilde{\lambda },\mu ):=f_0(x)+\sum _{i=1}^{p?1}{\tilde{\lambda }}_i{f}_i(x)+\sum _{j=1}^q{\mu }_j{h}_j(x).$$根据这些记号，下面给出如下的命题.

命题 5.2.1 设优化问题(3)和优化问题(8)的对偶函数分别为 $g(\lambda ,\mu )$ 和 $\tilde{g}(\tilde{\lambda },\mu )$, 那么 $?\lambda :=$ $({\tilde{\lambda }}^T,{\lambda }_p{)}^T\in {\mathbb{R}}_{+}^p,\mu \in {\mathbb{R}}^q$,有 $g(\lambda ,\mu )\le \tilde{g}(\tilde{\lambda },\mu )$.从而$$\underset{\lambda ?0}{\sup }g(\lambda ,\mu )\le \underset{\tilde{\lambda }?0}{\sup }\tilde{g}(\tilde{\lambda },\mu )\le \underset{x\in \tilde{\mathcal{D}}}{\inf }{f}_0(x)=\underset{x\in \mathcal{D}}{\inf }{f}_0(x).$$因而，当问题(3)满足强对偶性时，问题(8) 亦然，且二者的对偶问题具有相同的最优值.

证.根据拉格朗日函数的定义，问题 (3)的 Lagrange 函数为$$L(x,\lambda ,\mu )=\tilde{L}(x,\tilde{\lambda },\mu )+{\lambda }_p{f}_p(x).$$因而有：$?\lambda :=({\tilde{\lambda }}^T,{\lambda }_p{)}^T\in {\mathbb{R}}_{+}^p,\mu \in {\mathbb{R}}^q.\text{?由于?}\tilde{\Omega }?\Omega ,\text{?有}$$$g(\lambda ,\mu )=\underset{x\in \Omega }{\inf }L(x,\lambda ,\mu )\le \underset{x\in \tilde{\Omega }}{\inf }L(x,\lambda ,\mu )\le \underset{x\in \tilde{\Omega }}{\inf }\tilde{L}(x,\tilde{\lambda },\mu )=\tilde{g}(\tilde{\lambda },\mu ).$$

根据问题(8)的弱对偶性，以及上述不等式，有$$\underset{\lambda ?0}{\sup }g(\lambda ,\mu )\le \underset{\tilde{\lambda }?0}{\sup }\tilde{g}(\tilde{\lambda },\mu )\le \underset{x\in \tilde{\mathcal{D}}}{\inf }{f}_0(x)=\underset{x\in \mathcal{D}}{\inf }{f}_0(x).$$所以这就证明了优化问题(3)的强对偶性可以推出优化问题(8)的强对偶性，且两个优化问题有相同的最优值.

此外，如果将优化问题(3)的一个等式约束转换为集约束，也就是考虑如下的优化问题：$$\begin{array}{r}?\begin{array}{l}\min f_0(x)\\ s.t{f}_i(x)\le 0,i=1,?,p,\\ h_j(x)=0,j=1,?,q?1,\\ x\in \tilde{\Omega },\end{array}\end{array}\text{\hspace{1em}?}$$其中 { Ω ~ : = { x ∈ Ω ∣ f p ( x ) ≤ 0 } , D ~ : = { x ∈ Ω ~ ∣ f i ( x ) ≤ 0 , i = 1 , ? ? , p ; h j ( x ) = 0 , j = 1 , ? ? , q ? 1 } = D . \begin{cases}\tilde{\Omega}:=\{x\in\Omega|f_p(x)\leq0\},\\\tilde{\mathcal{D}}:=\{x\in\tilde{\Omega}|f_i(x)\leq0,i=1,\cdots,p;h_j(x)=0,j=1,\cdots,q-1\}=\mathcal{D}.\end{cases} {Ω~:={x∈Ω∣fp?(x)≤0},D~:={x∈Ω~∣fi?(x)≤0,i=1,?,p;hj?(x)=0,j=1,?,q?1}=D.?，由于 $\tilde{\mathcal{D}}=\mathcal{D}$，可以用类似于上述命题的方法证明如下的命题，证明就不贴上来了，因为方法是类似的.

命题 5.2.2 设优化问题(3)和优化问题(9)的对偶函数分别为 $g(\lambda ,\mu )$ 和 $\tilde{g}(\tilde{\lambda },\mu )$, 那么 $?\mu :=$ $({\tilde{\mu }}^T,{\mu }_p{)}^T\in {\mathbb{R}}_{+}^p,\lambda \in {\mathbb{R}}^q$,有 $g(\lambda ,\mu )\le \tilde{g}(\lambda ,\tilde{\mu })$.从而$$\underset{\lambda ?0}{\sup }g(\lambda ,\mu )\le \underset{\lambda ?0}{\sup }\tilde{g}(\lambda ,\tilde{\mu })\le \underset{x\in \tilde{\mathcal{D}}}{\inf }{f}_0(x)=\underset{x\in \mathcal{D}}{\inf }{f}_0(x).$$因而，当问题(3)满足强对偶性时，问题(9) 亦然，且二者的对偶问题具有相同的最优值.

6. 对偶的对偶

这节的标题是对偶的对偶，不经会引人发问：对偶的对偶会不会类似于负负得正一样而变回原问题呢？好吧，先卖个关子，具体如何先看下文.

考虑如下问题：$$\begin{array}{r}\{\begin{array}{ll}\min ?g(\lambda ,\mu )& \\ s.t?\lambda ?0& \end{array}\end{array}\text{\hspace{1em}?}$$的对偶，并称之为原问题$$?\begin{array}{l}\min f_0(x)\\ s.t{f}_i(x)\le 0,i=1,?,p,\\ h_j(x)=0,j=1,?,q,\\ x\in \Omega ,\end{array}$$的二次对偶问题.此外，补充定义 $g(\lambda ,\mu )$ 在 $\lambda ?0$ 处的值为 $?\infty$，于是(10)的拉格朗日函数和对偶函数分别为$$L_{\mathrm{dual}}(\lambda ,\mu ,\alpha ):=?[g(\lambda ,\mu )+{\alpha }^T\lambda ]\text{和}{g}_{\mathrm{dual}}(\alpha ):=\underset{\lambda ,\mu }{\inf }{L}_{\mathrm{dual}}(\lambda ,\mu ,\alpha ).$$因此，(10)的对偶问题就是$$\begin{array}{r}\{\begin{array}{ll}\max g_{\mathrm{dual}}(\alpha )& \\ s.t\alpha ?0.& \end{array}\end{array}\text{\hspace{1em}?}$$好了，现在来回答一下我们在开头的疑问，一般情况下，对偶的对偶未必就是原问题.实际上我们可以发现，二次对偶函数 $g_{dual}(\alpha )$ 的变量 $\alpha$ 与 $\lambda$ 是同维数的，是原问题(3)的不等式约束的个数，所以与原问题的变量 $x$ 的维度并不一定相同，也就是说二次对偶问题不一定能够回到原问题.

设 ${\xi }_{\mathrm{dual}}^{?}$ 和 ${\eta }_{\mathrm{dual}}^{?}$ 分别是问题(10) 及其对偶问题(11)的最优值，${\xi }^{?}$ 和 ${\eta }^{?}$ 分别是原问题(3)及其对偶问题的最优值. 显然有 ${\eta }_{\mathrm{dual}}^{?}\le {\xi }_{\mathrm{dual}}^{?}=?{\eta }^{?}$. 那么又会有一个自然的问题：二次对偶的最优值 ${\eta }_{\mathrm{dual}}^{?}$ 与原问题的最优值 ${\xi }^{?}$ 有什么关系？先看下面的命题.

命题 6.1 (对偶之对偶) 设优化问题(3)即$$?\begin{array}{l}\min f_0(x)\\ s.t{f}_i(x)\le 0,i=1,?,p,\\ h_j(x)=0,j=1,?,q,\\ x\in \Omega ,\end{array}$$满足条件$$\{\begin{array}{ll}?\infty <f_i(x)\le \infty & i=0,1,?,p,\\ ?\infty <h_j(x)<\infty & j=1,?,q,\end{array}?x\in \Omega .$$ 那么$$\begin{array}{r}{\eta }^{?}=?{\xi }_{\mathrm{dual}}^{?}\le ?{\eta }_{\mathrm{dual}}^{?}\le {\xi }^{?},\end{array}\text{\hspace{1em}?}$$因此，当原问题也就是优化问题(3)满足强对偶性的时候，对偶问题(11)即$$\{\begin{array}{ll}\max g_{\mathrm{dual}}(\alpha )& \\ s.t\alpha ?0.& \end{array}$$也满足强对偶性.

证.由于$g(\lambda ,\mu )={\inf }_{x\in \Omega }L(x,\lambda ,\mu )$，其中 $L(x,\lambda ,\mu )$ 是优化问题(3)的拉格朗日函数，根据拉格朗日函数以及对偶函数的定义，有$$\begin{array}{rl}{g}_{\mathrm{dual}}(\alpha )& =?\underset{\lambda ,\mu }{\sup }[g(\lambda ,\mu )+{\alpha }^T\lambda ]=?\underset{\lambda ?0,\mu }{\sup }[g(\lambda ,\mu )+{\alpha }^T\lambda ]\\ & =?\underset{\lambda ?0,\mu }{\sup }\underset{x\in \Omega }{\inf }[L(x,\lambda ,\mu )+{\alpha }^T\lambda ]\\ & =?\underset{\lambda ?0,\mu }{\sup }\underset{x\in \Omega }{\inf }(f_0(x)+{\lambda }^T[f(x)+\alpha ]+{\mu }^{T}h(x)),\end{array}$$其中$$f(x):=(f_1(x),?,f_p(x){)}^T,h(x):=(h_1(x),?,h_q(x){)}^T$$是优化问题(3)的约束函数所构成的向量.于是根据 $\text{sup}$ 和 $\text{inf}$ 的性质，有$$\begin{array}{rl}?\underset{\alpha ?0}{\sup }{g}_{\mathrm{dual}}(\alpha )& \begin{array}{rl}& =\underset{\alpha ?0}{\inf }\underset{\lambda ,?0\mu }{\sup }\underset{x\in \Omega }{\inf }\left(f_0(x)+{\lambda }^T[f(x)+\alpha ]+{\mu }^{T}h(x)\right)\end{array}\\ & \begin{array}{rl}& \le \underset{x\in \Omega }{\inf }\underset{\alpha ?0}{\inf }\underset{\lambda ?0,\mu }{\sup }\left(f_0(x)+{\lambda }^T[f(x)+\alpha ]+{\mu }^{T}h(x)\right)\end{array}\\ & \begin{array}{rl}& \le \underset{x\in \mathcal{D}}{\inf }(f_0(x)+\underset{\alpha ?0}{\inf }\underset{\lambda ?0,\mu }{\sup }({\lambda }^T[f(x)+\alpha ]\left)\right).\end{array}\end{array}$$对任意的 $x\in \mathcal{D}$. 由于优化问题(3)满足条件$$\{\begin{array}{ll}?\infty <f_i(x)\le \infty & i=0,1,?,p,\\ ?\infty <h_j(x)<\infty & j=1,?,q,\end{array}?x\in \Omega .$$可以知道 $f(x)\in \mathbb{R}$. 令$\alpha :=?f(x)?0$，则有$$\begin{array}{r}\underset{\alpha ?0}{\inf }\underset{\lambda ?0,\mu }{\sup }\left({\lambda }^T[f(x)+\alpha ]\right)\le \underset{\lambda ?0,\mu }{\sup }\left({\lambda }^T[f(x)?f(x)]\right))=0.\end{array}$$所以$$\begin{array}{r}?{\eta }_{\mathrm{dual}}^{?}=?\underset{\alpha ?0}{\sup }{g}_{\mathrm{dual}}(\alpha )\le \underset{x\in \mathcal{D}}{\inf }{f}_0(x)={\xi }^{?}.\end{array}$$联立上文二次对偶问题得到的不等式 ${\eta }_{\mathrm{dual}}^{?}\le {\xi }_{\mathrm{dual}}^{?}=?{\eta }^{?}$，就可以得到$$\begin{array}{r}{\eta }^{?}=?{\xi }_{\mathrm{dual}}^{?}\le ?{\eta }_{\mathrm{dual}}^{?}\le {\xi }^{?}\end{array}$$

注: 原问题(3)不满足强对偶性时, 根据弱对偶性, 对偶问题的最优值 ${\eta }^{?}$ 提供了原问题之最优值 ${\xi }^{?}$ 的一个下界. 不等式(12)表明, 多做一次对偶便可以获得原问题(3)的一个更好的下界 $?{\eta }_{dual}^{?}$. 那么, 反复求解对偶问题的能逐步逼近原问题吗?

虽然一般对偶问题的对偶未必是原问题, 但对于线性规划而言, 却是肯定的. 所谓线性规划, 是指目标函数和约束函数都是仿射函数的优化问题, 线性规划可以写成如下标准形式$$\begin{array}{r}?\begin{array}{ll}\min c^{T}x,& \\ s.tAx=b,& \\ x?0.& \end{array}\end{array}\text{\hspace{1em}?}$$

命题 6.2 线性规划(13)的二次对偶是原问题.

证. 线性规划(13)的 Lagrange 函数为$$L(x,\lambda ,\mu ):=c^{T}x?{\lambda }^{T}x+{\mu }^T(Ax?b)=(c?\lambda +A^T\mu {)}^{T}x?b^T\mu .$$

所以其对偶函数为$$g(\lambda ,\mu ):=\underset{x\in {\mathbb{R}}^n}{\inf }L(x,\lambda ,\mu )=\{\begin{array}{ll}?b^T\mu & \lambda =A^T\mu +c,\\ ?\infty & \text{其他?}.\end{array}$$因而, 对偶问题及其 Lagrange 函数分别为$$\{\begin{array}{ll}\min ?g(\lambda ,\mu )& \\ s.t?\lambda ?0,& \end{array}$$
和$$L_{\mathrm{dual}}(\lambda ,\mu ,\alpha )=?g(\lambda ,\mu )?{\alpha }^T\lambda =?\begin{array}{ll}{b}^T\mu ?{\alpha }^T\lambda & \lambda =A^T\mu +c,\\ \infty & \text{其他?}.\end{array}$$于是, 对偶函数问题的对偶函数为$$g_{\mathrm{dual}}(\alpha ):=\underset{\lambda ,\mu }{\inf }{L}_{\mathrm{dual}}(\lambda ,\mu ,\alpha )=\underset{\mu }{\inf }[b^T\mu ?{\alpha }^T(A^T\mu +c)]=?\begin{array}{ll}?{\alpha }^{T}c& A\alpha =b,\\ ?\infty & \text{其他?}.\end{array}$$
所以, 二次对偶问题为$$\{\begin{array}{l}\max g_{\mathrm{dual}}(\alpha )\\ \text{s.t}\alpha ?0.\end{array}\text{即}?\begin{array}{l}\min c^T\alpha \\ \text{s.t}A\alpha =b,\\ \alpha ?0.\end{array}$$也就是说最后所得的问题就是原问题(3)，即线性规划的二次对偶问题是原问题.

7. 仿射约束优化问题的对偶函数的计算

考虑如下仿射约束优化问题之对偶函数的计算:$$\begin{array}{r}?\begin{array}{l}\min f(x),\\ \text{s.t}Ax?b,\\ Cx=d,\end{array}\end{array}\text{\hspace{1em}?}$$其中 $f:{\mathbb{R}}^n\to \mathbb{R}$.此时，取 $\Omega :={\mathbb{R}}^n$. 那么$$L(x,\lambda ,\mu )=f(x)+(A^T\lambda +C^T\mu {)}^{T}x?(b^T\lambda +d^T\mu ),\mathrm{dom}(L):={\mathbb{R}}^n\times {\mathbb{R}}^p\times {\mathbb{R}}^q.$$此时，对偶函数为$$\begin{array}{r}g(\lambda ,\mu )=\underset{x\in {\mathbb{R}}^n}{\inf }[f(x)+(A^T\lambda +C^T\mu {)}^{T}x]?(b^T\lambda +d^T\mu ).\end{array}\text{\hspace{1em}?}$$

例 7.1 设 $A\in {\mathbb{R}}^{q\times n},b\in {\mathbb{R}}^q$，优化问题
$$\min x^{T}x,s.tAx=b$$的对偶函数为$$g(\mu )=?\frac{1}{4}{\mu }^{T}A{A}^T\mu ?b^T\mu$$

证.令 $f_0(x):=x^{T}x$.根据(15),该优化问题的对偶函数为$$g(\mu )=\underset{x\in {\mathbb{R}}^n}{\inf }[x^{T}x+(A^T\mu {)}^{T}x]?b^T\mu .$$上式右端第一项的下确界在满足 $2x+A^T\mu =0$ 的 $x$ 处达到，即 $x=?A^T\mu /2$.将之代入上式即得 $g(\mu )=?\frac{1}{4}{\mu }^{T}A{A}^T\mu ?b^T\mu$.

例 7.2 设 $A\in {\mathbb{R}}^{q\times n},b\in {\mathbb{R}}^q,\parallel ?\parallel$ 是 ${\mathbb{R}}^n$ 中任意范数，则优化问题$$\min \Vert x\Vert ,s.tAx=b$$的对偶函数为$$g(\mu )=\{\begin{array}{llc}?b^T\mu & \Vert A^T\mu {\Vert }_{?}\le 1,& \\ ?\infty & \Vert A^T\mu {\Vert }_{?}>1.& \end{array}$$

证.令 $f_0(x):=\Vert x\Vert$.根据(15),该优化问题的对偶函数为$$\begin{array}{rl}g(\mu )& =\underset{x\in {\mathbb{R}}^n}{\inf }[\Vert x\Vert +(A^T\mu {)}^{T}x]?b^T\mu .\end{array}$$
(1) 当$\Vert A^T\mu {\Vert }_{?}\le 1$ 时，利用内积的性(只是作为类比来理解)，可以得到 $(A^T\mu {)}^{T}x\ge ?\Vert A^T\mu {\Vert }_{?}\Vert x\Vert$, 于是$$\begin{array}{r}\underset{x\in {\mathbb{R}}^n}{\inf }[\Vert x\Vert +(A^T\mu {)}^{T}x]\ge \underset{x\in {\mathbb{R}}^n}{\inf }(1?\Vert A^T\mu {\Vert }_{?})\Vert x\Vert \ge 0,\end{array}$$而取 $x=0$ 可知 ${\inf }_{x\in {\mathbb{R}}^n}[\Vert x\Vert +(A^T\mu {)}^{T}x]\le 0$. 所以 ${\inf }_{x\in {\mathbb{R}}^n}[\Vert x\Vert +(A^T\mu {)}^{T}x]=0.$

注: 当范数 $\Vert ?\Vert$ 为 Euclidean 范数时, 例 7.1和例 7.2中的优化问题是等价的. 然而, 它们的对偶函数完全不同.

例 7.3 线性规划$$?\begin{array}{l}\min c^{T}x\\ \text{s.t}Ax=b,\\ x?0.\end{array}$$的对偶函数为$$g(\lambda ,\mu )=\underset{x\in {\mathbb{R}}^n}{\inf }(c?\lambda +A^T\mu {)}^{T}x?b^T\mu =?\begin{array}{ll}?b^T\mu ,& c?\lambda +A^T\mu =0,\\ ?\infty ,& \text{其他}.\end{array}$$

Reference

包括但不限于以下内容：

(1)[BBV04] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
(2)[BOG94] JR Bar-On and KA Grasse. Global optimization of a quadratic functional with quadratic equality constraints. Journal of Optimization Theory and Applications, 82(2):379–386, 1994.
(3)[BOG97] JR Bar-On and KA Grasse.Global optimization of a quadratic functional with quadratic equality constraints, part 2. Journal of Optimization Theory and Applications,93(3):547–556, 1997.
(4)[Dau88] I. Daubechies. Time-frequency localization operators: a geometric phase space approach. IEEE Transactions on Information Theory, 34(4):605–612, 1988.
(5)[DMA97] G.Davis, S. Mallat, and M. Avellaneda. Greedy adaptive approximation. J Constructive Approximation, 13(1):57–98, 1997.
(6)张恭庆, 林源渠, 郭懋正. 泛函分析讲义 (下册). 北京大学出版社, 1990.
(7)袁亚湘, 孙文瑜. 最优化理论和方法. 北京: 科学出版社, 1997.