为什么凸优化这么重要？

acecase · 发表于 2021-7-4 05:44

看到好多人都在学习凸优化，但是有感觉有多少问题多符合凸优化条件的呢？为什么非得是凸优化这么重要？现有的优化方法不是都能解决吗？那凸优化又有什么用呢？

RedZero9 · 发表于 2021-7-4 05:48

谢邀。
题主主要提了两个问题，这边分别回答一下。这个回答基于我个人的经验，未必说的到位，请各位看官轻喷。
<hr/>1. 为什么凸优化重要?
各位答主们已经洋洋洒洒写了很多了。我这边简单来说就是两点，凸优化性质好，并且即使是日常生活中的许多非凸优化问题，目前最有效的办法也只能是利用凸优化的思路去近似求解。一些例子有：带整数变量的优化问题，松弛之后变成凸优化问题（所以原问题其实是凸优化问题+整数变量）；任意带约束的非凸连续优化问题，其对偶问题作为原问题解的一个lower bound，一定是凸的！一个更具体的例子，大家都知道针对带有hidden variable的近似求解maximum likelihood estimate的EM算法，或者贝叶斯版本里头所谓的variational Bayes(VB) inference。而原本的MLE其实是非凸优化问题，所以EM和VB算法都是找到了一个比较好优化的concave lower bound对这个lower bound进行优化。
这是什么意思呢？也就是说到今天2019年为止，我们还是只对凸优化问题比较有把握。当然有人可能要说了，现在各种深度学习中的优化问题都是极其复杂的非凸优化问题，不是大家也能解的挺好？这个问题的回答就更难一些，我个人观点，简单来说是这样，目前对于这些非凸优化问题取得的算法理论方面的突破大体其实归结于找到这些非凸优化问题中“凸”的结构。这也是为什么我们看到一阶算法（SGD, ADAM等）仍然大行其道，而分析这些非凸优化算法的时候其实很多的lemma（引理）仍然是凸优化（凸分析）里的引理或者引申。举个例子，我们大家都知道凸函数的各种等价定义。而在Zeyuan Allen-Zhu的一系列非凸优化算法的文章中所谓的非凸性的刻画仍然是基于此衍生出来的：
来源：Allen-Zhu, Zeyuan. Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter. International Conference on Machine Learning. 2017.
我们知道它里面这个刻画非凸性的参数 $\sigma$ 如果取成0，那就等价于凸函数的定义，如果取成负的，那么实际上就是所谓strongly convex，而如果是正的，就变成它这里的non-convexity了。实际上，现在非凸优化里面很多的非凸性刻画都是脱胎于凸优化，比如prox regularity之类的，或者一些更弱的convexity定义（这在经典凸分析里就已经有不少研究了，quasi-convex，psuedo-convex等等），这里不再赘述。
个人认为，我们能真正一般化地解决非凸优化问题，那肯定是要对一般的混合整数（线性）规划（MILP, mixed integer linear programming）要有好的办法求解才算。因为任意一个非凸优化问题，都可以用很多的分段线性函数逼近，最后变成一个MILP。当然，因为P!=NP这个猜想的存在，这件事情在理论上肯定是hopeless，但是在实际当中，基于硬件能力的提升，还有比如量子计算机一类的新技术，我个人对人类未来能够在实际中求解MILP还是持一个比较乐观的态度。到那个时候，我觉得我们才能说传统的凸优化理论才是真正过时了。
<hr/>2. 现有的优化方法不是都能解决（凸优化）吗？那凸优化又有什么用呢？
首先先明确一点，凸优化难吗？嗯相比非凸优化，各种NP-complete问题，凸优化里各种P问题，那肯定是简单的。然而，在实际当中，我们完全不可能满足于有一个“多项式时间算法”就好了。
我们知道，运筹学，优化问题，反映到现实世界里面就是各种数学建模问题。这些问题，普遍地出现在航空业、金融业、广告业、电商零售业、能源业、医疗业、交通业等各个领域。我们必须要明确一点，计算复杂性理论（P,NP这套东西）在实际当中其实是没什么用处的。嗯，NP hard, NP complete问题很难，没有多项式时间算法，但如果你实际的问题规模不太大，比如几十个城市的旅行商问题（TSP, travelling salesman problem），几十x几十的图上的NP-complete问题，是不是很难？然而现在2019年，你在iphone上下个app，一部小小的手机不要几秒钟就能给你算出最优解。（实际上，他们这个app，1000个左右城市的TSP iphone也顶多要算个几小时就能找到全局最优解，无近似）
TSP求解app，当然，这得益于他们家目前行业领先的解大规模TSP底层算法...
与此相对应的，即使是一个P问题，但是如果实际当中你的问题规模超级大呢？实际上反而这个问题会让你更头疼的。举个例子，比如现在优酷、天猫、京东、亚马逊这些个平台，每天你登陆网站，它在推荐栏都需要根据你的历史活动记录决定推荐哪些产品给你。这个在线推荐算法，本质上只是需要求解一个线性规划问题（LP, linear programming, 比一般的凸优化还简单），甚至还不是一个一般的线性规划，有个专门的名字叫做packing LP，这类packing LP理论上可以有跟问题规模呈线性的复杂度的算法（忽略log项，跟排个序差不多...）。听起来是不是很简单？然而，实际这些问题的规模无比巨大，每天这些平台上线人次可以以亿记，这些平台可以推荐的商品也是至少百万千万规模的。。而且实际问题还有各种各样的现实约束，比如我们希望我们的算法可以完全在线更新（online，甚至是streaming algorithm），我们的算法需要灵活运用存储数据的数据结构，需要利用计算集群的并行能力，分布式能力，这也是需要非常非常专门的（一阶）优化算法设计的。。这边就不再多说了，因为我个人确实在之前公司实习的时候，发现中国最好的IT公司面对这类海量规模的“简单”LP，实际上远没有能力去完美地求解。。
因此你说现有的方法能解决所有的凸优化问题，但从实际的角度其实还差的远。事实上，目前的大公司面对如此规模的优化问题，也就LP还可以勉强接受，像是什么second-order cone prorgamming (SOCP), semidefinite programming (SDP)根本目前实际中都不可能大规模求解。而这两类问题在理论上还仍然都是“线性”的，因为可以写成linear conic programming，所以就更不要说一般的带约束的凸优化问题了。实际上，在这个方面，无论是求解器（solver）还是更好的理论算法的开发都还有大量的研究空间。比如，SDP实际当中的大规模算法设计目前来看还基本一片空白，有很多很基本的问题都还没有在理论上得到满意的解答（像SDP其实和另一类凸优化问题只有一丝之隔，copositive programming，而这类凸优化问题的计算复杂度却是NP complete的，所以即使是凸优化也未必复杂度就容易！实际上，所有mixed 0/1 nonconvex quadratic program都可以写成copositive program这个凸优化的形式。两者的算法设计也因此都很蛋疼）。。还有这么多没有解决的问题，又如何能说凸优化的问题都已经被“解决”了呢？
至于具体如何把mixed 0/1 nonconvex quadratic program写成凸优化形式，这是个很cute的结果，有兴趣的同学可见我这篇专栏文章的第二部分。
覃含章：Copositive Programming简介<hr/>随手写写没想到也吐了不少嘈，我这边最后就再总结个几点吧：

