優化理論與算法基礎

目   錄

第 1 章 導論與預備知識 1

1.1 歐幾里得空間 中的點集 1

1.1.1 集合  1

1.1.2 歐幾里得空間  的性質  2

1.1.3 中的點集拓撲  4

1.1.4  中的極限  6

1.1.5 上確界與下確界 6

1.2 連續函數 9

1.2.1 連續函數的定義與性質  9

1.2.2 上極限與下極限  11

1.2.3 上半連續性與下半連續性  13

1.3 多元函數的微分中值定理與 Taylor 公式  13

1.3.1 多元函數的微分中值定理  13

1.3.2 多元函數的 Taylor 公式  15

1.4 凸集  16

1.4.1 仿射集  16

1.4.2 凸集  17

1.4.3 凸集分離定理  18

1.5 錐  25

1.5.1 錐和凸錐  25

1.5.2 廣義不等式  26

1.5.3 最小元與極小元  27

1.6 對偶錐. 28

1.6.1 對偶錐  28

1.6.2 對偶廣義不等式  30

拓展閱讀建議  31

第 1 章習題  31

第 2 章 凸函數 34

2.1 凸函數的定義及判定  34

2.1.1 凸函數的定義  34

2.1.2 一元凸函數的判定  35

2.1.3 多元凸函數的判定  36

2.2 凸函數的性質  41

2.2.1 一元凸函數的連續性與單邊導數  41

2.2.2 多元凸函數的連續性 43

2.2.3 上圖與下水平集  46

2.2.4 凸函數的極值  47

2.3 保持凸性的運算 48

2.4 應用及例子  52

2.4.1 .-範數  52

2.4.2 Jensen 不等式  56

2.4.3 凸函數/凹函數的例子 59

2.5 共軛函數  62

2.5.1 共軛函數的定義與計算實例  62

2.5.2 共軛函數的性質  68

2.6 矩陣的核範數  70

拓展閱讀建議  73

第 2 章習題  74

第 3 章 優化問題  80

3.1 優化問題  80

3.2 凸優化問題  82

3.2.1 凸優化問題的概念  82

3.2.2 凸優化問題的性質  82

3.3 Lagrange 對偶函數  85

3.3.1 Lagrange 對偶函數的定義  85

3.3.2 最優值的下界估計  87

3.3.3 Lagrange 對偶函數與共軛函數的關系  88

3.4 Lagrange 對偶問題  90

3.4.1 對偶問題的概念及例子  90

3.4.2 強對偶性  92

3.5 最優性條件  97

3.5.1 無約束優化問題的最優性條件  97

3.5.2 只含等式約束的優化問題的最優條件  98

3.5.3 只含不等式約束的優化問題的最優條件  101

3.5.4 一般形式的 Karush-Kuhn-Tucker 定理  103

3.5.5 凸優化問題的 Karush-Kuhn-Tucker 定理  109

拓展閱讀建議  109

第 3 章習題  109

第 4 章 廣義不等式約束與向量優化  116

4.1 廣義單調性與凸性  116

4.1.1 相關概念回顧  116

4.1.2 在偏序集上取值的函數  117

4.1.3 可微函數的單調性和凸性條件  120

4.2 效用函數相關知識  122

4.2.1 偏序、全序和預序  122

4.2.2 效用函數  124

4.2.3 連續效用函數  126

4.2.4 von Neumann-Morgenstern 期望效用函數  132

4.3 廣義不等式約束的凸優化問題  135

4.3.1 問題的一般形式  135

4.3.2 半定規劃  136

4.3.3 一些例子  137

4.4 向量優化  141

4.4.1 向量優化問題  141

4.4.2 向量優化問題的標量化  143

4.4.3 凸向量優化問題  144

4.5 福利經濟學基本定理  146

4.5.1 產品經濟系統  146

4.5.2 福利經濟學基本定理  148

拓展閱讀建議  150

第 4 章習題  151

第 5 章 優化算法基礎知識  152

5.1 算法的收斂性與收斂速度  152

5.2 一維牛頓法與割線法  154

5.3 區間分割法  157

5.4 線搜索. 161

拓展閱讀建議  172

第 5 章習題  172

第 6 章 梯度下降法與共軛梯度法  174

6.1 梯度下降法  174

6.1.1 梯度下降法的基本思想與算法  174

6.1.2 強凸性  177

