前言
第1章 凸集和凸函数 1
1.1 最优化问题和方法 1
1.2 凸集及相关性质 4
1.3 凸集的分离 5
1.3.1 点和凸集的分离 5
1.3.2 凸集和凸集的分离 11
1.4 凸函数 13
1.4.1 凸函数及相关性质 13
1.4.2 凸函数的判别 15
1.5 凸规划问题 20
1.6 习题 21
第2章 线性规划的基本性质 23
2.1 线性规划的形式 23
2.1.1 线性规划的三种基本形式 23
2.1.2 三种形式相互等价 29
2.2 可行域和顶点 30
2.3 解线性规划的图解法 32
2.4 基本解和基本可行解 33
2.5 线性规划基本定理 41
2.6 习题 43
第3章 单纯形算法 45
3.1 单纯形算法的基本思想 45
3.2 几何形式的单纯形算法 46
3.3 代数化的单纯形算法 46
3.3.1 基本思想 46
3.3.2 代数化的单纯形算法示例 46
3.4 一般的单纯形算法 51
3.4.1 检验数向量 51
3.4.2 目标函数值和检验数向量的值 51
3.4.3 单纯形算法 53
3.5 表格化的单纯形算法 54
3.5.1 单纯形表 54
3.5.2 旋转 55
3.6 使用数学软件解线性规划 62
3.6.1 使用MATLAB解线性规划 63
3.6.2 使用CPLEX解线性规划 64
3.7 单纯形算法的分析 66
3.8 退化问题的处理 71
3.9 两阶段法 72
3.9.1 两阶段法的基本思想 72
3.9.2 解辅助线性规划 73
3.9.3 两阶段单纯形算法 75
3.10 矩阵的全单位模性质 85
3.11 再议解线性规划 87
3.11.1 单纯形算法的复杂性 87
3.11.2 解线性规划的多项式时间算法 88
3.11.3 单纯形算法的平滑分析 88
3.12 习题 89
第4章 线性规划对偶理论 92
4.1 线性规划的对偶 92
4.2 对偶定理 98
4.3 对偶单纯形算法 107
4.4 关于单纯形表检验数行和右端项的讨论 112
4.5 原始对偶算法 113
4.5.1 最短路问题的整数规划 114
4.5.2 原始对偶算法 115
4.5.3 算法分析 117
4.6 习题 121
第5章 整数规划 124
5.1 整数规划问题 124
5.1.1 背包问题 124
5.1.2 最小生成树问题 125
5.1.3 旅行售货商问题 126
5.1.4 整数线性规划 127
5.2 割平面法 129
5.2.1 割平面法的基本思想 129
5.2.2 割平面的生成方法 129
5.3 分枝定界法 135
5.3.1 分枝定界法的基本思想 135
5.3.2 分枝定界法解整数规划 136
5.4 习题 143
第6章 动态规划 144
6.1 动态规划的原理 144
6.1.1 多阶段决策问题 144
6.1.2 最优化原理 149
6.1.3 前向优化和后向优化 151
6.2 问题举例 152
6.2.1 最长公共子序列问题 152
6.2.2 背包问题 154
6.2.3 从背包问题谈时间复杂度 157
6.2.4 旅行售货商问题 160
6.2.5 一般图上的最短s-t路问题 164
6.3 习题 167
第7章 图与网络算法 169
7.1 最大流问题 169
7.1.1 最大流的增广路算法 169
7.1.2 最大流和最小割 178
7.1.3 对偶理论的观点 179
7.2 最小费用流问题 183
7.3 匹配问题概述 193
7.4 二分图上不带权重的最大匹配问题 194
7.4.1 使用最大流算法求解 194
7.4.2 增广路算法 197
7.5 二分图上带权重的最大匹配问题 204
7.5.1 归约到最小费用流问题的解法 204
7.5.2 匈牙利算法 206
7.6 一般图上的最大匹配问题 211
7.7 习题 211
第8章 无约束优化的基本概念 214
8.1 一元函数的极小化问题 214
8.1.1 黄金分割法 214
8.1.2 函数逼近法 218
8.2 下降方向 218
8.3 一维搜索的基本概念 219
8.4 习题 220
第9章 使用导数的无约束优化方法 221
9.1 无约束优化问题的一阶极值条件 221
9.2 下降算法的一般形式 222
9.3 最速下降法 223
9.3.1 算法 223
9.3.2 搜索为什么要沿负梯度方向进行 223
9.3.3 最速下降法的锯齿现象 227
9.4 牛顿法 228
9.4.1 一元优化问题的牛顿法 228
9.4.2 多元优化问题的牛顿法 230
9.4.3 阻尼牛顿法 234
9.4.4 牛顿法的进一步修正 237
9.5 共轭梯度法 238
9.5.1 基本概念 238
9.5.2 共轭方向的几何意义 239
9.5.3 共轭梯度算法 241
9.5.4 一般无约束优化问题的共轭梯度法 250
9.6 无约束优化问题的二阶极值条件 251
9.7 拟牛顿法 253
9.7.1 拟牛顿方程 253
9.7.2 DFP算法 254
9.7.3 BFGS算法 256
9.8 习题 256
第10章 约束优化问题的基本概念和性质 258
10.1 问题举例 258
10.2 可行方向 260
10.3 不等式约束问题的一阶最优性条件 261
10.3.1 必要条件 262
10.3.2 充分条件 272
10.4 一般约束问题的一阶最优性条件 273
10.4.1 必要条件 273
10.4.2 充分条件 275
10.5 约束优化问题的对偶理论 279
10.5.1 对偶问题 279
10.5.2 凸规划的对偶 283
10.6 习题 288
第11章 约束优化问题的解法 290
11.1 二次规划的解法 290
11.1.1 等式约束二次规划的直接消元法 290
11.1.2 等式约束二次规划的拉格朗日方法 292
11.1.3 一种凸二次规划的有效集方法 295
11.2 简约梯度法 304
11.2.1 简约梯度 304
11.2.2 构造搜索方向 308
11.2.3 算法设计 312
11.3 罚函数法 321
11.3.1 外点罚函数法 321
11.3.2 内点罚函数法 327
11.4 习题 330
第12章 若干基本的数学概念和定理 332
12.1 n维空间中的点与集合 332
12.2 连续和一致连续 333
12.3 无穷小量与无穷小量的阶 333
12.4 一元函数可微和微分 334
12.5 二元函数可微和全微分 335
12.6 泰勒公式 336
12.6.1 带佩亚诺余项的泰勒公式 336
12.6.2 带拉格朗日余项的泰勒公式 336
12.7 方向导数 337
参考文献 339
索引 343

