如何从零开始学习凸优化？

Ilingis · 发表于 2022-1-23 21:20

我是学机器学习时，发现凸优化，然后直接看书的。就是boyd这本，从国家图书馆借的中文版。大概看了两个月。看着这本书很厚，但是我感觉是偏工具的，跟线性代数学起来感觉不一样，线性代数学完感觉很完整的了解了一个体系。这个感觉就是一个工具。所以看起来也比较快。我觉得就两部分，第一部分（2-5章），就是凸集、凸函数、对偶性，这些概念。然后就是算法（9-11章），无约束最小化，等式约束最小化，内点法。书中第二部分是应用（6-8章）我没有看。

我建议直接看书，第一部分（2、3、4、5章）：理论，第三部分（9、10、11章）：算法。第二部分：应用，可以跳过。

maltadirk · 发表于 2022-1-23 21:28

一、先给大家推荐一本凸优化的经典教材。（可能很多人都已经看过了，或者至少听说过）
《convex optimization》，作者是Stephen boyed，斯坦福教授
这本书主要是面向实际应用。书中提供了凸优化的理论框架，但不强调复杂的定理证明。特色是有着很丰富的实例，实例涉及广阔，涵盖通信，金融，机器学习等等。
Stephen教授在个人主页上提供了免费电子版本，而且还包含了习题以及相关数据和程序的下载。课程的讲义也可以在网站上找到。
http://www.stanford.edu/~boyd/cvxbook/

二、除了书籍，再推荐一门视频教程：矩阵与凸优化
这门课程不敢保证你学完就能彻底掌握凸优化，但是保证入门是没问题的，一共分6节课程，价格也不贵，只有1块钱，可以配合Stephen boyed的书一块学习。

七彩极 · 发表于 2022-1-23 21:30

浅见：先从线性规划开始，然而是凸优化基本问题，到理解拉格朗日乘子法（尤其是KKT条件衍生出一堆神结论）（至此，机器学习里面很多约束优化的问题比如SVM等就可以自己推导对偶形式了），再就是非线性规划对偶理论尤其是原始-对偶内点法，边学边实现相应的算法，会深刻一些。

Ylisar · 发表于 2022-1-23 21:37

谢邀！

说几条基本的，欢迎补充、指正。。

啥是凸？两点间线段都被包含在这个集合里，就是凸集。由此，香蕉不是凸集，足球是。
判断是否凸？（1）定义法（2）归类法（知道常见的凸函数类型，比如线性的、指数函数，然后对号入座）（3）能求导的函数用求导法，定义域内二阶导>=0是凸（4）用一些有名的不等式去求证，比如三角不等式证Norm函数是凸的
很重要一点：凸的有全局最优解
善用对偶
凸函数的一些基本换算后还是凸的，比如max {f1,...,fn} 还是凸的，如果f_i, i=1...n是凸的，画个图感知下，然后用定义法证明看看

2. 边用边学。

mastertravels77 · 发表于 2022-1-23 21:45

看 Sebastian Bubeck 的两本 survey。不过这两个survey并不会教你一些很基本的技巧，比如在优化中会用一阶Taylor展开来近似一个凸函数。我个人暂时也没找到技巧很丰富的textbook或者survey。
不要看Boyd，Boyd这书净讲一些有的没的。特别是给了很多屁用没有的例子，一句话讲清楚的事情非要写个两三页。当然，也不排除老大爷骗稿费养家糊口的可能，这都是人之常情，无可厚非。
多看论文，总结别人的思路和技巧。找一个小方向，每天坚持看一篇，写一页笔记和总结。

KaaPexei · 发表于 2022-1-23 21:53

Boyd的convex optimization很大很厚的，我不建议对着书学。他有开过相关的课，有些课件可以照着来学习一下。还有，很多其他老师也都有convex optimization的课的网页也都可以参考的。研究里碰到了问题反过来查那本书可能会更加有帮助吧。
还有就是Haven Jiang说到的，学习一些linear programming和nonlinear programming的基础会方便对后面的convex optimization的理解。

LiteralliJeff · 发表于 2022-1-23 21:56

Boyd的书讲的确实比较多，但是感觉不是很系统，而且知识点比较偏基础。入门阶段可以适当过一遍。想要更系统地学习凸优化，建议看这本书：Introductory Lectures on Convex Optimization - A Basic Course | Yurii Nesterov | Springer
这本书逻辑脉络清晰，对于bound证明推导很详细，非常适合进阶学习。

xiaozongpeng · 发表于 2022-1-23 21:59

如果您的分析基础过硬的话不用学直接读paper即可

fwalker · 发表于 2022-1-23 22:00

推荐凌青老师的凸优化视频教程（BILIBILI)上就有，加上我自己详细整理的笔记:
CVX-note/cvx-note.pdf at main · weiguowilliam/CVX-note (github.com)关于这门视频课程的更多信息，可以参考我的专栏：
渊池：教程推介 & 独家资源：《39个小时学会凸优化 - 凌青》

量子计算9 · 发表于 2022-1-23 22:07

先看本科生的运筹学教材，目的是了解最优化。有了基础后，再学习研究生的最优化理论以及boyd的凸优化这本书。

		自动登录	找回密码
密码			立即注册