报道 | 《中国科学》创刊70周年特邀综述---现代优化理论与应用（微信文章未删减版）

↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』转载

作者：中国科学杂志社

■ 作者：叶荫宇，葛冬冬，邓琪，高建军，何斯迈，江波，李晓澄，王子卓，杨超林

Nothing at all takes place in the universe in which some rule of maximum or minimum does not appear.

---Leonhard Euler

运筹学的主要目标是在给定的资源约束下, 合理调配资源进行量化决策, 以实现设定目标尽可能优化。它是一门高度强调应用性和交叉性的学科, 与数学、概率与统计学、计算机科学、经济学和管理学等多个学科有着密不可分的关系。它诞生于20 世纪上半叶, 特别是二战期间, 以服务大规模军事任务为目的, 取得了蓬勃的发展。其兴起的真正标志是, 对于较大规模线性约束和目标问题的建模优化和以单纯形法为核心算法、依托现代计算机技术实现的成功求解。

过去的数十年里, 运筹科学的应用范围进一步扩大, 在大规模制造与生产、供应链管理、现代交通 (如航海、航空和铁路管理)、能源 (如石油与电网运营)、经济与金融等多个事关国计民生的重要领域都起到了极其重要的决策支撑或辅助作用。研究领域与框架理论也有了深入的开拓, 核心的数学规划 (或称数学优化) 理论涵盖了线性规划、混合整数线性规划、非线性规划 (特别是凸优化与非凸优化)、组合优化、随机优化与鲁棒优化、在线学习与在线优化等一系列连续或离散、确定或随机的优化模型。高效的算法也不断被发明和深入发展, 从最初解决线性系统而发展起来的经典的单纯形法, 到后来可以针对更广泛意义模型的椭圆法、内点法, 到今天针对大规模问题 (特别是机器学习) 的梯度法及其变种加速方法、交替方向法等, 层出不穷。

最近的十年里, 随着大数据和人工智能时代的到来, 数学优化在机器学习中的应用越发广泛而深入, 而机器学习也为数学优化带来了更大的挑战与机遇。首先, 随着相关软硬件的发展, 可用数据量级不断提高, 使得经典算法不再适用, 新的算法不断产生。其次, 尽管很多问题的最坏情形算法复杂度早已被证明, 但现实中的问题往往并不是最坏情形, 通过利用更多的数据信息和模型结构, 高效的算法不断被提出, 一定程度上在不断打破之前的认知。再则, 随着机器学习与优化的不断交互, 越来越多的传统优化算法重新焕发生命, 在新的场景下有了新的意义。最后, 机器学习研究重点由线性模型演变为复合结构模型, 而优化问题也由凸优化变为更为复杂的非凸优化。如今, 如何更好地优化非凸模型成为一个最重要的研究热点, 如深度神经网络。

此篇综述由斯坦福大学的叶荫宇教授及其在上海财经大学和香港中文大学（深圳）的多位团队成员合作撰写。综述就运筹与优化多个领域的一些背景知识、前沿进展和相关算法及方法论做了尽可能详尽的概述。文章主要涵盖了现代优化理论的线性规划、在线优化、非线性规划、机器学习、组合优化、整数优化等, 以及与应用结合的机制设计、库存管理和收益管理等领域。需要提醒读者的是, 本文的主要目标并非百科全书式的综述, 而是更注重介绍运筹学某些领域的主流方法、研究框架与前沿进展, 特别强调了近期一些比较重要和有趣的发现, 希望以此引起科研工作者注意, 激发读者对这些领域的兴趣并进行有意义的研究。

论文信息

邓琪，高建军，葛冬冬，等. 现代优化理论与应用. 中国科学：数学，2020，50: 899--968

通信作者：

叶荫宇

斯坦福大学管理科学与工程系李国鼎工程讲座教授（K. T. Li Chair Professor），是美国运筹与管理科学协会会士，也担任运筹学、管理科学、优化与工程等多个领域的期刊主编或编委。主要研究兴趣包括连续和离散优化、数据科学和应用、算法设计和分析、计算博弈论/市场平衡、动态资源分配以及随机和鲁棒决策等。

叶荫宇教授获得过2014年美国应用数学学会优化大奖，2012年国际数学规划大会Tseng Lectureship奖，2009年美国运筹与管理学会冯诺依曼理论奖，2006年美国运筹与管理学会Farkas奖等多项荣誉。

共同通信作者：

葛冬冬

上海财经大学交叉科学研究院教授，研究兴趣为大规模优化理论与应用、算法设计，曾在OR、 MOR、MP、FOCS、SODA、NIPS、ICML等著名期刊与会议上发表论文。