大学之道, 在明明德, 在亲民, 在止于至善.
物有本末, 事有终始, 知所先后, 则近道矣.
------《大学》
在今天称为"大学"的地方要探求的是一种大学之道. 本书作者想要传播的是一种数学规划之道,这种"道"存在于我们若干年来的所观、所学、所想、所感乃至所悟之中.数学规划俗称最优化,它所追求的是一种"至善"之道,从数学的角度表达了人们处理实际问题时所遵循的一种理念, 即利用数学的语言将实际问题形式化, 获得一个抽象的数学问题,然后设计一种合适地求解数学问题的算法, 并且在分析算法性能的基础上,将数学问题的求解结果与实际问题的演化状况进行比较分析,验证这种数理分析的合理性与正确性. 因此, 我们说: 数学规划首先是一种理念, 其次才是一种方法.也许在实现这种理念的过程中, 由于主客观条件的制约,我们需要这样或者那样折中的、近似的做法,但是后者永远无法替代最优化理念所蕴涵的追求卓越的精神.
数学规划(最优化)作为一门学科孕育于20世纪的30年代,诞生于20世纪40年代第二次世界大战弥漫的硝烟中,以线性规划模型和单纯形算法的出现为标志.作为一种优化方法或者体现的现象, 可以上溯到很久以前, 比如:Cauchy提出的沿着负梯度方向寻找极小点的方法(最速下降法);求解等式约束优化问题的Lagrange方法;Leibniz发表的第一篇关于微分学的论文探究的是一种求极大与极小值和求切线的新方法;Fermat在研究求极大和极小的方法时发现了一元函数取极值的必要条件,等等. 此外, 在我国古代, 人们为了建立精确的天文历法,不能不涉及特定的极值问题, 比如,郭守敬对"月离迟疾"(月亮运行的最快点和最慢点)以及月亮白赤道与太阳黄赤道交点距离的极值("极数")的计算;二十四节气中"夏至"和"冬至"实际上是描述了一年中太阳光直射点南北移动的一种极端状况.如果注意到自然界中广泛存在的优化现象, 比如, 物理系统能量的变化,奔腾的江河, 光线的传播, 生物的进化, 等等, 那么我们可以说,数学规划(最优化)之道与天地共存、与日月同辉、与人事相伴.
本书以数学规划中常见的最优化问题为出发点,从理论、算法和计算等方面介绍了分析和求解线性规划、无约束优化、约束优化、多目标规划、组合优化与整数规划、全局优化等问题的一些基本方法.全书共分8章: 上述6类问题各对应一章, 另外有两章分别介绍了数学预备知识和最优化理论基础(凸分析). 具体地说,各部分涉及的内容如下:
第1章是从实例与模型的角度, 介绍了数学规划研究的问题的特点,并且简要地介绍了分析最优化问题时在数学方面所涉及的基础知识.第2章讨论了数学规划的理论基础----凸分析理论,涉及仿射集、凸集和锥、多面体的面、凸函数等基本概念,以及凸集分离定理、择一定理、多面体表示定理、凸函数的判定条件等基本性质.第3章介绍了线性规划的基本定理和单纯形算法,在讨论线性规划最优性条件的基础上, 介绍了线性规划的对偶理论以及对单纯形算法的改进和推广策略, 包括退化现象与避免算法循环的方法、原始-对偶算法、分解算法和灵敏度分析.此外, 本章也讨论了典型的、具有多项式时间的求解线性规划的内点算法.内点算法是基于非线性优化策略的求解线性优化问题的方法,所以它涉及非线性约束优化的内容, 包括最优性条件和罚函数的思想.由于这类算法的应用对象是线性规划问题,所以我们把这部分内容列入线性规划部分.第4章讨论了无约束优化问题的最优性条件、关于算法收敛性的一般理论以及常见的求解无约束优化问题的算法:最速下降法、牛顿法、共轭梯度法以及拟牛顿法.第5章分析了约束优化问题的最优性条件、对偶理论以及求解二次规划问题的方法.在此基础上, 介绍了一些典型的分析、求解约束优化问题的算法:可行方向法、序列无约束化方法和逐次二次规划法. 另外,从约束优化的角度, 讨论了一种求解无约束优化问题的信赖域法,目的是介绍与线搜索优化策略不同的另外一种基于信赖域搜索的优化策略.第6章在介绍向量集的有效点和弱有效点的基础上,引入了多目标规划问题的最优解的概念, 并讨论了最优解的性质以及基于单目标化策略、求解多目标规划问题的方法.第7章分析了常见的组合优化问题----网络流问题和匹配问题, 其中这些网络流问题的数学结构可以借助于线性规划模型来描述. 然后,在讨论整数规划的基本性质的基础上,分别介绍了求解(线性混合)整数规划问题的割平面法、分支定界法和分解算法.第8章着重介绍了全局优化的基本概念和性质、常见的全局优化模型以及三类典型的分析全局优化问题的方法:外逼近方法(割平面算法)、凹性割方法和分支定界法.本书各章节内容之间的关系, 可以用下面的图形简要地说明.
此外, 本书在每章的最后一节给出了一些习题,书后还列出了参考文献和索引.
值得说明的是, 关于各章节内容的组织, 我们遵循着一个基本的逻辑关系,即将数学规划各部分内容的基础设定为凸分析理论,在此基础上分别讨论线性优化、非线性优化以及它们的推广形式.凸分析理论的核心是凸集分离定理、择一定理和多面体表示定理. 特别地,我们将线性规划的基本定理看成多面体基本性质的一个推论.关于第3章中线性规划最优性条件, 我们是从择一定理的角度给出证明,而不是从单纯形算法的判优规则出发给出的.
本书是在清华大学数学科学系《最优化方法讲义》的基础上经过修改而撰写成的.在清华大学2001---2002学年度的春季学期,数学科学系开设的优化课程中包含"数学规划"和"最优化方法",前者的选课对象为数学系三年级本科生、计算机系二年级本科生以及其他系的部分学生;后者的选课对象为非数学系的研究生, 包括硕士生、博士生,也有部分校外单位的听课生. 来自各方的学生被编成两个大班,其中一个大班由中国科学院数学与系统科学研究院应用数学研究所的韩继业教授负责;另一个大班由当时在数学科学系工作的黄红选博士负责. 关于两个大班教学情况以及作者关于课程建设设想的初步总结,形成了上面提到的讲义. 值得指出的是, 在撰写讲义的过程中,早些年的授课经历(教学资料),特别是清华大学应用数学系(数学科学系的前身)1995级本科生数学规划课程的教学、关于线性规划内点算法的研究与总结材料等,对于讲义的形成都起到重要的作用.印刷这本讲义的首要目的是为了方便2002---2003学年度秋季学期的"最优化方法"课程教学,使得同学们有一本与课程讲授内容相近的参考资料,以便更好地掌握常用的最优化方法, 理解数学规划的原理.《最优化方法讲义》出版后,先后多次应用于清华大学研究生"最优化方法"课程和数学科学系"数学规划"课程的教学实践, 在此基础上形成了本书的基本结构和内容,其中多目标规划和全局优化两章的内容曾作为教学材料用于数学科学系四年级本科生专题课的教学.
多年来,在数学规划(最优化)的课程建设、《最优化方法讲义》的使用以及本书的撰写过程中,有许许多多的热心人给予作者很大的帮助, 借此机会,作者对他们表示衷心的感谢! 特别要感谢清华大学数学科学系的姜启源教授、谭泽光教授、韩云瑞教授、邢文训教授、谢金星教授、李津教授等多年来给予作者的关心和帮助!感谢清华大学热能系张毅同学、数学科学系孙杨同学担任助教期间先后为数学规划(最优化)课程建设付出的辛勤努力!我们还要感谢为此书出版给予支持的清华大学出版社和清华大学工业工程系.最后, 我们要感谢自己的亲人多年来对作者的关心、照顾和鼓励!
衷心地祝愿所有的读者在翻阅此书时愉快, 并有收获!
