數學規劃

本書以數學規劃為對象, 從理論、算法和計算等方面介紹了分析和求解常見的最優化問題的一些方法. 全書共分8章, 其中第1章介紹了數學規劃的實例、模型以及在分析最優化問題時所涉及的基礎知識, 第2章至第8章分別討論了凸分析、線性規劃、無約束優化、約束優化、多目標規劃、組合優化和整數規劃以及全局優化等七個方面的內容. 此外,書中每章的最後一節給出了一些習題,書末列出了參考文獻和索引.

本書可作為應用數學、計算數學、運籌學與控制論、管理科學與工程、工業工程、系統工程等專業的研究生和高年級本科生學習數學規劃的教材,也可以作為其他需要利用數學規劃方法進行建模和求解實際問題的各個學科領域的科研人員、工程技術人員的參考書 ^[1] 

第1章 引論1

1.1 學科簡介1

1.2 實例與模型4

1.3 預備知識9

1.3.1 線性空間9

1.3.2 範數12

1.3.3 集合與序列14

1.3.4 矩陣的分解與校正15

1.3.5 函數的可微性與展開17

1.4 習題20

第2章 凸分析22

2.1 仿射集22

2.2 凸集與錐25

2.3 凸集分離定理27

2.3.1 點與凸集分離28

2.3.2 凸集與凸集分離31

2.4 多面體理論32

2.4.1 多面體的維數33

2.4.2 擇一定理34

2.4.3 多面體的面和最小不等式表示38

2.4.4 多面體的表示定理44

2.5 凸函數49

2.5.1 基本性質49

2.5.2 函數凸性的判定方法52

2.6 習題54

第3章 線性規劃57

3.1 線性規劃的基本定理57

3.1.1 基本定理與標準形式58

3.1.2 極點的代數特徵61

3.2 單純形算法64

3.2.1 基本原理64

3.2.2 算法步驟與單純形表67

3.2.3 啓動機制70

3.3 線性規劃的最優性條件77

3.4 對偶理論79

3.4.1 對偶定理79

3.4.2 對偶單純形法84

3.5 單純形算法的改進與推廣88

3.5.1 修正單純形法88

3.5.2 原始-對偶算法91

3.5.3 退化與循環94

3.5.4 Dantzig-Wolfe分解算法99

3.5.5 靈敏度分析104

3.6 線性規劃內點算法108

3.6.1 算法複雜性概念108

3.6.2 單純形算法的複雜性111

3.6.3 Karmarkar投影尺度算法114

3.6.4 原始-對偶尺度算法124

3.6.5 原始-對偶路徑跟蹤算法130

3.6.6 內點算法的其他策略137

3.7 習題144

第4章 無約束優化150

4.1 無約束優化的最優性條件150

4.2 算法收斂性152

4.2.1 一維搜索與收斂性152

4.2.2 算法映射與收斂性162

4.2.3 收斂速度與算法停止規則166

4.3 牛頓法170

4.3.1 迭代格式170

4.3.2 局部收斂性172

4.3.3 修正牛頓法174

4.3.4 非精確的牛頓法177

4.4 共軛方向與線性共軛梯度法179

4.4.1 共軛方向與擴張子空間定理179

4.4.2 線性共軛梯度法與二次終止性181

4.5 非線性共軛梯度法186

4.5.1 FR 共軛梯度法187

4.5.2 PRP共軛梯度法192

4.6 擬牛頓方法196

4.6.1 擬牛頓條件和算法步驟196

4.6.2 對稱秩1校正公式197

4.6.3 對稱秩2校正公式200

4.6.4 Broyden族208

4.7 習題213

第5章 約束優化220

5.1 一階最優性條件與約束規格220

5.1.1 一階必要條件220

5.1.2 約束規格226

5.1.3 一階充分條件228

5.2 二階最優性條件230

5.2.1 二階必要條件231

5.2.2 二階充分條件233

5.3 對偶理論235

5.3.1 對偶形式235

5.3.2 對偶定理237

5.3.3 鞍點定理240

5.4 二次規劃242

5.4.1 基本性質244

5.4.2 等式約束的二次規劃248

5.4.3 凸二次規劃的積極約束集方法254

5.4.4 線性互補問題260

5.5 可行方向法265

5.5.1 Zoutendijk可行方向法266

5.5.2 Rosen梯度投影法268

5.5.3 Wolfe既約梯度法270

5.5.4 Frank-Wolfe線性化方法272

5.6 序列無約束化方法273

5.6.1 二次罰函數法275

5.6.2 對數障礙函數法280

5.6.3 乘子法284

5.7 逐次二次規劃法289

5.7.1 Newton-Lagrange方法289

5.7.2 逐次二次規劃的算法模型291

5.7.3 二次規劃子問題的Hesse矩陣297

5.7.4 價值函數與搜索方向的下降性299

5.8 信賴域法305

5.8.1 信賴域法的基本原理305

5.8.2 子問題的精確求解法308

5.8.3 子問題的近似求解法313

5.8.4 信賴域法的全局收斂性318

5.9 習題319

第6章 多目標規劃325

6.1 引言325

6.2 向量集的有效點與弱有效點327

6.2.1 幾何特徵328

6.2.2 代數特徵330

6.3 多目標規劃的解及其性質333

6.3.1 Pareto最優解333

6.3.2 KT-有效解與G-有效解335

6.3.3 最優性條件338

6.4 多目標規劃的解法338

6.4.1 基於一個單目標問題的方法339

6.4.2 基於多個單目標問題的方法343

6.5 習題345

第7章 組合優化與整數規劃347

7.1 網絡流問題與算法348

7.1.1 圖論中的基本概念348

7.1.2 最短路問題350

7.1.3 最大流與最小割問題352

7.1.4 最小費用網絡流問題355

7.1.5 最大森林問題356

7.2 匹配問題與算法357

7.2.1 匹配與最大基數匹配357

7.2.2 二部圖匹配359

7.3 整數規劃的基本性質362

7.3.1 整數規劃的模型363

7.3.2 整數規劃的性質366

7.4 割平面法371

7.4.1 Gomory割平面法371

7.4.2 構造有效不等式的方法379

7.5 分支定界法381

7.5.1 分支定界的基本原理381

7.5.2 分支定界的算法步驟383

7.6 分解算法388

7.6.1 基於Lagrange鬆弛的分解算法388

7.6.2 Benders分解算法392

7.7 習題397

第8章 全局優化401

8.1 全局優化的基本概念與性質401

8.1.1 凸集的性質401

8.1.2 函數的連續性與凹凸性403

8.1.3 凸包絡405

8.1.4 Lipschitz函數409

8.1.5 D. C. 函數411

8.2 常見的全局優化模型413

8.2.1 二次規劃413

8.2.2 凹極小化417

8.2.3 D. C. 規劃419

8.2.4 Lipschitz優化425

8.3 外逼近與割平面算法426

8.3.1 外逼近的基本原理427

8.3.2 割平面算法429

8.3.3 求解鬆弛問題的方法431

8.4 凹性割方法433

8.4.1 有效割與凹性割434

8.4.2 凹性割方法的收斂性437

8.4.3 反向凸約束的凹性割439

8.5 分支定界法441

8.5.1 基本算法442

8.5.2 多面體剖分444

8.5.3 定下界方法446

8.5.4 有限性和收斂性447

8.6 習題449

參考文獻452

索引455

^[1]