凸优化(1)——引入,优化实例分析,凸集举例与相关性质

运筹OR帷幄 2021-02-23 20:30


↑↑↑↑↑点击上方蓝色字关注我们!






『运筹OR帷幄』转载


作者:学弱猹 厦门大学信息与计算科学系本科生  现快手广告算法工程师


编者按

这一篇文章我们开始对凸优化的理论进行引入。凸优化是一个非常重要的课题,它也是一类最为容易求解的优化问题。在这一个系列中,我们会重点关注解决凸优化问题的基本思路和常见的算法,并且适当的将其与机器学习,深度学习,运筹学等内容结合起来,为大家提供一个全面的介绍。


大家好!

这是一个全新的系列,我们会给大家介绍凸优化(Convex Optimization)相关的内容。

凸优化在机器学习,深度学习等人工智能与大数据相关的方向都有举足轻重的作用。虽然现在很多实际的深度学习项目和课题中,多半不会直接利用上凸优化的知识,但学习凸优化有助于从一个更高的角度来思考相关的问题(当然了,这也是数学学科的一大优势了)。而且事实上,在当今的算法工程师面试中,很多企业都会加入对面试者凸优化知识的考查。相信很多相关专业的本科生和研究生,也修过学校的《凸优化》这一门课。

对于凸优化,我们最容易产生的疑惑就是它与最优化(数值优化)有什么区别?虽然它们俩本质上都是优化,但是凸优化的研究范围更窄,可以看出对“凸”的要求更高。所以在这个领域下,就会涌现出很多有趣而独特的理论与算法。因此如果要保留凸优化的本真,其实更多像是一门分析的课程(很多老师会把这门课起名叫“凸分析”),但我们这个系列不会这么做,而是尽量与数值优化相同,虽不可避免的要介绍一些理论,但还是努力以算法为导向,理论为辅助

因为厦大没有开设《凸优化》的课程,因此这一门课的参考资料会从两个地方选取。一是卡内基梅隆大学(CMU)Ryan Tibshirani 的Convex Optimization(10-725 / 36-725),二是中科大(USTC)凌青教授的《最优化理论》,它们俩共同的参考书则是Stephen BoydConvex Optimization。虽然我在写作之前还没有看完这两个系列,但也算能看出一点二者对课程设计的差别。简单来说,中科大的课程更加理论,而CMU的课程则更偏向于当前优化界,与机器学习和统计相关的算法(插一个小知识:CMU的课程的开头10表示这个是它们Machine Learning Department的课,36则表示是Statistics Department,725的7开头,表示是PhD level)。所以这一个系列还是会主要以CMU的课程为主,用中科大的课程来辅助一些理论的知识。

因为凸优化与数值优化的交集甚多,故很多凸优化所需要的知识,其实我们在数值优化中很有可能已经介绍过。因此在这个系列中,会有大量对《数值优化》这个系列的引用。也正是因为这个原因,很有可能出现一节的内容量很大的情况(毕竟有很多东西引用了,就不怎么占地方了,就会不由自主的为了凑字数多写一点2333……)。当然了,如果你事先没有看过《数值优化》,那么这个系列我也自然会推荐你去点开看一下

数值优化(C)——二次规划(下):内点法;现代优化:罚项法,ALM,ADMM;习题课

但如果没有看,跟上《凸优化》也没有问题,因为需要引用的时候,我会把引用范围说的比较清楚。

好的,废话说的够多了,我们开始吧。

目录

  • 引入:优化的历史
  • 引入:优化实例
  • 引入:凸优化的问题形式与基本性质
  • 凸集举例与相关结论
  • 延伸:单纯形法的思路来源

Source

  • CMU 10-725: Convex Optimization
  • USTC: 最优化原理
  • Boyd, Vandenberghe, Convex Optimization
  • Fan (1949), On a theorem of Weyl conerning eigenvalues of linear transformations

引入:优化的历史

什么是优化,在数值优化(1)——引入,线搜索:步长选取条件的开头引入中已经说的很清楚。这里只强调一下,我们比较关心的是如何求解

在《数值优化》中,我们根据问题是否有约束条件,会把问题拆分成无约束优化问题带约束优化问题。同时在数值优化中,我们的重点放在了数值上,我们介绍了很多实际的算法,然后需要通过编程来实际解决问题。但是其实优化本身的思想,和它发展的源头,事实上远比我们想象的要早,尽管主要的潮流认为,优化学科在二战得以兴起。我们也算是发了一笔战争财吧。

