我的凸优化学习之路

发表于 | |
字数统计: 3,050 | 阅读时长 ≈ 10

“凸优化理论真的很美”这是我学习完之后得到的切身感受。然而，在没认识到庐山真面目之前，她给我的感受却恰恰是个“冰山美人”，让人即爱又恨。明明知道，她在工程中具有非常多的应用，但各种技术细节却总让我冥思苦想，真是个磨人的小妖精！

本来我的课题是多目标优化，主要研究内容是将智能优化算法扩展到多目标优化领域。涉及的优化算法主要是遗传算法，差分进化，粒子群算法等。读的文献清一色地“鼓吹”智能优算优于传统的（基于梯度的）优化算法，如最速下降法，牛顿法，拟牛顿法等。可以说，我跟传统的数学优化算法无缘，大家楚汉之界，泾渭分明。

然而，古人云“天下大事，分久必合，合久必分”，近几年，多目标优化领域最新的研究方向就是将智能优化算法与传统的优化算法相结合。在这个方向上，华人学者张青富提出的MOEA/D是典型代表，该算法的核心思想是将多目标优化问题通过权重向量转化为多个单目标优化问题，并同时求解。沿着这个思路，我想寻找创新点。

工欲善其事必先利其器，为了打基础，我需要系统地学习下最优化理论。可是，之前研究生课《最优化理论》早就被我忘得一干二净(事实上，我不确定上过这门课)。那就只好自学。翻开当年的课本，清华大学陈宝林的《最优化理论与算法》，满页的公式对于非数学系的我真是相当不友好。如果没有人教，自学的话相当吃力，至少单纯型法（Simplex Method），我当年是看不懂的。

于是在网上寻找相关的视频教程，发现都是运筹学的相关课程，内容又乱又杂，良莠不齐，很是让人失望，几乎没有人讲得清晰透彻。偶然间，看到加拿大维多利亚大学陆吾生教授在华东师范大学讲授的暑期课程，如获至宝。陆教授写了一本书《Practical Optimization Algorithms and Engineering》，而该课程基本上就是按照这本书的内容讲授，只不过速度比较快。陆老师讲课深入浅出，非常让人容易接受。课程内容也是干货十足，不仅有传统的线性规划，还讲到了正定规划和多项式规划，在我看来真的是诚意十足，眼界大开。这里不得不吐槽下国内很多老师的讲课，很Boring，很多问题只告诉你怎么做，却不告诉你为什么？这样考试可能会得高分，却不是真正的做学问，学完之后很快就会忘。“授人以鱼不如授人以渔”！（陆老师2016年在我校讲授过机器学习的课程，当时没得到消息，没去听课，甚是遗憾）。

学习完陆老师的课之后，就接触了凸优化领域相当著名的一本书，美国斯坦福大学Boyd教授(2017年当选中国工程院院士)所著的《Convex Optimization》。怀着激动地心情翻开前几页，心情down到了谷底，这TM都讲的什么？相对内点，对偶范数，凸锥，逐点上确界等等概念接踵而至，劈头盖脸，我怎么感觉自己什么都不会了？凸优化真的这么难么？真是备受打击！不得已，这本书就被我束之高阁了。

又过了一段时间，因为课题需要，研究了一下图论中的二分图最大权匹配问题，自然而然地涉及线性规划问题(Linear Programming)。然后就在网上找了台湾国立交通大学的公开课，上面有美国北卡莱罗纳大学方述诚教授暑期课程线性规划，就像当年看陆吾生教授的课一样，感觉棒棒哒！当学生能够遇到这样的老师真幸福至极。方老师采用启发式教学，很多概念都会用几何的语言解释，学习的过程畅快淋漓。记得当年在寝室，一看就是一下午。上完课的收获就是，我感觉我自己智力还在线，内功已经修炼到一定程度，可以攻克凸优化这个大山了。另外提一点，方老师开设的另外一门课《非线性规划》也是非常的好（还未看完）。

接着再次翻看Boyd的《凸优化》，突然发现貌似没有以前那么难了，很多概念能模模糊糊地看懂了。但还是感觉不顺畅。

于是再次求助万能的网络，找到了印度的公开课网站上面有众多高质量的课程，这些课程多数由印度理工学院（相当于国内清华北大）所提供。其中《Convex Analysis》这门课看了前10课吧，总结下来，干货十足，但是感觉更像是数学系的课程，不太适合工科。另外一点：印度人的英语真的是让人蛋疼。所以作罢，等有时间再看吧。（另外，我觉得我越来越像数学系的了，居然对抽象代数和我微分几何感兴趣）。

我在网上有猎奇的嗜好，所以会在AMAZON上搜索凸优化相关的图书，偶然间遇到《Optimization Model》，看评论相当不错。然而网上却找不到电子版。所以只好求助图书馆，然而上海图书馆也没有这本书。我就只好把希望寄托在万能的淘宝上，结果惊喜地发现，有这本书的电子版，然后花费20元大洋购入。

