最优化理论与方法-第十讲-弱对偶定理，强对偶定理

1. 弱对偶定理

• 概述：具体详见此节： 最优化理论与方法-第十讲-约束优化
  设 $v(P)$是原问题$(P)$的最优值，$v(D)$是对偶问题$(D)$的最优值，则
  $$\begin{array}{c}v(D)\le v(P)\end{array}$$
• 我们知道对于$f(x)$来说，其最小值为$v(P)$,可得：$v(P)\le f(x)$,因为对于对偶问题$d(\lambda ,\mu )$来说，其最大值为$v(D)$,所以可得：$d(\lambda ,\mu )\le v(D)$
• 整理可得恒等式：
  $$\begin{array}{c}d(\lambda ,\mu )\le v(D)\le v(P)\le f(x)\end{array}$$

1.1 推论1

• 假设在原问题的定义域内存在一个 $\bar{x}\in S$,在对偶问题中的定义域内存在一对参数$(\bar{\lambda },\bar{\mu }),\bar{\lambda }\ge 0$,满足如下：
  $$\begin{array}{c}d(\bar{\lambda },\bar{\mu })=f(\bar{x})\end{array}$$
• 那么可得，且这个点同时为原问题和对偶问题的最优解。
  $$\begin{array}{c}v(D)=v(P)\end{array}$$
• 解释：因为满足弱对偶定理和前后相等可得：
  $$\begin{array}{c}d(\bar{\lambda },\bar{\mu })\le v(D)\le v(P)\le f(\bar{x}),d(\bar{\lambda },\bar{\mu })=f(\bar{x})\to v(D)=v(P)\end{array}$$

1.2 推论2

• 如果 $v(P)=-\infty$，则可得 $d(\lambda ,\mu )=-\infty ,\forall (\lambda ,\mu ),\lambda \ge 0$
• 如果 $v(D)=+\infty$，则可得 $v(P)=+\infty$,原问题P无可行解

2. duality gap

2.1 定义

我们定义duality-gap 表示原问题的最优值减去对偶问题的最优值如下：
d u a l i t y    g a p = v ( P ) − v ( D )

$$\begin{equation} duality\;gap=v(P)-v(D) \end{equation}$$ dualitygap=v(P)−v(D)​​

2.2 约束问题

假设我们有如下约束优化问题：

• 原问题：
  ( P )      min ⁡    { x 1 2 + x 2 2 } s t .      − x 1 − x 2 ≤ − 1 2 , x ∈ Z + 2

  $$\begin{equation} \begin{aligned} &(P)\; \;\min\; \{x_1^2+x_2^2\}\\ &st.\;\;-x_1-x_2\le -\frac{1}{2},x\in Z_+^2\\ \end{aligned} \end{equation}$$ ​(P)min{x12​+x22​}st.−x1​−x2​≤−21​,x∈Z+2​​​​

• 根据图形可得，当$x_1=0,x_2=1$时可以去的最小值，则$v(P)=1$

• 拉格朗日函数如下：
  d ( x , λ ) = x 1 2 + x 2 2 + λ ( 1 2 − x 1 − x 2 )

  $$\begin{equation} d(x,\lambda)=x_1^2+x_2^2+\lambda(\frac{1}{2}-x_1-x_2) \end{equation}$$ d(x,λ)=x12​+x22​+λ(21​−x1​−x2​)​​

• 对偶问题如下：
  max ⁡ λ min ⁡ ( x 1 , x 2 ) { d ( x , λ ) } = max ⁡ λ min ⁡ ( x 1 , x 2 ) { x 1 2 + x 2 2 + λ ( 1 2 − x 1 − x 2 ) }

  $$\begin{equation} \max\limits_{\lambda}\min \limits_{(x_1,x_2)}\{d(x,\lambda)\}=\max\limits_{\lambda}\min \limits_{(x_1,x_2)}\{x_1^2+x_2^2+\lambda(\frac{1}{2}-x_1-x_2)\} \end{equation}$$ λmax​(x1​,x2​)min​{d(x,λ)}=λmax​(x1​,x2​)min​{x12​+x22​+λ(21​−x1​−x2​)}​​

