凸优化入门 - 基本概念与 Jensen 不等式

原创
2020/12/23 19:31
阅读数 209

1引言

机器学习中经常会碰到希望优化某个函数值的问题。

例如,给定一个函数 ,我们想找一个 使 取最小值(或取最大值)具体如最小二乘、逻辑回归和支持向量机等这些问题都可被视为优化问题。

事实上,找到函数的全局最优值在一般情况下可能是一项非常困难的任务。但是,对于一类特殊的优化问题,即凸优化问题,在许多情况下我们可以有效地找到全局最优解。

这意味着我们可以在合理的时间内解决许多实际问题,即从理论上来讲,我们可以在问题规模的多项式复杂度内及时解决问题。

2凸集

.定义

线段 给定两点 之间的线段,是指所有点

的集合,其中

凸集 如果对于 中任意两点 ,它们间的线段仍然属于 ,即对于 ,都有

成立,则称集合 是凸的。

直观地讲,这意味着如果我们在 中任意取两个点,并在这两个点之间绘制一条线段,则该线段上的每一点也都属于

也称为点 的凸组合。下图显示了两个凸集(左、中图)和一个非凸集(右图)的示例。

.一些例子

所有

很明显,给定任意 ,都有

非负象限

非负象限由 中的所有元素非负的向量组成,即

为了验证这是凸集,只需注意给定任意 ,有

范数球

假设 上某个范数(例如,欧几里得范数, ,则集合 是凸集。

假设 ,其中 以及 ,则有

这里使用了范数定义中的三角形不等式和正齐次性。

仿射子空间和多面体

给定矩阵 和向量 ,仿射子空间是集合 (请注意,如果 不在 的值域内,则仿射子空间为空)

类似地,多面体是(再次可能是空的)集合 ,其中 在这里表示分量不等式(即 的所有元素均小于或等于 的相应分量)

为了证明这一点,首先考虑满足 ,以及 ,有

同样,对于满足 以及 ,有

类似地,对于两个向量, 表示 的每个分量大于或等于 的每个分量。有时候,用 代替 ,具体可以根据上下文确定(即,不等式的两侧都是向量)

凸集的交集

假设 是凸集。然后他们的交集

仍然是凸集。假设 以及 。然后,由凸集的定义可得,

因此


凸集的交集示例

但是请注意,凸集的并集通常不会是凸集。

凸集的并集示例

半正定矩阵

所有对称半正定矩阵的集合(通常称为半正定锥并表示为 是一个凸集(通常用 表示对称 矩阵的集合)

当且仅当 且对于所有 ,有 成立,则矩阵 是对称半正定的。

现在考虑两个对称半正定矩阵 。然后对于任意 ,有

相同道理,可以证明所有正定、负定和半负定矩阵的集合也都是凸集。

3凸函数

.定义

凸函数 对于函数 ,如果它的定义域 是一个凸集,并且对于所有 ,有

则函数 称为凸函数。

为了更加形象地理解凸函数,我们画个图看看。假设 ,如果取凸函数上的两点并在它们之间连一条线段,那么两点之间的函数部分都会在这条线段之下。请看下图中的蓝色曲线,而橙色曲线对应的函数就不是凸函数啦。

进一步定义,如果上述定义对 的条件成立,则称函数 为严格凸函数。如果函数 为凸的,则定义 为凹的,严格凹函数的定义以此类推。

注意: 这里要求 的域是凸集主要是为了确保 是有定义的(如果 不是凸的,即使 ,那么 也可能不在定义域内,因此未定义

请指出下图中哪些是凸函数,哪些不是凸函数。

4凸性条件

有了凸函数的定义,那是不是想知道凸函数有些什么特别之处呢?反过来满足什么性质的函数是凸函数呢?

.凸性的一阶条件(First Order Condition for Convexity)

假设函数 可微(即对于所有 ,导数 恒存在),当且仅当 为凸集且对于所有

都成立的时候,可以称函数 是凸函数。

函数 在点 处称为函数 的一阶逼近。

直观地讲,这可以认为是 与其在点 处的切线近似。

凸度的一阶条件说,当且仅当切线整体在函数 的下面时, 才是凸的。

可以通过下面的图来直观地理解什么是凸性的一阶条件: 对于凸函数上的任一点 ,该点处的切平面都将在函数 下方。

.凸性的二阶条件(Second Order Condition for Convexity)

假设函数 是两次可微的(即, 的定义域中的所有点 都有定义 Hessian 矩阵 。当且仅当 为凸集且其 Hessian 矩阵为半正定数时, 才是凸的: 即对于任何 ,有

此处,该符号 如果跟矩阵结合使用时,指该矩阵是半正定的,而不是分量不等式。当一维时,这等价于二阶导数 始终非负。

类似于凸性一阶条件的定义,如果 的 Hessian 为正定,则为严格凸,如果 Hessian 为半负定,则为凹,如果 Hessian 为负定,则为严格凹。

5Jensen 不等式

我们从凸函数的基本定义出发,对于 ,有

使用归纳法,可以很容易地将其扩展到多个点的凸组合,对于 ,有

实际上,这也可以扩展为无限项之和以及积分。对于积分,当 时,有

由于 积分为 ,因此通常将其视为概率密度函数,在这种情况下,可以用期望来改写前面的等式,

最后这个不等式被称为琴生不等式或者詹森不等式。

可以结合下图来理解上面的不等式。至于这个公式的意义和应用等后面再来揭示哈。

⟳参考资料⟲

[1]

Zico Kolter, Honglak. Lee: http://cs229.stanford.edu/section/cs229-cvxopt.pdf.



.相关阅读

拉格朗日乘子法的来历与直观解释

雅可比矩阵几何意义的直观解释及应用

最优化理论发展简史 - 群英璀璨,全知道就服你!



本文分享自微信公众号 - 机器学习与数学(Mathinside2016)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部