EE364A Lecture 7 and Lecture 8

课程主页：https://see.stanford.edu/Course/EE364A

这次回顾凸优化第七，第八讲，这部分介绍了凸优化问题以及对偶性。

Lecture 7 Convex optimization problems

广义不等式约束

考虑广义不等式约束下的凸问题：

$$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \preceq_{K_{i} } 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}$$

• $f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}$为凸函数；$f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}^{k_{i} }$关于正规锥$K_i$凸

锥形式问题：目标函数和约束为仿射函数的特殊情形

$$\begin{array}{cl}{\operatorname{minimize} } & {c^{T} x} \\ {\text { subject to } } & {F x+g \preceq_{K} 0} \\ {} & {A x=b}\end{array}$$

上述形式将线性规划（$K=\mathbf{R}_{+}^{m}$）推广为非多面体锥。

半定规划（SDP）

$$\begin{array}{cl}{ {\operatorname{minimize} } } & {c^{T} x} \\ {\text { subject to } } & {x_{1} F_{1}+x_{2} F_{2}+\cdots+x_{n} F_{n}+G \preceq 0} \\ {} & {A x=b}\end{array}$$

其中$F_{i}, G \in \mathbf{S}^{k}$

• 不等式约束被称为线性矩阵不等式（LMI）

• 上述形式包括多重LMI约束：例如

  $$x_{1} \hat{F}_{1}+\cdots+x_{n} \hat{F}_{n}+\hat{G} \preceq 0, \quad x_{1} \tilde{F}_{1}+\cdots+x_{n} \tilde{F}_{n} |+\tilde{G} \preceq 0$$

  等价于一个LMI

  $$x_{1}\left[\begin{array}{cc}{\hat{F}_{1} } & {0} \\ {0} & {\tilde{F}_{1} }\end{array}\right]+x_{2}\left[\begin{array}{cc}{\hat{F}_{2} } & {0} \\ {0} & {\tilde{F}_{2} }\end{array}\right]+\cdots+x_{n}\left[\begin{array}{cc}{\hat{F}_{n} } & {0} \\ {0} & {\tilde{F}_{n} }\end{array}\right]+\left[\begin{array}{cc}{\hat{G} } & {0} \\ {0} & {\tilde{G} }\end{array}\right] \preceq 0$$

将LP和SOCP视为SDP

LP以及等价的SDP。

LP：

$$\begin{array}{ll}{\text { minimize } } & {c^{T} x} \\ {\text { subject to } } & {A x \preceq b}\end{array}$$

SDP：

$$\begin{array}{ll}{ {\operatorname{minimize} } } & {c^{T} x} \\ {\text { subject to } } & {\operatorname{diag}(A x-b) \preceq 0}\end{array}$$

SOCP以及等价的SDP。

SOCP：

$$\begin{array}{ll}{\operatorname{minimize} } & {f^{T} x} \\ {\text { subject to } } & {\left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, \quad i=1, \ldots, m}\end{array}$$

SDP：

$$\begin{array}{ll}{ {\operatorname{minimize} } } & {f^{T} x} \\ {\text { subject to } } & {\left[\begin{array}{cc}{\left(c_{i}^{T} x+d_{i}\right) I} & {A_{i} x+b_{i} } \\ {\left(A_{i} x+b_{i}\right)^{T} } & {(c_{i}^{T} x+d_{i})I}\end{array}\right] \succeq 0, \quad i=1, \ldots, m}\end{array}$$

特征值最小化

$$\text { minimize } \quad \lambda_{\max }(A(x))$$

其中

$$A(x)=A_{0}+x_{1} A_{1}+\cdots+x_{n} A_{n},A_{i} \in \mathbf{S}^{k}$$

等价于SDP

$$\begin{array}{ll}{\text { minimize } } & {t} \\ {\text { subject to } } & {A(x) \preceq t I}\end{array}$$

• 变量$x \in \mathbf{R}^{n}, t \in \mathbf{R}$

• 上述等价是因为

  $$\lambda_{\max }(A) \leq t \quad \Longleftrightarrow \quad A \preceq t I$$

矩阵范数最小化

