当前位置：文档之家 › 第二节+凸函数和凸规划

第二节+凸函数和凸规划

  • 格式：ppt
  • 大小：531.50 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

最优化方法(凸集与凸函数)

最优化方法(凸集与凸函数)
i =1 i =1
m
m
原来凸集的性质告诉我们： 任意的两个点的凸组合都属于 D。 原来凸集的性质告诉我们： 任意的两个点的凸组合都属于 。 现在让我们证明 们证明， 现在让我们证明，任意的 m 个点的凸组合都属于 D。 。 咋办？？ 咋办？？
两个―――多个 两个―――多个 ――― 两个―――三个―――四个―――多个 两个―――三个―――四个―――多个 ―――三个―――四个―――
=
(i = 1 , 2 ,⋯, k ) 的凸组合。 的凸组合。
（2）凸集：设集合 X ⊂ R n ，如果 X 中任意两点的凸组合 ）凸集： 仍然属于 X ，则称 X 为凸集。 2.凸函数 凸函数 2 1 2 n 设 f : X ⊂ R → R ，任取 x , x ∈ X ，如果∀a1 , a2 ≥ 0 , i∑1ai = 1 ， 任取 如果 = 上的（ 有 f (a1 x 1 + a2 x 2 )(< ) ≤ a1 f ( x 1 ) + a2 f ( x 2 ) ，则称 f 为X上的（严格） 则称 上的 严格） 凸函数。 凸函数。
~ x+x 凸集， 由于 D 是凸集，故有 ∈ D ，又因为 γ 是集合 D 到 y 的 2
最短距离，上式应有等号成立，因此，存在实数 最短距离，上式应有等号成立，因此，存在实数 α 距离 应有等号成立 ~ y − x = α(y − x)
12
是凸集， 设 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 的最短距离点的充分必要条件为

凸函数与凸规划

