如何判断Convex Set(凸集)、Convex Function(凸函数)

1674-曲同学

发表文章数:87

热门标签

首页 » LeetCode » 正文

一、Convex Set(凸集)

1、凸集的几何解释

如果集合C中任意2个点 X 1、X 2,其连线上的所有点都是集合C中的点,则C为凸集。(下图中:“左图”为凸集,“右图”为非凸集)

如何判断Convex Set(凸集)、Convex Function(凸函数)

两个凸集的交集也是凸集。(intersection of convex set in convex)

如何判断Convex Set(凸集)、Convex Function(凸函数)

2、凸集的数学解释

对于任意x1,x2∈C,并且任意参数a∈[0,1],我们有ax1+(1-a)x2∈C,则集合为凸集。

二、Convex Function(凸函数)

  • 如何判断凸函数?
    接下来将从“两点法”(即:从任意的两点去理解凸函数)、“一点法”(即:从任意的一点去理解凸函数,分别对其“一阶条件”、“二阶条件”)进行介绍。

1、“两点法”

所谓凸函数,其实指的是下凸函数。从几何意义上看,凸函数就是任意两点之间的弦(即这两点构成的线段)都在该函数图像(此处是指这两点之间的函数图像,而非全部的函数图像)的上方。

如何判断Convex Set(凸集)、Convex Function(凸函数)
如果 domf(即函数的定义域)为凸集,对于定义域里任意 x、y,且对于任意 x、y∈domf 和任意 0≤θ≤1(如果将≤换成<,则是严格凸函数的数学定义)。

如何判断Convex Set(凸集)、Convex Function(凸函数)

2、“一点法”

凸函数上的任意一点,我们作该点的切线,则该切线总是在函数图像的下方。因为在该定义下,我们只需要通过函数图像上的一点即可判断是否为凸函数,所以称“一点法”。

如何判断Convex Set(凸集)、Convex Function(凸函数)

  • “一点法”的一阶条件
    函数f:Rn → R,假设 f 可微(即梯度 ∇f 在在开集 domf 内处处存在),则函数f是凸函数的充要条件是: domf 是凸集且对于任意的 x,y∈domf 。
    f(y)⩾f(x)+∇f(x)T(y−x)

  • “一点法”的二阶条件
    函数 f : Rn→R , 假设 f 二阶可微,即对于开集 domf 内的任意一点,函数 f 的 Hessian 矩阵或二阶导数 ∇2f 存在,则函数 f 为凸函数的充要条件是:如果二阶导后是 scalar,则 scalar≥0 ;如果二阶导后是矩阵,其矩阵是半正定的(即∇2f≽0)。

3、凸函数举例

  • 指数函数 eax
  • 幂函数 xa,其中 x大于或等于0,当a不属于0-1范围内时为凸函数,否则为凹函数
  • 绝对值的幂函数 |x|a,其中 a>1
  • 对数函数 logx
  • 负熵 xlogx
  • 范数
  • 最大值函数 max(x)
  • 二次-线性分式函数 f(x,y)=x2/y, y大于0
  • 指数和的对数f(x)=log(ex1+ex2+,…,+exn).这其实是一个soft-max
  • 几何平均 f(x)=(∏nxi)1/n
  • 行列式的对数 log|A|,其中 A矩阵正定

三、“判断是否为凸函数”示例

如何判断Convex Set(凸集)、Convex Function(凸函数)

如何判断Convex Set(凸集)、Convex Function(凸函数)

标签:

未经允许不得转载:作者:1674-曲同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《如何判断Convex Set(凸集)、Convex Function(凸函数)》 发布于2021-08-22

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录