$$\text { minimize }\|A(x)\|_{2}=\left(\lambda_{\max }\left(A(x)^{T} A(x)\right)\right)^{1 / 2}$$

其中

$$A(x)=A_{0}+x_{1} A_{1}+\cdots+x_{n} A_{n},A_{i} \in \mathbf{R}^{p \times q}$$

等价于SDP

$$\begin{array}{ll}{\text { minimize } } & {t} \\ {\text { subject to } } & {\left[\begin{array}{ll}{t I} & {A(x)} \\ {A(x)^{T} } & {t I}\end{array}\right] \succeq 0}\end{array}$$

• 变量$x \in \mathbf{R}^{n}, t \in \mathbf{R}$

• 约束是因为

  $$\begin{aligned}\|A\|_{2} \leq t & \Longleftrightarrow A^{T} A \preceq t^{2} I, \quad t \geq 0 \\ & \Longleftrightarrow\left[\begin{array}{cc}{t I} & {A} \\ {A^{T} } & {t I}\end{array}\right] \succeq 0 \end{aligned}$$

向量优化

广义向量优化问题

$$\begin{array}{cl}{\operatorname{minimize}(\text { w.r.t. } K)} & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {h_{i}(x) \leq 0, \quad i=1, \ldots, p}\end{array}$$

向量目标函数$f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}^{q}$，关于正规锥$K \in \mathbf{R}^{q}$最小化

凸向量优化问题

$$\begin{array}{cl}{ {\operatorname{minimize} }(\text { w.r.t. } K)} & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}$$

其中$f_0$为$K$凸，$f_{1}, \ldots, f_{m}$为凸

最优以及Pareto最优点

考虑目标函数的可行集

$$\mathcal{O}=\left\{f_{0}(x) | x \text { feasible }\right\}$$

• 可行点$x$是最优的，如果$f_0(x)$是$\mathcal O$的最小值
• 可行点$x$是Pareto最优的，如果$f_0(x)$是$\mathcal O$的极小值

多准则优化

考虑$K=\mathbf{R}_{+}^{q}$的向量优化问题

$$f_{0}(x)=\left(F_{1}(x), \ldots, F_{q}(x)\right)$$

• $q$个可微目标函数$F_i$；粗略来说我们希望所有$F_i$都很小

• 可行点$x^{\star}$为最优，如果

  $$y \text { feasible } \quad \Longrightarrow \quad f_{0}\left(x^{\star}\right) \preceq f_{0}(y)$$

  如果存在最优点，那么目标函数是非竞争。

• 可行点$x^{\mathrm{po} }$为Pareto最优，如果

  $$y \text { feasible, } \quad f_{0}(y) \preceq f_{0}\left(x^{\mathrm{po} }\right) \quad \Longrightarrow \quad f_{0}\left(x^{\mathrm{po} }\right)=f_{0}(y)$$

  如果存在多个Pareto最优值，那么目标函数之间存在权衡。

正则化最小二乘

$$\text { minimize }\left(\text { w.r.t. } \mathbf{R}_{+}^{2}\right) \quad\left(\|A x-b\|_{2}^{2},\|x\|_{2}^{2}\right)$$

标量化

为了找到Pareto最优点：选择$\lambda \succ_{K^{\star} } 0$，然后求解标量问题

$$\begin{array}{cl}{\operatorname{minimize} } & {\lambda^{T} f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {h_{i}(x)=0, \quad i=1, \ldots, p}\end{array}$$

将多准则问题标量化

为了找到Pareto最优点，最小化正项加权和

$$\lambda^{T} f_{0}(x)=\lambda_{1} F_{1}(x)+\cdots+\lambda_{q} F_{q}(x)$$

例子

• 正则化最小二乘问题

  选择$\lambda=(1, \gamma),\gamma >0$，

  $$\text { minimize } \quad\|A x-b\|_{2}^{2}+\gamma\|x\|_{2}^{2}$$

  对于固定的$\gamma$，上述问题是LS问题。

$$\begin{array}{ll}{\text { minimize } } & {-\overline{p}^{T} x+\gamma x^{T} \Sigma x} \\ {\text { subject to } } & {1^{T} x=1, \quad x \succeq 0}\end{array}$$

​ 对于固定的$\gamma >0$，这是要一个二次规划问题。

Lecture 8 Duality

拉格朗日函数

标准形式的问题（不一定凸）

$$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {h_{i}(x)=0, \quad i=1, \ldots, p}\end{array}$$

变量$x \in \mathbf{R}^{n}$，定义域$\mathcal D$，最优值$p^{\star}$

拉格朗日函数：$L : \mathbf{R}^{n} \times \mathbf{R}^{m} \times \mathbf{R}^{p} \rightarrow \mathbf{R}$，其中$\operatorname{dom} L=\mathcal{D} \times \mathbf{R}^{m} \times \mathbf{R}^{p}$，

$$L(x, \lambda, \nu)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x)$$

