Convex Set and Convex Function凸集与凸函数

Welcome To My Blog
Rockafeller说:”优化问题的分水岭不是线性和非线性,而是凸性和非凸性”

两点连线上的点

在介绍凸集和凸函数之前,先来看一个与之有关的基本问题:
如下图,已知空间中有B,C两点,在给定两点坐标的情况下如何量化B,C连线上的任意一点D?

很简单,看下图,设已知A,B,C,D的坐标,
AD = AB + BD
= AB + kBC (D在BC上,所以k∈[0,1])
= AB + k(AC - AB)
= kAC + (1-k)AB
(以上均为向量运算)

所以,已知空间中有两点X,Y,那么线段XY上的任意一点可以表示为kX + (1-k)Y,其中k∈[0,1]

凸集

定义

若集合S⊆Rⁿ满足
αx + (1 - α)y ∈ S, ∀x,y ∈ S, ∀α ∈ [0,1]
则称S是Rⁿ中的凸集.
(当α没有限制时,α为直线xy上的任意点,此时S是仿射集)

几何解释

从几何的角度可以这么理解,如果凸集S包含x,y两点,那么线段xy都在S中,如下图
左边的椭圆是凸集,右边的四角星不是凸集

凸函数

定义

凸函数

设S⊆Rⁿ是凸集. 若函数f : Rⁿ → Rⁿ满足
f[αx + (1-α)y] ≤ αf(x) + (1-α)f(y), ∀x,y ∈ S, ∀α ∈[0,1]
则称f是S上的凸函数

严格凸函数

接凸函数,若不等式
f[αx + (1-α)y] ≤ αf(x) + (1-α)f(y), ∀x,y ∈ S, ∀α ∈[0,1]
对所有 x≠ y和 α∈(0,1)成立,则称f是S上的严格凸函数

一致凸函数(强凸函数)

接凸函数,若存在常熟 m>0, 使不等式
f[αx + (1-α)y] ≤ αf(x) + (1-α)f(y) - mα(1-α)||x-y||² 对所有x,y∈S以及所有α∈[0,1]成立,则称f是S上的一致凸函数(强凸函数)

几何解释

1. 任意一点的切线都在图像下方(图像像个碗)
2. 任意两点确定的弦在其图像上方
   其实,横坐标为αx + (1-α)y时,对应弦AB上点的纵坐标就是αf(x) + (1-α)f(y)
   

Welcome To My Blog