• 化简如下：
  max ⁡ λ min ⁡ ( x 1 , x 2 ) { d ( x , λ ) } = max ⁡ λ min ⁡ ( x 1 , x 2 ) { ( x 1 − λ 2 ) 2 + ( x 2 − λ 2 ) 2 + λ 2 − λ 2 2 }

  $$\begin{equation} \max\limits_{\lambda}\min \limits_{(x_1,x_2)}\{d(x,\lambda)\}=\max\limits_{\lambda}\min \limits_{(x_1,x_2)}\{(x_1-\frac{\lambda}{2})^2+(x_2-\frac{\lambda}{2})^2+\frac{\lambda}{2}-\frac{\lambda^2}{2}\} \end{equation}$$ λmax​(x1​,x2​)min​{d(x,λ)}=λmax​(x1​,x2​)min​{(x1​−2λ​)2+(x2​−2λ​)2+2λ​−2λ2​}​​

• 也就是说，当$\lambda$确定时，内部的最小值指的是坐标点$P(x_1,x_2)$与$Q(\frac{\lambda }{2},\frac{\lambda }{2})$的最短距离，那我们就分类讨论$\frac{\lambda }{2}$在坐标轴哪？

• 当$\frac{1}{2}<\frac{\lambda }{2}<\frac{3}{2}$时，最短的点为$P=(1,1)$
  min ⁡ ( x 1 , x 2 ) { d ( x , λ ) } = min ⁡ ( x 1 , x 2 ) { x 1 2 + x 2 2 + λ ( 1 2 − x 1 − x 2 ) } = 2 − 3 2 λ

  $$\begin{equation} \min \limits_{(x_1,x_2)}\{d(x,\lambda)\}=\min \limits_{(x_1,x_2)}\{x_1^2+x_2^2+\lambda(\frac{1}{2}-x_1-x_2)\}=2-\frac{3}{2}\lambda \end{equation}$$ (x1​,x2​)min​{d(x,λ)}=(x1​,x2​)min​{x12​+x22​+λ(21​−x1​−x2​)}=2−23​λ​​

• 当$\frac{3}{2}<\frac{\lambda }{2}<\frac{5}{2}$时，最短的点为$P=(2,2)$
  min ⁡ ( x 1 , x 2 ) { d ( x , λ ) } = min ⁡ ( x 1 , x 2 ) { x 1 2 + x 2 2 + λ ( 1 2 − x 1 − x 2 ) } = 8 − 7 2 λ

  $$\begin{equation} \min \limits_{(x_1,x_2)}\{d(x,\lambda)\}=\min \limits_{(x_1,x_2)}\{x_1^2+x_2^2+\lambda(\frac{1}{2}-x_1-x_2)\}=8-\frac{7}{2}\lambda \end{equation}$$ (x1​,x2​)min​{d(x,λ)}=(x1​,x2​)min​{x12​+x22​+λ(21​−x1​−x2​)}=8−27​λ​​

• 当$k-\frac{1}{2}<\frac{\lambda }{2}<k+\frac{1}{2}$时，最短的点为$P=(k,k)$
  min ⁡ ( x 1 = k , x 2 = k ) { d ( x , λ ) } = min ⁡ ( x 1 = k , x 2 = k ) { 2 k 2 + λ ( 1 2 − 2 k ) } , k = 1 , 2 , ⋯   , n

  $$\begin{equation} \min \limits_{(x_1=k,x_2=k)}\{d(x,\lambda)\}=\min \limits_{(x_1=k,x_2=k)}\{2k^2+\lambda(\frac{1}{2}-2k)\},k=1,2,\cdots,n \end{equation}$$ (x1​=k,x2​=k)min​{d(x,λ)}=(x1​=k,x2​=k)min​{2k2+λ(21​−2k)},k=1,2,⋯,n​​

• 将$k=1,2,\cdots ,n$代入可得，根据$k-\frac{1}{2}<\frac{\lambda }{2}<k+\frac{1}{2}$
  max ⁡ λ min ⁡ ( x 1 , x 2 ) { d ( x , λ ) } = 1 2

  $$\begin{equation} \max\limits_{\lambda}\min \limits_{(x_1,x_2)}\{d(x,\lambda)\}=\frac{1}{2} \end{equation}$$ λmax​(x1​,x2​)min​{d(x,λ)}=21​​​
  

• 综上所示，$v(D)=\frac{1}{2},v(P)=1$,可得：
  d u a l i t y    g a p = v ( P ) − v ( D ) = 1 − 1 2 = 1 2

  $$\begin{equation} duality\;gap=v(P)-v(D)=1-\frac{1}{2}=\frac{1}{2} \end{equation}$$ dualitygap=v(P)−v(D)=1−21​=21​​​