做研究过程中，切忌轻易下结论。

基础永远是重要的

作为优化研究者，埋头研究的同时，一定要睁开眼睛看看业界的实际情况

Ylisar · 发表于 2021-7-4 05:54

觉得有必要写在前面的话：本答案主要面向运筹学、管理科学、运营管理、工业工程、系统工程等相关专业的以及其他对凸优化感兴趣的朋友。本人对机器学习、深度学习以及人工智能所知甚少，在此不便置喙。
以下是原答案。
我基于自己的理解聊一聊凸优化，具体实际中的凸优化的用处各位答主也给出了相应的答案，在此就不赘述。因为不了解题主的背景和基础，就尽量浅显地谈起吧，不会放太多理论推导。不过在看我的回答之前，可以先了解下凸函数、凸集、凸锥（简称“三凸”）的定义。
首先，我们还是要看下，什么是凸优化？抛开凸优化中的种种理论和算法不谈，纯粹的看优化模型，凸优化就是：1、在最小化（最大化）的要求下，2、目标函数是一个凸函数（凹函数），3、同时约束条件所形成的可行域集合是一个凸集。以上三个条件都必须满足。而世间万物千变万化，随便抽一个函数或集合它都可能不是凸的。
所以，先回答题主的第一个问题，这个世上的绝大部分优化问题当然不是凸优化问题。既然如此，为什么凸优化这么重要呢，以及凸优化有什么用呢？（另外，凸优化并不能看成是某一种优化方法）无非三点：
1、还是有相当一部分问题是或等价于凸优化问题。有许多问题都可以直接建立成凸优化模型（比如：线性规划LP（Linear Programming）、某些特殊的二次规划QP（Quadratic Programming）、锥规划CP（Conic Programming）其中包括：要求约束中变量落在一个二阶锥里的二阶锥规划SOCP（Second Order Cone Programming）、要求约束中变量是半正定矩阵的半定规划SDP（Semi-Definite Programming）等）。以上这些类型，总之就是要符合凸优化上述的要求。需要说明的就是，许多可行域都可以看作是凸锥（Convex Cone）的交集，所以将以上一些类型的约束混合起来，依然是凸优化问题。
另外还有一些问题，可以等价的转化为凸优化问题。例如 Linear-Fractional Programming (LFP)，目标函数是两个仿射函数（Affine Function）的比，约束是一个多面体。这种目标函数具有既是拟凸又是拟凹的性质，通过一个叫做 Charnes-Cooper transformation 的转化，可以变成一个线性规划。同时，如果我们要最大化 LFP 的目标函数，且其约束仅是一个0-1整数约束（这显然不是一个凸集），我们可以将其直接松弛（Relax）成0到1的约束，并且和原问题等价。因为最大化拟凸函数，最优值一定可以落在可行域的极点上。这个结论可以用来帮助解决 Multi Nomial Logit（MNL）选择模型下的商品搭配问题（ Assortment Optimization）。
又例如，与组合优化相关的整数规划模型里，当最小化一个线性函数 $c^Tx$ ，变量 $x$ 只能取整数，约束条件为 $Ax\geq b$ 时，如果 $b$ 为整数向量且 $A$ 是完全幺模（Totally Unimodular）的矩阵，我们可以将原问题松弛，即将整数约束去掉，变成线性规划。此时的最优解必然仍为整数，且即是原问题的最优解。这一结论经常用于调度（Scheduling）问题和指派（Appointment）问题。以上两类问题即是与凸优化直接等价的问题，还有一些优化问题本身就是NP-Hard，怎么处理我们后面再说。
2、大部分凸优化问题解起来比较快，也即多项式时间可解问题（P）。如果你的问题能直接或间接（但必须是等价的）转化成上面我提到的那些类型，那恭喜你，后面的事儿基本就可以交给solver啦，当然大规模问题还需要考虑诸如列生成（Column Generation）之类的方法，提高运算效率。
那为什么大部分凸优化解起来比较快呢？这涉及到凸函数的局部最优即全局最优的性质以及凸集分离定理（Seperation Theorem）。我们形象一点来思考这个问题，而不拘泥于理论。如果了解凸函数（或凹函数）的定义，我们可以想象成站在函数的曲线上去搜索最优解，所要做的无非就是向下到底（或向上到顶），需要考虑的是用什么样的角度迈出第一步以及每的步子要迈多大才更快的到达最优值。同时，作为凸集的可行域，让我们更容易在有限范围内迅速锁定最优解，而不用四处打探。（以下为简单说明这个道理，脑补了一段情节，对理论熟悉的可以略过）
以线性规划为例（目标函数既凸且凹，所以最大化最小化皆可），想象你在目标函数那个超平面上一路狂奔，因为是最小化（或最大化），你得往觉得最轻松（或费劲）的下坡（上坡）方向跑，跑着跑着，你就碰到可行域这个多面体的墙壁了。没关系，你感觉贴着壁的某个方向还是可以轻松（或费劲）地继续跑，跑着跑着到了一个拐角，即所谓的极点。你觉得再走下去就费劲（或省力）了，这样就找到了一个最优的极小值（极大值），否则，你可以沿着墙壁继续走下去。如果，这个时候的可行域不是凸集，而是被人胡乱咬了一口，形成了凹凸不平的缺口。如上方法搜索，你可能已经到达这个缺口的某一个角落，前方已经没有任何能改善你可行解的道路了，你可以就此停止吗？不能！因为想象有另一个你，也如上所述，跑到了这个缺口的另一个无处可走的角落，他也认为自己可以停止了，那你们就还需要比较两个各自所在的位置的解，哪一个会更优。当然，可能还有第三个你，第四个你。。。但不要忘了，每一个你的搜索都需要时间，最终的比较也需要时间（除非你们之间没有缺口，可能都会继续跑下去，到达了一个共同的最优值）。所以非凸的可行域要比一个凸集的可行域麻烦的多。（注：以上形象化的描述的未必就是多项式时间的算法。现实中如单纯形法就不是多项式时间的算法，但实际运用中仍然很高效。）
当然，也有例外，即虽然是凸优化但不是多项式时间可解的。比如在约束中，要求变量是一个Copositive 矩阵或者 Completely Positive 矩阵，这两种矩阵所在的锥恰为对偶锥。此类问题很难解的原因在于，你要去检查一个矩阵是不是落在这样的锥里，就已经不是多项式时间可以解决的了，更不用说整个优化问题。
3、很多非凸优化或NP-Hard的问题可以转化（并非是等价的）为P的凸优化问题。并给出问题的界或近似。这对如何设计合理的算法，或衡量算法结果的优劣起到很大的帮助。非凸优化的问题基本上都是NP-Hard的，所以要找到其最优解，理论上是不确定有一个多项式时间的算法的，所以这时候会考虑设计一些近似算法，或者启发式算法，就要依靠凸优化。要把一个优化问题转化为凸优化的方法和例子有很多，以下试举几例说明。
对偶（Duality）是每个学习运筹学或者凸优化的人都必须熟练掌握的方法，对偶有很多种，本科运筹就教会大家写一个线性规划的对偶形式，高等数学里面也会提到用到拉格朗日乘子之类的约束优化问题，也即解拉格朗日对偶或者KKT条件。一般的，对于许多非凸优化的问题，我们仍然可以写出它的拉格朗日对偶。如原问题如下 $\{\min_{x}f(x),\ \text{s.t.}\ g_i(x)\geq 0\}$ ，拉格朗日对偶为 $\max_{\lambda\geq 0}\min_{x}f(x)-\lambda^Tg(x)$ ，其中 $\ g(x)=(g_1(x)...g_n(x))^T$ 。可以看到 $f(x)-\lambda^Tg(x)$ 是关于的线性函数，因此 $\min_{x}f(x)-\lambda^Tg(x)$ 一定是一个关于的凹函数。因此，由我们之前给的定义来看，拉格朗日对偶永远都是一个关于对偶变量的凸优化问题，并且根据弱对偶定理，可以给出原问题的下界。
松弛（Relaxation）也是常用的方法之一，在第一点里，我们举了一些例子可以通过松弛，去掉整数约束，使其等价为凸优化。通常情况下，我们松弛原问题，只能得到一个可行域更大的问题，如果原问题是求最小，则松弛后的问题的最优值一定小于等于原问题的最优值，这也是一种给出下界的方法。松弛不仅仅用于整数约束，只要利于将可行域非凸变为凸集皆可。例如，某问题有一约束为 $x^2+bx+c=0$ ，就不构成一个凸集，但等价于 $x^2+bx+c\leq 0$ 和 $x^2+bx+c\geq 0$ ，前一个不等式即构成凸集，因此我们可以将后一个不等式从约束中去除，就得到原问题的一个凸优化松弛问题。
我们还可以举一个同时用到对偶加松弛的例子，在第二点的最后，我们聊到Copositive（CoP）矩阵与 Completely Positive(CP)矩阵，他们的锥与半正定（PSD）矩阵锥的关系是 $CP\subset PSD\subset CoP$ 。组合优化中很多问题都可以松弛成一个Completely Positive规划（去掉一个矩阵为Rank 1 的条件），由于Copositive和Completely Positive互为对偶锥，所以我们可以先写出对偶，写成 Copositive 规划，然后在某些假设之下，能证明 Copositive 规划与原问题等价。当然，如果没有那些假设，还可以尝试将Completely Positive约束，松弛成半正定矩阵的约束，因为Completely Positive必然是半正定，同时还加上Completely Positive的性质，如矩阵的所有元素都大于等于0。这样我们就得到了原问题的一个凸优化且易解的对偶松弛问题，一个SDP Relaxation。
当然，相应的处理方法还有很多，面临一些随机优化（Stochastic Optimization）、机会约束规划（Chance Constrained Programming）、鲁棒优化（Robust Optimization）、离散凸优化（Discrete Convex Optimization）问题，还有更多其他的处理方法，就不在此一一道来。更多内容，可以看各位答案里推荐的书籍，都是经典教材。
综上三个方面，供题主参考，也请各位多多指教，谢谢！

