最优化理论与方法-第十讲-对偶理论的基本性质和割平面法

1. 向量化拉格朗日对偶函数

( D ) max ⁡ d ( λ , μ ) s t . λ i ≥ 0 , i = 1 , ⋯ , m , d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ i = 1 l μ i h i ( x ) } \begin{equation}\begin{aligned} &(D)\; \;\max\; d(\lambda,\mu)\\ &st.\;\;\lambda_i\ge0,i=1,\cdots,m,\\ &\;\;d(\lambda,\mu)=\min\limits_{x\in X}\{f(x)+\sum_{i=1}^m\lambda_ig_i(x)+\sum_{i=1}^l\mu_ih_i(x)\}\\ \end{aligned}\end{equation} ​(D)maxd(λ,μ)st.λi​≥0,i=1,⋯,m,d(λ,μ)=x∈Xmin​{f(x)+i=1∑m​λi​gi​(x)+i=1∑l​μi​hi​(x)}​​​

• 为了方便向量的表达方式，我们记：
  $$\begin{array}{c}\begin{array}{rl}& g(x)=(g_1(x),g_2(x),\cdots ,g_m(x){)}^T\\ & h(x)=(h_1(x),h_2(x),\cdots ,h_l(x){)}^T\\ & \lambda =({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_m)\\ & \mu =({\mu }_1,{\mu }_2,\cdots ,{\mu }_l)\end{array}\end{array}$$
• 整理上式可得：
  ( D ) max ⁡ d ( λ , μ ) s t . λ i ≥ 0 , i = 1 , ⋯ , m , d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } \begin{equation}\begin{aligned} &(D)\; \;\max\; d(\lambda,\mu)\\ &st.\;\;\lambda_i\ge0,i=1,\cdots,m,\\ &\;\;d(\lambda,\mu)=\min\limits_{x\in X}\{f(x)+\lambda^Tg(x)+\mu^Th(x)\}\\ \end{aligned}\end{equation} ​(D)maxd(λ,μ)st.λi​≥0,i=1,⋯,m,d(λ,μ)=x∈Xmin​{f(x)+λTg(x)+μTh(x)}​​​

2. 对偶问题是凹函数

• 对偶问题(D)是凸问题,对偶函数是凹函数

• 这里的凹函数图像如下：这个定义国内外相反，真有点坑，容易糊涂
  

• 需要证明对偶函数 $d(\lambda ,\mu )$是凹函数
  d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } \begin{equation} d(\lambda,\mu)=\min\limits_{x\in X}\{f(x)+\lambda^Tg(x)+\mu^Th(x)\} \end{equation} d(λ,μ)=x∈Xmin​{f(x)+λTg(x)+μTh(x)}​​

• 假设X为有限个值 X = { x 1 , x 2 , ⋯ , x n } X=\{x_1,x_2,\cdots,x_n\} X={x1​,x2​,⋯,xn​},那么对偶函数,就是从N个函数中求最小值
  d ( λ , μ ) = min ⁡ i = 1 , ⋯ , n { f ( x i ) + λ T g ( x i ) + μ T h ( x i ) } \begin{equation} d(\lambda,\mu)=\min\limits_{i=1,\cdots,n}\{f(x_i)+\lambda^Tg(x_i)+\mu^Th(x_i)\} \end{equation} d(λ,μ)=i=1,⋯,nmin​{f(xi​)+λTg(xi​)+μTh(xi​)}​​

• 对于每个函数，一旦$x_i$确定后，$d(\lambda ,\mu )$就只是一个关于$\lambda ,\mu$的线性函数，也就是分段最小值函数，详见下图：
  

• 由上图可得，对偶函数是凹函数,是凸问题。

3. 对偶问题转换

• 我们有如下对偶问题：
  ( D ) max ⁡ d ( λ , μ ) s t . λ i ≥ 0 , i = 1 , ⋯ , m , d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } \begin{equation}\begin{aligned} &(D)\; \;\max\; d(\lambda,\mu)\\ &st.\;\;\lambda_i\ge0,i=1,\cdots,m,\\ &\;\;d(\lambda,\mu)=\min\limits_{x\in X}\{f(x)+\lambda^Tg(x)+\mu^Th(x)\}\\ \end{aligned}\end{equation} ​(D)maxd(λ,μ)st.λi​≥0,i=1,⋯,m,d(λ,μ)=x∈Xmin​{f(x)+λTg(x)+μTh(x)}​​​