事实上优化是从17世纪开始就有发展,一开始是Newton和Rapson在求解非线性方程的时候,将问题做了如下的修改

然后通过优化方法来找。类似的方法也被Gauss-Seidel和Jacobi所利用(对,就是数值分析里面的那两种求解线性方程组的迭代法),它们是为了求解这样的一个问题。

所以一个重要的思想就是:求解方程的根和优化函数的极小值,二者很多时候可以等价。这个思想在《数值优化》中也被多次提及过。

随着时间的发展,到了二战的前后,其实出现了很多有趣的发展。很多发现其实体现在与优化紧密联系的运筹学中。比方说1940年,Bellman发展了动态规划算法 (Dynamic Programming,DP)。这个算法的关键在于,状态转移不再是从前往后,而是从后往前。这样的话可以避免很多重复计算。当然了这个算法就我自己看来算是很困难的,也是算法工程师面试必考的代码算法之一。

说到凸优化,我们一般还会提一下单纯形法(Simplex Method),这个方法是1947年由Dantzig完善。说到数值优化,都会提一下内点法(Interior Point Method)。内点法是1984年由Karmarkar完善。而之后的很多优化的发展,都关注在了内点法的很多细节上。

好的,关于优化的历史,我们就说这么多。大家就当看小说就好了。

引入:优化实例

关于优化的实例我们之前说的不算多,这里给大家补几个例子来丰富这一节的内容。这里的每一个例子都有一些高阶的设计思想在,有些理解的话需要对高等代数有比较深刻的认识。不过即使没有理解也没有关系,用来看看优化可以做什么的,也足够了。

Example 1: Linear Quadratic Regulator (Source: USTC)

考虑一个控制器,那么线性二次调节器要解决的优化问题为

这是一个自动化的问题。抽象来说就是状态集合,而就是我们在每一步的状态输入,且状态一步一步都会有转移,用转移矩阵表示。这个目标函数可以拆分为两个部分理解。可以理解为状态的方差可以理解为输入的方差,或者说是物理上的能量的概念。所以我们的目标就是控制每一步的输入能量尽可能的小。虽然不是学这个方向的,但是我相信这句话如果翻译成“节能减排”,那么大家就都能够理解这个优化问题有什么实际的作用了。

Example 2: Shortest-Path Problem (Source: USTC)

考虑最短路问题,严格来说可以把它写成一个优化问题,即,

这里表示是起点(Source),表示是终点(Destination)。这个优化问题直接来看是很抽象的,我们画张图解释一下。

这里的就表示是否选取从的路径。所以对于一条路径而言,如果是起始点,那么因为它的出度比入度要大1,如果是终点,它的入度比出度一定大1(也就是出度一定比入度大-1),中间的经过的点则出度与入度相同,这个即使不懂图论,看蓝色的一条路径也很容易看出这一点。

当然了这个优化问题并不是一个非常容易的问题。因为它的约束是离散的点,离散的点当然不可能是凸的。因此很多时候,会考虑使用凸松弛的技巧。也即

当然了凸松弛之后,与原始问题是否等价就是一个大的问题

接下来给出几个统计机器学习的例子。

Example 3: 2d-fused LASSO (Source: CMU)

考虑问题,其中是数据点。

如果去掉后面的罚项部分,那么就是一个最小二乘回归问题。而这个罚项可以看出,它是针对相邻点的差距来进行惩罚的。换句话说,如果你的值变化的频繁,变化的幅度大,对应的罚项就大,这样的话就一定程度上使得曲线变成了分段的直线。因此事实上越大,曲线就越来越不可能有值的变化,这也就是下面的图所展现的趋势。

接下来这个例子是一个比较一般的优化形式。

Example 4: Eliminating Equality Constraints (Source: CMU)

考虑问题, , ,问是否可以消去等式约束?

这一部分其实就是想解决这个问题。消除等式约束的做法比较像线性方程组求解中,先找到一个特解,然后就可以得到无数多个通解的情况。简单来说,就是设,其中(这是为了保证表示的列空间)。那么这个时候,问题就会变为

这是因为对于来说并没有任何其它的限制了。

