5，6 几种重要凸集

2019-06-23  本文已影响0人  抄书侠

超平面与半平面

\{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.

\Leftarrow\Rightarrow \left\{ \begin{array}{c} A_1x\geq A_1V_0\\ 1^TA_1x\leq 1+1^TAV_0\\ A_2x=A_2V _0 \end{array} \right.

上一篇 下一篇

猜你喜欢

热点阅读