• 定义 $\theta =d(\lambda ,\mu )$
  ( D ) max ⁡ θ s t . λ i ≥ 0 , i = 1 , ⋯ , m , θ = d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } \begin{equation}\begin{aligned} &(D)\; \;\max\; \theta\\ &st.\;\;\lambda_i\ge0,i=1,\cdots,m,\\ &\;\;\theta=d(\lambda,\mu)=\min\limits_{x\in X}\{f(x)+\lambda^Tg(x)+\mu^Th(x)\}\\ \end{aligned}\end{equation} ​(D)maxθst.λi​≥0,i=1,⋯,m,θ=d(λ,μ)=x∈Xmin​{f(x)+λTg(x)+μTh(x)}​​​
• 因为最终求$\theta$的最大值，所以可以缩放$\theta =d(\lambda ,\mu )\to \theta \le d(\lambda ,\mu )$
  ( D ) max ⁡ θ s t . λ i ≥ 0 , i = 1 , ⋯ , m , θ ≤ d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } \begin{equation}\begin{aligned} &(D)\; \;\max\; \theta\\ &st.\;\;\lambda_i\ge0,i=1,\cdots,m,\\ &\;\;\theta\le d(\lambda,\mu)=\min\limits_{x\in X}\{f(x)+\lambda^Tg(x)+\mu^Th(x)\}\\ \end{aligned}\end{equation} ​(D)maxθst.λi​≥0,i=1,⋯,m,θ≤d(λ,μ)=x∈Xmin​{f(x)+λTg(x)+μTh(x)}​​​
• 整理后可得：
  ( D ) max ⁡ θ θ ≤ min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } s t . λ ≥ 0 \begin{equation}\begin{aligned} &(D)\; \;\max\; \theta\\ &\;\;\theta\le \min\limits_{x\in X}\{f(x)+\lambda^Tg(x)+\mu^Th(x)\}\\ &st.\;\;\lambda\ge 0\\ \end{aligned}\end{equation} ​(D)maxθθ≤x∈Xmin​{f(x)+λTg(x)+μTh(x)}st.λ≥0​​​
• 如果最终存在一个$\bar{\theta }$是上面的最大值，那么就是最优值
  $$\begin{array}{c}\bar{\theta }=v(D)\end{array}$$
• 假设X有有限个解 X = { x 1 , x 2 , ⋯ , x n } X=\{x_1,x_2,\cdots,x_n\} X={x1​,x2​,⋯,xn​}，那么存在n个不等式,可以用scipy的库进行线性规划问题的求解，假设X有无穷多解，那么代表的就是无穷多个线性不等式。
  θ ≤ min ⁡ i = 1 , ⋯ , n { f ( x i ) + λ T g ( x i ) + μ T h ( x i ) } s t . λ ≥ 0 \begin{equation}\begin{aligned} &\;\;\theta\le \min\limits_{i=1,\cdots,n}\{f(x_i)+\lambda^Tg(x_i)+\mu^Th(x_i)\}\\ &st.\;\;\lambda\ge 0\\ \end{aligned}\end{equation} ​θ≤i=1,⋯,nmin​{f(xi​)+λTg(xi​)+μTh(xi​)}st.λ≥0​​​
• 我们假设 X 0 = { x 1 , x 3 } X_0=\{x_1,x_3\} X0​={x1​,x3​}，现在只有两个约束，那么这个得到的最大值肯定大于N个约束的的最大值 $\bar{\theta }$,因为约束越多，其定义域的范围越小，那么值域就越小，最大值也就越小
  $$\begin{array}{c}\begin{array}{r}{\theta }_0\ge \bar{\theta }\end{array}\end{array}$$
• 我们记最优解为$({\lambda }_0,{\mu }_0,{\theta }_0)$,现在求 $d({\lambda }_0,{\mu }_0)$
  d ( λ 0 , μ 0 ) = min ⁡ x ∈ X { f ( x ) + λ 0 T g ( x ) + μ 0 T h ( x ) } \begin{equation} d(\lambda_0,\mu_0)=\min\limits_{x\in X}\{f(x)+\lambda_0^Tg(x)+\mu_0^Th(x)\} \end{equation} d(λ0​,μ0​)=x∈Xmin​{f(x)+λ0T​g(x)+μ0T​h(x)}​​