3. 强对偶定理

3.1 概述

• 假设：
  1） 集合X为非空凸集，$f(x)$及$g_i(x),i=1,2,\cdots ,m$是凸函数，$h_i(x),i=1,2,\cdots ,l$均为线性函数。
  2） 假设存在 $\hat{x}\in X$使得$g_i(\hat{x})<0,i=1,\cdots ,m,h_i(\hat{x})=0,i=1,\cdots ,l$,且
  $0\in \mathrm{int}h(X)$,其中$h(X)=\{[h_1(x),h_2(x),\cdots ,h_l(x){]}^T|x\in X\}$,则强对偶成立，即：
  min ⁡ { f ( x ) ∣ x ∈ S } = max ⁡ { d ( λ , μ ) ∣ λ ≥ 0 , μ } $$\begin{equation} \min \{f(x)|x\in S\}=\max \{d(\lambda,\mu)\big|\lambda \ge 0,\mu\} \end{equation}$$ min{f(x)∣x∈S}=max{d(λ,μ) ​λ≥0,μ}​​
• 假设1保证了G是一个凸函数集
• 假设2保证了图集G在-y处有阴影
• 基于如下讨论最优化理论与方法-第十讲-约束优化，可得原问题P的最小值和对偶问题的最大值一致
  

3.2 证明：

• 由于$\hat{x}$的存在，则原问题$(P)$有可行解

• 若$v(P)=-\infty$，根据弱对偶定理推论可得：$d(\lambda ,\mu )=-\infty ,\forall (\lambda ,\mu ),\lambda \ge 0$

• 若$v(P)=v$，根据弱对偶定理推论可得：不存在 $x\in X$，使得$f(x)<v,g_i(x)\le 0,i=1,\cdots ,m,h_i(x)=0,i=1,\cdots ,l$

• 定义H函数如下：
  H = { ( p q r ) ∈ R 1 + m + l ∣ f ( x ) − v < p , g i ( x ) ≤ q i , i = 1 , ⋯   , m ; h i ( x ) = r i , i = 1 ⋯   , l , x ∈ X }

  $$\begin{equation} H=\{\begin{pmatrix}p\\\\q\\\\r\end{pmatrix}\in \mathbb{R}^{1+m+l}\big|f(x)-v<p,g_i(x)\le q_i,i=1,\cdots,m;h_i(x)=r_i,i=1\cdots,l,x\in X\} \end{equation}$$ H={ ​pqr​ ​∈R1+m+l ​f(x)−v<p,gi​(x)≤qi​,i=1,⋯,m;hi​(x)=ri​,i=1⋯,l,x∈X}​​

• 可知：H是凸函数，且 ( 0 0 0 ) ∉ H

  $$\begin{pmatrix}0\\\\0\\\\0\end{pmatrix}$$ \notin H ​000​ ​∈/H,根据凸集分离定理，则存在$\left(\begin{array}{c}{\lambda }_0\\ \\ \lambda \\ \\ \mu \end{array}\right)\ne 0$,使得：
  $$\begin{array}{c}{\left(\begin{array}{c}{\lambda }_0\\ \\ \lambda \\ \\ \mu \end{array}\right)}^T\left(\begin{array}{c}p\\ \\ q\\ \\ r\end{array}\right)\ge 0,\forall \left(\begin{array}{c}p\\ \\ q\\ \\ r\end{array}\right)\in \mathrm{d}(H)\end{array}$$
  

• 整理可得：${\lambda }_0,q$为实数，不是向量，不需要转置
  λ 0 p + λ T q + μ T r ≥ 0 → λ 0 ≥ 0 , λ i ≥ 0 , i = 1 , ⋯   , m

  $$\begin{equation} \lambda_0p+\lambda^Tq+\mu^Tr\ge0\to \lambda_0\ge0,\lambda_i\ge0,i=1,\cdots,m \end{equation}$$ λ0​p+λTq+μTr≥0→λ0​≥0,λi​≥0,i=1,⋯,m​​

