当前位置: 主页 > 新闻资讯 > 行业动态

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

2024-04-15 12:37   作者:佚名

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

首先,运筹学和最优化基本上可以视为对等的。当然,如果将最优化看成是运筹学的一部分,也是可以的。一般来说,运筹学比最优化要广一些。

最优化方法,以凸性来分类,可以分为凸优化和非凸优化;以线性性来分来,可以分为线性规划和非线性规划。一个非线性规划问题,有可能是凸的,也有可以不是凸的。这是两种不同的分类方法。

如果要入门最优化,建议先学习凸优化,先了解一些基本的常识,从比较简单的无约束优化问题入手,读一些比较容易读的经典文献,然后慢慢的补充各方面的知识。不要捧着大部头去啃,效率不高。当然,也可以从线性规划入门,但是线性规划的核心是对偶,初学者不太容易深入理解对偶,反而容易糊涂。

等我失业了我就去当网管

function(x,y,z)->k(or function) 的过程是很常见的

如果做逆过程,已知k,调整参数(x,y,z)来逼近k值,就是拟合

对逼近值和应该具有的k值做比较(比如残差),就是评估

通过评估和拟合,调整参数,来让评估结果更优,就是优化

调整参数的方式有很多,例如求梯度寻极值(可见scipy提供的很多种优良优化方案),这些理论就称作优化方法

形式化的实现就是优化算法

优化算法可能涉及到约束条件,比如使得优化的过程中一直保持某些参数所处范围或者其他limitation,那么就有了规划

规划可以是线性也可以是非线性,取决于函数和约束函数的形状

优化方法的选择有赖于待优化函数是否连续可导光滑等等这些函数所具备的特性,而通常凸函数是比较容易优化也是常见问题中出现的,对于凸函数的优化处理就是凸优化

这个过程中有输入有输出,扮演function角色的就是模型

对于某个target,采用的模型+优化方法就是方案

描述确定目标、制定方案、建立模型和制定解法等等常识问题的学科就是运筹学

运筹学,operations research,已经偏向应用层面了,解决问题的时候会建模求解,建模一般是优化模型。

线性规划,linear programming,属于优化类的问题,也可以成为linear optimization,目标函数和约束条件都是线性的。

非线性规划,nonlinear programming,目标函数或者约束条件是非线性的优化问题;

凸优化,convex optimization,线性规划都是凸的,或者转换一下都是凸的。非线性的话,二次规划是凸的;

最优化,optimization,那就更泛了,可以是非凸的。

这几门课以前学生时代都学过,但是不同学校讲法、用书、教师的偏好都会有差别,所以我只说说我的经历。仅供参考

首先这几门课其实都可以归为最优化理论。其中运筹学偏向于算法,比如运筹学必讲的线性规划:单纯形算法;非线性规划:梯度下降算法、共轭梯度算法、惩罚函数法;动态规划的递归方法……总之透露着浓浓的工程师的味道。所以一般认为,运筹学与统计学的性质有些像,一般并不认为是真正意义上的数学。

与之相比,凸优化更偏向理论一些,也就是说“数学”的味道更浓一些。一般凸优化的课程不太会像运筹学一样讲算法,而是讲一些原理性的东西,“理科”的氛围更足一些。比如共轭函数、分离超平面、Fenchel对偶定理、Lagrange对偶定理、Kuhn-Tucker定理……这些东西我都是在凸优化课程中学到的,运筹学课程并不会讲这些。(所以我再强调一遍:不同学校讲法、用书、教师的偏好都会有差别,我的学习经历仅供参考。)

此外,一般不会把线性规划单独开一门课吧?(我猜的,可能真有吧)。一般线性规划,包括线性整数规划都会放在运筹学课程中讲的,而非线性规划内容有很多,凸优化、动态规划其实都可以算作非线性规划。除此之外还有非凸优化问题,是一类更为困难的非线性规划问题,这方面我了解的也不多,因为我也不是运筹学/最优化方向的。是的,我知识量很少。

顺带提一句,以上谈的主要还是静态优化(动态规划除外)。动态优化(最优控制)的课程一般并不会放在《运筹学》、《数学规划》这样的课程中去(可能也有,但比较少见),因为……怎么说呢,课程的特点不太一样。但其实从纯数学的角度看,静态/动态其实无非就是有限维/无限维规划的区别,用泛函分析的框架可以统一地进行处理……核心的 Trick 就在于:

  1. 凸集分离定理在无限维空间也是成立的(这背后的原因是由于Hahn-Banach定理)
  2. 多变量微分学,特别是反函数定理在无限维空间有着平行的推广(Banach空间的微分学),结合Lagrange乘子定理可以证明最优控制的最大值原理。

