第3讲凸集凸函数凸规划

{ {
} }
{
}
+ D1 ⊂ H 0 = x ∈ R n | a T x > β
− D2 ⊂ H 0
{ = {x ∈ R
n
| aT
} x < β}
+ − 则称超平面 H 严格分离 D1 和 D2 ，其中 H 0 和 H 0 分别表示
H + 和 H − 的内部
7
点到凸集的投影
是凸集， 设 D ⊂ R n 是凸集， y ∈ R n 但是 y ∉ D ，则 的距离最小， （1）存在唯一的点 x ∈ D ，使得集合 D 到点 y 的距离最小，即 x − y = inf { x − y , x ∈ D} （2） x ∈ D 是点 y 到集合 D 的最短距离点的充分必要条件为
α 1 x (1) + α 2 x ( 2 ) ――― α 1 x (1) + α 2 x ( 2 ) + α 3 x ( 3 )
α 1 x (1) + α 2 x ( 2 ) ――― α 1 x (1) + α 2 x ( 2 ) + α 3 x ( 3 )
4
是凸集， 设 D ⊂ R n 是凸集，则任意 m 个点 x ( i ) ∈ D( i = 1,2,⋯ , m ) 的凸组合仍 即有： 属于 D ， 即有：
( x − x )T ( x − y ) ≥ 0 ， ∀x ∈ D
证明： （1） 证明： ） （ 令 S = x ∈ R n | x ≤ 1 则取充分大的 µ > 0 使得
Ds = D ∩ ( y + µS ) ≠ φ
因此连续函数 f ( x ) = x − y 在 D s 上必定可以取到极小点 存在性证明完毕

hj ( x ) 是线性函数。 其中 f ( x ) , gi ( x ) 是凸函数，
D { x | f ( x ) , x X , f 是凸函数}。 水平集：
性质：水平集一定是凸集。 3. 凸函数的性质 定理. 凸函数的局部极小点就是全局极小点。 4. 凸函数的判断条件 定理1. f ( x ) 是凸集X上的凸函数的充要条件是 x1 , x 2 X ，有 f ( x 2 ) f ( x1 ) f ( x1 )T ( x 2 x1 ) .
k
k : k 1 ； （4）令 x k 1 x k k d k ，
k （5）判断 x 是否满足停止条件。是则停止，否则转第2步。
搜索步长确定方法：
f ( x k k d k ) min f ( x k d k )

称 k 为最优步长，且有 f ( x k k d k )T d k 0 。
2 f ( x ) x 例子：
5. 凸规划 （1） min
s .t . f ( x) x D
其中 f ( x ) 是凸函数， D 是凸集。
（2） min
f ( x)
s .t .
g1 ( x ) 0 gl ( x ) 0 h1 ( x ) 0 hk ( x ) 0
八. 凸集与凸函数
1.凸集 （1）凸组合：已知 X R n ，任取k个点 x i X ， 如果存在常数 k k ai 0 (i 1 , 2 ,, k ) ， ai 1 ，使得 ai x i x ，则称 x 为 x i i 1 i 1
(i 1 , 2 ,, k ) 的凸组合。
定理2.设 f ( x ) 在凸集X上有二阶连续偏导数，则 f ( x ) 是凸

Df 2.9设S n非空，y n,则点y与集合S 之间的距离dist(y,S)定义为 dist（y, S) inf y-x (2.4)
xS
Th2.5设S为En中的闭凸集，y S,则存在唯一的
点x S,使得 y-x inf y-x xS
2. 凸集与凸函数
证明：令 inf y-x r 0 xS
换言之d不能表成它的两个不同方向的凸锥组合
d
d
d
x0
x0
2. 凸集与凸函数
例2.4 集合S {(x1, x2 ) x2 | x1 | 凡是与向量(0,1)T 夹角 45的向量 都是它的方向。(1,1)T，(1,1)T 是其仅 有的两个极方向
例2.5 设S {x Ax b, x 0} ,d是非零向量。 证明,d是S的方向 d 0且Ad 0.
x
n
x k xk jd j
kK
jJ
k 1,k 0, k K , j 0, j J
kK
(3)指标集J是空集当且仅当P是有界集合,即多胞形.
2. 凸集与凸函数
推论2.1 若多面体S={x|Ax=b,x≥0}非空,则S必有极点.
表示定理直观描述:设 X 为非空多面体. 则存在有限个极点 x1, …, xk , k>0. 进一步,存在有限个极方向 d1, …, dl, l>0 当且 仅当 X 无界. 进而, xX 的充要条件是 x 可以表为 x1, …, xk 的凸组合和d1, …, dl的非负线性组合(凸锥组合).
C T
2. 凸集与凸函数
有限点集{x0, x1,..., xm} n的凸包称为多胞形。 若{x0,x1,..., xm}仿射无关时，对应的凸包称为m维单纯形。 向量xi称为该单纯形的顶点。

凸集与凸函数的性质与应用凸集与凸函数是数学中两个非常重要的概念，它们在各个领域都有广泛的应用。

本文将围绕凸集与凸函数的性质展开讨论，并探讨它们在实际问题中的应用。

一、凸集的定义及性质1. 凸集的定义在数学中，一个集合称为凸集，如果对于集合中的任意两点，连接这两点的线段上的所有点也在该集合内部。

2. 凸集的性质（1）凸集的交集仍然是凸集。

即若集合A和集合B都是凸集，则它们的交集A∩B也是凸集。

（2）凸集的闭包仍然是凸集。

即若集合A是凸集，则它的闭包A 也是凸集。

（3）凸集的仿射变换仍然是凸集。

即若集合A是凸集，线性变换T将A的元素变换到B，B上的任意两点通过T来自A的元素，B也是凸集。

二、凸函数的定义及性质1. 凸函数的定义在实数域上，如果一个函数的定义域是凸集，并且满足对于任意一对定义域内的点x₁和x₂以及任意的x∈ [0,1]，都有凸函数性质：x(xx₁+(1−x)x₂) ≤ xx(x₁)+(1−x)x(x₂)则该函数被称为凸函数。

2. 凸函数的性质（1）凸函数上的割线位于函数图像的下方或与之切线重合。

（2）凸函数的上、下半级集都是凸集。

即对于凸函数x(x)，有以下性质：- x∈ℝ且x∈ℝ，x(x) ≤ x≤ x(x) 成立，则对于该函数来说，有x(x) ≤ x，其中x∈ [x, x]。

- 若x(x) ≤ x，则x(x) ≤ x，其中x∈ℝ。

三、凸集与凸函数的应用1. 最优化问题凸集与凸函数在最优化问题中有着广泛的应用。

凸函数的性质保证了在一定条件下的最优解存在且唯一。

在优化问题中，我们可以将目标函数设为凸函数，将约束条件设为凸集，从而利用凸函数的性质来求解最优解，简化了问题的求解过程。

2. 经济学凸集与凸函数在经济学中也有重要的应用。

例如，生产函数、效用函数等都是凸函数，它们描述了在一定约束下的最优决策。

同时，凸集与凸函数也被应用在市场均衡理论、优化分配问题等经济学中的重要概念和工具中。

3. 机器学习凸集与凸函数在机器学习中也占据重要地位。