作者：留德华叫兽，美国克莱姆森大学数学硕士（运筹学方向）、Ph.D. ，欧盟玛丽居里学者，德国海德堡大学数学博士（离散优化、图像处理方向），期间前往意大利博洛尼亚大学、IBM演习半年，巴黎综合理工访问一季。
现任德国某汽车集团无人驾驶部门打算机视觉研发工程师。

本文于2018年1月18日发布于【运筹OR帷幄】微信公众年夜众号。

序言

运筹学在海内，远没有新兴的人工智能以及传统学科统计来的遍及。
人工智能、统计末了险些都能化简成求解一个能量/丢失函数的优化问题。
但相信很多人不知道，运筹学正是研究优化理论的学科。
而因此，我把运筹学称为人工智能、大数据的“引擎”，基本管理其在人工智能中主要性。

本文提要

1，运筹学、线性方案回顾

2，整数方案问题

3，什么是组合优化

4，非凸优化

5，整数方案与非凸优化的关系

6，整数方案、非凸优化为何主要

7，整数方案在工业界的运用

8，整数方案在AI的运用和展望

注：以下文中黑体字代表其在学术界的术语

首先，对运筹学（O.R.）还比较陌生的童鞋，请戳本专栏的开篇之作：

运筹学--一门建模、优化、决策的科学 - 知乎专栏

（https://zhuanlan.zhihu.com/p/25579864?refer=operations-research）

1. 运筹学、线性方案（Linear Programming）回顾

运筹学的初学者，欢迎查看我不才面的回答：

运筹学如何入门？-知乎

（https://www.zhihu.com/question/22686770/answer/113176244）

运筹学、数学方案（Math Programming）问题的数学表达式，由自变量（Variables）、目标函数（Objective Function）和约束条件（Constraints）组成，所有优化问题实质上都可以化简为由它们组成的数学表达式，然后求解知足约束条件下使得目标函数最大/小的变量的值。

如上图，当自变量是连续的，目标函数和不等式是线性的时候，该问题被称为线性方案问题。
线性方案因其具有的良好性子（例如，最优解必定涌如今极点），可以用纯挚型法（Simplex Method）或内点算法（Interior Method）高效地求解，熟习算法繁芜度的童鞋，知道它是多项式韶光可解的（Polynomial Time Solvable--O（n^k））。
这里n表示自变量个数。

可行域（Feasible Set）：可行解的凑集。
如下图，阴影区域（多面体、Polyhedron）即为三个线性不等式（半平面）组成的可行域。
是不是很眼熟？实在高中代数课大家就已打仗过线性方案了。

2. 整数方案（Integer Programming）问题

整数方案，或者离散优化（Discrete Optimization），是指数学方案问题中自变量存在整数。
与线性方案连续的可行域不同，整数方案的可行域是离散的。

如上图，蓝线依旧代表线性不等式，但是这里x,y被约束成整数变量，因此可行域变成了红线区域内的9个离散的点。

凸包（Convex Hull）:整数方案所有可行点的凸包围，即图中红线组成的多面体（想象多维的情形）。
凸包是未知的，已知的是蓝线的不等式，并且凸包是非常难求解的，或者形成凸包须要指数数量级的线性不等式（图中红线）。
如果知道了凸包的所有线性表示，那么整数方案问题就可以等价为求解一个凸包表示的线性方案问题。

其余，除了整数方案，还有稠浊整数方案（Mixed Integer Programming, MIP），即自变量既包含整数也有连续变量。
如下图：

x是连续的，y被约束成整数变量，这时候可行域变成了4条离散的橘黄色线段+4处的赤色整数点（0,4）。
课后作业，求图中的凸包。

整数方案的精确算法常日须要用到分支定界法（Branch and Bound Method）,以及增加分支定界效率的各种技巧，例如割平面方法（Cutting Planes Method）。
总的来说，求解整数方案的精确解是NP难的，也便是指数级算法繁芜度（Exponential Time Solvable）。

怎么来理解指数级繁芜度呢？假设这里的整数是0,1变量，那么我们可以大略地理解为算法繁芜度是2^n（须要解2^n个线性方案问题）。
也便是说，每增加一个0，1变量，求解的速率就有可能要增加一倍！
例如求解n=100的整数方案问题须要1小时，那么求解n=101的规模可能会须要2小时，n=102须要4小时，n=105须要32小时。
。
这便是指数爆炸！

因此，整数方案问题被看作数学方案里、乃至是天下上最难的问题之一，被很多其他领域（例如机器学习）认为是不可追踪（Intractable）的问题，也便是他们直接放弃治疗了。

