蓝色的信封作者

运筹学发展概况(上)

文章来源于微信公众号:运筹OR帷幄(ORycww),经过整理和修改而成。

前言

『运筹OR帷幄』特别推出了运筹学历史回顾的专题运筹学的发展概论,本篇文章为运筹学概论(上),后续会推出中篇和下篇,尽请各位持续关注。60 多年以来,运筹学在研究与解决复杂的实际问题中不断地发展和创新,各种各样的新模型、新理论和新算法不断涌现,有线性的和非线性的,连续的和离散的、确定性的和不确定性的。至今它已成为一个庞大的、包含多个分支的学科,其中一些已经发展得比较成熟,另外一些还有待完善,还有一些才刚刚形成。

数学规划

数学规划是在决策变量满足一定约束下求一个或多个函数的极小值或者极大值。它以大量实践中抽象出来的典型最优化模型为研究对象,利用数学工具研究这些模型的数学性质,构造与实现求解方法,以及将算法应用于实际问题。
自从1939 年康托罗维奇提出线性规划模型、1947 年丹齐格提出求解线性规划问题的单纯形法、卡罗胥和库恩与塔克先后分别独立地给出一般非线性规划问题的最优性条件以来,数学规划得到了快速发展,形成了多个分支。

线性规划

自1939 年苏联数学家康托罗维奇提出线性规划问题和1947 年美国数学家丹齐格求解线性规划问题的通用方法──单纯形法以来,线性规划可以说是研究得最为透彻的一个研究方向。单纯形法统治线性规划领域达40 年之久,而且至今仍是最好的应用最广泛的算法之一。虽然它在最坏情况具有指数复杂性,但在平均意义下已经证明是一个多项式算法。目前,关于单纯形算法的研究主要在于如何选取主元。

另一大类算法是内点法,它起源于1979 年苏联数学家卡奇扬提出的多项式椭球算法,而因1984 年美籍印度裔数学家卡玛卡提出的多项式时间算法而迅速成为国际热点,各式各样的算法大量涌现:诸如仿射变换法、势函数方法、对数罚函数法、路径跟踪法、原始对偶法、不可行内点法等等。

目前线性规划的内点法也趋于成熟,这方面的研究者们目前大都致力于以线性规划作为特例的锥规划,以及如何利用线性规划松弛求解整数规划等方面的研究。然而,就线性规划而言,是否存在强多项式算法仍然是一个重要且困难的理论问题。

非线性规划

等式约束规划问题的最优性条件可追溯到拉格朗日,一般非线性规划问题的最优性条件则归功于卡罗胥和库恩与塔克,是他们奠定了非线性规划的理论基础。然而,目前还有不少人试图在没有强互补的条件下进行理论分析和算法研究。对偶理论是非线性规划理论研究的另一个重点。在计算方法方面,早期的方法以最速下降法和牛顿法为主。1959 年拟牛顿法的引入和1964 年非线性共轭梯度法的出现,吸引了许多研究者研究非线性规划。目前,序列二次规划算法是一类被用于广泛求解一般非线性规划的有效算法,同时也还有许多研究者在为改善这类算法努力,其中包括序列线性规划算法以及内点算法等。非线性规划算法通常使用线搜索策略选取步长,或通过求解信赖域子问题而得到新的迭代点。这两个方面的研究非常基本,但仍有改善的空间。2001年弗莱彻和勒斐通过将非线性规划问题视为双目标问题而提出的滤子方法和2002 年鲍威尔提出的基于二次插值的直接法是近些年来两个重要的算法进展。对于约束规划问题,如何推广鲍威尔的直接法;对于大规模问题,如何设计子空间算法;以及如何有效求解一般非线性规划的全局最优,和一些来自于图像处理等领域的特殊的非光滑问题是目前非线性规划比较重要的研究问题。

总之,尽管在表面上看非线性规划已经有许许多多的研究,但由于非线性的存在,好的研究结果还将会不断出现,并且随着问题的不同而产生更加具有针对性的特殊算法。

