|
配合视频 中科大-凸优化
配合笔记 凸优化笔记
二、凸优化问题
1.凸优化问题概述
- 判断一个优化问题是否是凸优化
- 纠正拟凸证明，凸优化问题
- 可行性优化问题，等价问题
- 凸优化问题，凸优化问题的性质
-
x
?
∈
X
f
x^*\in X_f
x?∈Xf?最优
??
?
??
\iff
?
▽
f
0
T
(
x
?
)
(
y
?
x
?
)
≥
0
▽f_0^{T}(x^*)(y-x^*)\ge0
▽f0T?(x?)(y?x?)≥0的
?
\Rightarrow
?理解：根据凸函数一阶条件
f
0
(
y
)
≥
f
0
(
x
?
)
+
▽
f
0
T
(
x
?
)
(
y
?
x
?
)
f_0(y)\ge f_0(x^*)+▽f_0^{T}(x^*)(y-x^*)
f0?(y)≥f0?(x?)+▽f0T?(x?)(y?x?)，而
f
0
(
x
?
)
f_0(x^*)
f0?(x?)已经最小了，
f
0
(
y
)
f_0(y)
f0?(y)必然是要
≥
f
(
x
?
)
\ge f(x^*)
≥f(x?)的，因此必须加一个
≥
0
\ge0
≥0的数才能找到这样的
y
y
y
2.凸优化约束条件
- 约束仅为等式约束或非负约束，线性规划一般形式
- 当约束为非负约束时，证明最优解处的梯度必须为零，理解关键：因为
x
x
x是最优解，即给定了，此时
▽
f
0
T
(
x
)
(
y
?
x
)
▽f_0^{T}(x)(y-x)
▽f0T?(x)(y?x)是一个关于
y
y
y的函数，
f
(
y
)
=
▽
f
0
T
(
x
)
y
?
▽
f
0
T
(
x
)
x
f(y)=▽f_0^{T}(x)y-▽f_0^{T}(x)x
f(y)=▽f0T?(x)y?▽f0T?(x)x，它相当于是很多个一次函数，每个一次函数的系数是
▽
f
0
(
x
)
▽f_0(x)
▽f0?(x)的一个分量，而这些所有的一次函数在
y
≥
0
y\ge0
y≥0的时候都必须非负，因此每个系数都不能是负的，即
▽
f
0
T
(
x
)
≥
0
▽f_0^{T}(x)\ge0
▽f0T?(x)≥0
3.具体优化问题
|