• 假设存在一个 $x_0$ 满足如下条件：
  $$\begin{array}{c}g(x_0)\le 0,h(x_0)=0,{\lambda }_0^{T}g(x_0)=0\end{array}$$
• 反正上面都为0，等式左右相加不影响：
  $$\begin{array}{c}f(x_0)=f(x_0)+{\lambda }_0^{T}g(x_0)+{\mu }_0^{T}h(x_0)\end{array}$$
• 我们定义$x_0$为$d({\lambda }_0,{\mu }_0)$最优解，那么可得：
  $$\begin{array}{c}d(x_0,{\lambda }_0,{\mu }_0)=f(x_0)+{\lambda }_0^{T}g(x_0)+{\mu }_0^{T}h(x_0)=f(x_0)\end{array}$$
• 则强对偶定理成立
• 若$d({\lambda }_0,{\mu }_0)={\theta }_0$，可得：
  $$\begin{array}{c}d({\lambda }_0,{\mu }_0)=v(D)\end{array}$$

4. 外逼近法

4.1 步骤

• step 0: 选取X的非空子集$X^1$,其中$X^1$包含有限个元素，令$k=1$
• step 1: 求解线性规划问题：
  ( D ) max ⁡ θ θ ≤ min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } , ∀ x ∈ X k s t . λ ≥ 0 记最优解为 ( λ k , μ k , θ k ) \begin{equation}\begin{aligned} &(D)\; \;\max\; \theta\\ &\;\;\theta\le \min\limits_{x\in X}\{f(x)+\lambda^Tg(x)+\mu^Th(x)\},\forall x\in X^k\\ &st.\;\;\lambda\ge 0\\ & 记最优解为(\lambda^k,\mu^k,\theta^k) \end{aligned}\end{equation} ​(D)maxθθ≤x∈Xmin​{f(x)+λTg(x)+μTh(x)},∀x∈Xkst.λ≥0记最优解为(λk,μk,θk)​​​
• step 2: 求解相应的子问题：
  min ⁡ { f ( x ) + ( λ k ) T g ( x ) + ( μ k ) T h ( x ) ∣ x ∈ X } ； \begin{equation} \min\{f(x)+(\lambda^k)^Tg(x)+(\mu^k)^Th(x)\big|x\in X\}； \end{equation} min{f(x)+(λk)Tg(x)+(μk)Th(x) ​x∈X}；​​
• 记其最优解为$x^k$,最优值为$d({\lambda }^k,{\mu }^k)$
• step 3: 若$x^k$是原问题$(P)$的可行解，且$({\lambda }^k{)}^{T}g(x^k)=0$，则算法终止，$x^k$和$({\lambda }^k,{\mu }^k)$分别是原问题P和对偶问题D的最优解，且最优值相等，若
  $$\begin{array}{c}{\theta }^k=d({\lambda }^k,{\mu }^k)\end{array}$$
  则算法终止，$({\lambda }^k,{\mu }^k)$即对偶问题的最优解，且最优值为 ${\theta }^k$
• step 4: 令 X k + 1 = X k ∪ { x k } , k : = k + 1 X^{k+1}=X^k\cup\{x^k\},k:= k+1 Xk+1=Xk∪{xk},k:=k+1,转 step 1

4.2 注意事项

• 1. X的子集合点总需要包含一个原问题的可行解，这样能保证$\theta$有一个上界,使得迭代更好收敛。
     $$\begin{array}{c}\theta \le f(x)+{\lambda }^{T}g(x)+{\mu }^{T}h(x)\le f(x)\end{array}$$
• 2. X包含无穷多个解，为了方便迭代，我们可以动态去掉$X^k$中多余的解，加速迭代
• 3. 割平面法，通过不断加约束来不断地缩小定义域，近似的逼近最优解。就像切西瓜一样，不断地切，最后切成我们想要的形状。
     
• 在最优解附近具有不稳定性，我们通常通过加正则项的方法进行正则化
• 后续研究次梯度法和bound method