但这里要注意的是这样的做法在有些时候是不推荐的。如果说是一个稀疏矩阵,那么一般来说就会是一个稠密矩阵,因为低秩的可能性比较大,所以的零空间的秩就不会小。这样的话原始矩阵的性质就被破坏了,因此在数值上就不一定是一个值得提倡的方法了。

Example 5: Principal Components Analysis (Source: CMU)

考虑下面这个优化问题。其中

这个问题就是机器学习中的主成分分析,形式上可能不同地方写的不一样,这里给大家放一个我录的视频作为辅助理解。

https://www.bilibili.com/video/BV1ZK4y1b7Xt/

学过这个的人会知道它是有一个基于奇异值分解的闭合解的。也即,这里的就是对应的矩阵的前列,行或前个对角元素等(因为这个不是重点,我们不说太多)。但是我们要说明的是,它的约束是一个非凸集,因此这本质上是一个非凸优化问题。

为什么秩的限制集合是非凸的问题呢,事实上举一个例子就好了。

可以看出两个秩1矩阵加在一起不一定是秩1矩阵。

当然了,科学家有办法解决这个问题,把它转变成了一个凸优化的问题,而且可以获得一致的最优解。具体的可以看Source中的Fan (1949)

引入:凸优化的问题形式与基本性质

对于凸优化,我们的问题形式如下

这里的话就是目标和约束函数所有的限制的交集。也就是《数值优化》中已经提到的可行域的概念。如果要问题是一个凸优化问题,那么要求是凸的,并且要求具有仿射性。也就是说我们要求

将问题归结为这个形式,一个最重要的原因就是下面这个性质。

Proposition 1:

凸优化问题局部最优解即为全局最优解

我们证明一下这个结论。考虑反证法,假如说点处是局部极小值,但存在一个,使得,那么设,那么这个时候,因为仍然成立(这是因为函数的凸性),仍然成立(这是因为线性性),所以依然是一个可行解。但是这个时候,注意到目标函数也是凸的,所以

这里的关键是在于说明,如果局部极小值不是全局极小值,那么我们可以通过修改,使得靠近,成为与竞争“局部极小值”的一份子,进而得出矛盾。这个条件是好满足的,因为我们会发现,由于

这就说明了我们可以选择合适的,使得,换句话说,即使的邻域内,都有,这就违背局部极小值的定义了。

所以到此为止,我们也算是介绍完了凸优化的一些基本场景和设定。和最优化不同的是,我们不会立刻长驱直入进入到介绍算法的环节,而是会先用大量的理论和展示来介绍与凸性有关的一些内容。


凸集举例与相关结论

凸集的定义我们在数值优化(1)——引入,线搜索:步长选取条件中已经给出,简单来说,就是

比方说直线肯定是凸集。但是一个关键的地方在于空集,单点集也是凸集。这有点反直觉,但是走定义的话不难说明。比方说对于空集,因为是集合的元素,而空集的线性组合自然也是空集,所以这是符合凸集的定义的。所以看似你在讨论一个“不存在”的概念,但这个“不存在”其实是“存在”于任何一个集合中的。很有哲学的意味了。

说到凸集必然要提到凸组合和凸包的概念。

Definition 1: Convex Combination, Convex Hull

定义的凸组合为,其中。定义凸包为集合的凸组合的所有可能,记为

接下来我们给出一些其它的定义

Definition 2: Norm ball, Hyperplane, Halfspace, Affine Space

定义球(虽然严格来说叫范数球,但我真的不喜欢这个名字……)为,其中给定。定义半平面为,其中给定。定义半空间为,定义仿射空间为,其中给定。

这些都比较好理解,部分的图可以在数值优化(A)——线性规划中的单纯形法与内点法中找到,在线性规划中这些都是必备的几何具象。

相对来说比较陌生的是下面的这几个

Definition 3: Polyhedron, Simplex

定义多面体为,定义单纯形为。其中这些点是仿射独立的(简单来说,三个点不在一条直线上)。

这一张图解释了什么是多面体。

而对于单纯形而言,可以认为是这个五边形的五个顶点的凸包。可能有的人会问为什么我只画了一张图,就能解释这两个概念。这个原因我们在之后会说。

这里有一个细节,就是在很多地方也是多面体的定义。这个的原因在于,我们可以把它写成

