2. 凸集(2)

Convex Sets(2)

0. 前言

• 这一篇笔记涉及的东西比较抽象，且涉及比较多实变中的定义。对度量空间上的各类集合性质不甚熟悉的话，学起来会比较吃力（特别是一些证明）。我认为需要首先掌握好重要的概念，并且对定理有直观的认识体会（先不要求严格证明）。

• 定义复习：
  • 闭集S：S的所有聚点都在S中
  • 开集S：闭集的补集
  • 可列集：S的基数和自然数集相当
  • 紧集：任一开覆盖都包含有限子覆盖；$R^n$ 中的紧集是有界闭集

1. Operations that preserve convexity

$f: \mathcal{R}^m\rightarrow\mathcal{R}^n$ preserves convexity if $f(S)$ is convex for any $S\subseteq R$

1.1 Intersection

• $S_1\cap S_2$ convex, if $S_1, S_2$ convex

1.2 Affine transform

• $f(x)=Ax+b: \mathcal{R}^n\rightarrow\mathcal{R}^m ,(A\in R^{m\times n})$
• $f(S)$ convex if $S$ is convex
  $f^{-1}(S)={x\mid Ax+b\in S}$ is convex
• Eg. $S_1\times S_2 ={(u,v)\mid u\in S_1, v\in S_2}$
  $S_1+S_2={u+v\mid u\in S_1, v\in S_2}$
  $f(u,v)=u+v$

1.3 Perspective function

• perspective transform:
  $P:R^{n+1}\rightarrow R^n$
  and $(x,t)\rightarrow \frac{x}{t}$
  with $dom(P)={(x,t)\mid x\in R^n, t>0}$
  If $S\subseteq dom(P)$ and convex $\rightarrow P(S)$ is convex

  Proof:
  $\forall P(x),P*y( x,y\in S,$ we need to prove $[P(x), P(y)]\subseteq P(S)$ …
  Just calculate..(

• $P^{-1}:R^n \rightarrow R^{n+1}$
  $P^{-1}(C)={(x,t)\mid \frac{x}{t}\in C, t>0 }$
  If $C$ is convex, then $P^{-1}(C) convex$

1.4 Linear fractional

$$f(x)=\frac{Ax+b}{c^Tx+d}$$ for $c^Tx+d>0$ - $f(x)=p_0g$ $$g(x)=\begin{pmatrix}A\\c^T\end{pmatrix}x+\begin{pmatrix}b\\d\end{pmatrix}, p(x,t)=\frac{x}{t}, t>0$$

If $S$ is convex $\rightarrow f(s)=p_0g(S)$ convex

(Operation 不一定是严格的映射)

2. Separation theorem

If $C,D$ are two non-empty, disjoint, convex sets, then

$$\exists a\neq 0, a\in R^n, b\in R, s.t.\\ 1.a^Tx\leq b,\forall x\in C\\ 2.a^Tx\geq b,\forall x\in D$$

算是一个符合直觉的结论，两个非空凸集不相交的话一定会有一个超平面将两个凸集隔开
但是证明并不好证
逆命题需要加条件，需要其中一个集合为开

Proof
通过构造两个凸集之间的”平分线（超平面）“来找到相应的a和b，然后计算a和b满足条件
其中需要考虑多种情况(开集/闭包包含0)

3. Strict Separation

If $C,D$ are two non-empty, disjoint, convex sets, then strict separation is

$$\exists a\neq 0, a\in R^n, b\in R, s.t.\\ 1.a^Tx< b,\forall x\in C\\ 2.a^Tx> b,\forall x\in D$$

$C$ is convex closed set, $x_0\neq C \Leftrightarrow$ strict separation
$\overline{C-D}\cap{0}=\varnothing \Leftrightarrow$ strict separation

4. Convex cone

• k is a proper cone if

1. convex
2. closed
3. solid
4. pointed

• generalized inequalities:

• Define partial order:
  $x\preceq_K y \Leftrightarrow y-x\in K$
  $x\prec_K y \Leftrightarrow y-x\in int(K)$ 是K的内点

x和y的偏序关系不一定非得成立其中一个

4.1 Dual cone

• Let k be a cone
  $k^*={y\mid x^Ty\geq 0, \forall x\in k}$

k 可以定义成任意集合，无所谓

• Properties:

1. $k^*$ is closed, convex cone
2. $k_1\subseteq k_2\rightarrow k^*_2\subseteq k_1^※$
3. $k^*=\overline{conv(K)}$
4. if K is proper cone, K is proper cone and K*=K

• Some eg

1. $K=R^n+\rightarrow K^*=R^n+$
2. $K=S^n+\rightarrow K^*=S^n+$
3. $K={(x,t)\mid |x|\leq t}\rightarrow K^*{(u,v)\mid |u|\leq v}$

Minimum and minimal element of S

• x is a minimum element of S $\Leftrightarrow S\subset x+K$ 最小元
• x is a minimal element of S $\Leftrightarrow (x-K)\cap S={x}$ 极小元

最小元条件更强，且要么不存在要么为1(?)

• • x is a minimum element of S $\Leftrightarrow \forall \lambda \succ_{K^*}0, x$ is the unique minimizer of $\lambda^T z $ over S
  • x is a minimal element of S $\Leftarrow$ for some $\lambda\succ_{K^*}0$ , x is the minimizer of $\lambda^Tz$ over S

极小元条件的右方向不成立。直接用极小元定义可以看出来（一个口向左下的C字集合）。如果S凸，那么右方向成立
每个集合S可以从原点引一锥包K，可求对偶锥K。若一超平面法向（即 $\lambda$）在K内，则超平面可以作一个极小元(?)