凸优化之Convex set概念

2021-12-21 本文已影响0人十年磨剑_莫回首

凸集合

今天，定义一下凸集合（convex set）C：

假设凸集合C： C $\subseteq$ $R^{n}$ , 有两个向量 x,y $\in$ C,

使得 tx+(1-t)y $\in$ C 对于 $\forall$ t $\in$ [0,1] 恒成立。

用图示的方法表示就是：第一个是凸集合，第二个不是凸集合。

convex set

convex hull

凸集合的常见例子：

1 空集，一个点，一条线

2 Norm ball: $\{ x :||x||\leq r \}$ $对于给定的 norm ||\cdot ||, 半径是 r$

证明如下：

$let \ x_{1} \ and \ x_{2} \in A=\{x:||x||\leq r\}, then \ \forall \theta \in [0,1], we \ could \ conclude \ that \\\ ||\theta x_{1}+(1-\theta)x_{2}||\leq\theta||x_{1}||+(1-\theta)||x_{2}||\leq \theta r + (1-\theta)r=r, so \ A \ is \ convex$

3 Hyperplane:

$\{ x: a^{T}x=b \}, for \ given \ a \ and \ b$

4 Halfspace:

$\{x : a^{T}x \leq b \}$

5 Affine space:

$\{ x : Ax =b \}, for \ given \ A, \ b$

6 Polyhedron:

$\{ x : Ax \leq b \} \ or \ \{ x: Ax \leq b, Cx=d \}$

Cone set

凸集合的几个重要性质：

凸函数概念

对于保留凸函数和凸集合的操作，这块就不继续展开了，大家如果对这些兴趣，欢迎阅读：

Boyd 的《convex optimization》

Rockafellar 的《convex analysis》

上一篇下一篇

猜你喜欢

热点阅读