《运筹学》,《线性规划》，《非线性规划》，《凸优化》，《最优化方法》这几门课程有什么区别和联系？

RhinoFreak · 发表于 2021-9-15 08:38

目前在自学《凸优化》，看到这几本书的目录，内容好像有不少重叠，请问这些课程有哪些区别？想学优化的话应该以什么顺序学习？

七彩极 · 发表于 2021-9-15 08:46

运筹学：这个概念在这几个名词中是最大的，运筹学包含了线性规划，非线性规划，凸优化以及大部分最优化的内容。同时运筹学不仅仅包含上面这些内容，它还包括整数规划，组合优化，随机优化，鲁棒优化，半定规划，锥规划，动态规划，非凸优化等等。运筹学主要的内容就是研究各种类型优化问题的建模+求解，线性规划也好，凸优化也好都只是一类特殊的优化问题而已，所以说运筹学的概念是非常广的。
当然要指出的是国内很多本科阶段名为“运筹学”的课，主要内容其实就是线性规划（更具体点说就是单纯型法）。线性规划确实是运筹学中很重要的一部分同时也是运筹学中最基础的内容，但是线性规划不等于运筹学。本科阶段一部分课程名称命名的不规范可能也造成了大家对这些概念之间产生了混淆，目前国内本科阶段的运筹学课的设置有着很大的问题，此处我就不再吐槽国内坑爹的“运筹学”课了。
线性规划：这个大家应该是最熟悉的了，线性规划顾名思义只研究目标函数和约束是线性的优化问题的建模和求解。线性我们都知道拥有者非常好的性质，目前线性规划的求解方面相对来说是拥有者比较成熟的算法。一个问题如果是线性规划问题那么说明这个问题的求解一般来说难度并不大。线性规划包含在凸优化之中，那为啥不直接把线性规划就合并在凸优化里边呢。主要因为线性规划由于较为特殊，线性的性质导致有很多比较漂亮的结果，同时线性规划学习起来相对比凸优化简单很多。
非线性规划：与线性规划相对的就是非线性规划。世界并不总是线性的，大多数真实场景的应用问题都是非线性的居多。
凸优化：凸优化包含了线性规划，但一部分非线性规划问题也是凸优化问题。凸优化是指目标函数和约束条件都是凸函数的优化问题。优化问题的难度分水岭是凸和非凸。一般来讲，一个优化如果是凸优化的话，大概率意味着这个问题也应该是比较好求解的（严谨的来说有一部分凸优化问题也并不好求解初学者可以先忽略掉）。如果是到了研究生阶段或者是做科研的话，开始系统学习运筹学的话，第一门课是线性规划，第二门课基本就要是凸优化了。之所以凸优化这么重要主要在于凸很大程度上可以保证全局最优。详细的关于凸优化为什么这么重要可参考：
为什么凸优化这么重要？
最优化方法：很多国内高校喜欢开始一门名为最优化/最优化方法的课程。大多数最优化方法的课程的内容事实上是 Numerical optimization 的内容，直接翻译过来就是数值优化或者数值最优化。这类课程的主要内容围绕着基于梯度的优化算法展开，一般会从梯度法开始，介绍梯度法（最速下降法），共轭梯度法，牛顿法，拟牛顿法等等。可以看到数值优化的内容侧重在于处理可微分的优化问题，在数值优化中很关心目标函数连续不连续可微不可微，但较少关心是不是凸的。数值优化算法可以用来求解非凸的可微的优化问题，但一般也只能保证收敛到局部最优。
值得一提的是在 Stochastic gradient 算法没有流行起来之前，传统神经网络的训练问题（也就是传统神经网络的BP算法）本质上就是最优化介绍的方法。当然现在的 Deep learning 里边已经较少直接采用最优化里边介绍的方法。
最后啰嗦一下谈一点题外话：我个人觉得有必要多做一些关于运筹学的科普介绍，本问题涉及到的这些概念对于有多年运筹学研究经验的人来说并不难，但是对于初学者或者本科同学来说确实会对这些概念感到困惑。这些类似于 big picture 的内容其实应该在本科运筹学的课程中去介绍，但目前以我个人观察来看我们的本科运筹学课程的教学思维还是非常落后的，基本上只学一点线性规划，然后线性规划还只学了单纯型法，然后单纯型法的学习过程还沉迷于手动计算。所以大家貌似学了很多内容，但根本不太清楚这些课程的Motivation是啥？和其它课程有什么联系？

Zephus · 发表于 2021-9-15 08:55

首先，运筹学和最优化基本上可以视为对等的。当然，如果将最优化看成是运筹学的一部分，也是可以的。一般来说，运筹学比最优化要广一些。
最优化方法，以凸性来分类，可以分为凸优化和非凸优化；以线性性来分来，可以分为线性规划和非线性规划。一个非线性规划问题，有可能是凸的，也有可以不是凸的。这是两种不同的分类方法。
如果要入门最优化，建议先学习凸优化，先了解一些基本的常识，从比较简单的无约束优化问题入手，读一些比较容易读的经典文献，然后慢慢的补充各方面的知识。不要捧着大部头去啃，效率不高。当然，也可以从线性规划入门，但是线性规划的核心是对偶，初学者不太容易深入理解对偶，反而容易糊涂。

NoiseFloor · 发表于 2021-9-15 09:05

运筹学，operations research，已经偏向应用层面了，解决问题的时候会建模求解，建模一般是优化模型。
线性规划，linear programming，属于优化类的问题，也可以成为linear optimization，目标函数和约束条件都是线性的。
非线性规划，nonlinear programming，目标函数或者约束条件是非线性的优化问题；
凸优化，convex optimization，线性规划都是凸的，或者转换一下都是凸的。非线性的话，二次规划是凸的；
最优化，optimization，那就更泛了，可以是非凸的。

