一、简介

2018-09-09 本文已影响0人 cheerss

定义1.1 凸函数和凸集

简而言之，凸集满足的性质就是对于集合中的任意两点，他们连线上的点也都是集合中的点
凸优化研究的是凸集上的凸函数的优化。

凸集与非凸集

1.1 机器学习中的一些优化问题

机器学习中的优化问题大多具有这样的形式

如果对应到神经网络，这个地方的x实际代表的是网络中的参数

例如在二分类问题中，我们所熟知的

hinge loss：

y=(1, -1)

logistic loss:

以及回归问题中的：

3.最小二乘法

以及正则项：

lasso正则项

ridge 正则项

以及矩阵补全，见pdf第六页，正文第三页

1.2 凸的基本性质

定理1.1

这里的反除号的意思是x0属于Rn但是不在集合X中

这个定理直观上理解就是平面上总存在一条线，可以将x0和凸集中的点分到两边。这条直线w=（k, -1），t = b。在一个二维平面内，假设直线kx-y+b=0，则直线上方的点满足kx-y+b < 0，而直线下方的点满足kx-y+b > 0。所以只需要找一条直线使得x0在线的上方，凸集内的点在直线下方即可。定理就是说这个点一定存在。这是凸集区别于非凸集的一个特点，想想一个非凸集对于某些点x0，这样的直线是不存在的

对于一条直线y=kx+b，可以将它看成一个一元函数，也可以看成一个二元方程kx-y+b=0

如果看做函数，则其斜率为k，法向量为(k, -1)，法向量与直线垂直，因此可以有两个不同的方向

如果看做方程，则z=kx-y+b=0，其实是一个三维空间的平面与xoy平面的交线，这个平面与z轴的交点坐标是（0，0，b），这个平面的法向量是(k, -1, -1)。

定理1.2

这里的偏导符号意思是x0是凸集的边界点

这个定理意思是说在边界上可以找到一条线（超平面），这条线的法向量是w，在这个w下，始终有不等式成立。实际上这个线（超平面）就是凸集在x0处的切线（切平面），见下图。这条线和y轴的截距是t，w=(k,-1)，所以wx0=t，而凸集内的点则都满足wx > t。（自己备注：如果x0跑到了图中的下面怎么办，不是直线上方的点都<0吗？怎么解释？实际上只要取w=(-k, 1)就可以保证wx > t了（因为-wx < t），实际上两个w都是直线的法线，只不过，当w反向时，按理说t也应该取-t才满足之前说的上方的都小于0，所以此处并不矛盾）。这个定理的严格证明可以根据定理1.1证明。对于非凸集，边界点的切平面有可能会经过集合内部