最優化方法

前言
第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