作为研究天下上最难问题的学者，想出理解决整数方案问题的各种其他路子，例如近似算法（Approximation Algorithms），启示式算法（Heuristic Algorithms），遗传算法（Evolution Algorithms, Meta-Heuristic）等等。
它们虽然不能求得整数方案的最优解，但是却能在短韶光（常日多项式韶光）内给出一个较好的可行解。

篇幅限定，我将不才一篇专栏着重磋商整数方案精确解的算法、整数方案求解器、近似算法以及启示式算法，敬请期待。

3. 什么是组合优化(Combinatorial Optimization)

普通的讲，我把组合优化理解为，在组合优化种可能性里找出最优的方案。
假设自变量为n，用强力搜索法（Brute-force Algorithm）来解组合优化的算法繁芜度最坏须要n的阶乘！
什么观点？这比指数爆炸还要恐怖！

从这个意义上讲，组合优化是整数方案的子集。
的确，绝大多数组合优化问题都可以被建模成（稠浊）整数方案模型来求解。
但是彷佛学术圈更多地把组合优化与图（Graph）优化以及网络流（Network Flow）优化联系在一起，并且终极目标不在精确解，而是近似解。
（这点可以从整数方案的国际会议上看出）

Anyway，这里开始，我将稠浊整数方案、离散优化、组合优化。

下面给出一个经典的组合优化例子-最大流问题（Max Flow Problem）：

给定一张图G（V，E），V是点（Node）的凑集，E是边（Edge）的凑集。
该问题试图从点0到5导流最大的流量，边上的数字代表该条边的最大流量，因此形成了约束条件--每条边的流量不得超过该条边的限额。
自然而然地，该问题可以被建模成一个整数方案问题。

我们跳过模型和算法，直不雅观的判断该问题的算法繁芜度大概为多少。
设想从0出发，有俩种可能线路，0到1以及0到2；从1和2出发，有分别有两种可能的线路。
因此，可以初步判断，改问题如果用强力算法（穷举法），算法繁芜度将为指数级！

但是聪明的组合优化学家，把这个看似指数级算法繁芜度的问题，用奥妙的算法多项式韶光便可求解出最优解。
This is the beauty of Mathematics!

韶光关系，该问题的详细模型和近似算法，会放不才一篇专栏展开，有兴趣的可以搜索“Max Flow/Min Cut”。

4. 非凸优化 （Non-Convex Optimization）

凸（Convex） VS 非凸的观点，数学定义就不写了，先容个直不雅观判断一个凑集是否为Convex的方法，如下图：

大略的测试一个凑集是不是凸的，只要任意取凑集中的俩个点并连线，如果说连线段完备被包含在此凑集中，那么这个凑集便是凸集，例如左图所示。

凸优化有个非常主要的定理，即任何局部最优解即为全局最优解。
由于这个性子，只要设计一个较为大略的局部算法，例如贪婪算法（Greedy Algorithm）或梯度低落法（Gradient Decent），收敛求得的局部最优解即为全局最优。
因此求解凸优化问题相对来说是比较高效的。
这也是为什么机器学习中凸优化的模型非常多，毕竟机器学习处理大数据，须要高效的算法。

而非凸优化问题被认为是非常难求解的，由于可行域凑集可能存在无数个局部最优点，常日求解全局最优的算法繁芜度是指数级的（NP难）。
如下图：

最经典的算法要算蒙特卡罗投点法(Monte Carlo Algorithm)了，大概思想便是随便投个点，然后在附近区域（可以假设convex）用2中方法的进行搜索，得到局部最优值。
然后随机再投个点，再找到局部最优点。
如此反复，直到知足终止条件。

假设有1w个局部最优点，你至少要投点1w次吧？并且你还要假设每次投点都投到了不同的区域，不然你只会搜索到以前搜索过的局部最优点。

5. 整数方案与非凸优化的关系

大家或许不知道，（稠浊）整数方案被称为极度非凸问题（highly nonconvex problem），如下图

实心黑点组成的凑集，是一个离散集，按照4中止定一个凑集是否为凸集的技巧，我们很随意马虎验证这个离散集是非凸的，并且比较4中的非凸集愈甚。
因此整数方案问题也是一个非凸优化问题。

6. 整数方案、非凸优化为何主要

虽然韶光是连续的，但是社会韶光却是离散的。
例如时候表，常日都是几时几分，纵然精确到几秒，它还是离散的（整数）。
没见过小数计数的时候表吧？

同样，对现实社会各行各业问题数学建模的时候，整数变量有时是不可避免的。
例如：x辆车，y个人。
x，y这里便是整数变量，小数是没故意义的。

决策变量(Decision Varible): x={0,1}.

0/1变量被广泛地运用在商业和决策领域。
我们假设变量x={0,1}，当x=1的时候，我们便可以建模实行x这个决策；x=0，则表示不实行。
这样引入决策变量x的建模技巧，在工业界案例中习认为常。