xiangtingsl · 发表于 2021-7-4 06:01

理论上，凸性既具有良好的几何性质，比如分离平面和支撑平面，也具有良好的全局分析特性，比如subgradient。更重要的是，90年代以来，结构凸优化问题LP,SOCP特别是SDP，产生了高效的数值计算方法。在这之前，西方学者还以为SDP是很难计算的。SDP异常强大的建模和表达能力是凸优化火起来的重要原因。

良好的理论分析特性，高效的实际可计算性和强大的建模能力是大家选择凸建模的原因。注意，我这里说的是凸建模！科学研究的第一步是对实际问题抽象近似，建模成数学问题，这里有巨大的选择自由度！虽然非凸建模具有最强的表达能力，也最省事，代价却是理论上难以分析和实际中无法可靠计算！近十年来火的一塌糊涂的压缩感知，稀疏表示和低秩恢复都是由凸建模带动起来的！研究者们通过分析凸问题的性质来解释和理解真实世界的机理！要注意，很多这样的问题几十年前就已经有非凸的表达形式了，只有用凸建模才焕然一新！更进一步，通过对凸建模的深入理解，大家对具体的非凸问题，注意不是所有，开始利用特殊的结构特点做分析，得出了一些很深刻的结果，比如神经网络收敛到局部最优解，而不是平稳点，随机算法有助于逃离鞍点。但是，非凸分析几乎都是case by case，没有统一有效的手段，这与凸分析差别甚大。从这个角度来说，凸建模和凸优化是研究实际问题的首选！