凸函数与凸规划
特别，取每个 i 1 n , 有
(
xn x1 xn x1 ) , x1 , , xn 0. n n
推论 3 虽然凸函数除了至多可数个点以外，处处可导，但它的导数却可以在一个处处
稠密集上不存在. 例如，设 {rn } 为 R 上有理数的全体， n 0, n 1,2, ,
可能的. 令 :
1 , 由上面的分离不等式得到 2
y f ( x0 ) ( x x0 ), ( x, y ) (epi f ) i .
令 y f ( x) 得到 f ( x) f ( x0 ) ( x x0 ), x (a, b).
f ( x2 ) f ( x1 ) sup f ( x2 ). x2 x1 x( x1 , x2 )
定理 2.1.4 f 是 (a, b) 上的凸函数的充要条件为 f 在 (a, b) 处处左、右可导，且满足
, x2 ( x1 , x2 ), x1 , x2 x1
epi f （ epi f 定义式中“ ”取到“ ”）. 因此， [0,1],
((1 ) x1 x2 , (1 ) f ( x1 ) f ( x2 )) (1 ) ( x1 , f ( x1 )) ( x2 , f ( x2 )) epi f .
~ f ( x0 ) f ( x0 ) ( x x0 ) f ( x) f ( x0 ) ( x x0 ) 2 o([ x x0 [ 2 ). 1! 2!
于是，也可以说，凸函数几乎处处有上式意义下的“二阶导数” f ( x0 ). 在这一节的最后，我们将函数的凸性与图像空间的凸集联系起来. 设 f : (a, b) R, 称图像空间 R 中的集合

凸函数凸规划

凸函数凸规划

凸函数
下面的图形给出了凸函数f x, y x4 3x2 y4
y2 xy的等值线的图形，可以看出水平集是凸集.
凸函数
凸函数
凸函数的判别定理
定理1:设 f x是定义在凸集 D Rn 上，x, y D ,
令 t f tx 1 t y, t 0,1, 则:
i1
i1
凸函数
性质
定理2.3.2
f1 , f2 ,..., fk 是凸集S上的凸函数, 则
k
(x) ifi (x),i 0(i 1,2,..., k) i 1
和
(x) max 1 i k
fi ( x)
都是S上的凸函数.
凸函数
水平集(Level Set)
凸函数
凸函数(Convex Function) ----定义2.3.1
设 D Rn 是非空凸集， f x: S R,
若对任意的 x, y D ,及任意的 0,1
都有：f x 1 y f x 1 f y 则称函数 f x 为 D 上的凸函数．
(1) f x是凸集 D上的凸函数的充要条件是对 任意的x, y D ,一元函数t为 0,1上的凸函数.
(2)设 x, y D , x y,若 t 在 0,1 上为严格
凸函数，则f x在 D上为严格凸函数．
凸函数
该定理的几何意义是：凸函数上任意两点之 间的部分是一段向下凸的弧．
故, cT x 是凸函数． 类似可以证明 cT x 是凹函数．
凸函数
性质
定理2.3.1
设 f x是凸集D Rn上的凸函数，
x1 , x2 ,..., xk S , i 0(i 1,2,..., k ),

凸集与凸函数ppt课件

凸集与凸函数ppt课件
3
2. 凸集与凸函数
Th2.2 给定向量p(≠0)∈Rn, ∈R,则
H {x ¡ n | pT x } (2.1)
是Rn中的一个超平面.反之,Rn任一超平面都可表成 上式的形式,且在相差一个非零常数的意义下, (p, )是唯一的. Th2.3 给定矩阵A mn ,向量b n ,则
M {x ¡ n | Ax b}(简记为Ax b) (2.2) 是 n中的一仿射集.反之, n中的每一仿射集 都可表成(2.2)式的形式,即一组超平面的交集.
17
2. 凸集与凸函数
Df 2.12，设S( ) n, p n，p 0, x S 若S H {x pT (x x ) 0}或者S H － {x pT (x x ) 0}
则称H {x pT (x x )＝0}是S在x处的支撑超平面，若S H ,
则称H为S在x处的正常支撑超平面。
11
2. 凸集与凸函数
m
Df 2.8 给定m个向量, x1,..., xm ¡ n,以及满足 i 1的 i1
非负实数i R,i 1,..,m,称向量
1x1 ... mxm为{x1,..., xm}的凸组合.
Th2.4 集合S ¡ n是凸集,当且仅当S包含其中任意有限个
元素的凸组合,即对m
于是,由下确界定义知,存在序列{x(k)}, x(k) S, 使得 y x(k) r.
先证{x(k)}存在极限x S.只须证{x(k)}为柯西数列。
x(k) x(m)
2
(x(k) y) (x(m) y) 2
2
x(k) y
2
2
x(m) y
2
(x(k) y) (x(m) y)
2
19
多面体(polyhedral set)是有限闭半空间的交. (可表为 Axb ). x1

1-2凸集与凸函数

1-2凸集与凸函数
(2) 设 D R n 为 凸集 f ( x ) 为 D 上 的 严格 凸函数 且 凸 规划 凸集, 严格凸函数 凸函数,且 全局极小点 极小点存在 全局极小点 唯一的 极小点是 问题 min f ( x ) 的全局极小点存在,则全局极小点是唯一的.
x∈D
2010-8-21
21
(2) 设 x , y ∈ D, x ≠ y , 若 ( t ) 在 [ 0,1] 上 为 严 格 凸 函 数 , 则
f ( x ) 在 D 上为严格凸函数. 严格凸函数
2010-8-21
16
该定理的几何意义是： 该定理的几何意义是：凸函数上任意两点 间的部分是一段向下凸的弧. 之间的部分是一段向下凸的弧
则称 f ( x ) 为凸集 D 上的凸函数 。 上的凸函数 凸函数。
定义1.5 严格凸函数 定义
定义中 不等式反向 可以得到 函数的定义。 反向,可以得到凹 注:将上述定义中的不等式反向 可以得到凹函数的定义。 将上述定义
严格凸 例 : 设 f ( x ) = ( x 1) ,试 证明 f ( x ) 在 ( ∞ , +∞ ) 上 是 严格 凸 试
§1.2 凸集与凸函数
2010-8-21
1
一、凸集
定义1.1 定义1.1 设集合 D Rn , 若对于任意两点
x , y ∈ D, 及实数 λ ( 0 ≤ λ ≤ 1) , 都有： 都有：
λx + (1 λ) y ∈ D
凸集． 则称集合 D 为凸集． 注：常见的凸集：空集，整个欧氏空间 Rn 常见的凸集：空集， 常见的凸集 超平面： 超平面： = {x ∈Rn a1x1 + a2 x2 +L+ an xn = b} H
为凸集, 上的凸函数,则称规划 定义 1.6: 设 D R n 为凸集 f ( x ) 为 D 上的凸函数 则称规划 为凸规划问题. 问题 min f ( x ) 为凸规划问题

凸集凸函数凸规划

凸集凸函数凸规划

凸集-----性质
k
推论：设Di , i 1,2,, k是凸集，则 i Di i 1 也是凸集，其中i 是实数．
(4) S 是凸集当且仅当S中任意有限个点的凸 组合仍然在S中.
凸集-----性质
注： 和集和并集有很大的区别，凸集的并集
未必是凸集，而凸集的和集是凸集．
例：D1 x,0T x R 表示 x 轴上的点． D2 0, yT y R 表示 y 轴上的点．
x 1 y D,
则称集合 D 为凸集．
常见的凸集：单点集 { x }，空集 ，整个欧氏空间 Rn，
超平面：H x Rn a1 x1 a2 x2 an xn b ,
H
半空间：
x Rn a1x1 a2 x2
= x Rn aT x b
则 D1 D2 表示两个轴的所有点，它不是凸集；
而 D1 D2 R2 凸集．
凸集-----凸包(Convex Hull)
定义 设 S Rn , S 中任意有限个点的所有凸 组合所构成的集合称为S的凸包，记为H(S),即
m
m

H(S) i xi xi S, i 0, i 1,2...,m, i 1, m N
注：将上述定义中的不等式反向，可以得到 凹函数的定义．
凸函数
严格凸函数
设 D Rn 是非空凸集， f x: S R,
若对任意的 x, y D (x y),及任意的 0,1
都有：f x 1 y f x 1 f y
则称函数 f x 为 D 上的严格凸函数．
i 1
i 1
凸组合 (Convex Comb, xi Rn , i 1,2,...m且 i 1.

02凸优化理论与应用_凸函数


6
下水平集(sublevel set)

定义：集合
C { x dom f | f ( x ) }
称为 f 的 下水平集。

定理：凸函数的任一下水平集均为凸集。 任一下水平集均为凸集的函数不一定为凸函数。

信息与通信工程学院 庄伯金 bjzhuang@
7
函数上半图(epigraph)

定义：集合
epi f {( x , t ) | x dom f , f ( x ) t }
称为函数

f
的上半图。
f
定理：函数
为凸函数当且仅当
f
的上半图为凸集。
信息与通信工程学院 庄伯金 bjzhuang@
8
Jensen不等式

f
为凸函数，则有：
yC

凸函数的透视算子
g ( x , t ) tf ( x / t )
信息与通信工程学院 庄伯金 bjzhuang@
11
共轭函数(conjugate function)

定义：设函数 f : R 定义为
*
n
R
，其共轭函数 f : R
T
*
n
R
，
f ( y ) su p ( y x f ( x )).
n
为真锥，函数 f : R
n
R
称为 K 单调增，若函数 f ( x ) 满足：
x K y f (x) f ( y)

广义凸函数的定义：设K R 均有
m
为真锥，函数 f : R
n
R
m
称为 K 凸，若函数 f ( x ) 满足对 x , y dom f , 0 1

第二节 凸函数和凸规划


∂f ( x 1 ) ∂f ( x 1 ) T ,...., ) 是函数 f 在点 x 1 处的一 其中 ∇f ( x ) = ( ∂x 1 ∂x n 阶 导数或梯度。 导数或梯度。 （2） f 是 S 上的严格凸函数的充要条件是 ∇f ( x 1 ) T ( x 2 − x 1 ) < f ( x 2 ) − f ( x 1 ) ， ∀ x1 , x 2 ∈ S, x1 ≠ x 2
是非空凸集， 是凸函数， 定理 4.2.2 设 S ⊂ Rn 是非空凸集， f : Rn ֏ R 是凸函数， c ∈ R ，则集 合 H S ( f , c) = {x ∈ S f ( x) ≤ c} 是凸集。 是凸集。
注：一般来说上述定理的逆是不成立的。
1. 凸函数及其性质续二
是非空开凸集， 可微， 定理 4.2.3 设 S ⊂ R n 是非空开凸集， f : S ֏ R 可微，则 （1） f 是 S 上的凸函数的充要条件是 ∇f ( x 1 )T ( x 2 − x 1 ) ≤ f ( x 2 ) − f ( x 1 ) ， ∀ x 1 , x 2 ∈ S
上的凸函数 凸函数， 上是凸 则称 f 是 S 上的凸函数，或 f 在 S 上是凸的。如果对于任意的 α ∈ (0,1) 有
f (αx 1 + (1 − α ) x 2 ) < αf ( x 1 ) + (1 − α ) f ( x 2 ) ， x 1 ≠ x 2
上是严格凸的 则称 f 是 S 上的严格凸函数，或 f 在 S 上是严格凸的。 上的严格凸函数， 严格凸函数 严格凸
1
证明
1. 凸函数及其性质续三
是非空开凸集， 二阶连续可导， 定理 4.2.4 设 S ⊂ R n 是非空开凸集， f : S ֏ R 二阶连续可导，则 f 是 S 上的凸函数的充要条件是 f 的 Hesse 矩阵 ∇ 2 f ( x ) 在 S 上是半正定 的。 上是正定矩阵时， 上的严格凸函数。（注意： 。（注意 当 ∇ 2 f ( x ) 在 S 上是正定矩阵时，f 是 S 上的严格凸函数。（注意：该 逆命题不成立。） 逆命题不成立。） ∂ 2 f ( x) ∂ 2 f ( x) ∂ 2 f ( x) .... 2 ∂x 1 ∂x 1 ∂x 2 ∂x 1 ∂x n 2 2 ∂ 2 f ( x) ∂ f ( x) ∂ f ( x) ... 2 ∂x ∂x ∂x 2 ∂x 2 ∂x n 2 2 1 ∇ f ( x) = . . . . 2 ∂ f ( x) ∂ 2 f ( x) ∂ 2 f ( x) 2 ∂ x n ∂x 1 ∂ x n ∂ x 2 ∂x n

数学中的凸优化与凸分析

数学中的凸优化与凸分析凸优化和凸分析是数学中重要的分支领域，它们在诸多应用领域都有着广泛的应用。

本文将介绍凸优化和凸分析的基本概念、性质以及它们在实际问题中的应用。

一、凸集与凸函数在进一步探讨凸优化和凸分析之前，我们先来了解一些基本概念。

首先是凸集和凸函数。

1. 凸集凸集是指集合中任意两点的连线上的点都属于该集合。

具体地，对于任意$x, y$属于集合$C$和$0\leq\lambda\leq 1$，满足$\lambda x+(1-\lambda)y$也属于$C$，则$C$是一个凸集。

2. 凸函数凸函数是定义在凸集上的实值函数，满足对于集合内的任意$x,y$和$0\leq\lambda\leq 1$，有$f(\lambda x+(1-\lambda)y)\leq \lambdaf(x)+(1-\lambda)f(y)$。

简单来说，凸函数的任意两点的连线上的函数值都不超过连线两端的函数值。

二、凸优化凸优化是指优化问题的目标函数是凸函数，约束条件是凸集的优化问题。

凸优化问题有着许多重要的性质和算法。

1. 凸优化问题的一般形式凸优化问题的一般形式可以表示为：$$\begin{align*}\text{minimize}\quad &f(x)\\\text{subject to}\quad &x\in C\end{align*}$$其中，$f(x)$是凸函数，$C$是凸集。

2. 凸优化问题的性质凸优化问题具有以下性质：（1）全局最优解是局部最优解。

这意味着在凸优化问题中，存在一个全局最优解，同时该最优解也是局部最优解。

（2）凸优化问题无局部最优解和全局最优解之间的鞍点。

凸优化问题不存在鞍点，因此可以通过寻找局部最优解来获得全局最优解。

3. 典型凸优化问题凸优化问题在实践中有着广泛的应用，以下是一些典型的凸优化问题：（1）线性规划问题（Linear Programming，简称LP）$$\begin{align*}\text{minimize}\quad &c^Tx\\\text{subject to}\quad &Ax\leq b\\&x\geq 0\end{align*}$$（2）二次规划问题（Quadratic Programming，简称QP）$$\begin{align*}\text{minimize}\quad &\frac{1}{2}x^TPx+q^Tx+r\\\text{subject to}\quad &Gx\leq h\\&Ax=b\end{align*}$$（3）半正定规划问题（Semidefinite Programming，简称SDP）$$\begin{align*}\text{minimize}\quad &\langle C,X\rangle\\\text{subject to}\quad &\langle A_i,X\rangle=b_i,\quad i=1,\ldots,m\\&X\succeq 0\end{align*}$$三、凸分析凸分析是研究凸集和凸函数性质的数学分支，它主要研究凸集的性质以及凸函数的导数和二阶导数。

§4.2 凸函数和凸规划

§4.2 凸函数和凸规划1、凸函数及其性质定义 4.2.1 设n R S ⊂是非空凸集，R S f α:，如果对任意的)1,0(∈α有)()1()())1((2121x f x f x x f αααα-+≤-+，S x x ∈∀21, 则称f 是 S 上的凸函数，或 f 在 S 上是凸的。

如果对于任意的)1,0(∈α有)()1()())1((2121x f x f x x f αααα-+<-+，21x x ≠ 则称f 是S 上的严格凸函数，或f 在S 上是严格凸的。

若 f -是S 上的（严格）凸函数，则称f 是S 上的（严格）凹函数，或f 在S 上是（严格）凹的。

例 4.2.1 线性函数既是凸函数，又是凹函数定理 4.2.1 设n R S ⊂是非空凸集。

（1）若R R f n α:是S 上的凸函数，0≥α，则f α是S 上的凸函数；（2）若R R f f n α:,21都是S 上的凸函数，则21f f +是S 上的凸函数。

定理 4.2.2 设n R S ⊂是非空凸集，R R f n α:是凸函数，R c ∈，则集合}{c x f S x c f H S ≤∈=)(),(是凸集。

（称集合),(c f H S 为函数 f 在集合 S 上关于数 c 的水平集）证：任取),,(,21c f H x x S ∈ 则有S x S x ∈∈21,以及c x f c x f ≤≤)(,)(21因为S 是凸集，所以对于任意的)1,0(∈α有S x x ∈-+21)1(αα又因为f 是S 上的凸函数，因此有c c c x f x f x x f =-+≤-+≤-+)1()()1()())1((2121αααααα所以 ),()1(21c f H x x S ∈-+αα。

因此 ),(c f H S 是凸集。

定理 4.2.3 设n R S ⊂是非空开凸集，R S f α:可微，则（1）f 是S 上的凸函数的充要条件是)()()()(12121x f x f x x x f T -≤-∇， S x x ∈∀21, 其中T n x x f x x f x f ))(,....,)(()(1111∂∂∂∂=∇是函数f 在点1x 处的一阶导数或梯度。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

x ( 2)
f ( x 2 ) > f ( x1 ) + f '( x1 )( x 2 − x1 )
y = f ( x ) + f ' ( x )( x − x )
1 1 2 1
f ( x2 )
x (1) x ( 2)
凸函数的定义表明， 凸函数的定义表明，凸函数上任意两点的函数值的 连线上的点都在曲线的上方； 连线上的点都在曲线的上方；而上述充要条件则说 函数图像上任一点处的切线都在曲线的下方。 明，函数图像上任一点处的切线都在曲线的下方。
书例4.2.2 书例
2. 凸规划及其性质
min f ( x ) s .t . g i ( x ) ≤ 0, i = 1,..., p h j ( x ) = 0, j = 1,...q
g ( x) ≤ 0, i = 1,...,p n i X = x ∈ R hj ( x) = 0, j = 1,...,q
是非空凸集。 定理 4.2.1 设 S ⊂ R 是非空凸集。 n 上的凸函数， （1） 若 f : R a R 是 S 上的凸函数， α ≥ 0 ，则 α f 是 S 上的凸函数； 上的凸函数； n （2） 若 f1 , f 2 : R a R 都是 S 上的凸函数， 上的凸函数， 上的凸函数。 则 f1 + f 2 是 S 上的凸函数。
第二节 凸函数和凸规划
对于定义在凸集上的凸函数，其极小点就是最小点， 对于定义在凸集上的凸函数，其极小点就是最小点， 极小值就是最小值。 极小值就是最小值。
• 凸函数及其性质 • 凸规划及其性质
称为凸集， 集合 S 称为凸集，如果 S 中任两点的连线内的 点都在集合 S 内。
X2
x1
证明一集合是否为凸集的方法为，假设 证明一集合是否为凸集的方法为，假设X1,X2在此集 合中，则有任意a(0<a<1)使得 1+(1-a)X2属于该集合 使得aX 属于该集合. 合中，则有任意 使得
充分小， 取α>0充分小，有 充分小
α x + (1 − α ) x* ≈ x* ∈ X I N δ ( x*),
1 （）
⇒ f ( x*) ≤ f (α x + (1 − α ) x*)，与（2）矛盾
p112例 4.2.3 验证下列（MP）是凸规划 验证下列（MP）
2 2 min f ( x1, x2 , x3 ) = 2x12 + x2 + 2x3 + x1x3 − x1x2 + x1 + 2x2 2 s.t. g1 ( x) = x12 + x2 − x3 ≤ 0 g2 ( x) = x1 + x2 + 2x3 ≤ 16 g3 ( x) = − x1 − x2 + x3 ≤ 0
⇒ f ( x 2 ) > f ( x1 ) + ∇f ( x1 )T ( x 2 − x1 )
∀ x1 , x 2 ∈ S, x1 ≠ x 2
f (x)
αf ( x (1) ) + (1 − α ) f ( x ( 2) )
f (αx (1) + (1 − α ) x ( 2) )
o x (1)
2 min f ( X ) = x12 + x2 − 4 x1 + 4 g1 ( X ) = − x1 + x2 − 2 ≤ 0 g2 ( X ) = + x12 − x2 + 1 ≤ 0 x , x ≥ 0 1 2
1．建立M文件 ．建立 文件 文件mycon1.m定义非线性约束： 定义非线性约束： 定义非线性约束 function [g,ceq]=mycon1(x) g=[-x(1)+x(2)-2;x(1)^2-x(2)+1]; ceq=[]; 2．输入: ．输入 clear
是非空开凸集， 二阶连续可微 定理 4.2.4 设 S ⊂ R n 是非空开凸集， f : S a R 二阶连续可微，则 f 是 S 上的凸函数的充要条件是 f 的 Hesse 矩阵 ∇ 2 f ( x ) 在 S 上是半正定 的。 上是正定矩阵时， 上的严格凸函数。（注意： 。（注意 当 ∇ 2 f ( x ) 在 S 上是正定矩阵时，f 是 S 上的严格凸函数。（注意：该 逆命题不成立。） 逆命题不成立。） ∂ 2 f ( x) ∂ 2 f ( x) ∂ 2 f ( x) .... 2 ∂x1 ∂x1 ∂x 2 ∂x1 ∂x n 2 2 ∂ 2 f ( x ) 注：线性函 ∂ f ( x) ∂ f ( x) ... 2 ∂x ∂x ∂x 2 ∂x 2 ∂x n 数是凸函数 2 ∇ f ( x) = 2 1 . . . . 2 ∂ f ( x) ∂ 2 f ( x) ∂ 2 f ( x) 2 ∂x n ∂x1 ∂x n ∂x 2 ∂x n
如图所示，该问题最优解（最小点） 如图所示，该问题最优解（最小点）在x*点取得 点取得 。
= (0.58 1.34)
T
f ( X * ) = 3.8
g2 ( X ) = 0
x2
2 1
g1( X ) = 0
x *(0.58, 1.34)
•
f ( X *) = 3.8
1 2
4
−2 o
x1
2 2 min f ( X ) = x12 + x2 − 4 x1 + 4 = ( x1 − 2) 2 + x2 g1 ( X ) = − x1 + x2 − 2 ≤ 0 g2 ( X ) = + x12 − x2 + 1 ≤ 0 x , x ≥ 0 1 2
1 2 1 2 1 2
Q S 是凸集， α ∈ 0,1)，有ax 1 + (1 - a)x 2 ∈ S, ∴∀ （ ⇒ 而 f 是 S上 的 是 凸 函 ， f (α x1 + (1 − α ) x 2 ) ≤ α f (x1 ) + (1 − α ) f ( x 2 ) ≤ α c + (1 − α )c = c, ⇒ α x + (1 − α ) x ∈ H S ( f , c )
f ( x*) ≤ f ( x )， ∀x ∈ X I N δ ( x*)
如果x*不是整体最优解，则 ∃ x ∈ X，使 如果 不是整体最优解， 不是整体最优解
1 （）
f ( x*) ≥ f ( x )，
又因为f是凸函数， 又因为 是凸函数，所以 是凸函数
f (α x + (1 − α ) x*) ≤ α f (x ) + (1 − α ) f ( x*) < α f ( x*) + (1 − α ) f ( x*) = f ( x*) （2 ）
上的凸函数， 皆为线性函数， 皆为 R n 上的凸函数， h j ( x ), j = 1,..., q 皆为线性函数， 上的凸函数， (MP)是凸规划 是凸规划。 并且 f 是 X 上的凸函数，则(MP)是凸规划。
定理 4.2.6 体最优解。 体最优解。
凸规划的任一局部最优解都是它的整
证明： x*是凸规划的一个局部解， 证明：设x*是凸规划的一个局部解，则存在δ>0,使 是凸规划的一个局部解 使
∂ 2 g2 ∂ 2 g2 ∂x1∂x2 ∂x12 2 0 半正定， 2 ∇ g2 ( X ) = = . 半正定， ∂2 g 0 0 凸函数 ∂ 2 g2 2 2 ∂x2 ∂x2 ∂x1
所以，该问题为凸规划。
* * X * = ( x1 x2 )T
g1 ( X ) , g 2 ( X )
∂ 2 g1 ∂ 2 g1 ∂x12 ∂x1∂x2 0 0 2 ∇ g1 ( X ) = = , 2 2 ∂ g ∂ g1 0 0 1 2 ∂x2 ∂x1 ∂x2
半正定， 半正定， 凸函数
1. 凸函数及其性质
是非空凸集， 定义 4.2.1 设 S ⊂ Rn 是非空凸集， f : S a R ，如果对任意的 α ∈(0,1) 有
f (αx1 + (1 − α)x2 ) ≤ αf ( x1 ) + (1 −α) f ( x2 ) ， ∀x1 , x2 ∈ S
上的凸函数 凸函数， 则称 f 是 S 上的凸函数，或 f 在 S 上是凸的。如果对于任意的 α ∈(0,1) 有
n
定理 4.2.2 设 S ⊂ R c ∈ R ，则集合
n
f : R n a R 是凸函数， 是非空凸集， 是凸函数， 是非空凸集，
H S ( f , c ) = {x ∈ S f ( x ) ≤ c}
是凸集。 的水平集） 是凸集。（f 在 S 上关于数 c 的水平集）
证明： 证明
∀x , x ∈ H S ( f , c ), 有f x ) ≤ c, f ( x ) ≤ c, 且x , x ∈ S， (
(a) 凸函数
(b)凹函数 (b)凹函数
f(X) f(X2)
f(X1)
X1
X2
X
f(X) f(X2)
+(1f(αx1+(1-α)x2 ) f(X1)
X1
αx1+(1-α)x2 +(1-
X2
X
f(X) αf( x1 ) +(1- α) f( x2) +(1f(X2)
f(αx1+(1-α)x2 ) +(1-
f(X1)
X1
αx1+(1-α)x2 +(1-
X2
X
f(X) 任意两点的函数值的连线上的点都在曲线的上方 αf( x1 ) +(1- α) f( x2) +(1f(X2)