运筹学:这个概念在这几个名词中是最大的,运筹学包含了线性规划,非线性规划,凸优化以及大部分最优化的内容。同时运筹学不仅仅包含上面这些内容,它还包括 整数规划,组合优化,随机优化,鲁棒优化,半定规划,锥规划,动态规划,非凸优化等等。运筹学主要的内容就是研究各种类型优化问题的建模+求解,线性规划也好,凸优化也好都只是一类特殊的优化问题而已,所以说运筹学的概念是非常广的。

当然要指出的是 国内很多本科阶段名为“运筹学”的课,主要内容其实就是线性规划(更具体点说就是单纯型法)。线性规划确实是运筹学中很重要的一部分 同时也是运筹学中最基础的内容,但是线性规划不等于运筹学。本科阶段一部分课程名称命名的不规范可能也造成了大家对这些概念之间产生了混淆,目前国内本科阶段的运筹学课的设置有着很大的问题,此处我就不再吐槽国内坑爹的“运筹学”课了。

线性规划:这个大家应该是最熟悉的了,线性规划顾名思义只研究目标函数和约束是线性的优化问题的建模和求解。线性我们都知道拥有者非常好的性质,目前线性规划的求解方面相对来说是拥有者比较成熟的算法。一个问题如果是线性规划问题那么说明这个问题的求解一般来说难度并不大。线性规划包含在凸优化之中,那为啥不直接把线性规划就合并在凸优化里边呢。主要因为线性规划由于较为特殊,线性的性质导致有很多比较漂亮的结果,同时线性规划学习起来相对比凸优化简单很多。

非线性规划:与线性规划相对的就是非线性规划。世界并不总是线性的,大多数真实场景的应用问题都是非线性的居多。

凸优化:凸优化包含了线性规划,但一部分非线性规划问题也是凸优化问题。凸优化是指目标函数和约束条件都是凸函数的优化问题。优化问题的难度分水岭是凸和非凸。一般来讲,一个优化如果是凸优化的话,大概率意味着这个问题也应该是比较好求解的(严谨的来说 有一部分凸优化问题也并不好求解 初学者可以先忽略掉)。如果是到了研究生阶段或者是做科研的话,开始系统学习运筹学的话,第一门课是线性规划,第二门课基本就要是凸优化了。之所以凸优化这么重要主要在于凸很大程度上可以保证全局最优。详细的关于凸优化为什么这么重要可参考:

为什么凸优化这么重要?


最优化方法:很多国内高校喜欢开始一门名为 最优化/最优化方法的课程。大多数最优化方法的课程的内容事实上是 Numerical optimization 的内容,直接翻译过来就是数值优化或者数值最优化。这类课程的主要内容围绕着 基于梯度的优化算法展开,一般会从梯度法开始,介绍梯度法(最速下降法),共轭梯度法,牛顿法,拟牛顿法等等。可以看到数值优化的内容侧重在于处理可微分的优化问题,在数值优化中很关心目标函数连续不连续 可微不可微,但较少关心是不是凸的。数值优化算法可以用来求解非凸的可微的优化问题,但一般也只能保证收敛到局部最优。

值得一提的是 在 Stochastic gradient 算法没有流行起来之前,传统神经网络的训练问题(也就是传统神经网络的BP算法)本质上就是最优化介绍的方法。当然现在的 Deep learning 里边已经较少直接采用 最优化里边介绍的方法。

最后啰嗦一下谈一点题外话:我个人觉得有必要多做一些关于运筹学的科普介绍,本问题涉及到的这些概念对于有多年运筹学研究经验的人来说并不难,但是对于初学者或者本科同学来说确实会对这些概念感到困惑。这些类似于 big picture 的内容其实应该在本科运筹学的课程中去介绍,但目前以我个人观察来看 我们的本科运筹学课程的教学思维还是非常落后的,基本上只学一点线性规划,然后线性规划还只学了单纯型法,然后单纯型法的学习过程还沉迷于手动计算。所以大家貌似学了很多内容,但根本不太清楚这些课程的Motivation是啥?和其它课程有什么联系?

如果想入门运筹的话我个人建议从三优化开始,线性规划+凸优化+数值优化,上述三门课程的推荐教材和视频课程可以在如下链接中获取:

运筹学入门课程之三优化(附教材和视频课程)

同类文章推荐
电竞圈恶霸全文阅读_1
实用旅游英语大全(上)
视频课堂必备!惠普星Book Pro 14锐龙版智能AI提升在线学习体验
抖音入局本地生活外卖,会让市场更卷吗?
如果初中毕业去哪留学比较好?哪些国家是不错的选择呢?
甘肃提升服务增效能 优化营商大环境

咨询登记

平台注册入口