凸优化问题-白红宇

凸优化问题

阅读量：4303 次

发布时间：2019-05-27

本文共 430 字，大约阅读时间需要 1 分钟。

凸集

$\theta x + (1-\theta )y \euro C$

凸集的交集还是凸集。 $\bigcap C_{i}$

仿射空间是典型的凸集，Ax = b，Ax < b 线性等式和线性不等式是凸集。

凸函数

判断凸函数的方法：定义，一阶导数判定，二阶导数判定。

定义： $f(\theta x+(1-\theta )y)) \leq \theta f(x) + (1-\theta )f(y)$

一阶：f(y) > f(x) + f '(x)*(y-x)；二阶：f ''(x) >= 0，>0为严格凸函数，二维则Hessian矩阵为半正定，正定为严格凸函数。

凸函数的线性组合 $\sum w_{i}\cdot f(t)$ 还是凸函数。

二次函数是典型的凸函数。

凸优化问题是目标函数是凸函数，可行域是凸集，即双凸。

如SVM的目标函数和约束条件， $\frac{1}{2}ww^{T}$ 为单位矩阵，即正定，是凸函数， $y_{i}(w^{^{T}}x_{i}+b)$ <0 为线性不等式，是凸集，所以SVM的的优化问题为凸优化问题，而 $\frac{1}{2}ww^{T}$ 是二次型，所以是凸二次规划问题。

凸优化问题的性质，局部最优解是全局最优解，并且规避了鞍点问题（因为Hessian矩阵是半正定的，不存在不确定的点）

slater条件是强对偶的充分但不必要问题。满足slater条件是 1）凸函数+ 2）至少存在一组解使g(x) < 0两个条件。

转载地址：http://jhmws.baihongyu.com/

你可能感兴趣的文章