凸优化都是可计算的吗？这个问题要放到information based complexity的理论框架下来谈。众所周知，椭球法或者各种切平面法能够在多项式迭代次数求得要求精度的解，这似乎意味着所有的凸优化都是多项式时间可计算的。这是一个错觉！大多数的半无穷凸优化semi-infinite convex optimization是不可计算的，因为目标函数和约束条件是多项式时间不可计算的。以椭球法为例，虽然迭代次数是多项式的，然而每次迭代需要计算函数值和次梯度，而这部分计算不是多项式时间的！最典型的不可计算的凸优化例子是协正优化copositive optimization。给个不可计算的具体例子吧 [1]，如下图。

最后，只需要引入无穷多个变量，几乎所有的数学规划问题都可以表示成凸优化问题！思路也非常简单直接，就是把约束域内的点换成对应的Borel概率密度函数，很自然的，目标函数和约束条件都可以写成概率密度函数的线性积分，也就是凸的。这就把问题变换成了求最优的概率密度函数，无穷多个变量，而其对偶问题则有无穷多个约束！例子见下图 [2]

再举个具体例子，SDP就可以如下表示[3]，其他非线性函数也可以类似表达。这丝毫不违背NP-hard理论，哈哈！这种dimension lifting的思路最为熟知的就是SDR！上面这个思路是现在做非凸多项式优化的凸近似研究的热点，用不断增大维度的有限维问题一步步逼近半无穷问题！已经有很多研究表明，有限维近似就可以准确求解原来的半无穷问题。

