欢迎转载，作者：Ling，注明出处：机器学习：原理简明教程07-SVM预备知识-凸优化与对偶问题

预备知识：凸优化

凸函数与凸集：y=x2是凸函数，函数图像上位于y=x2上方的区域构成凸集。

• 凸函数图像的上方区域，一定是凸集；
• 一个函数图像的上方区域为凸集，则该函数是凸函数。

(超)几何体的向量表达：

• 给定二维平面上两个定点：a(x1,y1)，b(x2,y2)，则：

直线：x=θa + (1-θ)b, θ∈R

线段：x=θa + (1-θ)b, θ∈[0,1]

• 一般的，f(x,y)=0表示定义域在R2的曲线

特殊的，y=g(x)表示定义域在R的曲线，f(x,y)=y-g(x)

• 一般的，f(x,y,z)=0表示定义域在R3的曲面

特殊的，z=h(x,y)表示定义域在R2的曲面，f(x,y,z)=z-h(x,y)

• 上述表达方式可以方便的推广到高维

记x=(u1,u2,…un)，则f(x)=0表示定义域在Rn的超曲面。

不特殊说明，后面将使用x1表示向量，如：定义两个点x1,x2, 则x=θx1 + (1-θ)x2, θ∈R表示经过这两点的直线

仿射集(Affine set)：

定义：通过集合C中任意两个不同点的直线仍然在集合C内，则称集合C为仿射集。

例子：直线、平面、超平面

超平面：Ax=b

凸集：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。

因为仿射集的条件比凸集的条件强，所以，仿射集必然是凸集。

实例：

超平面hyperplane

半空间halfspace

就是平方和开根号

多面体

保凸运算：

集合交运算：

仿射变换：函数f=Ax+b的形式，称函数是仿射的：即线性函数加常数的形式

透视变换

凸集的透视变换仍然是凸集。

投射变换(线性分式变换)

分割超平面

分割超平面的构造

• 两个集合的距离，定义为两个集合间元素的最短距离。
• 做集合C和集合D最短线段的垂直平分线。

支撑超平面

凸函数：若函数f的定义域domf为凸集，且满足

一阶可微：若f一阶可微，则函数f为凸函数当前仅当f的定义域domf为凸集，且

二阶可微：

凸函数举例：

上境图：注意，这个只是上境图，非凸函数

凸函数与凸集：

一个函数是凸函数，当且仅当其上境图是凸集。

进一步，一个函数是凹函数，当且仅当其亚图(hypograph)是凸集。

Jensen不等式：若f是凸函数，

注：Jensen不等式是几乎所有不等式的基础，期望，就是概率与x求积分

注：注意到y=-logx在定义域上是凸函数

保持函数凸性的算子

凸函数的逐点最大值

凸优化

优化问题的基本形式

一些名词：

性质

非凸优化问题的变形

对偶问题：

原问题：

Lagrange对偶函数(dual function)：inf表示下确界，对偶问题一般是原问题求导带入

左侧为原函数，右侧为对偶函数

注: 对偶问题是关于λ的函数，不同的在左侧可以得到不同颜色的曲线，最下方的曲线是原问题的约束条件

鞍点：最优点

原问题求极小值：

原问题求极小值的本质：对L求极大值后(λ)，求极小值（x）

而：

证明：

注： f一定小于max，这个时候max中x是一个常数，两边加min y不变，由于第二个式子右边是定值，即无论x取什么，都要小于等于，最后一个式子取max x，也是小于等于

强对偶条件：即Karush-Kuhn-Tucker (KKT)条件

若要对偶问题的最大值即为原问题的最小值，考察需要满足的条件：

当λ大于0，f小于0，则第一个不等号，第二项一定小于0，而h=0，第三项一定等于0，所以有最后的不等号，如果L求导=0，则满足驻点，等号成立

一个对偶函数应用：