• 目标函数和约束函数的加权和
• $\lambda_i $为$f_i(x)\le 0$对应的拉格朗日乘子
• $\nu_i $为$h_i(x)= 0$对应的拉格朗日乘子

拉格朗日对偶

拉格朗日对偶函数：$g : \mathbf{R}^{m} \times \mathbf{R}^{p} \rightarrow \mathbf{R}$，

$$\begin{aligned} g(\lambda, \nu) &=\inf _{x \in \mathcal{D} } L(x, \lambda, \nu) \\ &=\inf _{x \in \mathcal{D} }\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x)\right) \end{aligned}$$

$g$是凹函数，对某些$\lambda, \nu$可能为$-\infty$

下界性质：如果$\lambda \succeq 0$，那么$g(\lambda, \nu) \leq p^\star$

证明：如果$\tilde x$可行并且$\lambda \succeq 0$，那么

$$f_{0}(\tilde{x}) \geq L(\tilde{x}, \lambda, \nu) \geq \inf _{x \in \mathcal{D} } L(x, \lambda, \nu)=g(\lambda, \nu)$$

关于所有可行的$\tilde x $最小化给出$p^{\star} \geq g(\lambda, \nu)$。

线性方程的最小范数解

$$\begin{array}{ll}{\text { minimize } } & {x^{T} x} \\ {\text { subject to } } & {A x=b}\end{array}$$

对偶函数

• 拉格朗日函数为$L(x, \nu)=x^{T} x+\nu^{T}(A x-b)$

• 关于$L$最小化$x$，令梯度为$0$可得

  $$\nabla_{x} L(x, \nu)=2 x+A^{T} \nu=0 \quad \Longrightarrow \quad x=-(1 / 2) A^{T} \nu$$

• 带入可得

  $$g(\nu)=L\left((-1 / 2) A^{T} \nu, \nu\right)=-\frac{1}{4} \nu^{T} A A^{T} \nu-b^{T} \nu$$

  这是关于$\nu$的凹函数

下界性质：对所有$\nu$，$p^{\star} \geq-(1 / 4) \nu^{T} A A^{T} \nu-b^{T} \nu$

标准形式的LP

$$\begin{array}{ll}{\text { minimize } } & {c^{T} x} \\ {\text { subject to } } & {A x=b, \quad x \succeq 0}\end{array}$$

对偶函数

• 拉格朗日函数

  $$\begin{aligned} L(x, \lambda, \nu) &=c^{T} x+\nu^{T}(A x-b)-\lambda^{T} x \\ &=-b^{T} \nu+\left(c+A^{T} \nu-\lambda\right)^{T} x \end{aligned}$$