[1] Lectures on Modern Convex Optimization-Analysis Algorithms and Engineering Applications
[2] Introduction to Semidefinite, Conic and Polynomial Optimization
[3] Semi-infinite linear programming approaches to semidefinite programming problems

zt3ff3n · 发表于 2021-7-4 06:10

凸优化之所以重要，应当有下面几个原因：
1. 凸优化问题有很好的性质
众所周知，凸问题的局部最优解就是全局最优解（许多答主已经提到了）。不过，凸优化理论中最重要的工具是Lagrange对偶，这个为凸优化算法的最优性与有效性提供了保证。近些年来关于凸问题的研究非常透彻，以至于只要把某一问题抽象为凸问题，就可以近似认为这个问题已经解决了。
2. 凸优化扩展性强
前面提到，许多问题的关键是在于将问题抽象为凸问题。因此许多非凸问题通过一定的手段，要么等价地化归为凸问题，要么用凸问题去近似、逼近。典型的如几何规划、整数规划，它们本身是非凸的，但是可以借助凸优化手段去解，这就极大地扩张了凸优化的应用范围。
3. 凸优化的应用十分广泛
现实生活中确实有大量的非凸问题，但是并不妨碍凸优化在许多问题上都可以大展身手。往细了说，比如线性回归、范数逼近、插值拟合、参数估计，以及许多的几何问题；往大了说，在通信、机器学习、统计、金融等涉及优化、决策的研究领域，凸优化都是非常有效的手段。
4. 针对其他非凸问题的研究还不充分
凸优化之重要，从另一个角度说，就是我们没有找到很好的非凸优化的算法，这一部分还有许多学者都在努力。

以上是我在学习凸优化过程中的一点点感悟，藉当抛砖引玉了，欢迎讨论。
在我比较熟悉的机器学习领域，最近二三十年有两个算法相继成为机器学习应用的明星，一个是支持向量机（Support Vector Machine），一个是深度学习（Deep Learning）。SVM本身就是把一个分类问题抽象为凸优化问题，利用凸优化的各种工具（如Lagrange对偶）求解和解释。深度学习则是神经网络的又一次爆发，其中关键的算法是反向传播（Back Propagation），本质就是凸优化算法中的梯度下降算法，即使问题极度非凸，梯度下降还是有很好的表现，当然深度学习的机制还有待研究。
凸优化的重要性，在工程领域应该说是无可撼动的了。

mastertravels77 · 发表于 2021-7-4 06:17

之前看过Nesterov的 Introductory Lectures on Convex Programming 颇有一些收获，再这里就把Nesterov 关于凸函数的观点简单的解读一下。
若 $f\left( x \right) \in {C^1}$ 对于如下无约束的优化问题
$\mathop {\min }\limits_x f\left( x \right)$
我们都知道一个基本的事实是  是该优化问题局部最优解的必要条件。
这个条件被称为一阶必要条件，什么是必要条件呢，就是满足这个条件的不一定是最优解，而不满足的一定不是最优解。如果把在茫茫人海中寻找到你的最佳伴侣比喻成找到优化问题的最优解，那么这个一阶必要条件就相当于一个筛选条件，例如有房有车的。没房没车的人肯定不是最佳伴侣，下面仅仅在有房有车的人当中找最佳伴侣，这样事情会变得简单一些了。
一阶必要条件可以帮我们筛选掉一些肯定不是局部最优解的，让问题变得简单，但是这个一阶必要条件有两个致命伤：一是它是一个必要条件啊，必要条件多多少少看着就让人有点不爽。我们辛辛苦苦用梯度法，拟牛顿法或者共轭梯度法找到了一个满足必要条件的点，然后一阶必要条件告诉我们，这个点可能是最优解，也可能不是。二是该条件是针对局部最优解的，根本没谈全局最优的事情，能不能找到全局最优只能看运气喽，梯度法的初始点选得好兴许能找到，也兴许没找到。概况以上两点就是“局部最优不一定，全局最优全靠碰。”

那么到这里肯定就想问一下，有没有办法让这个一阶必要条件变成充要条件，同时让局部最优变成全局最优的情况呢？
答案是有的，对一些特殊一点的  而言，一阶必要条件会变成充要条件。
那这类性质非常好的函数长什么样呢？
答案是凸函数。

