最优化是运筹学的一个重要分支，在很多领域具有广泛的应用. 《最优化计算方法》系统地介绍了线性规划、无约束优化及约束优化的基础理论和求解方法，主要内容包括：线性规划的对偶理论与最优性条件、无约束优化的最优性条件、约束优化的最优性条件与鞍点定理；求解线性规划的单纯形算法、内点算法、非内部连续化算法；求解无约束优化的最速下降法、牛顿法、共轭梯度法、拟牛顿法、非单调线搜索法、信赖域法；求解约束优化的序列无约束优化法、可行方向法、序列二次规划法等，也简单介绍了多目标规划的基本理论与求解方法。
更多科学出版社服务，请扫码获取。
目 录
前 言
第1章 引论 1
1.1 最优化问题概述 1
1.2 预备知识 3
1.2.1 向量范数与矩阵范数 3
1.2.2 函数的可徽性 6
1.3 凸集、凸函数、凸规划 8
1.3.1 凸集 8
1.3.2 凸函数 12
1.3.3 凸规划 17
1.4 线搜索选代算法概述及收敛性准则 18
1.4.1 线搜索迭代算法的一般框架 18
1.4.2 选代方向 19
1.4.3 选代步长 20
1.4.4 算法收敛性 24
习题1 25
第2章 线性规划 28
2.1 线性规划问题及其基本概念 28
2.2 线性规划的基本理论 30
2.2.1 解的儿何特性 30
2.2.2 对偶理论与最优性条件 33
2.3 线性规划的单纯形算法 39
2.3.1 算法介绍 39
2.3.2 单纯形表 45
2.3.3 初始基可行解的求法 48
2.4 线性规划的对偶单纯形算法 55
2.5 线性规划的原对偶可行路径跟踪内点算法 57
2.5.1 算法描述 57
2.5.2 算法的多项式复杂性 61
2.6 线性规划的非内部连续化算法 63
2.6.1 算法描述 63
2.6.2 算法的收敢性 66
习题2 72
第3章 无约束优化方法 78
3.1 算法理论基础 78
3.1.1 最优性条件 78
3.1.2 线搜索迭代下降算法及其收敛性 80
3.2 最速下降法 84
3.3 牛顿法 87
3.3.1 经典牛顿法 87
3.3.2 带钱搜索的牛顿法 89
3.4 共辄梯度法 90
3.4.1 二次函数极小化的共辄方向法 90
3.4.2 三次函数极小化的共辄梯度法 93
3.4.3 一般函数极小化的共辄梯度法 94
3.5 拟牛顿法 97
3.5.1 拟牛顿条件 97
3.5.2 DFP算法 99
3.5.3 BFGS算法 102
3.6 非单调线搜索算法 103
3.7 信赖域方法 108
3.8 最小二乘法 112
3.8.1 线性最小二乘问题 112
3.8.2 非线性最小二乘问题 113
习题3 114
第4章 约束优化方法 117
4.1 约束优化问题的最优性条件 117
4.1.1 一阶最优性条件 117
4.1.2 工阶最优性条件 125
4.1.3 凸规划问题的最优性条件 127
4.2 对偶与鞍点问题 129
4.3 二次规划 132
4.3.1 基本概念与基本性质 132
4.3.2 等式约束的三次规划 135
4.3.3 一般的束二次规划的有效集方法 144
4.4 序列无约束方法 147
4.4.1 外罚函数法 148
4.4.2 内罚函数法 155
4.4.3 乘子法 160
4.5 可行方向法 171
4.5.1 Zoutendijk可行方向法 172
4.5.2 Roaen梯度投影法 178
4.5.3 既约梯度法 183
4.6 序列二次规划法 186
习题4 195
第5章 多目标规划简介 202
5.1 多目标规划的模型及其分类 203
5.1.1 多目标规划问题的例子 203
5.1.2 多目标规划问题的数学模型及其分类 204
5.2 多目标规划解的概念及其性质 207
5.2.1 解的概念 207
5.2.2 解的性质 209
5.3 多目标规划问题的解法 212
5.3.1 评价函数法 212
5.3.2 权系数的确定 217
5.3.3 分层求解法 219
习题5 222
参考文献 225
《最优化计算方法》：
第1章 引论
本章首先介绍最优化问题的数学模型?基本概念及其分类， 然后介绍凸集和凸函数的概念及相关性质， 最后介绍线搜索迭代算法的一般框架?线搜索准则及其算法收敛性判别.
1.1 最优化问题概述
在现实社会中， 人们经常遇到这样一类问题： 判别在一个问题的众多解决方案中什么样的方案最佳， 以及如何找出最佳方案. 例如， 在资源分配中， 如何分配有限资源， 使得分配方案既能满足各方面的需求， 又能获得好的经济效益； 在工程设计中， 如何选择设计参数， 使得设计方案既能满足设计要求， 又能降低成本等. 这类问题就是在一定的限制条件下使得所关心的指标达到最优. 最优化就是为解决这类问题提供理论基础和求解方法的一门数学学科.
最优化问题的基本数学模型为
min f（x）
s.t. ci（x） > 0； 8i 2 I ：= f1； 2； ￠ ￠ ￠ ； pg；
ci（x） = 0； 8i 2 E ：= fp + 1； p + 2； ￠ ￠ ￠ ；mg； （1.1.1）
其中， min 是 minimize 的缩写， s.t. 是 subject to 的缩写， x 2 Rn 称为决策向量，函数 f ： Rn ! R 称为目标函数， 函数 ci（￠） （i 2 I） 称为不等式约束函数， 函数ci（￠） （i 2 E） 称为等式约束函数， 不等式 ci（x） > 0 （i 2 I） 称为不等式约束， 方程ci（x） = 0 （i 2 E） 称为等式约束， I 称为不等式约束的指标集， E 称为等式约束的指标集. 记
F ：=8<：
x 2 Rnˉˉˉˉˉˉ
ci（x） > 0； 8i 2 I = f1； 2； ￠ ￠ ￠ ； pg ；
ci（x） = 0； 8i 2 E = fp + 1； p + 2； ￠ ￠ ￠ ；mg9=；： （1.1.2）
那么， 称集合 F 为最优化问题 （1.1.1） 的可行域， F 中的每个点 x 称为最优化问题（1.1.1） 的一个可行点. 若 F = ?， 则称问题 （1.1.1） 是不可行的； 否则称问题 （1.1.1）是可行的. 因此， 最优化问题 （1.1.1） 就是在可行域 F 中寻找一点 x 使得它对应的目标函数值 f（x） 不大于 F 中其他任何点所对应的目标函数值.
定义 1.1.1 假设可行域 F 由 （1.1.2） 式给出.
（i） 若 x¤ 2 F， 且对所有的 x 2 F 恒有 f（x¤） 6 f（x）， 则称 x¤ 为最优化问题（1.1.1） 的一个全局最优解.
（ii） 若 x¤ 2 F， 且对所有的 x 2 F n fx¤g 恒有 f（x¤） < f（x）， 则称 x¤ 为最优化问题 （1.1.1） 的严格全局最优解.
（iii） 若 x¤ 2 F， 且存在 x¤ 的某个邻域
N"（x¤） ：= fx 2 Rn j kx . x¤k < "g； "为正实数且k ￠ k表示某种范数；
使得对所有的 x 2 F \N"（x¤） 恒有 f（x¤） 6 f（x）， 那么称 x¤ 为最优化问题 （1.1.1）的一个局部最优解.
（iv） 若 x¤ 2F， 且存在 x¤ 的某个邻域 N"（x¤）， 使得对所有的 x 2 F \ N"（x¤）n fx¤g 恒有 f（x¤） < f（x）， 那么称 x¤ 为最优化问题 （1.1.1） 的一个严格局部最优解.
显然， 全局最优解一定是局部最优解； 而局部最优解不一定是全局最优解. 求解最优化问题 （1.1.1） 就是在可行域 F 上寻找问题 （1.1.1） 的全局最优解. 但是， 在一般情况下， 不容易求得全局最优解， 往往只能求出局部最优解. 以下若不做特别声明， 全局最优解简称最优解.
定义 1.1.2 对于最优化问题 （1.1.1）， 称其最优解 x¤ 对应的目标函数值 f（x¤）为此优化问题的最优值.
对于最优化问题 （1.1.1）， 最优解不一定存在， 即使存在也不一定唯一； 但是， 若最优解存在， 则最优值必唯一. 以下用 S 表示最优化问题 （1.1.1） 的最优解集. 如果S = ?， 那么最优化问题 （1.1.1） 无最优解； 否则最优化问题 （1.1.1） 有最优解. 显然，若最优化问题 （1.1.1） 不可行； 或者该问题可行但它的目标函数值在可行域上无下界， 则最优化问题 （1.1.1） 都无最优解. 另外需要提到的一点是： 在实际中， 若需要极大化目标函数， 那么通过将目标函数前加负号可转化为极小化问题求解. 因此，不失一般性， 本书中只考虑极小化问题.
最优化问题 （1.1.1） 也常被写成
min8<：
f（x)ˉˉˉˉˉˉ
ci（x） > 0； 8i 2 I ：= f1； 2； ￠ ￠ ￠ ； pg；
ci（x） = 0； 8i 2 E ：= fp + 1； p + 2； ￠ ￠ ￠ ；mg
9=；
或者 minff（x） j x 2 Fg； 或者 minx2F f（x）； 或者 x¤ = arg minx2F f（x） 等， 其中arg min 为 the argument of the minimum 的缩写.
最优化问题形形色色， 对应的最优化模型多种多样， 不同的优化模型， 其求解方法有很大的差异. 因此， 为了有效地求解最优化问题， 人们首先应能区分优化问题的类型. 下面从不同的角度对优化问题进行分类.
（1） 根据有无约束条件分为无约束优化和约束优化 若 F = Rn， 则称问题 （1.1.1） 为无约束优化问题； 若 F μ Rn 且 F 6= Rn， 则称问题 （1.1.1） 为约束优化问题.
（2） 根据所涉及的函数是否线性分为线性规划和非线性规划 若目标函数和约束函数都是线性的， 则称问题 （1.1.1） 为线性规划问题； 若目标函数和约束函数中至少有一个是非线性的， 则称问题 （1.1.1） 为非线性规划问题. 若目标函数是二次函数且所有约束函数都是线性函数， 则称问题 （1.1.1） 为二次规划问题. 二次规划是一 类简单?特殊的非线性规划问题.
（3） 根据目标函数分为单目标规划和多目标规划 若目标函数 f 是一个实值函数， 则称问题 （1.1.1） 为单目标规划问题； 若目标函数 f 是一个向量值函数， 则称问题 （1.1.1） 为多目标规划问题.
（4） 根据涉及函数的可微性质分为光滑优化和非光滑优化 若目标函数和约束函数都是连续可微的， 则称问题 （1.1.1） 为光滑优化问题； 否则称为非光滑优化问题.
（5） 根据涉及函数的凸性分为凸规划和非凸规划 若可行域 F 是凸集且目标函数 f 是凸函数， 则称问题 （1.1.1） 为凸规划问题； 否则称为非凸规划问题. 1.3节将详细介绍凸规划.
（6） 根据可行点的个数情况分为连续优化和离散优化 若可行域 F 中含有无穷多个点且可行域中的点连续变化， 则称问题 （1.1.1） 为连续优化问题. 若可行域F 中含有有限个点或可数个点， 则称问题 （1.1.1） 为离散优化问题. 若所有决策变量取整数， 则称问题 （1.1.1） 为整数规划问题； 若部分决策变量取整数且其他决策变量连续变化， 则称问题 （1.1.1） 为混合整数规划问题. 在整数规划中， 如果决策变量只能取 0 和 1， 那么对应的优化问题称为 0-1 整数规划问题.需要指出两点：第一， 部分不同优化问题在某些情况下可以相互转化； 第二， 这里只是给出一些基本的分类， 最优化问题还有其他的一些分类.本书主要讨论光滑的单目标无约束优化和约束优化问题的理论与求解算法， 对多目标规划只做简单的介绍.
1.2 预 备 知 识
本节介绍在最优化理论与方法中经常使用的数学基础知识， 包括向量范数?矩阵范数?函数的梯度与 Hesse 阵?Taylor 展开式等.
1.2.1 向量范数与矩阵范数
本小节介绍向量范数与矩阵范数的定义以及几个重要不等式.
在本书中， 约定向量取列向量形式， 即 x 2 Rn 是指 x 具有如下形式：
其中， x1； x2； ￠ ￠ ￠ ； xn 分别是向量 x 的分量， 记号 \：=" 表示 \定义". 此外， 对任意的 x； y 2 Rn， 常用的内积 hx； yi 定义为
定义 1.2.1 称映射 k ￠ kRn !R 为 Rn 上的范数， 当且仅当它具有下列性质：
（i） 对任意的 x 2 Rn， 有 kxk > 0， 且 kxk = 0 当且仅当 x = 0；
（ii） 对任意的 x 2 Rn 和任意的 . 2 R， 有 k.xk = j.jkxk；
（iii） 对任意的 x； y 2 Rn， 有 kx + yk 6 kxk + kyk.
对任意的 x 2 Rn， 常用的向量范数如下.
（1） l1-范数： kxk1 =
注 在本书中， 向量范数 k ￠ k2 广为使用， 为了简便， 简写为 k ￠ k.
由上述各种范数的定义，容易验证： 对任意的 x 2 Rn， 有向量范数等价性的定义如下.
命题 1.2.1 假设 k ￠ k. 和 k ￠ kˉ 是定义在 Rn 上的任意两种范数. 那么总存在两个正数 .1 和 .2， 使得对任意的 x 2 Rn， 有 .1kxk. 6 kxkˉ 6 .2kxk
因此，以上定义在 Rn 上的向量范数是等价的. 在最优化方法中， 常需要考察某个点列 fxkg 趋向于 x¤ 的速率， 利用命题 1.2.1， 只需要按某种范数 k ￠ k 考察kxk . x¤k 趋向于 0 的速率即可.
另外，假设 A 2 Rn￡n 是对称正定矩阵. 那么向量的椭球范数 k￠kA 定义如下： kxkA ：= pxTAx； 8x 2 Rn：
1.2 预 备 知 识
类似于向量范数， 可以定义矩阵范数.
定义 1.2.2 称映射 k ￠ k ： Rn￡n ! R 为 Rn￡n 上的范数， 当且仅当它具有下列性质：
（i） 对任意的 A 2 Rn￡n， 有 kAk > 0， 且 kAk = 0 当且仅当 A = 0；
（ii） 对任意的 A 2 Rn￡n 和任意的 . 2 R， 有 k.Ak = j.jkAk；
（iii） 对任意的 A；B 2 Rn￡n， 有 kA + Bk 6 kAk + kBk.
对任意的 A = （aij）n￡n 2 Rn￡n， 最常用的矩阵范数是 Frobenius 范数， 其定义为
其中， Tr（ATA） 表示矩阵 ATA 的迹， 即 ATA 的所有主对角线元素之和， 也等于ATA 的所有特征值之和. 另一个常用的矩阵范数是由向量所诱导的矩阵范数， 也称为算子范数， 其定义为
其中， k ￠ k 是某种向量范数. 特别地， 对任意的 A 2 Rn￡n， 有
（1） 由向量 l1- 范数诱导的矩阵范数 （列范数） 为 kAk1 = max . n Xi=1jaij jˉj 2 f1； 2； ￠ ￠ ￠ ； nga；
（2） 由向量 l1- 范数诱导的矩阵范数 （行范数） 为 kAk1 = max . n Xj=1jaij jˉˉi 2 f1； 2； ￠ ￠ ￠ ； nga；
（3） 由向量 l2- 范数诱导的矩阵范数 （谱范数） 为 kAk2 = p.max（ATA）， 其中.max（ATA） 表示矩阵 ATA 的最大特征值.
假设 k ￠ k 表示上述定义四种矩阵范数中的任意一种范数， 那么它满足相容性件， 即对任意的 A；B 2 Rn￡n， 有 kABk 6 kAkkBk； 并且它与相应的向量范数是 相容的， 即对任意的 A 2 Rn￡n 和 x 2 Rn 有 kAxk 6 kAkkxk.
下面介绍五个常用的不等式.
……
书单推荐
