为什么凸优化这么重要？

super1 · 发表于 2021-7-4 06:39

有很多水平很高的回答珠玉在前，我也努力和分享自己的一点体会。
凸优化的重要性
凸优化的重要性在于凸函数有很好的性质，那就是局部最优点就是全局最优点。所谓局部最优点，简单地理解，就是梯度为0的点。为什么局部最优点就是全局最优点呢？凸函数有这样的一阶刻画（一阶的意思就是用梯度来刻画凸性）：
$f(y)-f(x)\ge \nabla f(x)^\top (y-x)$
上面这个公式大家画个函数图像就能很直观的理解。把上面的公式移项之后，就有
$f(x)\le f(y)-\nabla f(x)^\top (y-x)$
如果说在x点的梯度是0的话，我们就有
$f(x)\le f(y)$
注意到y是任给的，所以x这个点实际上就是全局的最优点（之一）。
那这样有什么好处呢？大家想想梯度下降，梯度下降是这样的迭代
$x_{k+1}=x_k-\alpha_k\nabla f(x_k)$
这是过程考虑就只有在当前点的梯度这个局部信息。而它的终止条件是梯度为0或者很小的时候就可以终止了。当它终止的时候，我们知道这个点会是一个局部最优点。那么自然的问题是，梯度下降算法终止的点是不是全局最优呢？我们有没有必要再去看看别的地方的点呢？如果这个函数是凸函数的话，那回答就是不必了。
反过来想，如果这个函数是非凸的，当梯度下降算法终止，我们达到一个局部最优点的时候，我们没法确定这个点有多好。我们完全可以在另一个算法没有触碰到的区域，挖一个很深很深的井，在那里藏着全局最优，那么这个局部最优点有可能任意地差。
一言以蔽之，凸优化事实上标志了优化里面可解（tractability）和不可解（intractability）的分野。
关于凸优化的应用和非凸优化，下次有空再说吧。

RedZero9 · 发表于 2021-7-4 06:46

首先，优化领域只有两种问题可以认为是完全可以解决的，那就是最小二乘法和线性规划优化问题。哪怕是凸优化问题，也并没有定论一定能解决。所以“现有优化方法都能解决”是一个错误的表述。

其次，凸优化之所以重要是因为以下几个原因：

1. 每个初学优化的人基本上都是从线性规划开始的，线性规划也是凸优化的一种。
2. 由于线性规划的局限性，现实问题很少能够建成线性优化的模型。而凸优化的范畴会更广一些。
3. 凸优化问题尽管并没有被完全解决，但也是一个相对比较成熟的“技术”（实际上，如果你读了Boyd的《凸优化》这本书，凸优化由于还没有行业公认的通行解决方法，因此还不能称之为技术）
4. Boyd（斯坦福大学）同时称：我们可以期待凸优化在最近几年内被完全解决，从而成为一种“技术”，“基本上，如果你把一个现实问题建成凸优化问题模型，你就可以认为这个问题已经被解决了”。
5. 在非凸优化中，凸优化同样起到很重要的作用
1）当你要解决一个非凸优化问题时，可以先试图建立一个简化多凸优化模型，解出来以后作为非凸问题的一个起始点。
2）很多非凸优化问题的启发式算法的基础都是基于凸优化
3）你可以先建立非凸优化的松弛问题，使用凸优化算法求解，作为非凸优化问题的上限或下限（bound）

说到优化的本质，其实是用数学方法解决现实问题。当你在建模时，难免会简化现实问题，也就是我们通常意义的“模型”。
在建模的时候，如何简化现实问题就显得很重要了。
你当然可以做很少的简化，几乎把现实问题完全搬进来。但这样很可能导致计算压力过大。
你也可以做比较多的简化，将原问题建立成一个凸优化问题，这样子就牺牲了准确性保证了效率。

如何在上面两种情况之中取一个合适的平衡点是优化的艺术。

以上内容基本上都出自Boyd的《凸优化》一书。

Mecanim · 发表于 2021-7-4 06:55

凸优化（Convex Optimization）之所以重要是因为它是所有优化问题中最容易解决的。凸优化包含但不限于线性优化（Linear Optimization）以及一些具有特殊性质的非线性优化（Nonlinear Optimization）。凸优化之所以‘容易’是因为任何可证明的局部最优解（Local Optimal Solution）都同时为全局最优解（Global Optimal Solution）。换句话说，一旦你找到了一个局部最优解，那么它一定是你能找到中最好的（也就是全局最优的）。之所以说它重要，我认为有两点原因：1. 它是所有优化问题中最简单的，很多复杂的算法要基于凸优化，因此很重要； 2. 线性优化是所有优化中最为基本的，一般学习优化算法要从线性优化开始。
一些个人的观点，欢迎批评指正和补充。谢谢！

ainatipen · 发表于 2021-7-4 06:59

我是学机器学习的，也学过凸优化。
从结论上来说，凸优化对于主攻机器学习的人来说，有用，但不是特别重要。

首先凸优化是一个强大的工具，因为它的应用非常广泛，很多非常复杂或者计算难度非常大的都可以应用一个良好的模型和凸优化去解决。

但是学机器学习的人，有的时候目光太局限与机器学习问题了，什么都是给你输入输出数据集，然后training出结果，对这些人来说凸优化就只是剃度下降和统计剃度下降。但是现实中有很多问题并不是这样的，没有数据集，然而很复杂，这个时候很多机器学习方面的人就会说，这种问题我解决不了。数据集都没有，我怎么拟合，分析？
这个时候一个学过凸优化的人，就可以解决这一类问题。如果对凸优化有所研究，加上有良好的建模能力的人，就可以更好更完美的解决那些问题。

