凸优化

简介

机器学习中常用到数学优化技巧,最常见的优化就属凸优化了,本文参考Stanford CS229 Machine Learning的教学资料:http://cs229.stanford.edu/section/cs229-cvxopt.pdf,对凸优化问题的初步认识,以下是几个重要的概念笔记。

凸集

几何意义为,集合C中任意两点间的线段仍然在C中,其示意图如下:convex set
数学定义,对任意x1,x2$ \epsilon C$,$0 \leq \Theta \leq 1$,都有convexf
常见的凸集有,n维实数空间;一些范数约束形式的集合;仿射子空间;凸集的交集;n维半正定矩阵集。

凸函数

几何意义为,函数任意两点连线上的值大于对应自变量处的函数值,示例图如下:convex_function
数学定义,如果函数定义域(dom f)是凸集,且对于任意$x,y\epsilon dom f$和任意$0\leq \Theta \leq 1$,有$$f(\Theta x+(1-\Theta )y)\leq \Theta f(x)+(1-\Theta )f(y).$$
常见的凸函数有,指数函数族;非负对数函数;仿射函数;二次函数;常见的范数函数;凸函数非负加权的和等

凸优化问题

研究定义于凸集中的凸函数最小化问题。它要求目标函数是凸函数变量所属集合是凸集的优化问题。或者目标函数是凸函数,变量约束函数是凸函数(不等式),或仿射函数(等式约束)
数学定义
convex_prob
常见的凸优化问题有,线性规划、二次规划、二次约束的二次规划、半正定规划。

对偶

在约束最优化问题中,常常利用拉格朗日对偶性将原始问题转换成对偶问题,通过解对偶问题而得到原始问题的解。这样做的优点是对偶问题往往更容易求解。
Lagrange对偶的基本思想是在目标函数中考虑上图中的约束条件,也就是添加约束条件的加权和,得到增广的目标函数。定义上面问题的Lagrange函数lagr

附:仿射函数

如果f(x)=a·x+b,$a \epsilon R^{n},b\epsilon R,x \epsilon R^{n}$,则f(x)为仿射函数。

分享