Convex Optimization Note(1): Affine Set and Convex Set

1. Convex Sets

1.1 Affine Set $C$

Definition: $\mathrm{\forall }{x}_1,x_2\in C,\theta x_1+(1-\theta )x_2\in C$

Property:

• Solution Set of Linear Equation $⟺$ Affine Set(线性方程的解集是affine set，同时affine set都能写成线性方程的解)

• Subspace: $V=C-x_0$ where $x_0\in C$(无论选择哪个$x_0$，subspace $V$始终能穿过原点)

1.2 Affine Hull $\mathbf{\text{aff }}C$

Definition: All affine combinations of points in set $C$

Property: Smallest affine set that contains $C$

Example: Affine set of a circle $\{(x_1,x_2)\in {\mathbb{R}}^2|x_1^2+x_2^2=1\}$ is ${\mathbb{R}}^{\mathbb{2}}$, the affine dimesion is 2.

1.3 Convex Set

Definition: Affine set with $$$$, we have similarly Convex Hull

Property:

• works for infinite sums and integral

• pass through expectation

1.4 Cone(non-negative homogeneous)

Definition: $$$$

1.5 Simplex

Definition: Convex hull of $$$$ affine independent vector

affine independent: 直观理解与线性相关定义类似，数学表达上对于$$$$，如果$$$$线性无关，则这k+1个向量仿射无关。值得一提的是对于二维平面，要证明四个及以上向量仿射无关就需要证明三个及以上二维向量线性无关，而三个二维向量必定线性相关，因此不存在四个及以上仿射相关的二维向量，因此 $$$$ 中的simplex只可能是三角形（而不会是四边形或更多边形）。

1.6 Positive Semi-definite Cone

Definition: Set of Semi-definite matrix $$$$

Property: This set is a convex cone. (任意两个半正定矩阵线性组合，系数为正的情况下，结果仍为半正定矩阵)

2. Operation that preserves convexity

• Intersection of convex sets is still convex

• Affine Function projects convex sets to convex sets

  Affine Function: 等同于线性变换

• Perspective Function -> Linear-Fractional Function

  $$$$ to $$$$

3. General Inequality

3.1 Proper Cone

Convex; Closed; Solid(non-emplty interior); Pointed(不超过半平面)

3.2 Inequality

Let $$$$ be a proper cone in vector space $$$$, we say vector $$$$ is greater than $$$$ with respect to $$$$ when we have $$$$. Denoted as: $$$$

4. Seperating and supporting hyperplane

Seperating hyperplane: For two convex sets that are disjoint(no intersection), there exists a hyperplane that seperates these two sets.

Converse theorm: If at least one convex set is open, existing seperating hyperplane means disjoint sets.

Supporting hyperplane: Seperating hyperplane on a boundary point

5. Dual Cone

Definition: For a cone $$$$, the dual cone is defined as: $$$$

几何上可以理解为与所有目标锥内的向量夹角都不超过90度的向量构成的锥

Property:

• $$$$ is the minimum element of set $$$$ with respect to $$$$, it means that for $$$$, $$$$ is the minimizer of $$$$ over $$$$