EE364A Lecture 7 and Lecture 8

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

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

Lecture 7 Convex optimization problems

广义不等式约束

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

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

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

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

半定规划(SDP)

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

  • 不等式约束被称为线性矩阵不等式(LMI)

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

    等价于一个LMI

将LP和SOCP视为SDP

LP以及等价的SDP。

LP:

SDP:

SOCP以及等价的SDP。

SOCP:

SDP:

特征值最小化

其中

等价于SDP

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

  • 上述等价是因为

矩阵范数最小化

其中

等价于SDP

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

  • 约束是因为

向量优化

广义向量优化问题

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

凸向量优化问题

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

最优以及Pareto最优点

考虑目标函数的可行集

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

多准则优化

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

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

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

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

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

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

正则化最小二乘

标量化

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

将多准则问题标量化

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

例子

  • 正则化最小二乘问题

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

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

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

Lecture 8 Duality

拉格朗日函数

标准形式的问题(不一定凸)

变量$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}$,

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

拉格朗日对偶

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

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

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

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

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

线性方程的最小范数解

对偶函数

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

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

  • 带入可得

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

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

标准形式的LP

对偶函数

  • 拉格朗日函数

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

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

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

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

对偶函数

其中

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

证明:利用如下事实

  • 如果$|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$:

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

双向划分

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

对偶函数

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

Lagrange对偶和共轭函数

对偶函数

  • 回顾共轭的定义

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

对偶问题

Lagrange对偶问题

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

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

标准LP

对偶形式

弱和强对偶

弱对偶:

  • 弱对偶总是成立(对凸问题以及非凸问题)

强对偶:

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

Slater约束准则

对于凸问题,强对偶成立

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

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

具有强对偶性的非凸问题

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

对偶函数:

  • 如果$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:

SDP

几何解释

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

对偶函数的解释:

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

上镜图变化:考虑

强对偶

  • 成立在$\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)$是对偶最优

因此,两个不等号取等号

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

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

本文标题:EE364A Lecture 7 and Lecture 8

文章作者:Doraemonzzz

发布时间:2019年09月02日 - 23:20:00

最后更新:2019年09月09日 - 20:39:50

原始链接:http://doraemonzzz.com/2019/09/02/EE364A Lecture 7 and Lecture 8/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。