中国数学规划新近进展及展望摘要数学规划又称数学优化，它是运筹学的一个重要分支。

它主要研究在一定约束条件下，如何求一个实数或者整数变量的实函数的最大值或者最小值。

它是运筹学和管理科学中最常用的一种建模工具和求解问题的方法，在工程、经济和金融等领域有非常广泛的应用。

在本章中，首先我们简单地介绍数学规划的历史、应用及其主要研究方向；然后我们概述数学规划的发展现状和在中国的发展情况。

最后我们将按照数学规划的以下七个主要方向：（1）线性和非线性规划，（2）锥和鲁棒优化，（3）变分不等式和互补问题，（4）多目标优化与向量优化，（5）整数规划，（6）组合优化，（7）张量与多项式优化，分别介绍其背景和应用领域，研究现状，未来发展趋势和主要研究问题。

Recent Development and Future Prospect ofMathematical Programming in ChinaMathematical programming or mathematical optimization is an important branch of operations research that studies the problem of minimizing or maximizing a real function of real or integer variables, subject to constraints on the variables. It is one of widely used modeling tools and methodologies in operations research and management science and has numerous applications in engineering, economics and finance. In this chapter, we first give a brief introduction of mathematical programming problems, applications, history and main research areas. We then review the state-of-the-art of mathematical programming study with an overview of the development of mathematical programming in China. Research perspectives of mathematical programming is also presented. The main parts of the chapter devote to the following seven research areas of mathematical programming: (1) Linear and nonlinear programming; (2) Conic and robust optimization; (3) Variational inequality and complementarity problem; (4) Multi-objective optimization and vector optimization; (5) Integer programming; (6) Combinatorial optimization; (7) Tensor and polynomial optimization. In each of the above research areas, we introduce background and applications of the problems, the state-of-the-art of the methodologies, the current research trends and the key research problems.一、数学规划学科概述（一）背景和意义数学规划问题是指在一定约束条件下最大化或最小化某一目标函数的问题，其变量可能是连续或离散的；研究这类问题的数学性质、求解算法和具体实现以及应用这些算法解决实际问题的学科统称为数学规划。

数学规划的一个“近似”或通俗的名字是“最优化”。

数学规划问题求解“最优”的特征决定了其应用的广泛性。

早在18世纪，著名数学家欧拉就曾说：宇宙万物无不与最小化或最大化的原理有关系。

经济社会中，在有限的资源下求解最优的计划、方案、路线、组合和策略等问题都可以归结为数学规划问题；数学规划的应用遍及工程、经济、金融、管理、医药和军事等领域。

可以说，数学规划的原理渗入到社会发展的各个方面，甚至在我们的日常生活里也有各种各样的最优化问题。

在学科分类上，一般把数学规划看成是运筹学的一个分支，是运筹学的基础学科。

在管理科学中，数学规划是最常用的建模方法和工具，与统计和模拟仿真一起组成三大基本方法和技术。

由于数学规划与数学理论的天然联系，也可以把数学规划看成是应用数学的一个分支。

在国际上，数学规划的研究活动分布在运筹学、管理科学、应用数学、计算机科学和电子工程等领域中。

在一些国际大型学术组织中，如美国运筹与管理科学学会、国际运筹学会联合会、欧洲运筹学会、美国工业与应用数学联盟和美国计算机科学学会等，数学规划都是非常活跃的研究方向和分支。

数学规划的历史可以追溯到17世纪法国数学家费尔马给出的实函数极值点的平稳性条件和18世纪法国数学家拉格朗日处理等式约束的乘子方法，而牛顿提出的求函数极值点的迭代算法成为后来无约束最优化和非线性方程组的基本算法。

现代数学规划发展于上世纪二次大战以后，其标志是线性规划的提出和应用。

1939年康托洛维奇就已经把线性规划方法应用于二战中前苏联的军事和生产规划，但西方科学界直到50年代末才知道他的工作。

1947年,丹齐格提出了求解线性规划的单纯形方法，而冯·诺依曼发展了线性规划对偶理论并将其应用于博弈论。

线性规划的单纯形方法的提出被认为是现代数学规划也是运筹学学科的开端，是20世纪计算科学的十大算法之一,丹齐格也被认为是“数学规划之父”。

1951年库恩和塔克提出了约束最优化问题必要条件，后称为KKT-条件，标志着现代非线性规划理论研究的开端。

二战后，西方经济和科学技术的繁荣发展使数学规划的发展进入了黄金阶段，特别是计算机技术的普及使数学规划的算法能真正广泛地应用于求解各种现实问题的最优化模型。

