凸集

article/2025/9/12 3:22:47

本文参考自清华大学研究生公共课教材——数学系列《最优化理论与算法》（第二版）

一：凸集

定义：设S为n维欧式空间中 $\mathbb{R}^{n}$ 中的一个集合，若对S中任意两点，联结它们的线段仍属于S，称这样的集合S是一个凸集。

用代数的形式表达为：对S中任意两点 $x^{(1)}$ ， $x^{(2)}$ 及每个实数 $\lambda \in [0,1]$ ，都有

$\lambda x^{(1)}+(1-\lambda )x^{(2)}\in S$

称S为凸集

$\lambda x^{(1)}+(1-\lambda )x^{(2)}$ 称为 $x^{(1)}$ ， $x^{(2)}$ 的凸组合。

下面验证几个集合是否为凸集：

例一：验证集合 $H=\left \{ x|p^{T}x=a \right \}$ 为凸集，其中，p为n维列向量，a为实数

对于任意两点 $x^{(1)}$ ， $x^{(2)}$ $\in H$ ，及每个实数 $\lambda \in [0,1]$ 都有

$\lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}$

$\because p^{T}x^{(1)}=p^{T}x^{(2)}=a$

$\therefore \lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}=\lambda a+(1-\lambda)a=a$

所以 $\lambda x^{(1)}+(1-\lambda )x^{(2)}\in H$

H称为 $\mathbb{R}^{n}$ 中的一个超平面，所以超平面为凸集。

例二：验证集合 $H^{-}=\left \{ x|p^{T}x\leqslant a \right \}$ 为凸集

对于任意两点 $x^{(1)},x^{(2)}\in H^{-}$ ，及每个实数 $\lambda \in [0,1]$ 都有

$p^{T}\left [ \lambda x^{(1)}+(1-\lambda)x^{(2)} \right ]\leqslant a$

上式左 $=\lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}$

$\because p^{T}x^{(1)}\leqslant a$ $p^{T}x^{(2)}\leqslant a$

$\lambda+(1-\lambda)=1$

$\therefore \lambda p^{T}x^{(1)}+(1-\lambda)p^{T}x^{(2)}\leqslant a$

所以 $\lambda x^{(1)}+(1-\lambda)x^{(2)}\in H^{-}$

所以 $H^{-}$ 为凸集，集合 $H^{-}=\left \{ x|p^{T}x\leqslant a \right \}$ 称为半空间，所以半空间为凸集

例三：验证集合 $L=\left \{ x|x=x^{(0)}+\lambda d,\lambda\geqslant 0 \right \}$ 为凸集，其中d是给定的非零向量， $x^{(0)}$ 是定点

对于任意两点 $x^{(1)},x^{(2)}\in L$ 及每一个数 $\lambda \in [0,1]$ ，必有 $x^{(1)}=x^{(0)}+\lambda_{1}d$ ， $x^{(2)}=x^{(0)}+\lambda_{2}d$ ， $\lambda_{1},\lambda_{2}$ 是非负数

$\lambda x^{(1)}+(1-\lambda)x^{(2)}=\lambda(x^{(0)}+\lambda_{1}d)+(1-\lambda)(x^{(0)}+\lambda_{2}d)$

$=x^{(0)}+\left [ \lambda \lambda_{1}+(1-\lambda)\lambda_{2} \right ]d$

由于 $\lambda \lambda_{1}+(1-\lambda)\lambda_{2}\geqslant 0$ ，所以 $\lambda x^{(1)}+(1-\lambda)x^{(2)}\in L$ ，所以L为凸集

集合 $L=\left \{ x|x=x^{(0)}+\lambda d,\lambda\geqslant 0 \right \}$ 成为射线，所以射线为凸集， $x^{(0)}$ 为射线的预点

二：极点

若假设S为非空凸集， $x=\lambda x^{(1)}+(1-\lambda)x^{(2)}(\lambda \in (0,1)),x^{(1)},x^{(2)} \in S$ ，必推得 $x=x^{(1)}=x^{(2)}$ ，则称x为凸集S的极点

这个论断对于紧凸集是正确的，但是对于无界集并不成立，此时引入极方向的概念

三：极方向

设S为 $\mathbb{R}^{n}$ 中的闭凸集，d为非零向量，如果对S中的每一个x，都有射线

$\left \{ x+\lambda d|\lambda\geqslant 0 \right \}\subset S$

则称向量d为S的方向。

设 $d^{(1)}$ 和 $d^{(2)}$ 是S的两个方向，若对任意正数 $\lambda$ ，有 $d^{(1)}\neq \lambda d^{(2)}$ ，则称 $d^{(1)}$ 和 $d^{(2)}$ 为两个不同的方向。

若S的方向d不能表示为该集合中两个不同方向的正的线性组合，则称d为S的极方向。

四：凸集分离定理

对于两个集合S1，S2，存在一个超平面H，使S1在H的一边，S2在H的另一边。

设超平面的方程为 $P^{T}x=a$ ，那么对于H某一边的点 $x$ ，有 $p^{T}x\geqslant a$ ，而对另一边的点 $x$ ，必有 $p^{T}x\leqslant a$

称超平面分离集合 $S_{1}$ 和 $S_{2}$

凸集

一：凸集

二：极点

三：极方向

四：凸集分离定理

相关文章

凸集（Convex sets）

【深度学习】logistic回归模型

十分钟理解logistic回归原理

python数据挖掘学习笔记——logistic逻辑回归实现

logistic回归分类与softmax回归

ｓｐｓｓ－logistic回归

logistic回归——PYTHON实现

二项logistic回归案例分析（附操作数据）

Logistic回归--实例

SPSS（八）logistic回归（图文+数据集）

2.2、logistic回归

Logistic Regression(逻辑回归)详细讲解

第13章Stata Logistic回归分析

机器学习笔记-Logistic回归

logistic回归详解

机器学习笔记（六）Logistic回归

【机器学习】Logistic回归（重新整理）

C语言 fprintf 函数 - C语言零基础入门教程

【printf函数的具体用法】

C语言printf函数详解