首页 » 学习 » 凸集基本概念

凸集基本概念

convex_optimization
  1. 线与线段
  2. 仿射集
  3. 仿射维度和相对内部
  4. 凸集
  5. 参考

本文是我在学习Convex Optimization这本书第2章Convex sets过程的读书笔记,翻译了凸优化基本概念的定义和相关性质。一些名词的翻译参考了其他博客的翻译,没有经过仔细查阅文献,所以专业名词都保存了英文原文。

凸优化

1 线与线段

设不等的两个点 x_1、x_2 \in \mathbf{R}^n,这两个点可以通过
y=\theta x_1+(1-\theta)x_2
形成直线(line)y,其中\theta \in \mathbf{R}。通过调整\theta可以得到x_1、x_2所在直线上任意一个点。
也可以变形
y=x_2+\theta(x_1-x_2)
0<\theta<1时,y为以x_1、x_2为端点的线段(line segment)

2 仿射集

当一个属于\mathbf{R}^n的C,其中任意两个不同的点所在直线仍在C中,则称C是一个仿射集(affine set)。也就是,\forall x_1、x_2 \in C,\theta \in \mathbf{R}, \theta x_1+(1-\theta) x_2 \in C

还可以将点的数量进行拓展。\theta_1x_1+\cdots+\theta_kx_k,其中\theta_1+\cdots+\theta_k=1,则称为其为x_1,\cdots,x_k仿射组合(affine combination)。当x_1+\cdots+x_k都属于仿射集C,那么他们的仿射组合仍然属于仿射集C。

属于\mathbf{R}^n内的集C内所有的仿射组合被称为仿射包(affine hull),记为\mathbf{aff}C
\mathbf{aff}C=\{\theta_1x_1+\cdots+\theta_kx_k\mid x_1,\ldots,x_k \in C,\theta_1+\cdots+\theta_k=1\}

3 仿射维度和相对内部

集合的仿射维度(affine dimension)为其仿射包的维度。它与常见的维度定义不太相同,例如一个单位圆\{x\in \mathbf{R}^n\mid x_1^2+x_2^2=1\}的仿射维度为2维,而在常用的维度定义下他是1维的。

集合C的相对内部(relative interior)为其仿射包的内点,记为\mathbf{relint}C
\mathbf{relint}C=\{x\in C\mid B(x,r) \cap \mathbf{aff}C \subseteq C ,r >0\}
其中B(x,r)=\{y \mid \parallel y-x \parallel \leqslant r \}

4 凸集

以集合C中任意两个不同的点作为端点形成的线段都被集合C所包括,那么称集合C为凸集(convex set)

我们称\theta_1x_1+\cdots+\theta_kx_x,其中\theta_1+\cdots+\theta_k=1,\theta_i\geqslant 0,i=1,\ldots,k,为点x_1,\ldots,x_k凸组合(convex combination)

集合C的凸包(convex hull)为C内所有的凸组合,记为\mathbf{conv}C
\mathbf{conv}C=\{\theta_1x_1+\cdots+\theta_kx_k\mid x_i\in C,\theta_i\geqslant 0,i=1,\ldots,k,\theta_1+\cdots+\theta_k=1\}

5 锥

如果集合C内每一个点x,对任意大于零的\theta,都有\theta x\in C,那么称C为锥(cone)。也就是以原点为起始点,包含点x的射线在集合C内。

若集合C是锥且是凸的,那么C为凸锥(convex cone)
\theta_1x_1+\theta_2x_2\in C,\forall x_1,x_2\in C,\theta_1,\theta_2\geqslant 0

\theta_1,\ldots,\theta_k\geqslant0条件下满足\theta_1x_1+\cdots+\theta_k x_k则称为x_1,\ldots,x_k锥组合(conic combine)

集合C的锥包(conic hull)是集合内所有锥组合的集合。

6 参考

标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注