墨奇博客 | 凸优化简介:极值何时存在?文章来源于微信公众号:墨奇科技 引言 同学们可能能回忆起来,对于二次函数 在求解这个问题之前,我们应该先判断问题本身是不是可解的。一些同学可能能想起有个东西叫极值存在定理。它是这样描述的:在一个有界区间中,如果一个函数是连续的,那么在这个区间内它一定存在极大值和极小值。然而对于最优化问题来讲,我们在当前区间内更关心这个极大值唯一吗?或者这个极小值唯一吗?读到这里的同学们可以先思考一下,能有什么样的性质能帮助我们判断这种唯一性吗? 当然聪慧的你们肯定能察觉到一些蛛丝马迹。正如标题中提到的凸优化中的 “凸”,我们看重的是问题的 “凸” 性。在深入到各种数学符号之前,我觉得大家应该更加感性的理解这个问题。 举个例子,想象有一块橡皮泥,我们希望这块橡皮泥印在平板上的印记只有一个。那么这个橡皮泥应该是什么样子的呢?如果是个正方体,那么印记会是一条线段或者一个长方形或者一个点。若是一个球形的,那么印记会是一个点。这两个例子都满足前文“印记只有一个”的前提要求。但如果是马鞍形,印记则可能是两个点。是不是感觉有点理解这个感性认识了? 如果你能找到点感觉,那就带着这个感觉先赶快看一下经典 Weierstrass 级值定理吧。这部分内容能够帮助你理解一个更广义的极值存在定理,并将连续这个概念拓展到更广泛的场景中。 经典 Weierstrass 极值定理基本定义与定理本节我们会介绍一些基本概念,包括什么是有界、闭合、紧致等定义。同时我们还会回顾一些连续性的相关定义,以方便我们去证明后续的一些定理。 1.有界 (bounded) :有界集合有穷的集合半径;有界集合内部的任两个点的距离都是有穷的。 2.闭合 (closed) :闭合集合是有界的且边界在集合中的。 3.紧致 (compact) :紧致集合是有界的且闭合的。 4.真性 (proper):真度量空间内所有的闭合球 (closed ball) 都是紧致的。换言之,真度量空间都是完备的(complete)。真函数 (proper functions) 在自身非空的定义域中每个值都大于 5.下半连续 (lower semi-continuous) :闭合函数都是下半连续的,反之亦然。(上半连续 + 下半连续 = 连续) 极值存在定理在证明经典 Weierstrass 极值定理之前,我们先推出一个初始版本的极值定理: (定理 1) 对于一个闭合,强制性的真函数 (coercive, closed and proper function) 证明: 先定义一个序列 声明: 由上面的推导,我们可以声明 因此我们有, 其中, 且因为 经典 Weierstrass 极值定理的证明上面的一些定理能够帮助我们去定义一个函数是否有一个极小值。在引出经典 Weierstrass 极值定理之前,我们还需要补充指示函数的一些定义和性质 在面对指定定义域的问题时,可以结合指示函数来定义目标函数,比如 那么现在我们终于来到了本节的大 boss: (经典 Weierstrass 极值定理) 对于一个下半连续(lower semi-continuous)的函数 证明: 小结一下现在成功的将极值存在定理从连续函数拓展到了半连续 (semi-continuous) 函数上。同学们可能会问了,这有什么用呢?这个很有用,因为实际场景中连续性是比较少见的。熟悉神经网络的同学们可能会知道 ReLU 这个东西,是一个分段函数 (piece-wise) ,虽然不是连续的但是却是半连续的。所以本节当中推导的 经典 Weierstrass 极值定理能够确保我们即使遇到半连续的函数,也能确保我们还能用极值存在作为已知前提。 凸函数与 Hilbert 投影定理感谢能看到这里的同学,接下来就是比较让人激动的内容了。本节我们会介绍凸函数和可分离定理。这是对于凸优化非常重要的基本概念。这为最优化算法可行性的判定提供了有效的依据。我个人也是觉得这部分算是容易理解并且很优雅的一节内容。 什么是凸函数重点来了!敲黑板!! 1.凸函数的定义有两种形式: a. 定义:(类似地,我们可以来思考一下 凸集合的定义是什么?) b. Jensen 不等式形式: 我们可以简单消化一下:如果在函数围成的区域内随意取两个点,并将两点连成线段,那么如果这个线段上任意点都还在这个区域里,那么这个函数就是凸的。这个被函数围成的区域也是有学名的,它叫上镜图 Epigraph(如果把函数围成的区域替换成集合,那么凸集合的定义就呼之欲出了) 2.凸函数的一些性质: a.(仿射不变性) 对于一个线性映射 证明: b.(非负权和下不变) 对于非负的 证明:这个证明很简单,推导一下就可以得到这个结果 c.(凸函数集合的上确界为凸) 对于一个凸函数集合 证明: 点到集合的投影1.支撑函数(Support function):支持函数 经过推导我们可以知 支持函数 是闭合且凸的。支持函数可以理解为绕着集合的一个函数,描绘了集合的边界。 2.支持函数的性质:(这里我们定义 a. b. c. d. 3. 集合的投影(Projection of a set):对于一个 非空且闭合的集合 4. 对于欧几里得范数 5. 如果 证明: 有了上面的凸集投影唯一的性质,我们就可以很方便地得到本节的主题:Hilbert 投影定理 Hilbert 投影定理(Hilbert 投影定理)对于一个闭合的凸集合 证明:因为集合为凸且闭合, 我们做了一个图示以方便大家理解。请大家看下图, 有了这样优美的理论,我们总感觉还差点什么。就让我们引申一下,看分离定理是怎么推导的: (分离定理)对于 证明: 换言之,我们总能找到一个非零超平面 这个是不是很酷?上面的一些推导向我们展示了,“凸性“ (convexity) 能作为我们处理最优化问题的一个有力证据。本次由于篇幅问题我们还有很多精彩的内容没有覆盖,比如 KKT 条件 。我们将求解凸问题的最优化问题统称 “凸优化”。由于我们仅仅限制了凸性这个更加宽泛的性质,对于连续性和可微性的限制很小,所以接下来我们还需要拓展微分的概念。比如次微分 (subdifferential),次梯度 (subgradient)等等。 如果感兴趣的话,要记得时刻关注了解更多凸优化知识哦! —END—
文章分类:
对外活动
|