1. 凸集(1)

Convex Set(1)

0. 前言

• 主要说明了一些学习前需要了解的重要概念和前置知识。
• boyd教授的凸优化主页
• ucla的凸优化课程主页
• pku的凸优化课程主页

1. Line and segments

• $y: \theta x_1+(1-\theta)x_2, \theta\in \textrm{R}$

2. Affine sets(仿射集)

• $\mathcal{C}\subseteq \textrm{R}^n $ is affine
  • if $\forall x_1,x_2\in \mathcal{C}$ , then ${\theta x_1+(1-\theta)x_2\mid \theta\in \textrm{R}}\subseteq \mathcal{C}$
  • if $\forall x_1,x_2,\cdots,x_k$ , then ${\theta_1 x_1+\cdots \theta_k x_k \mid \sum\theta_i=1}\subseteq \mathcal{C}$
  • if $\mathcal{V}=C-x_0={x-x_0 \mid x\in \mathcal{C}}$ is a subspace, if $x_0\in \mathcal{C}$
  • affine hall

3. Convex set

• $\mathcal{C}$ is convex if $x_1, x_2 \in \mathcal{C}, 0\leq\theta\leq 1, \theta x_1+(1-\theta)x_2 \in \mathcal{C}$
  • smaller than affine sets cause for every 2 points it’s a segment but not a line in convex set

4. Convex cone

• $\mathcal{C}$ is cone if $x\in \mathcal{C}, {\theta x\mid \theta\geq 0}\subseteq \mathcal{C}$
• $\mathcal{C}$ is convex cone if $x_1, x_2\in \mathcal{C}, {\theta x_1+\theta x_2\mid\theta_1,\theta_2\geq 0}\subseteq \mathcal{C}$
  • $\alpha\theta_1 x_1+(1-\theta_1)x_2$

Eg.

5. Other eg

5.1 Hyperplanes

• ${x\mid a^Tx=b}={x\mid a^Tx=a^Tx_0}={x\mid a^T(x-x_0)=0}$
  so $a$ is normal direction
  $={x_0+v\mid a^Tv=0}=x_0+a^\perp(a^\perp={v\mid a^Tv=0})$
• Halfspaces ${x\mid a^Tx\leq b}$

5.2 Euclidean balls and ellipsoids

• $B(x,r)={y\mid |x-y|_2\leq r}={x+ru\mid|u|_2\leq 1}$
• $E={x\mid(x-x_c)^TP^{-1}(x-x_c)\leq 1}, P>0$ that is using $P$ to scale ball

5.3 Norm balls and cones

• Norm Cone:
  $\mathcal{C}={(x,t)\mid |x|\leq t}\subseteq \textrm{R}^{n+1}$
• Transfer n dimension function into n+1 dimension set(x+f(x))

5.4 Pohedra

• Polyhedron: $P={x\mid Ax\leq b, Cx=d}$
  • Hyperplanes + Halfspaces
• Simplex: $\mathcal{C}=conv\{v_0,\cdots,v_k\}=\{x=\theta_0v_0+\theta_1v_1+\cdots+\theta_kv_k\mid\theta_i\geq 0,\forall i, \sum\theta_i=1\}$
  $={x_0+By\mid y\geq0,\sum y_i\leq 1}, B=(v_1-v_0, \cdots,v_k-v_0)$
  $\exists$ non-singular $A\in R^{n×n}$ such that $$AB=\begin{pmatrix}A_1B\\A_2B \end{pmatrix}\begin{pmatrix}I\\0 \end{pmatrix}$$ $\mathcal{C}={x\mid A_2v_0=A_2x, A_1x\geq A_1v_0, 1^TA_1x\leq 1+1^TA_1v_0}$

5.5 positive semi-definite cone

$$\begin{align} S^n&=\{x\in \textrm{R}^{n×n}\mid x=x^T\}\\ S^n_+&=\{x\in \textrm{S}^n\mid x\geq 0\}\\ S^n_{++}&=\{x\in \textrm{S}^n\mid x>0\}\\ \end{align}$$