5，6 几种重要凸集

作者: 抄书侠 | 来源:发表于2019-06-23 11:29 被阅读0次

5，6 几种重要凸集
最优化基础
7,8 凸集的交，保凸运算
关于凸优化
深度学习笔记
夏天，是我不变的记忆
凸集
凸集
凸优化笔记2-主要内容
COAC：Introduction

超平面与半平面

$\{x|a^Tx=b\},x,a\in\mathbb{R}^n,b\in\mathbb{R},a\not=0$

超平面
两边为半平面

球和椭球

球 $B(x_c,r)=\{||x-x_c||_2\leq r \}=\{x|\sqrt{(x-x_c)^T(x-x_c)}\leq r \}$
椭球 $\varepsilon(x_c,P)=\{x|(x-x_c)^TP^{-1}(x-x_c)\leq 1\},x_c\in \mathbb{R}^n,P\in S^n_{++}$

多面体与单纯形

多面体 $P=\{x|a_j^T x\leq b_j,j=1,\ldots,m,c_j^T x=d_j,j=1,\ldots,p \}$
单纯形(simplex)在 $\mathbb{R}^n$ 空间中选择 $v_0,\ldots,v_k$ 共 $k+1$ 个点
$v_1-v_0,\ldots,v_k-v_0$ 线性无关
则与上述点相关的单纯形为：
$C=Conv\{v_0,\ldots,v_k \}=\{\theta_0 v_0+\ldots +\theta_k v_k,\theta\geq 0 ,1^T\theta=1 \}$

例：证明：Simplex是Polyhedron的一种
证： $x\in C\in \mathbb{R}^n,C为Simplex\Leftarrow\Rightarrow x=\theta_0 v_0+\ldots+\theta_kv_k$
$1^T\theta =1,\theta\geq 0,v_1-v_0,\ldots,v_k-v_0$ 线性无关
定义： $[\theta_1,\ldots,\theta_k]^T=y,y\geq 0,1^Ty\leq 1$
$[v_1-v_0,\ldots,v_k-v_0]=B\in\mathbb{R}^{n\times k}$
$x\in C\Leftarrow\Rightarrow x=\theta_0v_0+\ldots\theta_k v_k=v_0+\theta_1(v_1-v_0)+\ldots+\theta_k(v_k-v_0)=v_0+By$
$rank(B)=k (k\leq n)$
$\exists非奇异矩阵 A= \left\{ \begin{array}{c} A_1 \\ A_2 \\ \end{array} \right\} \in \mathbb{R}^{n\times n}$
$AB=\left [ \begin{array}{c} A_1 \\ A_2 \\ \end{array} \right ]\ B=\left [ \begin{array}{c} I_k \\ 0 \\ \end{array} \right ]$
$\Leftarrow\Rightarrow Ax=Ax_0+ABy$
$\Leftarrow\Rightarrow \left [ \begin{array}{c} A_1 \\ A_2 \\ \end{array} \right ] \ x=\left [ \begin{array}{c} A_1 \\ A_2 \\ \end{array} \right ] \ V_0+\left [ \begin{array}{c} I_k \\ 0 \\ \end{array} \right ] \ y$
$\Leftarrow\Rightarrow \left\{ \begin{array}{c} A_1x=A_1V_0+y\\ A_2x=A_2V_0\\ \end{array}\right.$