凸优化学习-（十九）深入分析对偶问题

凸优化学习

学习笔记

一、原问题最优值${\text{p}}^{\ast }$与与对偶问题最优值${\text{d}}^{\ast }$分析

1、背景知识

对于一个普通优化问题：
$$\begin{array}{rlrl}\min & & f_0(x)& \\ (\text{P})\text{s.t.}& & f_i(x)& \le 0i=1\cdots m\\ & & h_i(x)& =0i=1\cdots p\end{array}$$
拉格朗日函数($\text{lagrangian function}$)：
$$l(x,\lambda ,v)=f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{v}_i{h}_i(x)$$
由拉格朗日函数构造的对偶函数($\text{dual function}$)：
$$g(\lambda ,v)=\underset{x\in D}{\inf }l(x,\lambda ,v)$$
其对偶问题为：
$$\begin{array}{rlrl}\max & & g(\lambda ,v)& \\ (\text{D})\text{s.t.}& & \lambda \ge 0& \end{array}$$

结论：

1. 对偶问题是凸优化问题。
2. ${\text{d}}^{\ast }\le {\text{p}}^{\ast }$

定义：

1. ${\text{p}}^{\ast }$：原问题最优值。${\text{d}}^{\ast }$：对偶问题最优值。
2. 弱对偶$\text{Weak Duality}$：${\text{d}}^{\ast }\le {\text{p}}^{\ast }$时。任何优化问题都是弱对偶。
   强对偶$\text{Strong Duality}$：${\text{d}}^{\ast }={\text{p}}^{\ast }$时。凸问题一般是强对偶。
3. ${\text{p}}^{\ast }-{\text{d}}^{\ast }$：对偶间隙$\text{Duality gap}$。
4. 相对内部$\text{Relative Interior}$。
   形如：
   Relint D = { x ∈ D ∣ B ( x , r ) ∩ aff D ∈ D ∃ r ∈ D \text{Relint}D=\lbrace x\in D\mid B(x,r)\cap\text{aff}D\in D\quad\exist r\in D RelintD={x∈D∣B(x,r)∩affD∈D∃r∈D
   其中，$B(x,r)$是以$x$为中心，$r$为半径的球。$\text{aff}D$指$D$的仿射包。
   
   相当于将集合的边缘去掉，使之成为一个开集。

2、${\text{d}}^{\ast }={\text{p}}^{\ast }$的条件

$\text{Slater’s Condition}$（充分而不必要）：
若有凸问题：
$$\begin{array}{rlrl}\min & & f_0(x)& \\ \text{s.t.}& & f_i(x)& \le 0i=1\cdots m\\ & & h_i(x)& =0i=1\cdots p\end{array}$$
当$\exists x\in \text{relint}D$使$f_i(x)<0,i=1\cdots m,h_i(x)=0,i=1\cdots p$满足时，${\text{d}}^{\ast }={\text{p}}^{\ast }$。

一般我们见到的凸问题都是满足的，有一些人为构造的凸问题不满足。
当然这个可能还是有些难以满足，所以又有如下一个较弱的条件：
$\text{A Weaker Slater’s Condition}$
若不等式约束为仿射时，只要可行域非空，必有${\text{d}}^{\ast }={\text{p}}^{\ast }$。

线性规划若可行，必有${\text{d}}^{\ast }={\text{p}}^{\ast }$。
例1： QCQP问题
$$\begin{array}{rlrl}\min & & \frac{1}{2}{x}^T{\text{P}}_{\text{0}}x+q_0^{T}x+r_0& \\ (\text{P})\text{s.t.}& & \frac{1}{2}{x}^T{p}_{i}x+q_{i}x+r_i& \le 0i=1\cdots m\\ & & {\text{P}}_{\text{0}}\in {\text{S}}_{\text{++}}^n,p_i\in {\text{S}}_{\text{+}}^n& \end{array}$$
拉格朗日函数($\text{lagrangian function}$)：
$$\begin{array}{rl}l(x,\lambda )& =\frac{1}{2}{x}^T{\text{P}}_{\text{0}}x+q_0^{T}x+r_0+\sum _{i=1}^m{\lambda }_i(\frac{1}{2}{x}^T{p}_{i}x+q_{i}x+r_i)\\ & =\frac{1}{2}x(p_0+\sum _{i=1}^m{\lambda }_i{p}_i)x+(q_0+\sum _{i=1}^m{\lambda }_i{q}_i{)}^{T}x+r_0+\sum _{i=1}^m{\lambda }_i{r}_i\end{array}$$
对偶函数($\text{dual function}$)：
$$\begin{array}{rl}g(\lambda )& =\underset{x\in D}{\inf }l(x,\lambda )\\ & =-\frac{1}{2}{q}^T(\lambda )p^{-1}(\lambda )q(\lambda )+r(\lambda )\end{array}$$
其对偶问题为：
$$\begin{array}{rlr}\max & & -\frac{1}{2}{q}^T(\lambda )p^{-1}(\lambda )q(\lambda )+r(\lambda )\\ (\text{D})\text{s.t.}& & \lambda \ge 0\end{array}$$
显然${\text{d}}^{\ast }={\text{p}}^{\ast }$，此时我们验证一下$\text{Slater’s Condition}$：
对于约束$\frac{1}{2}{x}^T{p}_{i}x+q_{i}x+r_i\le 0i=1\cdots m$当$q_i=0,r_i=0$时，怎么样都不满足此约束。
故QCQP问题是一个不满足$\text{Slater’s Condition}$但${\text{d}}^{\ast }={\text{p}}^{\ast }$的问题。

个人思考

凸问题的另一良好性质展现了，${\text{d}}^{\ast }={\text{p}}^{\ast }$，这对于不是很好直接求解的凸问题提出了一种新的求解方法。

纸质笔记