本书深入浅出地介绍了线性规划、无约束与有约束的非线性优化方法并对相关的理论作了必要的阐述． 各部分的优化方法都是实用算法， 特别介绍了多项直至2007年的优化方法最新成果． 本书可作为运筹学、应用数学、计算数学和系统工程等专业的大学本科高年级学生和硕士研究生以及工科博士研究生的教材以及相关专业的教师，经济、管理与工程技术人员的参考书．

    最优化问题广泛存在于国民经济的工农业、能源、交通等许多部门以及信息科学、环境科学与军事等领域.“最优化方法”也成为高校应用数学的一门重要课程.本书是作者们在其有关最优化方法教学和指导研究生的讲义与材料基础上，经修改、整合而成的．全书共7章.第一作者以前4章的内容为首都师范大学数学科学学院的本科高年级优化课与研究生讲座讲过多次.前5章内容亦以选讲方式为中国科学院自动化研究所博士生讲过多次.第5~7章的内容及有关文献为第二作者近几年指导山东科技大学信息科学与工程学院的硕士生、博士生的讲义与基本材料.本书的前4章内容适合大学本科高年级学生，后3章面向硕士生与博士生，因此是一本基础与提高相结合的最优化方法教材.本书也可以作为应用数学和计算数学专业的教师、经济与管理工作者、工程技术人员的教学、科研与应用的参考书.

    为了使内容既有一定系统性，又能包括部分最新的研究成果，本书内容略多于一般教材，可根据对象适当取舍选讲.对于本科生，主要讲授基础知识与算法，大部分数学的论证可略去不讲.例如，第1，2章中的可行解表示定理的证明，逆矩阵单纯形方法、混合整数规划的Gomory割平面方法、分解算法可以略去不讲，而Karmarkar内点算法可作简单介绍.第3章中重点讲述共轭梯度法与拟牛顿算法.第4章简述最优性条件，主要介绍约束优化算法特别是二次规划的有效集方法、GRG方法与乘子法.根据授课对象情况，可用54学时或72学时讲授全书.

    本书主要内容涉及线性规划、无约束最优化、有约束最优化（非线性规划）、变分不等式和并行优化方法的基本理论和算法.主要介绍用于各种优化模型的求解算法及必要的相关理论.在介绍基础知识、传统的实用算法的基础上，介绍了多种近代算法，如著名的线性规划的Karmarkar内点算法、戴彧虹袁亚湘共轭梯度法、拟牛顿算法、序列二次规划（SQP）方法、系列线性方程组（SSLE）方法、PVD和PVT并行优化算法，其中包括多项近年直至2007年的研究成果，并提供了一些有助于了解各个方向研究动态的参考文献.其中如“有效集识别技术”、“无严格互补松弛假设条件”的算法等是近年的新成果，相信会引起人们的兴趣.第7章的并行算法，虽然国内研究的人不多，但随着计算机技术的发展，定会引起人们的关注.

    本书有如下特点： ①方法的适应面广、实用性强.②基础知识、实用传统算法与近代算法相结合.③采用几何直观与通俗语言表述.例如，第1章，先从线性规划约束条件构成的可行集的几何结构分析入手，从二维到n维，将极点与基础可行解、几何与代数特性对应，从直观上、整体上理解线性规划解的存在性、最优解的特征与解法性质，为掌握线性规划建立良好的基础.同时也显示了Farkars定理的基础作用.尽可能采用通俗语言来表述，以增加可读性.我们认为只要掌握有关的优化方法，就可以将它运用于实际，产生经济效益和社会效益.

    本书的出版得到亚太运筹学研究中心和国家自然科学基金（10571109）的资助并得到前中国运筹学会理事长章祥荪研究员的热情支持与鼓励，他为本书进行了认真的审查.第一作者曾在首都师范大学数学科学学院讲授优化课程3个学期，自始至终得到数学科学学院院长李庆忠教授、副院长朱一心教授与焦宝聪教授的积极支持和热情关怀.本书初稿整合完成以后，山东科技大学信息科学与工程学院的赵茂先教授、王永丽博士、韩丛英博士、首都师大数学科学学院陈兰平教授分别阅读了各章.作者们在此对他们的热情关怀、支持、帮助与提出的宝贵意见表示衷心的感谢.我们也对中国科学院自动化研究所研究生处的热情支持与清华大学出版社的佟丽霞、陈国新、王海燕老师对本书的出版的热情支持与指导表示衷心的感谢.同时，我们还要向协助我们付出许多劳动的中国科学院自动化所04级博士研究生张昌华、王秀菁，北京交通大学04级博士研究生卞文良，山东科技大学信息学院的硕士研究生王鑫、朱笑容，首都师大05级硕士研究生罗卓笔等同学表示衷心的感谢！

    限于作者的水平，书中不妥之处在所难免，敬请读者们批评指正.

