01 / 導讀
導讀
引用
Chong, E. K. P., Lu, W.-S., & Żak, S. H. (2023). An Introduction to Optimization: With Applications to Machine Learning (5th ed.). Wiley.
章節概要
全書分五個部分共31章，約670頁，另有參考文獻和索引。出版社稱每章之後都有MATLAB練習和習題。據出版社介紹，第5版新增了一章拉格朗日對偶，並擴充了矩陣博弈、投影梯度演算法和機器學習的內容。
第一部分（第1–5章）：數學回顧
第1章"證明方法與一些記號"僅用幾頁介紹真值表、德摩根律、條件語句與雙條件語句、直接證明、反證法（逆否）、歸謬法和歸納法，以及集合記號。第2章"向量空間與矩陣"講向量與矩陣、秩、線性方程組、內積與範數。第3章"變換"講線性變換、特徵值與特徵向量、正交投影、二次型和矩陣範數。第4章"幾何中的概念"講線段、超平面與線性簇、凸集、鄰域、多胞形與多面體。第5章"微積分基礎"講數列與極限、可微性、導數矩陣、求導法則、水平集與梯度、泰勒級數。
第二部分（第6–14章）：無約束最佳化
第6章"集合約束與無約束最佳化基礎"引入集合約束和無約束問題以及局部極小點的條件。第7章"一維搜尋方法"講黃金分割法、斐波那契法、二分法、牛頓法、割線法、括號法以及多維最佳化中的線搜尋。第8章"梯度法"和第9章"牛頓法"連同分析一起介紹最速下降法和牛頓法，以及列文伯格–馬夸特修正和非線性最小二乘。第10章"共軛方向法"和第11章"擬牛頓法"講共軛梯度演算法、秩一修正、DFP和BFGS。第12章"求解線性方程組"講最小二乘、遞推最小二乘、最小範數解和卡茨馬茲演算法。第13章"無約束最佳化與神經網路"講單神經元訓練和反向傳播。第14章"全域搜尋演算法"講內爾德–米德演算法、模擬退火、粒子群最佳化和遺傳演算法。
第三部分（第15–19章）：線性規劃
第15章"線性規劃導論"講簡史、簡單例子、二維線性規劃、凸多面體、標準形和基本解。第16章"單純形法"展開行運算、規範增廣矩陣、單純形演算法、矩陣形式、兩階段法和修正單純形法。第17章"對偶"講對偶線性規劃、其性質和矩陣博弈。第18章"非單純形法"講哈奇揚方法、仿射縮放法和卡瑪卡方法。第19章"整數線性規劃"講單模矩陣和戈莫里割平面法。
第四部分（第20–25章）：非線性約束最佳化
第20章"等式約束問題"講切空間與法空間、拉格朗日條件、二階條件，以及線性約束下二次函數的極小化。第21章"不等式約束問題"講卡魯什–庫恩–塔克條件和二階條件。第22章"凸最佳化問題"講凸函數、凸最佳化問題和半定規劃。第23章"拉格朗日對偶"（本版新增）講原–對偶對、對偶的一般性質、強對偶和凸的情形。第24章"約束最佳化演算法"講投影、投影梯度法及其收斂性、拉格朗日演算法和罰函數法。第25章"多目標最佳化"講帕累托解、帕累托前沿的計算、化為單目標問題以及不確定的線性規劃問題。
第五部分（第26–31章）：機器學習中的最佳化
第26章"機器學習問題與特徵工程"講資料歸一化、方向梯度直方圖、主成分分析與線性自編碼器。第27章"隨機梯度下降演算法"講隨機梯度下降及其方差縮減的變體。第28章"線性迴歸及其變體"講最小二乘迴歸、交叉驗證和正則化。第29章"用於分類的邏輯迴歸"講二分類和多類別分類。第30章"支援向量機"講合頁損失、二分類與多類別分類以及核技巧。第31章"K均值聚類"講該演算法、K-means++初始化、變體以及用向量量化進行影像壓縮。
核心概念
第一部分：數學回顧
- 證明方法：直接證明、反證（逆否）、歸謬和歸納。
- 二次型：後面用來陳述二階條件的矩陣工具。
- 凸集與多面體：線性規劃和凸最佳化所依賴的幾何。
- 梯度與泰勒級數：局部極小點條件背後的微積分。
第二部分：無約束最佳化
- 局部極小點的條件：第6章中的一階和二階條件。
- 最速下降法、牛頓法與擬牛頓法：迭代演算法的幾個主要系列，在第8至11章中通過分析加以比較。
- 共軛梯度演算法：為二次問題設計、並推廣到非二次問題的方法。
- 反向傳播：用於訓練神經網路的梯度計算。
第三、四部分：線性與非線性約束最佳化
- 單純形法與基本解：在多面體的頂點之間移動。
- 對偶：線性規劃的對偶，以及新增的第23章中非線性規劃的拉格朗日對偶。
- 卡魯什–庫恩–塔克條件：不等式約束的一階條件。
- 帕累托前沿：多目標問題中權衡解的集合。
第五部分：機器學習
- 隨機梯度下降：用樣本而不是整個目標函數來更新。
- 邏輯迴歸與支援向量機：通過最佳化訓練出來的分類器。
- K均值聚類：通過反覆指派和更新中心來聚類。
評析
優點
- 自足的預備知識。 第一部分在最佳化各章開始之前複習所需的線性代數、幾何和微積分，因此有知識缺口的讀者可以在書中補上。
- 範圍廣而有條理。 一本書從無約束方法走到線性規劃、非線性約束問題和機器學習。出版社把本書定位為一到兩學期的本科高年級或研究生起始階段課程的教材。
- 計算方面的支援。 出版社宣傳每章之後的MATLAB練習和例題。作者的網頁連結了演算法的M檔案、第五部分的資料集和程式碼，以及Paul Atzberger及其UCSB學生提供的部分演算法的Python程式碼。
- 來自舊版書評的稱讚。 封底引用了MAA Reviews對第3版的評價：本書引導讀者沿著學習路徑前進，例子陳述清楚，結果的呈現注重細節。
局限
- 解答手冊僅限教師。 解答手冊只提供給採用本書的教師，因此自學者只能在沒有答案的情況下做題。
- 某些地方廣而不深。 從目錄看，有些話題的處理似乎很簡短：半定規劃只是第22章的一節，整數規劃是隻有三節的一章。需要全面學習凸最佳化的讀者需要一本專門的教材。
- 神經網路止於基礎。 它們只出現在第13章（單神經元訓練和反向傳播），而機器學習部分列出的是迴歸、邏輯迴歸、支援向量機和K均值，沒有列出深度網路的結構。
- 對一門課來說篇幅很長。 31章、約670頁，一門課必須取捨。
在課程中的定位
在最最佳化與應用數學的書單中，Chong、Lu和Żak是涵蓋標準課程內容的通用教材。Guenin、Könemann和Tunçel的 A Gentle Introduction to Optimization 只假定學過線性代數的第一門課，以問題的建模和單純形法為基礎，是更平緩的第一門課。Boyd和Vandenberghe的 Convex Optimization 是當凸問題和對偶成為主題時更嚴格的後續讀物，本書的第22、23章可以作為過渡。
書單上的其他書涵蓋面更廣：Ostaszewski的 Advanced Mathematical Methods 把線性代數和微積分與應用結合起來，Jacques的 Mathematics for Economics and Business 把最佳化放在經濟背景下，Goriely的 Applied Mathematics: A Very Short Introduction 則是對應用數學家如何工作的非技術性概覽。
如何使用本書
出版社把本書定位為最最佳化理論與方法的一到兩學期的本科高年級或研究生起始階段課程的教材，也供數學、運籌學、電氣工程、經濟學、統計學和商學領域的研究人員和從業者參考。本站列出的先修條件是多元微積分和線性代數。
一個實用的計畫如下：
- 一學期課程的核心： 無約束最佳化的第6–11章、線性規劃的第15–17章，以及約束最佳化的第20、21章。
- 拓展： 為走向現代理論的讀者準備的凸最佳化第22章和拉格朗日對偶第23章；第12–14章和第18–19章可作為選讀。
- 機器學習路線： 為第五部分做準備，較為合適的是提供梯度法、最小二乘和反向傳播的第6–9章、第12章和第13章。
- 練習： 藉助作者網頁上的MATLAB或Python程式碼做練習，並把第一部分當作複習，而不是從頭讀到尾。