然后把约束拼起来,写成就可以了。所以严格来说,多面体内可以有不等式约束,也可以有等式约束。

接下来我们给出锥和凸锥的概念。

Definition 4: Cone, Convex Cone, Conic Combination, Conic Hull

,那么锥满足。凸锥满足。定义的凸锥组合为。定义凸锥包为凸锥组合的所有可能的集合。

虽然锥我们在《数值优化》里给出了定义,但是对于锥究竟是什么,我们这里还是需要多画一些图来做一些解释。

可以看出,左边的是一条过原点的直线,可以证明它其实也是一个锥。而对于右边,我们如果构造所有红点对应的凸锥包,那么蓝色的两条线对应的内部的区域就是结果,大家可以自己想一想为什么是这样。

好的,我们来给几个例题,温习一下这些概念。注意,我们不会直接堆砌所有的凸优化的性质啊定理啊来丰富我们的文章,而是希望通过几个小例题,介绍一些证明的思想工具,做到“四两拨千斤”的效果。

Problem 1:

证明是一个锥。

其中表示它的所有的特征值都非负,也就是半正定的含义。

要证明这个非常简单,现在假如说是某一个的元素,那么只要说明,对任意的,都有就可以了。但是这个是很显然的,一方面可以通过特征值都乘了一个倍,所以依然都非负来解释。另一方面也可以通过半正定的定义

来得到。而注意到,所以结论成立。

Problem 2:

,证明如果是一个凸集,那么也是一个凸集。

这个题也不是很困难。我们取,那么会有。取,那么会有(因为是凸的)。这就可以推出,也就证明完毕了。

这里补充一个知识:一般称为原象集 (pre-image) 或 (kernel)。这一个性质也说明了在线性映射下,凸集的性质可以被保留下来。因为相对称的,如果说是一个凸集,那么也是一个凸集,不过这里就不给大家写证明了,大家可以之后去思考这个事情。

事实上引出Problem 2也是出于特有的目的,也即下面这个例子。

Problem 3: Linear Matrix Inequality Solution Set (Source: USTC, CMU)

给定,那么所有满足不等式 的点构成的集合为凸集。

这个问题要想解释清楚,使用常规的凸集证明方式即可。但是有一种更加有趣的证明方法。设,那么这个时候我们会发现

而这个就是我们关注的那个集合。这个集合当然是凸集,因为它是一个凸集在线性映射下的原象集,也就是利用上了Problem 2的结论。

接下来我们给出一个凸集的加和性质,它的证明方法也是很巧妙的。

Problem 4: (Source: USTC)

如果集合是凸集,那么也是凸集。

我们证明一下这个结论。注意到

是一个凸集(想想为什么?),所以我们设。那么这个时候,可以得到

但是显然是一个线性映射,所以保凸性,因此这就完成了证明。不得不说这个证明很巧妙,因为集合的“和”本身就是一个很难具象的东西,因此缺失几何图像,就会使得联想的证明产生难度。

接下来我们给出一个解析几何的例子

Problem 5: Ellipsoid (Source: USTC)

证明椭球是一个凸集。

可能大家不知道怎么描述椭球,这里补充几句。如果化归到二维平面上,就是这样的一个形式,也就是高中数学里学过的椭圆。但是事实上它有一个更加通用的写法。

落实到我们这一个问题中,就是设,并且设是点的坐标,那么就是

因此二者是一致的。

那么注意到球体本身是一个凸集,而我们只要考虑设新变量,就可以把集合内部的表达式化为的形式,也就是一个球。又因为这个变换是一个仿射变换,所以保持了凸性(很容易证明球是一个凸集),因此我们就算证明完了这个结论。

下面就是一个球变成椭球的形象表示(在的那个部分)。这里用了奇异值分解的图,是因为对于来说,它的两个特征值就对应椭圆的长轴和短轴

好的,关于凸集的例子,我们就说这么多。

延伸:单纯形法的思路来源

最后,我们给出两个结论来说明单纯形法设计的思路。

Proposition 2: (Source: USTC)

证明单纯形是多面体

证明这个的目的是要利用到一个多面体的性质,而这个性质会与我们之后的单纯形法有密切的关联。