也就是说对于  是可微的凸函数而言，一阶必要条件就变成了充要条件，同时局部最优也升格为全局最优。如果各位想看该命题的严谨证明的话参考Introductory Lectures on Convex Programming 的chapter2即可。
到此为止，我们可以自信满满的说若  是可微还是凸函数的话，满足  的点， ${x^*}$ 一定是全局最优解。哈哈，梯度法，拟牛顿法或者共轭梯度法等基于梯度的算法都可以完完全全保证能收敛到全局最优解上去。
所以说对优化问题而已凸函数的性质简直好到爆炸啊。个人感觉这就是凸优化为何那么重要的原因之一吧。套用一句经典话语：优化问题的分水岭不是线性和非线性，而是凸和非凸。
更多运筹学和凸优化相关的知识和精品文章可参考『运筹OR帷幄』大数据人工智能时代的运筹学

ChuanXin · 发表于 2021-7-4 06:25

前言：运筹学在国内，远没有统计和人工智能来的普及。

相信很多人不知道，运筹学正是研究优化理论的学科（包括凸优化），而人工智能模型最后几乎都能化简成求解一个能量/损失函数的优化问题。
因此，我把它称为人工智能、大数据的“引擎”。

本文的详细版本已发表在 @运筹OR帷幄专栏：
离散/整数/组合/非凸优化概述及其在AI的应用 - 知乎专栏

言归正传，为什么凸优化这么重要？
1，首先大家需要知道Convex VS Non-Convex的概念吧？
数学定义就不写了，介绍个直观判断一个集合是否为Convex的方法，如下图：
简单的测试一个集合是不是凸的，只要任意取集合中的俩个点并连线，如果说连线段完全被包含在此集合中，那么这个集合就是凸集，例如左图所示。

2，凸优化-相对简单
凸优化有个非常重要的定理，即任何局部最优解即为全局最优解。
由于这个性质，只要设计一个较为简单的局部算法，例如贪婪算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收敛求得的局部最优解即为全局最优。因此求解凸优化问题相对来说是比较高效的。
另一个侧面，可微分的凸优化问题满足KKT条件，因此容易求解：
【学界】关于KKT条件的深入探讨
这也是为什么机器学习中凸优化的模型非常多，毕竟机器学习处理海量的数据，需要非常高效的算法。

3，非凸优化-非常困难
而非凸优化问题被认为是非常难求解的，因为可行域集合可能存在无数个局部最优点，通常求解全局最优的算法复杂度是指数级的（NP难）。如下图：
最经典的算法要算蒙特卡罗投点法了，大概思想便是随便投个点，然后在附近区域（可以假设convex）用2中方法的进行搜索，得到局部最优值。然后随机再投个点，再找到局部最优点--如此反复，直到满足终止条件。
假设有1w个局部最优点，你至少要投点1w次吧？并且你还要假设每次投点都投到了不同的区域，不然你只会搜索到以前搜索过的局部最优点。

4，为何要学习非凸优化呢？
因为现实生活中，几乎所有问题的本质都是非凸的。
把3中的图看作山川盆地，你在现实中有见过左图这么“光滑”的地形么？右图才是Reality！

5，凸优化为何这么重要呢？
科学的本质便是由简到难，先把简单问题研究透彻，然后把复杂问题简化为求解一个个的简单问题。
例如3中经典的蒙特卡罗投点法，就是在求解一个个的凸优化问题。
假设需要求解1w个凸优化问题可以找到非凸优化的全局最优点，那么凸优化被研究透彻了，会加速凸优化问题的求解时间，例如0.001秒。
这样求解非凸优化问题=求解1w个凸优化问题=10秒，还是可以接受的嘛！
【学界】非凸转成凸、约束转无约－运筹学和支持向量机中的拉格朗日松弛法

6，运筹学中线性规划与凸优化的关系
线性规划是运筹学最基础的课程，其可行域（可行解的集合）是多面体（polyhedron），具有着比普通的凸集更好的性质。
因此是比较容易求解的（多项式时间可解）。
如有兴趣，且听我唠叨一下关于运筹学的四个知乎 Live
7，运筹学中（混合）整数规划与非凸优化的关系
大家或许不知道，（混合）整数规划被称为极度非凸问题（highly nonconvex problem），如下图：
实心黑点组成的集合，是一个离散集，按照1中判断一个集合是否为凸集的技巧，我们很容易验证这个离散集是非凸的。
因此整数规划问题也是一个非凸优化问题，并且它也是NP难的。
那么整数规划的求解思路呢，也遵循了科学研究的本质，即被分解为求解一个个的线性规划（凸优化）问题。
感兴趣的朋友可以搜索参考下文：
【学界】混合整数规划/离散优化的精确算法--分支定界法及优化求解器

8，（混合）整数规划为何重要？
虽然时间是连续的，但是社会时间却是离散的。例如时刻表，通常都是几时几分，即使精确到几秒，它还是离散的（整数）。没见过小数计数的时刻表吧？
同样，对现实社会各行各业问题数学建模的时候，整数变量有时是不可避免的。例如：x辆车，y个人。x，y这里便是整数变量，小数是没有意义的。