随着共轭梯度法和拟牛顿法的提出，非线性规划方法日趋成熟，其中许多算法程序成为工程计算的标准子程序。

1979年卡奇杨提出了第一个线性规划的多项式算法-椭球法，而1984年卡玛卡提出的线性规划内点法更使数学规划研究进入了内点法时代，内点法随后被涅斯捷罗夫和尼米洛夫斯基等推广到一些凸优化问题。

数学规划的其他分支，如多目标规划和向量优化、整数规划、组合优化、随机优化、变分不等式和互补问题等在上世纪后半叶也得到了迅速的发展，成为相对成熟和独立的数学规划分支和研究方向。

近年来，锥优化，鲁棒优化、稀疏优化、张量和多项式优化等成为数学规划新的热点研究方向，连续优化和离散优化的相关理论不断深入和发展，使数学规划成为运筹学学科应用最广泛和最具活力的研究领域。

（二）研究与应用现状通过几十年的发展，数学规划理论和方法的研究不断深入，应用领域也不断扩大。

数学规划的研究大体上可分为三个主要的方面：（1）数学规划理论：研究数学规划问题相关的数学理论。

数学规划的理论研究对学科的发展具有基础性的作用，数学规划的一个鲜明的特点是其理论的严密性。

（2）数学规划算法：研究求解数学规划问题的精确和近似算法。

这是数学规划研究的核心部分，是数学规划学科应用性的体现，是数学规划学术研究和现实应用之间的桥梁。

没有算法研究的数学规划只能停留在数学理论领域。

在数学规划发展的历史上，算法研究是推动数学规划发展的主要力量，新算法的提出推动学科向前发展。

（3）数学规划建模、应用与软件：数学规划的生命力在于其应用的广泛性，从丹齐格把线性规划应用于美国空军作战计划开始，数学规划的发展都与解决实际应用问题密切相关。

工业、管理和信息等领域中有许多最优化建模问题，利用这些问题的物理特性建立模型后，需要对模型进行分析和简化，并应用合适的算法软件进行求解，而后回到现实环境中进行最优解分析和参数敏感性分析等。

可以说，重要的数学规划问题都来源于实际，其研究成果能被应用于实际。

数学规划的理论和应用属性决定了其研究队伍的广泛性和分散性。

在国内和国际学术界，数学规划的研究小组和人员一般分布在如下几个学科领域：1）数学和应用数学领域，这部分研究小组和学者主要从事数学规划理论和算法的基础研究；2）工业工程、系统工程和运筹领域，这部分研究小组主要以应用为导向，从事数学规划建模、算法和应用研究；3）管理科学领域，这部分研究小组和学者更注重最优化建模和分析，与管理科学中的运作管理、物流与供应链管理和金融工程有比较密切的合作和联系；4）信息与计算机科学领域，这部分研究小组致力于计算复杂性和算法设计与分析、信息处理的优化理论、模型、方法和应用研究。

当然，上述领域的分类并不严格，许多研究小组和学者都从事理论、算法和应用的交叉研究。

目前数学规划的主要研究领域有：（1）线性规划：研究目标函数和约束函数都是线性的数学规划问题的理论和算法，这类问题的可行域是多面体和多胞形。

线性规划在形式上是最简单但也是应用最广泛的数学规划问题。

线性规划是多项式时间可解的数学规划问题，其主要算法是单纯形算法和内点算法。

（2）非线性规划：研究目标或约束函数有非线性性质的数学规划问题，有如下的一些主要研究分支。

凸规划是非线性规划中经典和重要的一类问题，系指目标函数和约束都是凸的数学规划问题。

无约束优化问题的经典算法有共轭梯度法、拟牛顿法和信赖域法。

经典的约束优化问题的算法有罚函数法、可行方向法、内点法和序列二次规划方法等。

二次规划问题指目标函数是二次而约束是线性的非线性规划问题。

二次规划是介于线性规划和一般非线性规划之间的数学规划问题，其理论和算法研究趋于成熟，主要算法有传统的积极集法和近年来发展的内点法。

当目标和约束都是二次函数时，这一类问题称为二次约束二次规划问题，其研究难度则大大增加。

多项式规划研究目标函数和约束函数都是多项式的数学规划问题。

多项式优化与张量分析、代数几何和矩理论等数学分支密切相关。

目前，求解多项式优化问题的主要途径是松弛和近似方法，如平方和逼近等。