从这些案例，社会是由一个个离散变量组成的。

关于非凸优化，现实生活中，万物的实质是非凸的，就像万物是趋于混乱（Chaos）的，规则化须要代价。
如果把4中的图看作山川盆地，你在现实中有见过左图那么“光滑”的地形么？右图才是Reality！

说到这里，当然不能否定了凸优化和连续优化的浸染，科学的实质便是由简到难，先把大略问题研究透彻，然后把繁芜问题简化为求解一个个的大略问题。
求解整数方案便是利用分支定界法求解一个个线性方案问题，非凸优化同样如此。

7. 整数方案在工业界的运用

路径优化问题（Routing Problem）--交通领域（GPS导航）；

仓储、运输等物流（Logistics）以及供应链(Supply chain)领域；

制造业里的生产流程优化（Process Optimization）；

电力领域的电网的布局以及分配(Power Grid)；

电子工程里的举动步伐部件分配问题(Facility Layout Problem)；

能源领域的优化，如：如何铺设输油管道；

火车、课程、飞机时候表安排问题等调度问题 (Scheduling Problem);

资产配置 （Asset Allocation）、风险掌握 (risk management)等经济金融领域的运用；

以上工业界的运用，频繁利用着决策变量，以及整数变量，建模成（稠浊）整数方案模型，而机器学习（ML），特殊是深度学习（DL），至今没有怎么渗透进来。
也希望有志青年探索ML、DL在这些领域的运用。

8. 整数方案在AI的运用和展望

这里我举一个统计和机器学习的例子，这个模型也可以和统计里经典的Lasso问题联系起来，以及可以给出L0范数问题的精确解。

如下图，是一个分段常数回归问题。
统计中大家都知道线性回归和常数回归，个中常数回归即求一组数的均匀值。
但是这里，我们想对数据分段，并且不知道分段的节点在哪里。
如下例所示，假设n个点，要分成三段作常数回归，节点有2个。
那么节点的选择有n选2种可能性，从这个意义上理解，这个问题是一个组合优化的问题。

自变量有实数变量w和整数变量x，y_i是常数，即点i的值，w_i是回归值，上半部分的表达式可以看作是伪表达式（pseudo formulation），L0函数即向量中非零的个数（可能须要一些高档的数学知识）。
我们直接看下半部分的稠浊整数非线性方案模型。

我们引进了一个0/1决策变量，X_{ei},这个变量是浸染在边上的。
我们希望当它是处于节点位置，即俩段常数回归的临界处，就即是1；但它处于某一段常数回归中间时，就即是0.

因此目标函数前半部分是回归方程，希望回归的偏差越小越好，后半部分即为规则化项（regularization term），用来约束分段的个数，来惩罚过多的分段以防止过拟合（over-fitting）。
大家常常可以在旗子暗记处理、图像处理中看到这样的目标函数。

约束条件第一个不等式担保了同一个分段回归中，w_i和w_{i+1}的值相等，由于x_{ei}=0；而在节点处，他们可以不相等，M是一个很大的常数，以担保节点处x_{ei}=1时，不等式总是成立。

写出了这个整数方案模型，我们就可以编程并调用整数方案的优化求解器来求解这个问题的最优解。
例如IBM Cplex。
虽然整数方案常日的算法繁芜度是指数级的，但是比起强力搜索，还是会高效很多很多。
这样我们就可以得到每个点的回归值w以及分段的节点，即哪些点x_e=1。

展望

深度学习的优化问题在运筹学看来是“小儿科”，这句话可能会打脸大部分不雅观众。
虽然目标函数非常繁芜，但是它没有约束条件啊！

深度学习里的丢失函数，是一个高度复合的函数。
例如h(x)=f(g(x))便是一个f和g复合函数。
深度学习里用到的函数，Logistic, ReLU等等，都是非线性 ，并且非常多。
把他们复合起来形成的函数h,便是非凸的。
但是深度学习演习参数的优化问题，实质是一个无约束的非凸优化问题。
求解这个非凸函数的最优解，类似于求凸优化中某点的gradient，然后按照梯度最陡的方向搜索。
不同的是，复合函数无法求gradient，于是这里用方向传播法（Back Propagation）求解一个类似梯度的东西，反馈能量，然后更新。

机器学习、数据科学由于处理数据量弘大，因此研究问题紧张的方法还是凸优化模型（包括线性方案、锥优化），缘故原由正是求解高效，问题可以scale。

虽然目前还很小众，但是随着打算机硬件能力的提高，以及GPU并行打算的盛行，以及非凸优化算法、模型的进化，想必非凸优化，（稠浊）整数方案会是未来的研究热点。