
- 凸优化教程
- 首页
- 简介
- 线性规划
- 范数
- 内积
- 极小值与极大值
- 凸集
- 仿射集
- 凸包
- Carathéodory定理
- Weierstrass定理
- 最近点定理
- 基本分离定理
- 凸锥
- 极锥
- 锥组合
- 多面体集
- 凸集的极点
- 方向
- 凸函数与凹函数
- Jensen不等式
- 可微凸函数
- 全局最优的充分条件与必要条件
- 拟凸函数与拟凹函数
- 可微拟凸函数
- 严格拟凸函数
- 强拟凸函数
- 伪凸函数
- 凸规划问题
- Fritz-John条件
- Karush-Kuhn-Tucker最优性必要条件
- 凸问题的算法
- 凸优化资源
- 凸优化 - 快速指南
- 凸优化 - 资源
- 凸优化 - 讨论
凸函数与凹函数
设f:S→R,其中S是Rn中的非空凸集,则如果对于所有λ∈(0,1),都有f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2),则称f(x)在S上是凸函数。
另一方面,设f:S→R,其中S是Rn中的非空凸集,则如果对于所有λ∈(0,1),都有f(λx1+(1−λ)x2)≥λf(x1)+(1−λ)f(x2),则称f(x)在S上是凹函数。
设f:S→R,其中S是Rn中的非空凸集,则如果对于所有λ∈(0,1),都有f(λx1+(1−λ)x2)<λf(x1)+(1−λ)f(x2),则称f(x)在S上是严格凸函数。
设f:S→R,其中S是Rn中的非空凸集,则如果对于所有λ∈(0,1),都有f(λx1+(1−λ)x2)>λf(x1)+(1−λ)f(x2),则称f(x)在S上是严格凹函数。
例子
线性函数既是凸函数又是凹函数。
f(x)=|x|是一个凸函数。
f(x)=1x是一个凸函数。
定理
设f1,f2,...,fk:Rn→R是凸函数。考虑函数f(x)=k∑j=1αjfj(x),其中αj>0,j=1,2,...k, 则f(x)是一个凸函数。
证明
因为f1,f2,...fk是凸函数
所以,对于所有λ∈(0,1)和i=1,2,....,k,都有fi(λx1+(1−λ)x2)≤λfi(x1)+(1−λ)fi(x2)。
考虑函数f(x)。
所以,
f(λx1+(1−λ)x2)
=k∑j=1αjfj(λx1+(1−λ)x2)≤k∑j=1αj[λfj(x1)+(1−λ)fj(x2)]
⇒f(λx1+(1−λ)x2)≤λ(k∑j=1αjfj(x1))+(1−λ)(k∑j=1αjfj(x2))
⇒f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)
因此,f(x)是一个凸函数。
定理
设f(x)是Rn中凸集S上的凸函数,则f(x)在S上的局部极小值是全局极小值。
证明
设ˆx是f(x)的局部极小值,且ˆx不是全局极小值。
因此,存在ˉx∈S使得f(ˉx)<f(ˆx)。
由于ˆx是局部极小值,存在邻域Nε(ˆx)使得对于所有x∈Nε(ˆx)∩S,都有f(ˆx)≤f(x)。
但f(x)是S上的凸函数,因此对于λ∈(0,1)
我们有f(λˆx+(1−λ)ˉx)≤λf(ˆx)+(1−λ)f(ˉx)
⇒f(λˆx+(1−λ)ˉx)<λf(ˆx)+(1−λ)f(ˆx)
⇒f(λˆx+(1−λ)ˉx)<f(ˆx),∀λ∈(0,1)
但是对于某个λ接近1但小于1,我们有
λˆx+(1−λ)ˉx∈Nε(ˆx)∩S且f(λˆx+(1−λ)ˉx)<f(ˆx)
这与假设矛盾。
因此,ˆx是全局极小值。
上图
设S是Rn中的非空子集,设f:S→R,则f的上图,记为epif或Ef,是Rn+1的一个子集,定义为Ef={(x,α):x∈S,α∈R,f(x)≤α}
下图
设S是Rn中的非空子集,设f:S→R,则f的下图,记为hypf或Hf,是Rn+1的一个子集,定义为Hf={(x,α):x∈S,α∈R,f(x)≥α}
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
定理
设S是Rn中的非空凸集,设f:S→R,则f是凸函数当且仅当其上图Ef是一个凸集。
证明
设f是一个凸函数。
要证明Ef是一个凸集。
设(x1,α1),(x2,α2)∈Ef,λ∈(0,1)
要证明λ(x1,α1)+(1−λ)(x2,α2)∈Ef
⇒[λx1+(1−λ)x2,λα1+(1−λ)α2]∈Ef
f(x1)≤α1,f(x2)≤α2
因此,f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)
⇒f(λx1+(1−λ)x2)≤λα1+(1−λ)α2
逆命题
设Ef是一个凸集。
要证明f是凸函数。
即,要证明如果x1,x2∈S,λ∈(0,1),
f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)
设x1,x2∈S,λ∈(0,1),f(x1),f(x2)∈R
由于Ef是一个凸集,(λx1+(1−λ)x2,λf(x1)+(1−λ)f(x2))∈Ef
因此,f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)