• 由图可得对于任意的$x\in X$来说，都在超平面上方，所以可得：
  ∀ x ∈ X , λ 0 ≥ 0 , λ 0 [ f ( x ) − v ] + ∑ i = 1 m λ i g i ( x ) + ∑ i = 1 l μ i h i ( x ) ≥ 0

  $$\begin{equation} \forall x\in X,\lambda_0\ge 0,\lambda_0[f(x)-v]+\sum_{i=1}^m \lambda_ig_i(x)+\sum_{i=1}^l \mu_ih_i(x)\ge0 \end{equation}$$ ∀x∈X,λ0​≥0,λ0​[f(x)−v]+i=1∑m​λi​gi​(x)+i=1∑l​μi​hi​(x)≥0​​

3.3 证明${\lambda }_0\ne 0$

• 我们可以设${\lambda }_0=0,x=\hat{x}$ 代入可得：
  $$\begin{array}{c}\sum _{i=1}^m{\lambda }_i{g}_i(\hat{x})+\sum _{i=1}^l{\mu }_i{h}_i(\hat{x})\ge 0;g_i(\hat{x})\le 0,h_i(\hat{x})=0\end{array}$$
• 只要有一个${\lambda }_i>0$,那么必然有${\sum }_{i=1}^m{\lambda }_i{g}_i(\hat{x})<0$,矛盾，所以只能都等于0
  $$\begin{array}{c}{\lambda }_i=0\end{array}$$
• 代入到通项可得：
  $$\begin{array}{c}\forall x\in X,\sum _{i=1}^l{\mu }_i{h}_i(x)\ge 0\end{array}$$
• 由于已知$0\in \mathrm{int}h(X)$,其中$h(X)=\{[h_1(x),h_2(x),\cdots ,h_l(x){]}^T|x\in X\}$，则存在一个 $\tilde{x},ϵ\to 0$,使得：
  $$\begin{array}{c}\left(\begin{array}{c}{h}_1(\tilde{x})\\ \\ ⋮\\ \\ h_l(\tilde{x})\end{array}\right)=ϵ\left(\begin{array}{c}-{\mu }_1\\ \\ ⋮\\ \\ -{\mu }_l\end{array}\right)\end{array}$$
• 代入可得：
  $$\begin{array}{c}\forall x\in X,ϵ>0,-ϵ\sum _{i=1}^l{\mu }_i^2\ge 0\to {\mu }_i=0\end{array}$$
• 综上所述可得：
  $$\begin{array}{c}{\lambda }_0=0,{\lambda }_i=0,{\mu }_i=0与题目\left(\begin{array}{c}0\\ \\ 0\\ \\ 0\end{array}\right)\notin H,矛盾，所以{\lambda }_0=0是错误的结论\end{array}$$
• 可得：
  $$\begin{array}{c}{\lambda }_0>0\end{array}$$
• 我们可以整理公式20可得：
  $$\begin{array}{c}[f(x)-v]+\sum _{i=1}^m\frac{{\lambda }_i}{{\lambda }_0}{g}_i(x)+\sum _{i=1}^l\frac{{\mu }_i}{{\lambda }_0}{h}_i(x)\ge 0;\forall x\in X\end{array}$$
• 为了方便后续，我们定义$\frac{{\lambda }_i}{{\lambda }_0}=\overline{{\lambda }_i}\ge 0,\frac{{\mu }_i}{{\lambda }_0}=\overline{{\mu }_i}$
  $$\begin{array}{c}[f(x)-v]+\sum _{i=1}^m\overline{{\lambda }_i}{g}_i(x)+\sum _{i=1}^l\overline{{\mu }_i}{h}_i(x)\ge 0;\forall x\in X\end{array}$$
• 移项可得：
  $$\begin{array}{c}f(x)+\sum _{i=1}^m\overline{{\lambda }_i}{g}_i(x)+\sum _{i=1}^l\overline{{\mu }_i}{h}_i(x)\ge v;\forall x\in X\end{array}$$
• 左边其实就是对偶问题，其中参数为$\bar{\lambda },\bar{\mu }$
  $$\begin{array}{c}d(\bar{\lambda },\bar{\mu })\ge v=v(P);\forall x\in X\end{array}$$
• 因为根据弱对偶定理可得：
  $$\begin{array}{c}d(\lambda ,\mu )\le v=v(P);\forall x\in X\end{array}$$
• 综上所述可得：
  $$\begin{array}{c}d(\bar{\lambda },\bar{\mu })=v(P);强对偶成立\end{array}$$