锥规划

锥规划是线性空间中凸锥上的数学规划,它是线性规划与非线性规划的推广。自上世纪90 年代中期开始,它一直是国际优化领域的研究热点。相关的研究带动了数学规划学科的深入发展,促进了代数、群论、拓扑学、几何学、非线性分析等分支在数学规划中的融合,以及优化理论与技术在工程、交通、经济与金融、管理等领域的广泛应用。

目前的锥规划方面的研究成果主要包括以下4 个方面:

  • 二阶锥优化和半定优化

线性二阶锥优化和半定优化已经得到了很好的发展,并且广泛地应用于各种实际问题。近些年,人们开始致力于非线性二阶锥优化和非线性半定优化的理论与算法研究;

  • 对称锥优化

上世纪末国际优化专家开始致力于这一领域的研究,主要集中在求解对称锥上线性优化问题的内点算法方面。近几年,人们开始探讨对称锥上的非线性优化问题和非凸优化问题的理论与各种算法;

  • 齐次锥优化

齐次锥的理论早在1963 年就有相关研究,但齐次锥优化问题的研究最近才开始;

  • 双曲锥优化

这方面目前只有很少的理论研究,需要寻求合适的工具开展其理论与算法的研究。

矩阵规划

在众多的科学领域与社会经济中,很多优化问题的决策变量是一个具有特殊结构的矩阵,这样的优化问题被称为矩阵优化或者矩阵规划。矩阵规划的早期研究可以追溯到1981 年,然而真正的研究是在20 世纪90 年代,它以被誉为21 世纪的线性规划-半定规划为研究起点。至今,线性半定规划的理论趋于完善,人们正在发掘它在实际中的应用。然而,目前的数值软件只能有效地求解矩阵维数小于500 的小规模线性半定规划问题,因此,开展大规模半定规划的数值方法研究是当前一项十分迫切而又重要的课题。

此外,由著名华裔数学家陶哲轩等人在2006 年提出的压缩传感理论而引发的低秩矩阵问题,其理论与算法研究是当今优化领域与信息科学领域(例如,信号处理、图像恢复与重建)共同关心的热点研究课题。

小结

在未来一段时期里,矩阵(锥)优化理论与算法、张量(锥)优化理论与算法、多项式优化理论与算法研究等方向必将引起人们的关注。
变分不等式与互补问题

变分不等式与互补问题是一类具有普遍意义的均衡优化模型。它不仅为非线性优化、极大极小、对策论、非线性方程、微分方程等提供了一个统一的理论框架,而且在力学工程、交通、经济、管理等实际部门有广泛的应用。

互补问题首先由丹齐格和科特尔于1963 年提出。次年,科特尔在他的博士论文中第一次提出求解它的非线性规划算法。变分不等式问题首先由哈特曼和斯塔姆巴切在1966 年提出。后来发现,变分不等式是互补问题的一个推广,且其数学性质和应用有惊人的相似之处。所以,它们经常在文献中成对出现。变分不等式与互补问题被提出后,很快引起了当时运筹学界和应用数学界的广泛关注和浓厚兴趣,许多人参与了这类问题的研究。经过40 余年的探索,特别是20 世纪最后10 年的研究,人们在理论与算法方面取得了丰富、系统的成果, 并在科技与经济中得到了广泛的应用。

当前主要是对于广义变分不等式和锥互补问题的研究,而对于不确定信息下变分不等式和互补问题的研究无疑是发展的必然。归纳起来,对它们的研究可分为理论与算法两方面:

前者主要研究解的存在性、唯一性、稳定性与灵敏度分析以及它们与其他数学问题的联系等;

后者则主要建立有效的求解方法及相应的理论和数值分析。

大数据人工智能时代的运筹学
旨在普及运筹学(优化理论)
及其在供应链管理和人工智能的应用

『运筹OR帷幄』是大数据人工智能时代的运筹学,普及运筹学和优化理论,及其在人工智能和供应链中的应用。

理论