• $L$关于$x$仿射，因此

  $$g(\lambda, \nu)=\inf _{x} L(x, \lambda, \nu)=\left\{\begin{array}{ll}{-b^{T} \nu} & {A^{T} \nu-\lambda+c=0} \\ {-\infty} & {\text { otherwise } }\end{array}\right.$$

  $g$在仿射定义域$\left\{(\lambda, \nu) | A^{T} \nu-\lambda+c=0\right\}$是线性的，因此是凹的

下界性质：对所有$\nu$，$p^{\star} \geq-b^{T} \nu$，如果$A^{T} \nu+c \succeq 0$

等式约束下的范数最小化问题

$$\begin{array}{ll}{\text { minimize } } & {\|x\|} \\ {\text { subject to } } & {A x=b}\end{array}$$

对偶函数

$$g(\nu)=\inf _{x}\left(\|x\|-\nu^{T} A x+b^{T} \nu\right)=\left\{\begin{array}{ll}{b^{T} \nu} & {\left\|A^{T} \nu\right\|_{\star} \leq 1} \\ {-\infty} & {\text { otherwise } }\end{array}\right.$$

其中

$$\|v\|_{\star}=\sup _{\|u\| \leq 1} u^{T} v$$

是$| .|$的对偶范数。

证明：利用如下事实

$$\begin{aligned} \inf _{x}\left(\|x\|-y^{T} x\right)=\begin{cases} 0 & \| y\|_\star \le 1\\ -\infty & \| y\|_\star >1 \end{cases} \end{aligned}$$

• 如果$|y|_{\star} \le 1$，那么对所有$x$，$|x|-y^{T} x \geq 0$，当$x=0$时等号成立

• 如果$|y|_{\star} > 1$，选择$x= tu$，其中$|u| \leq 1, u^{T} y=|y|_{\star}>1$：

  $$\|x\|-y^{T} x=t\left(\|u\|-\|y\|_{\star}\right) \rightarrow-\infty \quad \text { as } t \rightarrow \infty$$

下界性质：如果$\left|A^{T} \nu\right|_{\star} \leq 1$，那么$p^{\star} \geq b^{T} \nu$

双向划分

$$\begin{array}{ll}{\text { minimize } } & {x^{T} W x} \\ {\text { subject to } } & {x_{i}^{2}=1, \quad i=1, \ldots, n}\end{array}$$

• 非凸问题；可行集包括$2^n$个离散点

对偶函数

$$\begin{aligned} g(\nu)&=\inf _{x}\left(x^{T} W x+\sum_{i} \nu_{i}\left(x_{i}^{2}-1\right)\right) \\ &=\inf _{x} x^{T}(W+\operatorname{diag}(\nu)) x-\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}$$

下界性质：如果$W+\operatorname{diag}(\nu) \succeq 0$，那么$p^{\star} \geq-1^{T} \nu$

Lagrange对偶和共轭函数

$$\begin{array}{ll}{\text { minimize } } & {f_{0}(x)} \\ {\text { subject to } } & {A x \preceq b, \quad C x=d}\end{array}$$

对偶函数

$$\begin{aligned} g(\lambda, \nu) &=\inf _{x \in \operatorname{dom} f_{0} }\left(f_{0}(x)+\left(A^{T} \lambda+C^{T} \nu\right)^{T} x-b^{T} \lambda-d^{T} \nu\right) \\ &=-f_{0}^{\star}\left(-A^{T} \lambda-C^{T} \nu\right)-b^{T} \lambda-d^{T} \nu \end{aligned}$$

• 回顾共轭的定义

  $$f^{\star}(y)=\sup _{x \in \operatorname{dom} f}\left(y^{T} x-f(x)\right)$$

• 如果$f_0$的共轭已知，那么会简化对偶的推导

对偶问题

Lagrange对偶问题

$$\begin{array}{ll}{\text { maximize } } & {g(\lambda, \nu)} \\ {\text { subject to } } & {\lambda \succeq 0}\end{array}$$

• 找到$p^{\star}$的下界，通过拉格朗日对偶函数得到
• 对偶问题是凸优化问题；最优值用$d^{\star}$表示
• $\lambda ,\nu$为对偶可行，如果$\lambda \succeq 0,(\lambda, \nu) \in \operatorname{dom} g$
• 通过显式约束$(\lambda, \nu) \in \operatorname{dom} g$通常简化问题

例子：标准LP及其对偶形式

标准LP

$$\begin{array}{cl}{ {\operatorname{minimize} } } & {c^{T} x} \\ {\text { subject to } } & {A x=b} \\ {} & {x \succeq 0}\end{array}$$

对偶形式

$$\begin{array}{ll}{\text { maximize } } & {-b^{T} \nu} \\ {\text { subject to } } & {A^{T} \nu+c \succeq 0}\end{array}$$

弱和强对偶

弱对偶：

$$d^\star \le p^\star$$

• 弱对偶总是成立（对凸问题以及非凸问题）

强对偶：

$$d^\star=p^\star$$

• 一般情形下不成立
• （通常）对凸问题成立
• 保证凸问题的强对偶性成立的条件被称为强对偶准则

Slater约束准则

对于凸问题，强对偶成立

$$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}$$