第1章凸集和凸函数
　　本章首先简要介绍最优化方法这门学科，然后着重介绍凸集和凸函数这两个基本概念及其相关的性质.凸集和凸函数在最优化方法中广泛出现在线性规划、无约束优化以及约束优化等问题的描述和求解方法中.
　　1.1最优化问题和方法
　　最优化方法学科研究优化问题的求解方法.现实生活中，优化问题多种多样，最优化方法主要研究那些可以用数学模型刻画的优化问题.这些问题从总体上可分为组合优化问题和连续优化问题两类，它们是按照数学模型中所使用的变量的不同类型来划分的.
　　在历史上，优化技术出现得很早.17世纪时，在微积分技术的发展过程中，牛顿就研究过极值问题.后来又出现了处理带约束的目标函数极值问题的拉格朗日(Joseph-Louis Lagrange，法国，1736-1813)乘数法 1847年，柯西(Augustin-LouisCauchy，法国，1789-1857)研究了函数值沿什么方向下降最快的问题，提出了最速下降法.1939年，康托罗维奇(Kantorovich，苏联，1912-1986)提出了下料问题和运输问题的求解方法.直至20世纪30年代，最优化这个古老的课题尚未形成独立的学科.
　　20世纪40年代以来，由于工业生产和科学研究的迅猛发展，特别是计算机的日益广泛应用，最优化理论和算法迅速发展起来，成为运筹学的主体内容.运筹学(最优化方法)中的组合优化部分和计算机科学中的算法设计与分析部分是部分重合的，由于组合优化技术更强调了数学方法的运用，因此组合优化可以看作是传统的算法设计与分析的延伸.运筹学中的连续优化部分是在数学分析中的求导数和求极值的基础上发展起来的.现在，机器学习中损失函数的求解正好是连续优化问题.因此，运筹学的连续优化部分也构成了应用计算机科学解决实际问题的基础.
　　最优化方法的组合优化技术主要包括整数线性规划、动态规划以及面向问题的各种启发式方法等.最优化方法中的连续优化技术可分为线性规划和非线性规划，也可分为无约束优化和约束优化，这是分别按照不同的划分标准划分的.值得指出的是，线性规划技术，按照变量的类型划分属于连续优化，但线性规划技术也可以用于求解组合优化问题.例如在近似算法中，线性规划是获得广泛成功的一种算法设计方法.使用线性规划技术设计组合优化问题的近似算法时，人们首先用线性规划描述组合优化问题的松弛，然后求解线性规划得到最优解，再通过舍入等方法将线性规划最优解转化为组合优化问题的可行解.
　　下面我们看几个典型的优化问题.
　　例1.1.1利润最大化问题.某工厂用种原料生产种产品.第种原料的数量为每单位的第种产品需要第种原料的数量为，可获利润为.问如何安排生产，才能使总利润最大？
　　例1.1.1中的利润最大化问题是经济领域中经常遇到的一个非常基本的问题.这个问题可以用线性规划或整数线性规划进行描述和求解.
　　在这里，我们定义为第种产品的产量.则所有种产品的总利润就是.问题的目标是最大化这个总利润.当然，利润不可能无限大，因为安排生产受限于原材料的供给.当第种产品的产量为时，生产这种产品对原料的需求为，显然应有，因为第种原料总共有那么多.另外，每种产品的产量也不能为负数.综合起来，我们就得到
　　(1.1.1)
　　这就是例1.1.1的数学模型，这是一个线性规划，因为在这个规划中目标函数和约束条件都只包含变量的一次项，没有变量的二次项以及更高次项，更没有变量的幂以外的其他函数.
　　值得指出的是，线性规划(1.1.1)适用于描述那些产品“无限可分”的利润最大化问题，如产品为面粉、食用油等.换言之，产品数量取值为实数应该是有意义的.
　　如果在利润最大化问题中，产品数量仅能取值为整数，例如产品为家具、门窗等，则我们需要使用整数线性规划为利润最大化问题建模，如线性规划(1.1.2)所示.
　　(1.1.2)
　　1.1最优化问題和方法
　定义1.1.2设施选址问题(FacilityLocation Problem)
　　实例：有个设施和个客户，设施和客户之间，以及设施之间、客户之间都有距离，这些距离满足三角不等式.打开第个设施有一个费用方.每个客户都需要连接到一个打开的设施上.
　　目标：打开若干设施，满足客户的连通需求，使得设施的打开费用和客户的连接费用之和最小.
　　设施选址问题是组合优化领域中一个著名的最小优化问题.它描述了这样一种场景：比如有一个工厂，它有分布在多处地点的零售点.现在这个工厂要建立若干仓库，以满足向零售点配送货物的需要.建设仓库就有一个建设费用，仓库建好之后，零售点就会选择距离最近的仓库供货.如何在若干的候选位置建设仓库，以满足零售点的供货需求，就表达为设施选址问题.在这里，仓库的候选位置就是设施位置，零售点就是客户.设施的打开费用就是建设仓库的费用，客户的连接费用就是所有零售点到其最近的仓库的距离之和.
　　在定义1.1.2中，一个问题是按照实例和目标两部分叙述的.这是在计算机科学中对问题描述的一种常见的形式.定义1.1.2中的“实例”也可以叫做“输入”，“目标”也可以叫做“输出当问题是判定问题时(即，回答“是”和“否”的问题)，“目标”也可以写作“询问.
　　关于设施选址问题，“从m个设施中选择若干设施打开”和“从m个设施位置中选择若干位置建立设施”这两种说法是等价的.
　　在这里，我们继续用线性规划对设施选址问题进行建模，以领略线性规划强大的表达能力.
　　定义变量表示是否打开设施，若，表示不打开设施，若，则表示打开设施定义变量表示客户是否连接到设施上，它的值也是或者.这样，问题的总费用就可以表达为里表示顶点和之间的距离.客户要连接到设施上，必须设施打开的条件下才行，这可以用来表达.另外，每个客户一定要连接到某个设施上，这可表达为.因此，设施选址问题的线性规划模型为.
　　这个线性规划是一个整数线性规划，因为它的每个变量只能取整数值.
　　设施选择问题是一个基本的NP困难问题.设施选址问题还有很多的变形.对于设施选址问题及其变形，学者们设计了很多的近似算法，其中有若干算法是非常有名的.感兴趣的读者可进一步参考等著作及其引用的论文.
　　例1.1.3机器学习中的函数优化问题.神经网络是机器学习中的一种模型，它和优化问题密切相关.多层感知机(Multi-Layer Perceptron，MLP)是一种由若干模拟的神经元排列成矩阵结构的前馈神经网络，它所完成的基本任务是进行分类.可以使用一个函数来表达多层感知机所完成的任务.这里，向量是输入数据，向量:是多层感知机使用的参数，是多层感知机的输出，其含义是把输入数据在参数最的控制下分类成所表达的那种类型.例如，在实际应用中，可将图像数据输入给神经网络，让它将图像分成若干种类型.
　　为了使神经网络能够以尽量高的准确率完成分类，需要设定参数最的合适的值，这是在训练数据的帮助下完成的，即人们通常说的“训练一个神经网络训练集可表达为，即，已经知道数据，的类型为，也称为数据的标签.训练一个神经网络，就是调整参数，使得某种损失函数的值尽量地小.若选择平方误差为损失函数，则多层感知机的优化模型为.
　　其中，表示范数，其定义为按照最优化方法的观点，这是一个无约束优化问题.在这里，为了简单说明问题，我们将优化模型简化了.实际使用的优化模型还要加上一个正则项来进行修正.这些细节就略去了.
　　在足够强大的训练集的支持下将一个神经网络训练好(即，选择好了参数a:的值)，就可以在应用中使用这个神经网络完成数据分类任务了.
　　1.2凸集及相关性质
　　定义1.2.1
　　两个点，的凸组合还是中的一个点.它们的所有凸组合构成以这两个点为端点的一条线段.
　　定义I.2.2
　　定义1.2.3
　　例如，欧氏空间中三角形区域、矩形区域、圆形区域都是凸集.在几何直观上，凸集就是边界“向外鼓”的集合.
　　例1.2.4
　　例1.2.5
　　定义1.2.6
　　在几何直观上，三角形区域的顶点、矩形区域的顶点都是符合定义1.2.6的顶点.读者可领略定义1.2.6的精妙.注意，圆形区域是凸集，它有无数个顶点.
　　凸集具有良好的性质，人们对凸集有比较深入的把握.当一个数学规划的可行解的集合是一个凸集时，意味着这个数学规划可能会比较容易求解.例如，线性规划的可行域是凸集，当一个线性规划有解时，它的最优解可在顶点上取得.这些知识将在第2章中详细介绍.
　　1.3凸集的分离
　　凸集是点的集合，不在一个凸集中的点，在直观上，位于这个凸集的“外面我们如何使用数学的语言来精确描述这种直观？进而，两个凸集若不相交，它们是“分离”开的，这样的直观用数学语言如何表达？令人惊奇的是，这种看上去非常基本的直观概念，却蕴含着深刻的道理.例如，由点和凸集的分离定理1.3.3，可以推导出著名的Farkas引理(引理1.3.4)(G.Farkas，匈牙利，1847-1930)，而Farkas引理可推导出线性规划的强对偶定理(定理4.2.5).再如，由凸集和凸集的分离定理1.3.9可推导出戈丹引理(引理1.3.10)(P.A.Gordan，德国，1837—1912)，而戈丹引理又可推导出关于约束优化的著名的K-T定理(定理10.3.7).
　　1.3.1点和凸集的分离
　　在介绍定理1.3.2之前，先来回顾一下下确界符号inf.
　　定义1.3.1令SgR是一个集合，若3m，使得Vze民都有;则称m是S的一个下界.记L是S的所有下界所组成的集合.则L中的最大元素a称为S的下确界，记为
　　定理1.3.2
　　证明
　　则f(x)是连续函数.
　　若S是有界集，则是非空、有界且闭的，所以函数在上可以达到最小值，即，使得
　　即，
　　现在假设不是有界集.在中任取一点以为球心，为半径做一个球，如图1.3.1所示.
……