为凸集．
1,
0 证明： x , y 为超球中的任意两点， 设
则有：
x 1 y
r ???
x 1 y
r r r 1
即点 x 1 y 属于超球
所以超球为凸集．
注： 常见的凸集：空集，整个欧氏空间 超平面： H
T
aR
n
和实数
,
使得： T x a
a y , x D ,
xR a x
n T
即存在超平面 H y 与凸集 D .

严格分离点
注： 点与闭凸集的分离定理。
y.
D
定理
(点与凸集的分离定理)
是非空凸集，x D, 则存在 非零向量 a R n 使成立
DR
n
目标函数
R ( i 1, 2 , , p )
1
• 根据实际问题的不同要求，最优化模型有不同的形式， 但经过适当的变换都可以转换成上述一般形式.
最优化问题的分类
最优化问题
根据约束条件 分类
m in f ( x ), x R .
n
无约束最优化问题 约束最优化问题 等式约束最优化问题 不等式约束最优化问题 混合约束优化问题
设
a xa x
T T
x D . ( D代 表 D 的 闭 包 )
_ _
定理
(两个凸集的分离定理)
n
x
x
设 D1 , D2 是
且 R 的两个非空凸集， D1 D2 ,
则存在超平面分离 D1 和 D2 , 即存在非零向量 n a R 使得 aT x aT y , x D , y D . 1 2
f(x)
f ( x (1 ) y )
f(y)
x
y
例： 设 f x x 1 上是严格凸函数． 证明: 设
x, y R,
2
,
试证明 f x 在 ,
且x
y , 0,1 都有：
f x y f x f y 1 1
m in f ( x ), s.t. c i ( x ) 0, i 1, , m
m in f ( x ), s.t. c i ( x ) 0, i 1, , m
最优化问题的分类
最优化问题
连续最优化：决策变量取值连续
根据决策变 量的取值 光滑最优化：函数连续可微 线性规划 非线性最优化 非光滑最优化：有一个非光滑 离散最优化：决策变量取值离散
也是 D 上的凸函数.
n
f i ( x )( i 1, ..., m ) 是凸集 D R n (３) 设
f ( x ) m ax 1 i m f i ( x )
上的凸函数，
f i ( x )( i 1, ..., m )
m i i i 1
则 f (x)
是凸集 D R 上的凸函数， f ( x ) 也是 D 上的凸函数,其中 0. i
n
凸集的性质
(１) 有限个凸集的交集为凸集． (２) 设 (３) 设
D 是凸集，
是一实数， 则 是凸集. 的和(差)集
D y y x , x D
D1 , D2是凸集， 则 D1 , D2
D1 D2 y y x z , x D1 , z D2 是凸集.
f 都有： x 1 y f x 1 f y
则称函数 f x 为凸集 定义 严格凸函数
D 上的凸函数．
x y , ， (0,1)
注：将上述定义中的不等式反向，可以得到 凹函数的定义．
f ( x ) (1 ) f ( y )
例：二次函数 f ( x) G是正定矩阵. 证明：
f (x) 1 2
1 2
x Gx b x 是Rn上的严格凸函数当且仅当
T T
x Gx b x
T T
严格凸
x , y R , x y , 0 1,
n
都 有 f ( x (1 ) y ) f ( x ) (1 ) f ( y )
T证明: 设Fra bibliotekx, y R , [0,1], 则
n
f x 1 y c x 1 y
T
c x 1 c y f x 1 f y
T T
所以 c T x 是凸函数． 类似可以证明 c T x 是凹函数．
R
n
x R a1 x1 a2 x2 an xn b
n




H 开半空间： x R n
H 闭半空间： 0 x R
n
a1 x1 a2 x2 an xn b ( H )
a1 x1 a2 x2 an xn b ( H 0 )
凸函数的判定定理
闭包:D的闭包是所有包含D的闭凸集的交.
投影定理 设
DR
n
是非空闭凸集， y R
x D,
n
但 到点
y D,
则： 使得集合
inf
(１) 存在唯一的点
y
D
的距离最小， x y 即：
xD

x y , x D.
(２)
是点
y
到集合 D的最短距离点的
T
充要条件为：
x x x y 0
T
d bi 0, i 1, , l ',
T
d a0 0
T
无解当且仅当存在实数 i ( i 使得
l
1, , l ) 和 非 负 实 数 i ( i 1, , l ')
l'
a0
a b .
i i i i i 1 i 1
凸函数
定义 设函数 f x 定义在凸集 D R n 上， 若对任意的 x, y D , 及任意的 0,1
a21 x1 a22 x2 a2 n xn b2 am1 x1 am 2 x2 amn xn bm


D { x R | A x b , x 0}
n
是多面集吗？
yes
D { x R | A x b , x 0}
n
{ x R | A x b , x 0}
定义 可行域是凸集，目标函数是凸函数的最优 化问题称为凸规划问题 定理 设
x 是凸规划问题的一个局部最优解，则

凸规划
(1) 局部最优解
x

也是全局最优解.

(2) 如果目标函数是严格凸的，则 x 是唯一的全局最优解.
F {x | ci ( x) 0, i 1, 2,..., m}.
n
若对于任意两点
1,
及实数 0
都有：
x 1 y D 则称集合 D 为凸集．
换句话说，如果任意两点 x , y D , 则连接x与y的直线段上的所有点都在D内。
定义: 设
n xi R , i 1,2, , k , 实数 i 0 ,
i 1,
(1) (2)
m
A y b,y 0,
T
其中
xR , yR
n
.
Farkas引理在最优化理论研究中起重要作用
Farkas引理的另一种形式 设l. l’是两个非负整数，a0,ai (i=1,…,l)和bi (i=1,…,l’)
是Rn中的向量，则线性方程组和不等式组
d a i 0, i 1, , l ,
整数规划，资源配 置，邮路问题生产 安排等
最优化问题
无约束最优化问题
线性搜索
约束最优化问题
单纯形法

线性规划
对偶单纯形法
最速下降法，牛顿法， 拟牛顿法，共轭方向法
( k 1)
d
二次规划 有效约束集法 可行方向法 二次罚函数 最小二乘法
x
x
(k )
dk
定义 设集合
x, y D,
DR ,
由有限个闭半空间的交组成的集合
D { x | p i x i , i 1, ..., m } ,
T
叫多面集，其中 p i 是非零向量， i 是数。 多面集是一个闭凸集。
D { x R | A x b , x 0} 是多面集吗？ yes
n
a11 x1 a12 x2 a1n xn b1
最优化问题的数学模型
• 一般形式
决策变量
m in f ( x ) s.t. c i ( x ) 0, i 1, 2, , m , 约束 (1) c i ( x ) 0, i m 1, , p , 函数 其中 x x1 , x 2 , , x n T R n , f : R n R 1 , c i : R n 为连续函数，通常还要求连续可微.
注： 和集和并集有很大的区别，凸集的并集 未必是凸集，而凸集的和集是凸集．
定义 设 D1 , D2 R n 为两非空凸集，若存在 非零向量 a R n 和实数 , 使得：
D1 H D2 H

xR a x ,
n T n T
则称超平面 H x R a
n

R x
2 2
0??
2
x 1 y 1 x 1 1 y 1
1 x y