总的来说凸优化扩展了你解决问题的能力和范围。

说回机器学习，其实凸优化有也是很多人研究的一个重点。大部分人接触深度学习都会觉得能理解，但是感觉很难把握住那个数学细节。你会用神经网络这样生物的概念去描述它。但是作为一个纯数学的东西，深度学习却需要生物概念去描述和理解它，会让很多人很难受。因为每一个搞数学的人都想从理论分析它，掌握它。

所以在机器学习学派中，有一类人，他们完全基于数学去推导，理解机器学习的算法。特别是在传统机器学习领域，几乎很多算法都被吃透了。那么当然数学家也不会放过优化这个过程，他们会借助凸优化分析收敛速度，效果，以及期望。

但是为什么说凸优化没有那么重要呢，原因是现在机器学习的瓶颈并不在优化。第一在准确性上，即使凸优化拿到了最优解，结果效果依然不好。原因是模型并不够好，如果你用一个不怎么好的模型，就算用了最好的优化算法，也无法打败用梯度下降的神经网络。其次在速度，效率上也多少有类似的境遇。所以凸优化在现在机器学习的发展中，有很大用处，但是却不是瓶颈，所以并不太重要。

现在机器学习领域更加渴求在神经网络这种高度抽象非凸非线性的模型中，有更好的优化方法，但是这个命题实在太大太难，非一日之功也不是一个领域的问题。凸优化一定程度上肯定能指引我们去解决这个问题。但是是否是最终的解决之道，还是未知数。

闲鱼技术01 · 发表于 2021-7-4 07:00

是谁告诉你，现有的优化方法都能解决的？！
--------------------------------------------------------------------------

好吧，来好好回答一发。
有感觉有多少问题多符合凸优化条件的呢？
实际中并不多。
为什么非得是凸优化这么重要？
因为这是一类我们目前能很好解决的问题。我们关注凸优化很大程度上是因为这是目前能很好解决的一类问题。（有点像：我们的钥匙掉在了酒吧，但是我们在路灯下找，因为路灯下比较亮。）
现有的优化方法不是都能解决吗？
现在大量NP hard的优化问题都是搞不定的，无法得到全局最优解。比如TSP问题。准确来说，相比于能搞定的问题，更多的问题都是搞不定的。
那凸优化又有什么用呢？
凸优化的好处在于，很多实际的问题可能未必是凸的，凸优化提供了一个思路，将其转换为凸问题从而解决。若干解决凸问题的算法，比如gradient descent也都可以用在非凸的情况，只是不能保证全局最优。具体说，可能更加多一些，看看专业的书籍吧。
比如，入门可以Stephen Boyd的Convex Optimization
https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

DungDaj · 发表于 2021-7-4 07:10

凸优化问题性质好（凸性保证局部最优就是全局最优），虽然有时候还要再多加些假设（比如李普希兹连续，等等）。

不知道题主是做什么方向的，显然不是所有理工科的同学都需要凸优化这项工具，题目中所谓的『好多人都在学习凸优化』肯定是指一个圈子内吧？还请题主明示！了解题主所处领域会方便其他人回答。

优化圈子自不必说，肯定要学。此外一些管院做运筹学的也需要凸优化。做机器学习(统计学习)的人，肯定也需要学习凸优化，在机器学习圈子内往往不论模型无论凸不凸，都可以用凸优化算法求解，因为用凸算法求得一个非凸问题的局部最优解也是一个不差的解。

RhinoFreak · 发表于 2021-7-4 07:16

有个cvx，可以碰碰手气，看你的问题能不能刚好被解出来

xiangtingsl · 发表于 2021-7-4 07:25

凸优化之所以重要，是因为在所有的优化问题中，它是最容易被解决的，因此它的局部最优解也是全局最优解，而对于非凸问题，很容易陷入局部最优，无法找到全局最优。这里说凸优化最容易被解决，也是相对非凸优化来说的，但看凸优化本身，它并不简单，并且包含了很多内容，主要研究定义于凸集中的凸函数最小化的问题，方法包括但不限于单纯形法、内点法、捆集法以及次梯度法等。
可能会有人问，生活工作中，很多问题根本无法被假设为凸优化的问题，那么凸优化的意义何在呢？因为科学研究从来都是由易入难，从简单的开始，一点点的将研究深入，从而解决更加复杂的问题。虽然生活中很多优化问题都是非凸的，但可以将其近似为凸问题，从而求解最优解。同时，很多非凸优化问题的求解，都是以凸优化为起点。在解决非凸优化问题时，采用的启发式算法往往也会与凸优化的技术相结合。
最后，对于一个刚进入优化领域的人来说，凸优化是最容易入门的，有利于加强初学者对整个优化领域的认识。
<hr/>此为PK入驻导师或往届学员撰写，更多干货或需要留学、考研/保研的背景提升、科研论文辅导服务，请关注微信公众号：Paper King。

zt3ff3n · 发表于 2021-7-4 07:31

当你发现网络中经典的tcp拥塞控制其实就是凸优化问题中拉格朗日方法的分布式应用，当你发现频谱资源分配的注水原理也是凸优化中拉格朗日方法的应用，当你再发现传感器网络里面最有观测值的确定也可以用分布式凸优化来描述，你就知道凸优化多重要了。即便是在这几年Neely搞了一套网络随机优化理论的情况下，凸的在线优化仍然很重要。

只有不要脸，万物皆可凸，只要是凸的，那就有千千万万一定能找到最优解的方法。

zt3ff3n · 发表于 2021-7-4 07:36

因为一旦你把它变成凸的，
就一大套公式定理可以套了。
剩下的，一大帮前人帮你做了很多事，这就是站在巨人的肩膀上解题了～

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