6.1.3 梯度下降法的收斂性與誤差分析  179

6.2 共軛梯度法  183

6.2.1 無約束二次優化問題的共軛梯度法  183

6.2.2 非線性共軛梯度法  190

6.3 信賴域子問題 192

6.3.1 信賴域子問題及其最優性條件  192

6.3.2 截斷共軛梯度法  194

6.4 邏輯回歸問題 196

6.4.1 邏輯回歸模型  196

6.4.2 模型參數估計  197

6.4.3 計算實例  202

6.4.4 多分類問題  206

拓展閱讀建議  210

第 6 章習題  210

第 7 章 牛頓法與擬牛頓法  212

7.1 牛頓法. 212

7.1.1 牛頓法的基本思想  212

7.1.2 Hesse 矩陣不正定時的處理  213

7.1.3 牛頓法的收斂性  217

7.1.4 計算實例  220

7.2 擬牛頓法  226

7.2.1 擬牛頓法的基本思想  226

7.2.2 幾種常用的擬牛頓法  228

7.2.3 計算實例  233

7.3 正交距離回歸 238

7.3.1 變量帶誤差模型  238

7.3.2 正交距離回歸模型  239

7.3.3 參數估計算法  240

拓展閱讀建議  245

第 7 章習題  246

第 8 章 線性規劃與二次規劃  249

8.1 線性規劃  249

8.1.1 線性規劃的標準形式  249

8.1.2 線性規劃的對偶問題與最優性條件  250

8.1.3 可行集的幾何性質  251

8.1.4 單純形法  252

8.1.5 啟動點的計算  254

8.2 等式約束二次規劃  255

8.2.1 等式約束二次規劃及其最優性條件  255

8.2.2 等式約束二次規劃算法  257

8.2.3 計算實例  260

8.3 不等式約束二次規劃  261

8.3.1 不等式約束二次規劃的最優性條件  261

8.3.2 積極集方法  262

8.3.3 啟動點的計算  265

拓展閱讀建議  267

第 8 章習題  267

第 9 章 約束非線性優化  269

9.1 等式約束凸優化  269

9.1.1 等式約束凸優化的最優性條件  269

9.1.2 等式約束凸優化的牛頓法  269

9.1.3 初始點不是可行點的牛頓法  271

9.1.4 計算實例  274

9.2 內點法  276

9.2.1 一個具體的例子  276

9.2.2 凸優化問題的內點法  280

9.2.3 兩階段法  283

9.3 支持向量機  284

9.3.1 支持向量機模型  284

9.3.2 求解方法  286

9.3.3 核支持向量機  293

9.3.4 計算實例  297

拓展閱讀建議  301

第 9 章習題  302

第 10 章 機器學習中常用的復合優化算法  303

10.1 增廣 Lagrange 函數法  303

10.1.1 對偶上升法  303

10.1.2 增廣 Lagrange 乘數法  304

10.2 次梯度與次微分  306

10.2.1 擴展實值函數  306

10.2.2 閉函數  307

10.2.3 次梯度與次微分  307

10.2.4 次微分的性質  309

10.2.5 次微分的運算法則  314

10.3 交替方向乘數法  314

10.3.1 算法  314

10.3.2 收斂性分析  316

10.4 近似點算法  320

10.4.1 鄰近算子  320

10.4.2 近似點梯度法  326

10.4.3 LASSO 回歸問題  328

10.5 坐標下降法與分塊坐標下降法  335

10.5.1 坐標下降法  335

10.5.2 分塊坐標下降法  340

10.5.3 應用  341

拓展閱讀建議  344

第 10 章習題 344

附錄 A 特徵值與特徵值分解定理  346

A.1 特徵值與特徵向量. 346

A.2  n 階方陣的特徵分解  347

A.3 實對稱矩陣的對角化與特徵分解  350

A.4 實正定對稱矩陣與二次型  353

附錄 B 奇異值與奇異值分解定理  357

B.1 奇異值與奇異向量 357

B.2 奇異值的存在性及性質  358

B.3 奇異值分解定理  360

B.4 矩陣的低秩逼近  362

B.5 超定線性方程組與矩陣的偽逆  365

附錄 C 矩陣函數的導數與微分  368

附錄 D 反函數定理與隱函數存在定理  374

附錄 E Sherman-Morrison 公式與 Woodbury 公式  378

部分習題答案  381

參考文獻  406