凸优化问题最优解
定理：设 X 为凸优化问题的可行域，f0 (x)可微。则 x 为最优解当且仅当 f0 (x)T ( y x) 0, y X 成立。
可编辑
15
凸优化问题最优解
定理：无约束凸优化问题中，若 f0 (x)可微。则 x 为最 优解当且仅当 f0 (x) 0成立。
h1(x) (x1 x2 )2 0
等价于凸优化问题
minimize f0 (x) x12 x22 subject to f%1(x) x1 0
h%1(x) x1 x2 0
可编辑
13
凸优化问题的局部最优解
定理：凸优化问题的局部最优解均是全局最优解。
可编辑
14
可编辑
10
优化问题的上半图形式
minimize t subject to f0 (x) t 0,
fi (x) 0, i 1,..., m hi (x) 0, j 1,..., p
可编辑
11
凸优化问题的基本形式
凸优化问题的基本描述：
minimize f0 (x), x R n subject to fi (x) 0, i 1,..., m
hi (z) 0, j 1,..., p x z R, R 0
2
若 x 为局部最优问题的最优解，则它为原最优问题的
局部最优解。
可编辑
4
优化问题的等价形式(1)
定理：若 i 0,i 0,..., m, i 0,i 1,..., p
则原优化问题与以下优化问题等价
hi (x) 0, j 1,..., p
fi (x)为凸函数 hi (x)为仿射函数 若 f0 (x)为准凸函数，则优化问题称为准凸优化问题。 性质：凸优化问题的可行域是凸集。
可编辑
12
抽象凸优化问题
例：
minimize f0 (x) x12 x22 subject to f1(x) x1 /(1 x22 ) 0
minimize f%0 (x) 0 f0 (x), x R n subject to f%i (x) i fi (x) 0, i 1,..., m
h%i (x) hi (x) 0, i 1,..., p
可编辑
5
优化问题的等价形式(2)
定理：设 :R n R n 为一一对应，且 D (dom) 则原优化问题与以下优化问题等价 minimize f%0 (z) f0 ((z)), z R n subject to f%i (z) fi ((z)) 0, i 1,..., m h%i (z) hi ((z)) 0, i 1,..., p
可编辑
6
优化问题的等价形式(3)
定理：设 0 :R R 为严格单调增函数；1,..., m 满 足 i (u) 0 当且仅当 u 0 ；1,..., p 满足i (u) 0 当 且仅当 u 0 。则原优化问题与以下优化问题等价
minimize f%0 (z) 0 ( f0 (z)), z R n subject to f%i (z) i ( fi (z)) 0, i 1,..., m
可编辑
9
可分离变量优化问题
性质： 其中
inf f (x, y) inf f%(x)
x, y
x
f%(x) inf f (x, y)
y
定理：优化问题
minimize f0 (x1, x2 ), x R n
subject to fi (x1) 0, i 1,..., m1
f%i (x2 ) 0, i 1,..., m2 可以分离变量 x1, x2
h%i (z) i (hi (z)) 0, i 1,..., p
可编辑
7
优化问题的等价形式(4)
定理：原优化问题与以下优化问题等价
minimize f0 (x), x R n subject to fi (x) si 0, i 1,..., m
si 0 hi (x) 0, j 1,..., p
凸优化理论与应用
第三章 凸优化
可编辑
1
优化问题的基本形式
优化问题的基本描述：
minimize f0 (x), x R n
subject to fi (x) 0, i 1,..., m
优化变量
hi (x) 0, j 1,..., p x R n
不等式约束 等式约束 无约束优化
最优化值
p* inf{ f0 (x) | fi (x) 0, i 1,..., m, hi (x) 0, i 1,..., p}
最优化解
p* f0 (x*)
可编辑
3
局部最优解
局部最优问题
minimize f0 (z), x R n subject to fi (z) 0, i 1,..., m
fi (x) 0,i 1,..., m hi (x) 0.,i 1,..., p
m p0
可编辑
2
优化问题的基本形式
优化问题的域
m
p
D I domfi I domhi
i0
i1
可行点(解) (feasible) x D 且满足约束条件
可行域(可解集)
所有可行点的集合
例：无约束二次优化问题
f0
(
x)

1 2
xT
Px

qT
x

r
可知
f0 (x) Px q 0
可编辑
16
凸优化问题的最优解
定理：设凸优化问题仅有等式约束 minimize f0(x), x R n subject to Ax b
则 x 为最优解当且仅当 x X ，且存在向量 v 满足 f0 (x) AT v 0
s 称为松弛变量
Байду номын сангаас
可编辑
8
优化问题的等价形式(5)
定理：设 :R k R n 满足等式 hi (x) 0, j 1,..., p
成立，当且仅当 x (z) 。则原优化问题与以下优化
问题等价
minimize f0 ((z)), x R n subject to fi ((z)) 0, i 1,..., m