凸优化学习

文字：

对于任意集合 C C C，包含 C C C的最小的仿射集称为 C C C的仿射包。 数学： a f f    c = { θ 1 x 1 + ⋯ + θ k x k ∣ ∀ x 1 , ⋯   , x k ∈ C    θ 1 + ⋯ + θ k = 1 } aff\ \ c=\lbrace \theta_1 x_1+ \cdots +\theta _kx_k \mid{\forall x_1,\cdots,x_k \in C \ \ \theta_1+\cdots+\theta_k=1\rbrace} aff  c={θ1​x1​+⋯+θk​xk​∣∀x1​,⋯,xk​∈C  θ1​+⋯+θk​=1}

文字： 一个集合是凸集，当属于该集合的任意两点之间的线段仍然在该集合内。 数学：

C   i s   a   C o n v e x   S e t ⇔ ∀ θ x 1 + ( 1 − θ ) x 2 ∈ C , x 1 , x 2 ∈ C   ∀ θ    θ ∈ [ 0 , 1 ] C\ is \ a\ Convex\ Set\Leftrightarrow\forall \theta x_1+(1-\theta)x_2 \in C,x_1,x_2 \in C\ \forall \theta \ \ \theta\in[0,1] C is a Convex Set⇔∀θx1​+(1−θ)x2​∈C,x1​,x2​∈C ∀θ  θ∈[0,1]

图一为凸集，需要说明凸集的一个性质，凸集在几何上表现也是凸的。任意两点的连线都在六边形内。

文字： 一个集合是凸集，当属于该集合的任意数量的点的凸组合仍然在该集合内。 数学 C   i s   a   C o n v e x   S e t ⇔ θ 1 x 1 + , ⋯   , + θ k x k ∈ C , ∀ x 1 , ⋯   , x k ∈ C    ∀ θ 1 , ⋯   , θ k    θ 1 , ⋯   , θ k ∈ [ 0 , 1 ]     θ 1 + , ⋯   , + θ k = 1 C\ is \ a\ Convex\ Set\Leftrightarrow\theta_1 x_1+,\cdots,+\theta_k x_k\in C, \forall x_1,\cdots ,x_k \in C\ \ \forall \theta_1,\cdots,\theta_k \ \ \theta_1,\cdots,\theta_k\in[0,1]\ \ \ \theta_1+,\cdots,+\theta_k=1 C is a Convex Set⇔θ1​x1​+,⋯,+θk​xk​∈C,∀x1​,⋯,xk​∈C  ∀θ1​,⋯,θk​  θ1​,⋯,θk​∈[0,1]   θ1​+,⋯,+θk​=1 类似仿射集的定义，定义一和定义二仍然是等价的。

对于点 x 1 , ⋯   , x k x_1,\cdots,x_k x1​,⋯,xk​， θ 1 x 1 + , ⋯   , + θ k x k \theta_1 x_1+,\cdots,+\theta_k x_k θ1​x1​+,⋯,+θk​xk​称为它们的凸组合，其中 ∀ θ 1 , ⋯   , θ k    θ 1 , ⋯   , θ k ∈ [ 0 , 1 ]     θ 1 + , ⋯   , + θ k = 1 \forall \theta_1,\cdots,\theta_k \ \ \theta_1,\cdots,\theta_k\in[0,1]\ \ \ \theta_1+,\cdots,+\theta_k=1 ∀θ1​,⋯,θk​  θ1​,⋯,θk​∈[0,1]   θ1​+,⋯,+θk​=1

文字： 对于任意集合 C C C，包含 C C C的最小的凸集称为 C C C的凸包。 数学： ∀ C ∈ R n C o n v   C = { θ 1 x 1 + , ⋯   , + θ k x k ∣ ∀ x 1 , ⋯   , x k ∈ C    θ 1 + , ⋯   , + θ k = 1    θ 1 , ⋯   , θ k ∈ [ 0 , 1 ] } \forall C \in R^n \\Conv\ C=\lbrace \theta_1 x_1+,\cdots,+\theta_k x_k\mid\forall x_1,\cdots,x_k \in C\ \ \theta_1+,\cdots,+\theta_k=1\ \ \theta_1,\cdots,\theta_k\in[0,1]\rbrace ∀C∈RnConv C={θ1​x1​+,⋯,+θk​xk​∣∀x1​,⋯,xk​∈C  θ1​+,⋯,+θk​=1  θ1​,⋯,θk​∈[0,1]}

锥： C   i s   C o n e ⇔ ∀ x ∈ C , ∀ θ ≥ 0 ， 有 θ x ∈ C C\ is \ Cone \Leftrightarrow \forall x \in C,\forall \theta \geq0，有\theta x \in C C is Cone⇔∀x∈C,∀θ≥0，有θx∈C 凸锥： C   i s   C o n v e x ⇔ ∀ x 1 , x 2 ∈ C , ∀ θ 1 , θ 2 ≥ 0 ， 有 θ 1 x 1 + θ 2 x 2 ∈ C C \ is \ Convex \Leftrightarrow \forall x_1,x_2 \in C,\forall \theta_1,\theta_2 \geq0，有\theta_1 x_1+\theta_2x_2 \in C C is Convex⇔∀x1​,x2​∈C,∀θ1​,θ2​≥0，有θ1​x1​+θ2​x2​∈C 例

图三这三条射线构成的集合就是锥。

图四阴影部分为凸锥

对于点 x 1 , ⋯   , x k x_1,\cdots,x_k x1​,⋯,xk​， θ 1 x 1 + , ⋯   , + θ k x k \theta_1 x_1+,\cdots,+\theta_k x_k θ1​x1​+,⋯,+θk​xk​称为它们的凸锥组合，其中 ∀ θ 1 , ⋯   , θ k    θ 1 , ⋯   , θ k ≥ 0 \forall \theta_1,\cdots,\theta_k \ \ \theta_1,\cdots,\theta_k\ge0 ∀θ1​,⋯,θk​  θ1​,⋯,θk​≥0

文字： 对于任意集合 C C C，包含 C C C的最小的凸锥称为 C C C的凸锥包。 数学： ∀ C ∈ R n C o n v   C o n e   C = { θ 1 x 1 + , ⋯   , + θ k x k ∣ θ 1 , ⋯   , θ k ≥ 0 } \forall C \in R^n \\Conv\ Cone\ C=\lbrace \theta_1 x_1+,\cdots,+\theta_k x_k\mid\theta_1,\cdots,\theta_k\ge0\rbrace ∀C∈RnConv Cone C={θ1​x1​+,⋯,+θk​xk​∣θ1​,⋯,θk​≥0} 例

图五的凸包是该集合本身。

图六两条射线之间的区域则为凸包。

几个概念的比较 仿射集是凸集的特例，凸锥是凸集的特例。 凸组合是仿射组合的特例，仿射组合是凸锥组合的特例。 对于同一集合而言，它的 凸包 ⊂ \sub ⊂凸锥包 ⊂ \sub ⊂仿射包