这个证明不是特别简单,我们一步步来看,假如说是一个单纯形,那么就会有,并且有(注意这里的是一个向量,表示。并且线性无关(这就是它们仿射独立的含义)。

我们定义,那么这个时候,可以得到

注意到根据条件,是列满秩的,所以我们可以找到一个变换矩阵,使得。那么这个时候,会有

那么因为是有一个范围的限制的。所以我们会有

这个事实上就完成了证明,因为只需要把第一个不等式反号一下就可以了。

我们要证明这个,是为了用到下面这个凸多面体的性质。

Proposition 3:

证明在一个有界多面体作为可行域的情况下,凸函数的最大值在这个多面体的顶点上取到。

如果我们把这个有界多面体限制在上,那么就是一条线段。我们画一个图就能理解这个性质究竟是什么意思了。

你会发现,最大值要不就在处取到,要不就在处取到,它们俩都是边界上的点。

好的,我们证明一下这个结论。

注意到它是一个凸多面体,凸多面体是单纯形,所以可以写成它顶点的凸包。所以我们设是顶点的集合,那么这个时候所有的凸多面体的点就可以写成,且。那么这个时候,根据凸性就可以得到

这就证明了结论。

如果你看了数值优化(A)——线性规划中的单纯形法与内点法中的单纯形法的话,你就会明白为什么线性规划中的单纯形法,是通过找集合的extreme point来寻找极值的了。当然了如果深究细节还是有些不同,但是通过凸优化的这个性质,可以初见端倪。

小结

这一节我们给了一些优化的实例,并从相对high-level的层次上对优化目标的设计思路做了简单的分析。当然了除此之外,我们还给出了很多凸优化的与”凸“有关的分析性质,因此风格和《数值优化》有些不同。了解这些证明多半是为了让喜欢这一方面的朋友们能够看得舒服,看得过瘾。当然如果对这一块不感兴趣,或者更加关注凸优化中与算法相结合的部分,那么理论的部分跳过就好


欢迎社会各界加入『运筹OR帷幄』算法知识星球!

随着算法相关专业热度的提升,考研读博、留学申请、求职的难度也在相应飙升,『运筹OR帷幄』建立了【算法社区】知识星球,涵盖运筹学、数据科学、人工智能、管理科学、工业工程等相关专业,集结社区60W+专业受众的力量,提供给大家一个共同的学习交流平台,结交志同道合的伙伴。


更多星球福利内容,请戳《知识星球 | 『运筹OR帷幄』数据&算法社区》了解更多~

# 加入知识星球,您将收获以下福利 #

依托『运筹OR帷幄』60w+受众(包括名校教授|博士和名企研发高管)和60+细分群组的技术交流

海量学界|业界(独家内推)招聘|实习机会发布,申请|求职面试经验交流

数学模型|算法|论文|学习资料分享与提问,倡导同行交流,寻找志同道合的“队友”

鼓励大家分享和互动,每月开展一次“人气话题”和“人气回答”评选,百元红包奖励

每月一次“领读计划”带读Paper|技术推文等线上小组学习及各大城市线下Meetup免费入场资格

嘉宾做客“OR会客厅”,分享学习|留学申请|考研考博|发表Paper|职业发展经验

每月一次“行业InTalk”,与业界大佬直播交流行业背后的数据和算法业务逻辑

leetcode刷题小组、解读经典教材、带打天池/Kaggle/DataCastle等数据科学竞赛等项目陆续开发中...




相关文章推荐

点击蓝字标题,即可阅读《OR Talk NO.22 | 李玉喜博士: 深度强化学习进展:从 DQN 到 Agent57》


其他

OM | YouTube深度学习推荐系统的十大工程问题


Clubhouse线上会客厅

北京时间2.25上午8点(美东时间2.24晚7点、柏林时间2.25凌晨1点), 【运筹OR帷幄】创始人覃含章、留德华叫兽将在clubhouse聊聊"运筹学与人工智能的交叉应用"。现在就在clubhouse上follow【留德华叫兽】吧~



本文福利

可以在 公众号后台 回复关键词:“ 网盘 获取大量由我平台编辑精心整理的学习资料,如果觉得有用, 请勿吝啬你的留言和赞哦!


—— 完 ——




文章须知

文章作者:学弱猹

责任编辑:学弱猹

审核编辑:阿春

微信编辑:玖蓁

本文转载自公众号 学弱猹的精品小屋(ID:cha-diary)

原文链接:凸优化(1)——引入,优化实例分析,凸集举例与相关性质