第1章 关于凸性和最优化的基本结果 1
1.1 凸集和函数 1
1.2 最优化问题的一般特性 10
1.3 凸包络 17
1.4 库恩-塔克条件 21
1.5 二阶最优性条件 26
1.6 非线性规划的对偶性 28
1.7 复杂性论题 35
1.7.1 二次规划中库恩-塔克点的复杂性 37
1.7.2 局部极小化的复杂性 39
1.8 习题 43
第2章 二次规划 54
2.1 引言 54
2.2.1 线性和二次0-1规划 56
2.2 二次整数规划 56
2.2.2 非线性指派问题 58
2.2.3 最大团问题 62
2.2.4 二次0-1规划的分支定界算法 68
2.3 线性互补问题 79
2.4 二次优化的复杂性 81
2.4.1 二次优化是NP难的 81
2.4.2 在任意矩形超平行体上极大化欧氏范数的多项式算法 87
2.5 枚举方法 92
2.6 可分和插值 96
2.6.1 归约为可分形式 97
2.6.2 线性下方估计量和误差界 98
2.6.3 可保证的ε-近似解 102
2.6.4 实现方式 103
2.6.5 不定二次问题 109
2.7 习题 111
第3章 一般凹极小化 120
3.1 引言 120
3.2 应用 121
3.2.1 固定费用和规模经济 121
3.2.2 可转化为凹极小化问题的问题 123
3.3 基本操作 130
3.3.1 假设 130
3.3.2 “标准”多胞形上的凹极小化 131
3.3.3 γ-扩张 134
3.3.4 顶点枚举 136
3.3.5 极大面枚举 143
3.3.6 多面体剖分 147
3.4 割平面算法 149
3.4.1 凹性割 150
3.4.2 用于凹二次函数的割平面 152
3.4.3 算法3.1(割平面法) 157
3.5 外逼近算法 163
3.5.1 基本方法 163
3.5.2 算法3.2的实现 164
3.5.3 凸约束的外逼近 170
3.6 内逼近算法 174
3.6.1 基本算法 174
3.6.2 算法实现和有限收敛性 176
3.7 分支定界算法 179
3.7.1 基本算法 180
3.7.2 单纯形分支定界算法 183
3.7.3 锥形分支定界算法 190
3.7.4 矩形算法 196
3.7.5 凸约束的分支定界法 200
3.8 二次规划的单纯形分支定界法 202
3.9 习题 208
第4章 D.C.规划 216
4.1 引言 216
4.2 D.C.函数空间 217
4.3 一些其他的应用 222
4.3.1 反向凸约束 222
4.3.2 分离的D.C.规划 223
4.3.3 带有吸引和排斥的韦伯问题 224
4.3.4 极小极大问题 225
4.3.5 工程设计 227
4.4 最优性条件 229
4.5 典范D.C.规划 234
4.5.1 D.C.集和D.C.规划向典范形式的变换 234
4.5.2 典范D.C.规划的最优性条件 236
4.5.3 边跟踪算法 238
4.6 单纯形分支定界算法 244
4.7 在多胞形上极小化D.C.函数的棱柱算法 251
4.8 习题 261
第5章 利普希茨优化 264
5.1 利普希茨函数 264
5.2 利普希茨优化问题 267
5.2.1 逼近问题 268
5.2.2 非线性方程组和不等式组 270
5.3 下界 271
5.4 分支定界算法 276
5.4.1 矩形和单纯形上的利普希茨优化 276
5.4.2 线性约束 282
5.4.3 利普希茨约束 284
5.5.1 一般性评注 289
5.5 分支定界法的实现和数值结果 289
5.5.2 数值实例 290
5.6 习题 294
第6章 网络中的全局优化 297
6.1 引言 297
6.2 MCCFP的一些模型及其复杂性 300
6.2.1 固定费用的网络流问题 300
6.2.2 具有凹的生产成本的生产-运输问题 301
6.2.3 网络中的施泰纳问题 303
6.2.4 生产-库存问题 304
6.2.5 MCCFP的复杂性 306
6.3 求解方法 306
6.3.1 求解问题P(C1，Lm-1)的算法 306
6.3.2 求解问题P(Cp，Lq)的算法 309
6.3.3 求解问题P(Cm，Lo)的分解算法 318
6.4 习题 319
第7章 非凸优化中的分解算法 323
7.1 引言 323
7.2 变量分解 锥形算法 325
7.2.1 基本操作 325
7.2.2 算法 330
7.2.3 示范性例子 332
7.3 变量分解 外逼近 335
7.4 约束分解 锥形算法 340
7.5 约束分解 割平面算法 348
7.5.1 算法 348
7.5.2 实现与收敛性 350
7.6 习题 353
参考答案 355
参考文献 382
索引 390