EE364A Lecture 1 and Lecture 2

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

最近开始学习凸优化,公开课为斯坦福的凸优化公开课,主页如下。这次回顾凸优化第一第二讲,这部分介绍了凸集的概念。

Lecture 1 Introduction

主要介绍凸优化的历史和应用,这里从略。

Lecture 2 Convex sets

仿射集

穿过$x_1,x_2$的直线可以表示为

仿射集:包含过集合中任意两点的直线的集合。

例子:

凸集

过$x_1, x_2$的线段可以表示为

其中$0\le \theta \le 1$

凸集:包含过集合中任意两点的线段的集合,即

凸组合和凸壳

$x_{1}, \ldots, x_{k}$的凸组合:

其中

凸壳$\operatorname{conv} S$:包含集合中所有点的凸组合的集合,例如

凸锥

$x_1, x_2$的锥(非负)组合:

其中$\theta_{1} \geq 0, \theta_{2} \geq 0$

凸锥:包含集合中所有点的锥组合的集合

超平面和半平面

超平面:$\left\{x | a^{T} x=b\right\}(a \neq 0)$

半平面:$\left\{x | a^{T} x \leq b\right\}(a \neq 0)$

其中

  • $a$是单位向量
  • 超平面是仿射和凸的;半平面是凸的

欧式球和椭球

中心为$x_c$,半径为$r$的欧式球:

椭球:

其中$P \in \mathbf{S}_{++}^{n}$($P$为对称正定矩阵)。

另一种表示为:$\left\{x_{c}+A u ||u|_{2} \leq 1\right\}$,其中$A$为非奇异方阵。

范数球和范数锥

中心为$x_c$,半径为$r$的范数球:

范数锥:

多面体

多面体为有限多个线性不等式和方程组的交集

其中$A \in \mathbf{R}^{m \times n}, C \in \mathbf{R}^{p \times n}, \preceq$为元素不等号。

不难看出多面体为有限多个半平面和超平面的交集。

正定对称锥

记号:

  • $\mathbf{S}^{n}$为$n\times n$对称矩阵

  • $\mathbf{S}_{+}^{n}=\left\{X \in \mathbf{S}^{n} | X \succeq 0\right\}$:对称半正定$n\times n$矩阵

    $\mathbf{S}_{+}^{n}$为凸锥

  • $\mathbf{S}_{++}^{n}=\left\{X \in \mathbf{S}^{n} | X \succ 0\right\}$:对称半正定$n\times n$矩阵

保凸运算

有些运算可以保持集合的凸性:

  • 交集
  • 仿射函数
  • 透视函数
  • 线性分式函数
交集

凸集的交集为凸集。

仿射函数

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$为仿射函数,如果$f(x)=A x+b,A \in \mathbf{R}^{m \times n}, b \in \mathbf{R}^{n}$

  • 凸集在$f$下的像为凸集

  • 凸集的原像$f^{-1}(C)$为凸集

透视函数和线性分式函数

透视函数:$P : \mathbf{R}^{n+1} \rightarrow \mathbf{R}^{n}$,其中

凸集在透视函数下的像以及原像都是凸集。

线性分式函数:$f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$

凸集在线性分式函数下的像以及原像都是凸集。

广义不等式

凸锥$K \subseteq \mathrm{R}^{n}$是正规锥,如果

  • $K$是闭集(包含其边界)
  • $K$是实的(具有非空内部)
  • $K$是尖的(不包含直线,即$x \in K,-x \in K \Longrightarrow x=0$)

正规锥$K$定义的广义不等式:

例子

  • 元素不等号($K=\mathrm{R}_{+}^{n}$)

  • 矩阵不等号($K=\mathrm{S}_{+}^{n}$)

性质:$\preceq_{K}$的很多性质类似于$\mathbf R$上的$\le $,例如

最小和极小

$\preceq_{K}$一般不是线性序:我们可以有$x \not\preceq_{K} y$以及$y \not\preceq_{K} x$。

$x \in S$是$S$(关于$\preceq_{K}$)的最小元,如果

$x \in S$是$S$(关于$\preceq_{K}$)的极小元,如果

例子:考虑$K=\mathrm{R}_{+}^{2}$

那么$x_1$是$S_1$的最小元,$x_2$是$S_2$的极小元。

超平面分离定理

超平面分离定理

如果$C,D$是不交凸集,那么存在$a \neq 0, b$,使得

图示如下:

即超平面$\left\{x | a^{T} x=b\right\}$分离了$C$和$D$

支撑超平面定理

集合$C$在$x_0$处的支撑超平面为:

其中$a \neq 0$以及对于所有$x\in C, a^{T} x \leq a^{T} x_{0}$

支撑超平面定理:如果$C$是凸集,那么在$C$边界上每点都存在支撑超平面

对偶锥和广义不等式

锥$K$的对偶锥为

正规锥的对偶锥也正规,因此定义广义不等式:

对偶不等式定义的最小元和极小元

关于$\preceq_{K}$的最小元:

$x$是$S$的最小元当且仅当对于任意$\lambda \succ_{K^{*} } 0$,$x$是在$S$上最小化$\lambda^T z$的唯一点。

关于$\preceq_{K}$的极小元:

  • 如果对于某个$\lambda \succ_{K^{*} } 0$,$x$在$S$上最小化$\lambda^T z$,那么$x$是极小元

本文标题:EE364A Lecture 1 and Lecture 2

文章作者:Doraemonzzz

发布时间:2019年08月17日 - 12:18:00

最后更新:2019年08月17日 - 22:53:42

原始链接:http://doraemonzzz.com/2019/08/17/EE364A Lecture 1 and Lecture 2/

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