super1 · 发表于 2021-9-15 09:14

他不再和谁谈论相逢的孤岛
因为心里早已荒无人烟

function（x，y，z）->k（or function） 的过程是很常见的
如果做逆过程，已知k，调整参数（x，y，z）来逼近k值，就是拟合
对逼近值和应该具有的k值做比较（比如残差），就是评估
通过评估和拟合，调整参数，来让评估结果更优，就是优化
调整参数的方式有很多，例如求梯度寻极值（可见scipy提供的很多种优良优化方案），这些理论就称作优化方法
形式化的实现就是优化算法
优化算法可能涉及到约束条件，比如使得优化的过程中一直保持某些参数所处范围或者其他limitation，那么就有了规划
规划可以是线性也可以是非线性，取决于函数和约束函数的形状
优化方法的选择有赖于待优化函数是否连续可导光滑等等这些函数所具备的特性，而通常凸函数是比较容易优化也是常见问题中出现的，对于凸函数的优化处理就是凸优化
这个过程中有输入有输出，扮演function角色的就是模型
对于某个target，采用的模型+优化方法就是方案
描述确定目标、制定方案、建立模型和制定解法等等常识问题的学科就是运筹学

FeastSC · 发表于 2021-9-15 09:14

这几门课以前学生时代都学过，但是不同学校讲法、用书、教师的偏好都会有差别，所以我只说说我的经历。仅供参考。
首先这几门课其实都可以归为最优化理论。其中运筹学偏向于算法，比如运筹学必讲的线性规划：单纯形算法；非线性规划：梯度下降算法、共轭梯度算法、惩罚函数法；动态规划的递归方法……总之透露着浓浓的工程师的味道。所以一般认为，运筹学与统计学的性质有些像，一般并不认为是真正意义上的数学。
与之相比，凸优化更偏向理论一些，也就是说“数学”的味道更浓一些。一般凸优化的课程不太会像运筹学一样讲算法，而是讲一些原理性的东西，“理科”的氛围更足一些。比如共轭函数、分离超平面、Fenchel对偶定理、Lagrange对偶定理、Kuhn-Tucker定理……这些东西我都是在凸优化课程中学到的，运筹学课程并不会讲这些。（所以我再强调一遍：不同学校讲法、用书、教师的偏好都会有差别，我的学习经历仅供参考。）
此外，一般不会把线性规划单独开一门课吧？（我猜的，可能真有吧）。一般线性规划，包括线性整数规划都会放在运筹学课程中讲的，而非线性规划内容有很多，凸优化、动态规划其实都可以算作非线性规划。除此之外还有非凸优化问题，是一类更为困难的非线性规划问题，这方面我了解的也不多，因为我也不是运筹学/最优化方向的。是的，我知识量很少。
顺带提一句，以上谈的主要还是静态优化（动态规划除外）。动态优化（最优控制）的课程一般并不会放在《运筹学》、《数学规划》这样的课程中去（可能也有，但比较少见），因为……怎么说呢，课程的特点不太一样。但其实从纯数学的角度看，静态/动态其实无非就是有限维/无限维规划的区别，用泛函分析的框架可以统一地进行处理……核心的 Trick 就在于：

maltadirk · 发表于 2021-9-15 09:22

我默认你说这都是课。
《运筹学》：本科课，了解基本的linear programming，simplex method，dual problem, branch and bound, branch and cut for integer programming. 也会能了解小部分的stochastic optimization。本科课，重在了解应用，也许你会了解到很多graph的问题都可以用LP来解，但为什么可以这样解，不是非常清楚。
《线性规划》：研究生课程？内容基本和本科的《运筹学》一样，但更理论，把本科所有不明白的地方都给你讲明白。
《非线性规划》：Bertsekas的nonlinear programming书的前几章。
《凸优化》：Boyd的convex optimization的前几章
《最优化的方法》：Wright的《numerical optimization》的前几章。
p.s. 由于Boyd的书讲的算法相对较少，有些学校会跳过应用的章节，介绍更多的算法，例如Gradient descent, sgd, conjugate gradient descent, proximal gradient descent, Adam, sub gradient descent 之类的

zifa2003293 · 发表于 2021-9-15 09:28

在题主提到的这些概念中，即运筹学、线性规划、非线性规划、凸优化以及最优化方法，运筹学囊括的范围最大，它是近代应用数学的一个分支，主要是研究如何将生产、管理等事件中出现的运筹问题加以提炼，然后利用数学方法进行解决的学科。其中用到的方法可以成为“运筹学方法”或者“最优化方法”。在日常用语中， “运筹学”一般是包括了“最优化”（或者最优化方法）。
具体来说，运筹学主要包括了线性规划、非线性规划、整数规划、动态规划、排队论、决策论以及网络规划等。而最优化方法包括凸优化、非凸优化。同时，线性规划也可以转化为凸优化，非线性规划可以是凸优化也可以是非凸优化。
如果想学习优化知识，建议从凸优化开始入门，先了解一些基本的概念，如凸函数、凸集等等；之后可以学习线性规划（单纯形法、对偶问题等）、非凸优化、非线性规划等。
<hr/>此为PK入驻导师或往届学员撰写，更多干货或需要留学、考研/保研的背景提升、科研论文辅导服务，请关注微信公众号：Paper King。

mastertravels77 · 发表于 2021-9-15 09:32

他们背后的底层逻辑都是一个数学分支-----线性代数

FeastSC · 发表于 2021-9-15 09:41

运筹学 ~ 最优化

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