最优化计算机原理与算法程序设计

最优化方法是一门古老而又年青的学科。这门学科的源头可以追溯到法国数学家拉

格朗日关于一个函数在一组等式约束条件下的极值问题。伴随着工业、军事技术和管理

决策科学的发展，这门学科也在不断丰富发展它的内涵，衍生出组合优化，线性规划，非线

性规划，动态规划，最优控制等分枝。拉格朗日乘子法则、库恩塔克条件、庞特里雅金极大

值原理、贝尔曼最优化方程，奠定了优化理论研究发展的里程碑。这些经典的优化理论着

重描述了最优解的特征。但是，直到有了高速计算机，人们才能够对各类较大规模的优化

问题利用计算机实施求解，使最优化方法成为工程设计、决策管理的一种实用工具。

几乎所有类型的优化问题都可概括为这样的数学模型:给定一个集合(称为可行集)

和该集合上定义的实值函数(称为目标函数)，要计算函数在集合上的极值。通常，人们按

照可行集的性质对优化问题进行分类:如果可行集中的元素是有限的，则归结为“组合优

化”或“网络规划”，如图论中最短路径、最小费用最大流、最大权匹配等;如果可行集是有

限维空间中的一个连续子集，则归结为线性或非线性规划问题;如果可行集中的元素是依

赖于时间的决策序列，则归结为“动态规划”;如果可行集是无穷维空间中的连续子集(集

合中的元素是有限维空间中的一条曲线，由一组常微分方程描述，而目标函数为一定积

分)，则归结为“最优控制问题”。当然，这样的划分不是绝对的，不论是描述问题或是计算

求解。这些分支都有一定的联系。网络规划的许多问题都可表示为线性规划;而当今流行

的“内点算法”则用非线性规划的方法来求解线性规划。最优控制中的许多算决都可以在

非线性规划中找到它们的影子。

一般说来，各优化分支有其相应的应用领域〔但不是绝对的)。线性规划、网络规划、

动态规划更多地用于管理与决策科学;非线性规划更多地用于工程优化设计;最优控制常

用于控制工程。作为一本主要面向工程类研究生的教材，囿于40学时的教学时数，《最优

化计算原理与算法程序设计》主要介绍了非线性规划的理论和算法，并扼要地介绍了动态

规划的基本原理以及最优控制问题的数值方法。

非线性规划是在一组等式和不等式约束条件下，求一个函数的极值问题。t}si年，

库恩{ H . } , I}uhn)和塔克(A . W . Tt}}ker)等人提出了非线性规划的最优性条件，为其发展奠

定了埋论基础。随着计算机的发展和应用，各种非线性规划算法应运而生。最著名的算

法包括)rJFP { Iaavidon-Fletcher-Powell)和BFGS { Bmgdew-Fietrher-faaldfarh-}hanno)无约束变

尺度法、HP{ Hestenes-Powell )广义乘子法,}iP( }'Vilsan-Han-Powell)约束变尺度法。上述这

些算法都是针对计算日标函数的局部极小点。近十年来，全局优化算法渐露头角，提出了

较为成功的填充函数法。当然，全局优化的理论目前还很不成熟，算法也只是处于实验性

的阶段。本书对上述诸算法均给出了比较详细的介绍，其中，关于全局优化方面的内容，

目前国内的教材很少涉及。

作为土程类的研究生学习最优化方法，主要着重两方面—最优性条件与算法步骤。

如果说最优性条件指明了一次旅行要到达的口的地，那么，算法步骤则指导我们如何一步

一个脚印向目的地进发。本书在描述这些内容时，时刻考虑到大部分工程类研究生的数

学基础，为读者作丫尽可能细致的铺垫。图文井茂的叙述方式，生动、直观而不失严谨。

这是一本既可用于课堂讲授又适宜于自学的教材。

最优化方法是一门工具性的课程，仅仅理解它的内容是不够的。只有将那些算法变

成高质量的计算机程序，这类工具才能为人们广泛利用。按照一张精美的家俱图纸打造

出美观实用的家俱，要靠木匠师傅的技艺;由算法步骤到高质量的模块化结构的计算机程

序同样需要创造性的劳动。本书向读者提供了许多值得借鉴的编程经验、教训和技巧，这

些经验能让人少走弯路。对某些关键性的“算法构件”，本书还为读者提供了值得参考的

源程序。

这是，一本有特色的教材，我乐意将它推荐给广大读者。