如果该问题是严格可行的，即

$$\exists x \in \operatorname{int} \mathcal{D} : \quad f_{i}(x)<0, \quad i=1, \ldots, m, \quad A x=b$$

• 这同样保证了对偶问题达到最优性（如果$p^\star >-\infty$）

具有强对偶性的非凸问题

$$\begin{array}{ll}{\text { minimize } } & {x^{T} A x+2 b^{T} x} \\ {\text { subject to } } & {x^{T} x \leq 1}\end{array}$$

$A \not\succeq 0$，因此非凸

对偶函数：

$$g(\lambda)=\inf _{x}\left(x^{T}(A+\lambda I) x+2 b^{T} x-\lambda\right)$$

• 如果$A+\lambda I \not\succeq 0$或$A+\lambda I \succeq 0$以及$b \notin \mathcal{R}(A+\lambda I)$，那么无下界
• 可以通过$x=-(A+\lambda I)^{\dagger} b$最小化：$g(\lambda)=-b^{T}(A+\lambda I)^{\dagger} b-\lambda$

对偶问题以及等价的SDP：

$$\begin{array}{cl}{ {\operatorname{maximize} } } & {-b^{T}(A+\lambda I)^{\dagger} b-\lambda} \\ {\text { subject to } } & {A+\lambda I \succeq 0} \\ {} & {b \in \mathcal{R}(A+\lambda I)}\end{array}$$

SDP

$$\begin{array}{ll}{\text { maximize } } & {-t-\lambda} \\ {\text { subject to } } & {\left[\begin{array}{cc}{A+\lambda I} & {b} \\ {b^{T} } & {t}\end{array}\right] \succeq 0}\end{array}$$

几何解释

简化起见，考虑单约束问题$f_{1}(x) \leq 0$。

对偶函数的解释：

$$g(\lambda)=\inf _{(u, t) \in \mathcal{G} }(t+\lambda u), \quad \text { where } \mathcal{G}=\left\{\left(f_{1}(x), f_{0}(x)\right) | x \in \mathcal{D}\right\}$$

• $\lambda u+t=g(\lambda)$是$\mathcal G$的支撑超平面
• 超平面在$t$轴的截距为$t= g(\lambda)$

上镜图变化：考虑

$$\mathcal{A}=\left\{(u, t) | f_{1}(x) \leq u, f_{0}(x) \leq t \text { for some } x \in \mathcal{D}\right\}$$

强对偶

• 成立在$\left(0, p^{\star}\right)$处存在非竖直支撑超平面
• 对于凸问题，$\mathcal A$是凸集，因此在$(0, p^\star)$存在支撑超平面
• Slater条件：如果存在$(\tilde{u}, \tilde{t}) \in \mathcal{A}, \tilde u < 0$，那么$\left(0, p^{\star}\right)$处的超平面是非竖直的

对偶互补条件

假设强对偶成立，$x^\star$是原始问题的最优点，$\left(\lambda^{\star}, \nu^{\star}\right)$是对偶最优

$$\begin{aligned} f_{0}\left(x^{\star}\right)=g\left(\lambda^{\star}, \nu^{\star}\right) &=\inf _{x}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i}^{\star} f_{i}(x)+\sum_{i=1}^{p} \nu_{i}^{\star} h_{i}(x)\right) \\ & \leq f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} h_{i}\left(x^{\star}\right) \\ & \leq f_{0}\left(x^{\star}\right) \end{aligned}$$

因此，两个不等号取等号

• $x^{\star}$最小化$L\left(x, \lambda^{\star}, \nu^{\star}\right)$

• $\lambda_{i}^{\star} f_{i}\left(x^{\star}\right)=0$对$i=1,\ldots, m$：

  $$\lambda_{i}^{\star}>0 \Longrightarrow f_{i}\left(x^{\star}\right)=0, \quad f_{i}\left(x^{\star}\right)<0 \Longrightarrow \lambda_{i}^{\star}=0$$