8，深度学习为何非凸？
深度学习里的损失函数，是一个高度复合的函数。什么叫复合函数？好吧，例如h(x)=f(g(x))就是一个f和g复合函数。
当f，g都是线性的时候，h是线性的。但在深度学习里用到的函数，Logistic, ReLU等等，都是非线性，并且非常多。把他们复合起来形成的函数h,便是非凸的。
求解这个非凸函数的最优解，类似于求凸优化中某点的gradient，然后按照梯度最陡的方向搜索。不同的是，复合函数无法求gradient，于是这里使用Back Propagation求解一个类似梯度的东西，反馈能量，然后更新。

9，深度学习的优化问题在运筹学看来是“小儿科”
这句话可能会打脸大部分观众。
深度学习中的优化问题，虽然目标函数非常复杂，但是它没有约束阿，是一个无约束优化问题！
大家如果学过运筹学，就知道它由目标函数和约束条件组成，而约束条件，是使得运筹学的优化问题难以求解的重要因素（需要搜寻可行解）。
关于运筹学与人工智能更多的交叉与应用（自动驾驶），参见知乎Live：
理工科的你想要转AI？快上车！

总结：
机器学习、数据科学因为处理数据量庞大，因此研究问题主要的方法还是凸优化模型，原因正是求解高效，问题可以scale。
虽然目前还很小众，但是随着计算机硬件能力的提高，GPU并行计算的流行，以及（非）凸优化算法、模型的进化，想必非凸优化，甚至（混合）整数规划会是未来的研究热点。
这不，最近就有研究智能算法求解深度学习损失函数的paper了～
遗传算法，模拟退火算法，粒子群算法，神经网络等智能算法的作用？

纸上谈兵终觉浅
敬请关注『运筹OR帷幄』公众号，后台回复“学界”，进入运筹学-凸优化文件夹，获取凸优化经典教材。
<hr/>以上所有博文出自知乎专栏『运筹OR帷幄』：
『运筹OR帷幄』大数据人工智能时代的运筹学

扫二维码关注 @运筹OR帷幄公众号，加入全球运筹|机器学习|优化理论学者群交流：

JoshWindsor · 发表于 2021-7-4 06:26

比较系统地学习过数值优化和凸优化，首先，我觉得凸优化是一门比较高深学问，这门课即使是在斯坦福应该也是属于博士生级别的课程，stephen boyd讲的已经算是比较偏应用的了，那本书也是比较偏应用的，理论部分其实比较少，真正讲理论的《convex analysis》会比较好，可惜我自己也没能看下去，要看懂还是需要很强的数学功底的，所以，我其实比较怀疑有多少非数学系的人能真正懂凸优化。首先，这门课当然很重要，它会帮助你从high level去理解你常用的那些优化手段，比如我们都知道可以用梯度下降或者牛顿法来优化一个非凸函数，在这个过程中，我们已经用凸函数来对需要优化的函数做了局部近似，所以很多时候，一个非凸问题往往可以分解成多步的凸优化问题来求解，再者，很多实际问题，比如运筹，规划等，其实都可以转化成一个优化问题，然后利用凸优化手段来寻求局部或者全局最优解，所以运用的范围非常广泛，另外，凸优化理论，比如对偶理论也帮助我们从另一个角度来解决问题（任何原始问题的对偶问题都是凸优化问题，对偶问题相对于原始问往往更容易解决），利用对偶来解决优化问题的比较著名的例子就是SVM和ADMM算法，总之，凸优化是一门值得好好学习的基石课程。
另外，并不是很同意一些高票答案对凸优化的拔高以及对深度学习的贬低，从问题本身而言，深度学习的训练其实是一个更难的优化问题，我们甚至目前连理论都还没有，目前大家所了解的优化方法也都只是在找局部最优解，凸优化问题至少是研究得比较透彻，有理论指导，能分析收敛性的问题。另外，事实证明更多问题是非凸的，比如做多元回归，如果本身回归函数是高度非线性的，我们可以用线性回归，这样问题就可以变成凸优化问题，但是这个问题的全局最优解可能还不如一个简单神经网络获得的局部最优解。有了足够多的数据，深度学习是目前最强有力的建模武器之一，数据驱动建模的场景和运筹规划这样的问题解决思路还是有区别的。
最后，如果不是搞理论研究的，凸优化没必要学的很深（我是指从数学层面进行理论的推导，分析，证明）大部分人即使想学的很深，学力也达不到，但是基本的理论，算法以及应用还是很值得掌握的，即使不学凸优化，也最好要学一门数值优化课程，作为算法工程师而言，平时其实很少会用到凸优化方面的知识，所以不会的其实也大可不必那么担心，没人会因为你不会凸优化就拒绝你的，个人觉得，如果你只能50%地掌握10种复杂理论，还不如100%掌握一个简单的理论然后用它来解决实际问题。

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

