运筹学与最优化方法-第2章
定理1 S是凸集S中任意有限点的凸组合属于S。 (1) (2) (m ) (1) (2) 多胞形 H(x , x , … , x ):由 x , x , … , (m ) x 的所有凸组合构成。 (1) (2) (m) 单纯形:若多胞形 H(x , x , … , x )满足, (2) (1) (3) (1) (m ) (1) x - x , x - x , … , x - x 线性无关。
注: f 在 S 上不一定连续。 例如 : f(x)=2(当x=1); f(x)=x2 (当x<1) 。
n
3)设f 凸,则对任意方向的方向导数存在(前提首 先要是“可行方向”)。 4)设 S 是开集,f 在 S 上可微,则f凸 x*S,有
f (x) ≥ f (x*)+ f T(x*)(x-x*) , x S。
2.2 凸集、凸函数和凸规划
定义4 设集合 S R ,函数 f :SR, R ,
称 S = { x S∣f (x) ≤ } 为 f (x) 在 S 上 的 水平集。 n 定理3 设集合 S R 是凸集,函数 f :SR是 凸函数,则对 R ,S 是凸集。
n
2.2凸集、凸函数和凸规划
凸集
非凸集
非凸集
2.2凸集、凸函数和凸规划
例1 证明集合 S = { x∣Ax = b } 是凸集。 其中,A为 mn矩阵,b为m维向量。 (1) (2) (m) n 凸组合:设 x , x , … , x R , j≥ 0
m m (j) (1) (2) (m)
例
题
类似可得到极点 x(2) = (5, 25, 0, 5, 0 )T (对应B2) x(7) = (20, 0, 5, 0, 75 )T (对应B5) x(8) = (0, 25, 15, 15, 0 )T (对应B7) x(9) = (0, 0, 65, 40, 75 )T (对应B10) 而 x(3)= (0, 32.5, 0, 7.5, - 22.5 )T(对应B9) x(4)= (65/3, 0, 0, - 10/3, 75 )T (对应B6) x(5 )= (7.5, 25, - 7.5, 0, 0 )T (对应B1) x(6) = (0, 40, - 15, 0, - 45 )T (对应B8) 不是极点。
S中必存在有限多个极方向 ( ≤
m (n-m)Cn
)。
例2 考虑多面体S = 中 3 2 1 A = 2 1 0 0 3 0
{ xR Ax = b , x≥0 },其
0 0 1 0 0 1 65 b = 40 75
例
n
题
即
3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 ≥ 0
n
则称 f (x) 为在点x*沿方向d的方向导数存在,记 f ′ (x*;d) = lim [ f (x*+ d ) - f (x*) ] /
•
若 f (x) 在 x* 可导,则 f ′ (x*;d) = [f (x*) ] d 。
T
2.2 凸集、凸函数和凸规划
以下设 S R 为非空凸集,函数 f :SR 2)若f 凸,则 f 在 S 的内点集上连续。
5) 设 S 是开集,f 在 S 上二次可微,则
①f 凸 xS,2f (x) 半正定; ②若 xS,2f (x) 正定,则f严格凸。
2.2 凸集、凸函数和凸规划
1) 2) 3)
例: f (x)=x12+2x1x2+2x22+10x1 - 4 f (x)= - 3x12+x1x2 - x22 - 2x32 -2x2x3+26 f (x)=3x12+ax1x2+2x22-4x1+6 ( a=5, 4.5 )
2.3 多面体、极点、极方向
定理5(极点特征)设 A 满秩,x 是 S 极 点的充分必要条件是: 存在分解 A = (B , N ),其中B为 m阶非奇异矩阵,使 xT = ( xBT, xNT ), 这里 xB = B-1b≥0, xN =0。
S中必存在有限多个极点
( ≤ Cn ) 。
m
2.3 多面体、极点、极方向
严格凹函数 严格凸函数 凸函数
2.2 凸集、凸函数和凸规划
定理2 f (x) 为凸集 S 上的凸函数 S 上任 意有限点的凸组合的函数值不大于各点函 数值的凸组合。 思考:设f1, f2是凸函数。 1) 设1, 2 > 0, 1f1+2f2 , 1f1 -2f2是否凸函 数?(都是) 2)f (x)= max{ f1(x) , f2 (x) } , g(x)= min{ f1(x) , f2 (x) }是否凸函数? (不一定)
,
= 1 , 那么称 x 为 x , x , … , x 的 j j j =1 j=1 凸组合。 • 比较: z = j x j =1
m (j)
jR ——构成线性组合 —— 线性子空间 j≥0 , j >0 —— 构成半正组合 —— 凸锥 j≥0 , j =1 —— 构成凸组合 —— 凸集
2.2 凸集、凸函数和凸规划
2.凸函数 (1)凸函数及水平集 n 定义3 设集合 S R 为凸集,函数 f :SR。若 x(1), x(2) S, ( 0 , 1 ) ,均有 f(x(1)+(1-) x(2) ) ≤f(x(1))+(1 - )f(x(2)) , 则称 f (x) 为凸集 S 上的凸函数。 若进一步有上面不等式以严格不等式成立,则 称 f(x) 为凸集 S 上的严格凸函数。(几何意义见P27) 当- f (x) 为凸函数(严格凸函数)时,则称 f (x) 为凹函数(严格凹函数)。
2.2 凸集、凸函数和凸规划
3.凸规划 当(f S)中,S为凸集,f是S上的凸函数 (求min)时,称(f S)为凸规划。 对于(fgh), 当f ,gi为凸函数,hj为线性函 数时,(fgh)为凸规划。 n 定理4 设集合 S R 为凸集,函数 f :SR 。 f(x) 为凸集 S 上的凸函数。x*为问题(fs)的 l.opt.,则x*为g.opt.;又如果f是严格凸函数, 那么x*是(fs)的唯一g.opt.。
严格l .opt .
严格g .opt .
l .opt .
2.1数学规划模型的一般形式
函数形式: f (x), gi(x) , hj(x) : RnR Min f (x) (fgh) s.t. gi(x) ≤ 0 , i = 1,2,…,m hj(x) = 0 , j = 1,2,…,l 矩阵形式: Min f (x) , f (x) : RnR (fgh) s.t. g(x) ≤ 0 , g(x) : RnRm h(x) = 0 , h(x) : RnRl
最优值:
2.1数学规划模型的一般形式
局部最优解: x*S, x* 的邻域 N(x*) ,使满足 f (x*)≤ f (x), x S N(x*) ,则称 x*为(f S)的局部 最优解,记 为l .opt.(local optimum) 。 在上述定义中,当x x* 时有严格不等式成立,则 分别称 x* 为(f S)的严格全局最优解和严格局部最 优解。
2.2凸集、凸函数和凸规划
多胞形
单纯形
单纯形
2.2凸集、凸函数和凸规划
(2)凸集的性质
1)
2)
3) 4)
凸集的交集是凸集;(并?) 凸集的内点集是凸集;(逆命题是否成立?) 凸集的闭包是凸集。 (逆命题是否成立?) 分离与支撑:凸集边界上任意点存在支 撑超平面;两个互相不交的凸集之间存基础
第2章 基本概念和理论基础
Min ( f S) s.t. 其中,S 最优解:
1.1数学规划模型的一般形式 f(x) ——目标函数 xS ——约束集合,可行集 n R ,f :S R,xS称(f S )的可行解 x*S,满足f (x*)≤ f (x), xS,则称 x*为(f S)的全局最优解(最优解),记为 g.opt.(global optimum),简记 为opt. 。 x*为(f S)的最优解, 则称 f * = f (x*) 为 (f S)的最优值(最优目标函数值) 。
例
题
其中B4= 0,因而B4不能构成极点和极方向。其余 均为非奇异方阵,因此该问题共有9个可构成极点、 极方向的子矩阵,我们称之为基。 对于基 B3=(p1 ,p2 ,p5),令x3 = 0, x4 = 0,在等 式约束中令x3 = 0,x4 = 0,解线性方程组 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15,x2 = 10,x5 = 45,对应的极点 x = (x1,x2,x3,x4,x5 )T = (15,10,0,0,45 )T
支撑
强分离
分离
非正常 分离
2.2 凸集、凸函数和凸规划
(3)凸锥
定义2 C R , 若 x C, > 0 ,有 x C, 则 称 C 是以 0 为顶点的锥。如果 C 还是凸集,则 称为凸锥。 n 集合 { 0 }、R 是凸锥。
n
0
命题:C是凸锥C中任意有限点的半正组合属于S 。
例
题
3 2 1 0 0 A = ( p1 , p2 , p 3 , p 4 , p 5 ) = 2 1 0 1 0 0 3 0 0 1 A矩阵包含以下10个3×3的子矩阵: B1=(p1,p2 ,p3) B2=(p1 ,p2 ,p4) B3=(p1 ,p2 ,p5) B4=(p1 ,p3 ,p4) B5=(p1 ,p3 ,p5 ) B6=(p1 ,p4 ,p5 ) B7=(p2 ,p3 ,p4) B8=(p2 ,p3 ,p5) B9=(p2 ,p4 ,p5) B10=(p3 ,p4 ,p5)