草草地地翻看完这本书之后，感觉相逢恨晚——这真的是凸优化学习之路上的第一本书啊。整本书好像知道初学者哪里不会，哪里不懂似的，总是在你理解有困难的时候提供帮助。而且，本书在最开始还提供了线性代数的相关知识，对于后续课程的学习大有裨益，这也是Boyd的书所缺乏的。后来才知道，这本书是美国加州大学伯克利分校上课的教材，作者Laurent El Ghaoui确实了解学生学习的难度。

看完之后，再看Boyd的图书，就畅通无阻了。什么对偶理论，KKT条件，原本面目可憎，居然亲切起来。而且，居然能体会到，理论之美，前人怎么会有这样的想法，真的是太棒了。另外，Youtube上还有Boyd教授的上课视频作为补充（课程代号EE364A），虽然我认为他讲的课没有书写的好。

Boyd的《凸优化》分分为三部分：理论，应用和算法。理论部涉及：凸集合，凸函数，凸优化问题，优化条件，对偶等内容。应用部分主要是将工程中常见的问题抽象为凸优化问题。而算法部分主要是以内点法为主。

我个人认为，这本书作为凸优化的入门图书其实并不适合，主要原因有三点：

  1. 内容太多，中文版《凸优化》将近700页，对于初学者，学习主干内容就可以了，可能也就200多页，但是前提是有人指导。
  2. 算法内容有限，很多同学学习凸优化的目的可能更想学习算法部分，但该书主要讲解内点法，对于现在热门的次梯度法，近邻算子法等没有涉猎。
  3. 有更合适的入门书籍《Optimization Model》.

综上所述，我认为学习凸优化理论比较合适的路径是：

  1. 学习/复习线性代数和（少量）高等数学的知识。
    实际上，凸优化理论综合使用了线性代数和微积分的相关知识，比如方向导数，雅克比矩阵，海森矩阵，KKT条件等。这里强烈推荐MIT公开课《线性代数》，Gilbert Strang教授主讲，完全不是照本宣科，而是注重几何解释，非常具有启发性，学完之后，你会对线性代数有全新的认识。（没错，我是Strang教授的迷弟，为他疯狂打Call）

  2. 学习《Optimization Model》

    实际上，这本书分为三部分，分别是线性代数模型、凸优化模型、工程应用。时间紧的同学可以直接学习第二部分， 不过我强烈建议你把第一部分也复习一遍。另外，可以结合方述诚教授的《线性规划》(该课程已下线)，学习效果更佳。

  3. 学习《凸优化》
    有了1和2的准备，其实《凸优化》这本书已经差不多学习了80%，剩下的就是丰满自己的羽翼啦，把各个知识点串起来，形成网络。这一阶段，建议观看中科大老师凌青(现已跳槽中山大学)的视频课程《最优化理论》, 其内容安排和书基本一致，凌老师讲课细致入微，由浅入深，广受好评。

  4. (建议)如果你有时间，还可以再看看台湾Chong -yung Chi老师写的一本书《Convex Optimization in signal and communication》，虽然书名是一本应用导向的书，但其实主要内容是理论和算法，真正应用的部分不算多。关键是讲解很细致。

经过上述学习过程，对凸优化理论的认识就比较深刻了。比方说你能够对支持向量机（Support Vector Machine）的对偶形式（Duality）不再陌生。能够理解KKT条件中各条件的涵义，并能给出几何解释。但是，我发现以上所学习的也只是初级知识，内容大概是斯坦福大学的EE364A和加州大学伯克利分校EE127AT的内容，它们分别还有后续课程EE364B和EE227BT两门课。这两门课涉及的内容主要是次梯度法，近邻算子，ADMM等近现代优化算法，这算法主要是针对机器学习当中的问题而提出的，学习的难度也是不小，目前为也在学习当中（学无止境呀）。

在这个过程中，发现了卡内基梅隆大学CMU的教学视频《Convex Optimization》，可以在Youtube观看(机翻字幕)，包括2015 ~ 2019的视频，主讲人是Ryan Tibshirani（此君的老爸很厉害，同样在CMU，是Lasso的发明人），小伙子的Lecture做的很不错，就是语速很快。Lecture同样不错的还有UC Berkeley的EE227BT和UCLA的EE236B。下面列出目前学习的资料：

学校 教授 初级 进阶
Standford Stephen P. Boyd EE364A EE364B
UC berkeley Laurent El Ghaoui EE127AT EE227BT
UCLA L. Vandenberghe EE236A EE236B/EE236C
CMU Ryan Tibshirani 10-725 10-725

以上所列资料都是非常优秀的教程，在学习的时候可以相互参考。实际上，看他们的Lecture真是赏心悦目呀！

至于凸优化的应用，包络信号处理，图像处理，计算金融，控制，几何问题，试验设计等等。但我认为最重要的领域是机器学习（Machine Learning），实际上机器学学习里面绝大多数问题（除了神经网路）最终都可以归结为凸优化问题，因此，用凸优化的视角学习机器学习，真的是很惬意。

总结这几年学习凸优化的心得，发现凸优化其实并不难，关键是要用心学习。对关键概念的理解要深入，尤其是多思考，很过概念的引入动机是什么，多去发现问题，多去想反例。把知识形成网络，多思多考，才能融会贯通！

“吾生也有涯 而知也无涯”，希望大家在学习凸优化的路上痛并快乐着！