稍稍改编下男神Sébastien Bubeck在微软的超长访谈中的话：
主持人：让我们谈谈您在优化基础上参与的一个项目。因此，正如您所称，优化方法是机器学习算法的引擎。给我们概述该领域的研究方向，尤其是凸优化，并解释为什么它们对机器学习算法背后的理论很重要。
SébastienBubeck：因此，当今机器学习中的优化问题实际上具有两个关键特征。其中之一是，它们以很高的维度处理优化问题，这是一个非常大的障碍。另一特征是数据量庞大，这时您必须更加精打细算以避免系统崩溃。
现在，让我们返回优化文献，这些文献中常常要解决的问题是如何充分利用已经完成的计算。可以用来优化函数的基本计算是什么？您可以执行的基本操作之一是计算其导数、梯度。现在，根据您目前为止已观察到的梯度，设计算法最好地组合这些信息以计算下一个梯度。因此，优化在信息的最佳利用上有着悠久的历史，尤其是俄罗斯的一些学者，他们在70、80年代就开发了不少最优化方法，而我们现在才真正开始了解其背后的基本概念。（这实际上是一个非常有趣的故事。70年代末，俄罗斯学派最优化领域的佼佼者Arkadi Nemirovski发现，当您要优化的函数很平滑时，实际上您能比简单利用梯度下降技术做得更好，您可以更好地利用过去的信息。因此，他设计了一种加速技术，后来机器学习传奇人物Yurii Nesterov对其进行了大幅简化，并据此设计了非常实用的算法——Nesterov动量技术。因此，作为获得最优解的较优方法，这种动量技术首先是在凸优化的背景下设计的。）
……
正如我们已经讨论的那样，在机器学习中你会发现很多应用非常基本的假设之一就是凸性。比如，在多臂老虎机中，您发出连续的动作，并且损失函数被定形为凸函数，您需要思考：如何设计合理算法，使得仅采取少许探索就能恢复以前的最佳bound？

TheLudGamer · 发表于 2021-7-4 06:33

我就按着问题一个个的回答吧：首先，在现实生活中，如果对实际问题进行建模，直接符合凸优化条件的问题很少很少，少的可怜，我们在机器学习中、深度学习中所谓的模型正好符合凸优化模型的情况是经过无数先辈几十年的沉淀转化而来的，现今的机器学习、深度学习，所谓的智能，其实也只是数据进行建模，kNN、贝叶斯、决策树、SVM做超平面分隔、k聚簇等等只是在使用统计学的方法来做决策，其实只是概率(对已发生事件的频率统计)选择来进行决策而已，而解决这些问题的过程当中，存在着无数约束条件:等式+不等式。求解(x),使得等式+不等式符合条件，经过先辈们的改善、切合，发现转化为凸优化可以解决这类问题。但是还有着大量的问题没法解决，例如NP问题，目前是无解的，因为它涉及的约束条件、可能性太多，计算过于复杂。我们没法直接将它转化为凸优化。其次，凸优化的重要在于它是一个相对而言被嚼烂的数据模型，对凸优化的问题我们在基础数学上面已经有了很多解决方法，例如可以将凸优化问题Lagerange做对偶化，然后用Newton、梯度下降算法求解等等。

再次，现有的优化方法不是都解决了的，还是有很多问题是没有解决的，例如NP问题，如果转化为可解问题，如何对这些问题做近似优化处理，这就需要遇到具体问题的时候具体去分析，而且建立一个近似可解的优化模型需要我们对优化本身理解透彻。一个对水墨、颜料都不懂的画家如何能够创造出新颖的画风？
最后，回答末尾一个问题，凸优化的作用在于思维方式的转变，跟计算机思维方式一样，计算机从业人员在遇到问题的时候习惯了通过电脑去协助解决问题，而他们的价值不在于知道听得懂别人告诉他如何解决问题，而是遇到现实问题的时候都会将问题拆分成机器可以实现的方式去解决：例如遇到购物，阿里巴巴建立了网站、app、c/s系统、b/s系统，用互联网建立信息流，建立帝国。遇到查询问题，百度建立了搜索引擎。这种思维方式才是最重要的。。同样，凸优化的价值也在于思维转变，遇到现实生活问题的时候，我们必然要对问题进行建模，然后抽象问题，利用机器去帮助我们解决问题，那么，当问题的计算量接近无穷大的时候我们如何去解决？这就需要我们抽离问题抽象结构，想办法将转换成“凸优化问题”，因为凸优化已经被嚼烂，所以只要问题转化成凸优化，我们就可以分布迭代去运算，于是才有了机器学习、深度学习这一门门的交叉科学。凸优化是数学领域的重要分支，而计算机科学仅仅是数学这门基础科学的延伸而已，基础科学才是王道！！！ C#、Java固然是被封装成了便于人类使用的高级语言，但是总有些功能是“已有实现”没有封装好的，这时就需要我们回归更加原始语言C、汇编去编程。。深究底层、精通基础科学才是从容面对所有问题的解决王道，学会别人解决过的问题只能让你解决相同的问题，现实是无限可能的，总有未解决过的问题等着你，凸优化，你值得拥有

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

为什么凸优化这么重要？

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源