赖炎连  贺国平

2007年7月

第1章线性规划的性质与算法

1.1线性规划的基本性质

1.1.1线性规划问题与数学模型

1.1.2约束集合的几何与代数特性

1.1.3线性规划的基本定理与解的类型

*1.1.4分离定理与可行解的表示定理

1.2线性规划的基本算法

1.2.1线性规划的单纯形方法

1.2.2逆矩阵单纯形方法

1.2.3关于退化与循环的问题

1.3线性规划的最优性条件

1.3.1Farkas定理与最优极点

1.3.2线性规划的最优性条件

习题

参考文献

第2章线性规划的对偶与算法发展

2.1对偶线性规划

2.1.1对偶问题与对偶规划

2.1.2对偶定理与对偶单纯形方法

2.1.3影子价格及其经济意义

2.2整数线性规划

2.2.1整数规划问题与预备知识

2.2.2分支定界方法

2.2.3Gomory割平面方法

*2.3线性规划的DantzigWolfe分解算法

2.3.1DW分解算法原理

2.3.2DW分解算法的计算步骤

2.4线性规划的Karmarkar算法

2.4.1Karmarkar算法的基本概念与算法步骤

2.4.2关于Karmarkar算法性质的主要定理

习题

参考文献

第3章无约束非线性最优化方法

3.1预备知识

3.1.1凸函数与无约束优化的最优性条件

3.1.2下降算法与一维搜索方法

3.2最速下降法、牛顿法与改进算法

3.3共轭梯度法

3.3.1共轭方向与共轭梯度法

3.3.2共轭梯度法的性质与收敛性定理

3.3.3戴彧虹袁亚湘共轭梯度法

3.4拟牛顿算法

3.4.1拟牛顿算法的公式结构

3.4.2拟牛顿算法的基本性质

3.4.3关于拟牛顿算法的收敛性与超线性收敛性

3.5信赖域方法

3.5.1信赖域方法与基本性质

3.5.2LevenbergMarquardt方法

习题

参考文献

第4章约束优化的基本理论与算法

4.1约束规格与最优性条件

4.1.1约束优化的基本概念

4.1.2约束规格与KKT条件

4.2约束优化的基本算法

4.2.1FrankWolfe方法

4.2.2二次规划与有效集方法

4.2.3简约梯度法与广义简约梯度（GRG）方法

4.2.4罚函数与乘子法

4.3梯度投影算法与线性方程组方法

习题

参考文献

第5章约束优化问题的序列二次规划方法

5.1SQP方法

5.1.1WHP方法及相关问题

5.1.2二阶修正的SQP方法

5.1.3子问题相容的SQP算法

5.2投影拟牛顿算法

5.2.1线性约束优化的投影拟牛顿算法

5.2.2非线性约束优化的投影拟牛顿信赖域算法

5.3无严格互补松弛假设条件的算法

5.3.1KKT点的有效集识别技术

5.3.2无严格互补松弛假设条件的算法

参考文献

第6章超线性收敛的序列线性方程组方法

6.1序列线性方程组（SSLE）方法

6.1.1QPFREESSLE方法

6.1.2SSLE方法

6.1.3无严格互补松弛条件的SSLE方法

6.2广义投影SSLE算法

6.2.1广义投影方法

6.2.2广义投影SSLE方法

6.3变分不等式与SSLE方法

6.3.1VIP与等价的优化问题

6.3.2不需要计算F（x）导数的算法与SSLE算法

参考文献

第7章优化问题的并行算法

7.1无约束优化问题的并行算法

7.1.1无约束问题的并行变量分配算法

7.1.2同步运算的并行变量转换算法

7.1.3异步运算的并行变量转换算法

7.2约束可分优化问题的并行算法

7.2.1约束优化问题的并行SQP算法

7.2.2约束优化问题的并行SSLE算法

7.3线性约束问题的并行算法

7.3.1线性约束优化问题的PVD算法

7.3.2线性约束优化问题的PVT算法

参考文献