01 / 導讀
導讀
引用
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. 官方免費版本：https://web.stanford.edu/~boyd/cvxbook/
章節概要
全書共十一章，分為理論、應用、演算法三部分，另有三個附錄，每章末附習題。前言把目標定為掌握凸最佳化的實用知識：能夠識別、建模並求解凸問題。
第1章：Introduction（引言）
本章先給出一般的最佳化問題，把最小二乘和線性規劃作為有可靠求解方法的兩類問題，並把凸最佳化呈現為它們的共同推廣。隨後對比局部最佳化與全域最佳化，說明凸問題如何幫助處理非凸問題（提供初始點、稀疏解之類的啟發式方法、下界），並概述全書三個部分。
第2章：Convex sets（凸集）
先講仿射集與凸集、錐，以及標準例子（超平面、球與橢球、範數錐、多面體和半正定錐）。接著介紹保持凸性的運算、關於真錐的廣義不等式、分離與支撐超平面，以及對偶錐。
第3章：Convex functions（凸函式）
本章透過一階與二階條件、下水平集、上境圖和 Jensen 不等式定義凸函式，並列出大量例子。隨後建立保持凸性運算的“演算”（求和、逐點最大、複合、極小化、透視），再講共軛函式、擬凸函式、對數凹與對數凸函式，以及關於廣義不等式的凸性。
第4章：Convex optimization problems（凸最佳化問題）
這是講建模的一章。內容包括標準形式、等價問題以及可微目標的最佳性準則，然後按一般程度遞增列出主要問題族：線性規劃、二次規劃與二階錐規劃、幾何規劃、錐規劃與半定規劃，以及帶有 Pareto 最佳性和純量化的向量（多準則）最佳化。
第5章：Duality（對偶）
由 Lagrange 函式、對偶函式和對偶問題引出弱對偶、強對偶與 Slater 約束規範。隨後給出幾何解釋與鞍點解釋、KKT 最佳性條件、擾動與靈敏度分析、先變換問題再求對偶的例項、擇一定理，以及向廣義不等式的推廣。
第6章：Approximation and fitting（逼近與擬合）
範數逼近、最小範數問題、正則化逼近（包括雙準則權衡、平滑與去噪）、穩健逼近（隨機與最壞情形），以及函式擬合與插值；擬合部分還包括透過基追蹤得到稀疏表示。
第7章：Statistical estimation（統計估計）
極大似然與極大後驗估計、非引數分佈估計、最佳檢測器設計與假設檢驗、Chebyshev 與 Chernoff 界，以及實驗設計，均表述為凸問題。
第8章：Geometric problems（幾何問題）
集合上的投影、集合間的距離、Euclid 距離與角度問題、極值體積橢球、定心（Chebyshev 中心、最大體積橢球中心與解析中心）、線性與非線性判別的分類、佈局與定位，以及平面佈置。
第9章：Unconstrained minimization（無約束極小化）
本章在強凸性假設下引入下降方法，隨後講梯度下降、不同範數下的最速下降和 Newton 法，每種方法都有收斂性分析和數值例子。接著引入自協調性，這是 Newton 法進一步收斂分析所依據的條件，最後給出計算 Newton 步的實現說明。
第10章：Equality constrained minimization（等式約束極小化）
Newton 法被推廣到帶線性等式約束的問題：先講消元法和透過對偶求解，再講帶等式約束的 Newton 步和不可行起點 Newton 法。凸凹博弈作為一個應用出現，實現一節討論 KKT 系統的求解。
第11章：Interior-point methods（內點法）
對數障礙函式與中心路徑引出障礙法，隨後是收斂分析、尋找可行點的第一階段方法，以及基於自協調性的複雜度分析。本章還把障礙法推廣到廣義不等式，介紹原始—對偶內點法，最後討論線性規劃、半定規劃和網路速率最佳化的實現。複雜度一節的小結指出，最壞情形的界遠高於實務上觀察到的迭代次數。
附錄 A–C：Mathematical background；Problems involving two quadratic functions；Numerical linear algebra background（數學背景；涉及兩個二次函式的問題；數值線性代數背景）
附錄 A 彙集範數、分析、函式、導數和線性代數，並確定記號。附錄 B 處理含兩個二次函式的最佳化問題（S 引理和兩個對稱矩陣的值域），並給出相關強對偶結果的證明。附錄 C 涵蓋矩陣結構與浮點運算量、分解—求解法、LU、Cholesky 與 LDL^T 分解、分塊消元與 Schur 補。
核心概念
第2–3章：凸集；凸函式
- 保持凸性的運算：交集、仿射對映、非負加權和與逐點最大等規則，使讀者能把複雜的集合或函式拆成簡單部分，從而識別其凸性。
- 廣義不等式：由真錐定義的序，使向量與矩陣不等式可以像純量不等式一樣處理。
第4章：凸最佳化問題
- 問題層級：線性、二次、二階錐、幾何和半定規劃，是一層比一層一般的凸問題類。
- Pareto 最佳性：多準則問題中最佳權衡的概念，透過純量化加以研究。
第5章：對偶
- Lagrange 對偶與強對偶：對偶問題給出最佳值的下界，Slater 條件保證凸問題中該下界是緊的。
- KKT 條件：把原始可行性、對偶可行性與互補鬆弛結合起來的最佳性條件。
- 靈敏度分析：由對偶變數讀出約束變化時最佳值的響應。
第6–8章：應用
- 正則化與穩健性：在資料擬合與第二個準則之間權衡，或抵禦資料中的不確定性。
- 極大似然估計：把引數估計表述為對數似然函式的最大化。
第9–11章：演算法
- Newton 步與 Newton 減量：由二次模型得到的下降方向，以及用來衡量進展和停止的量。
- 自協調性：關於三階導數的條件，支撐 Newton 法的複雜度界。
- 障礙法與中心路徑：透過一系列等式約束問題來求解不等式約束問題。
評析
優點
- 以建模能力為組織主線。 前言和第1章指出，凸最佳化的難處在於識別和建模問題，全書結構隨之展開：第2至4章藉助集合、函式與問題類的目錄訓練識別能力，第二部分則加以應用。
- 簡短易懂的應用。 第二部分採用統計、幾何和資料擬閤中的簡化案例，篇幅精簡，照顧非專業讀者。
- 清晰的演算法層級。 第三部分從二次問題出發，經帶等式約束的 Newton 法到內點法，使每種方法都化為一系列更簡單的問題。
- 訓練建模的習題。 許多習題要求證明凸性或對問題建模，部分數值習題只需少量程式設計。
侷限
- 並非凸分析的理論專著。 前言說明本書主要不是講凸分析，也不給出結果的最一般形式；需要這類深度的讀者須另讀其他教材。
- 只講選定的演算法。 第三部分只限於 Newton 型和內點法，且是簡化形式。作者把擬 Newton、共軛梯度、束方法和割平面法列為未涵蓋的類別。
- 習題難度不一。 引言說明難度會毫無預告地從簡單變到棘手，因此選題需要一些斟酌。
- 要求一定的數學成熟度。 前言要求讀者熟悉高等微積分和線性代數，並指出沒學過基礎分析與機率的讀者仍能掌握要點，但未必能跟上每一個論證。
在課程中的定位
Boyd 與 Vandenberghe 是本課程中專講凸最佳化的教材。書單中另有兩本起點更早：A Gentle Introduction to Optimization 面向學過線性代數入門課的學生，講線性與整數規劃及單純形法；Chong、Lu 與 Żak 的 An Introduction to Optimization 為高年級本科生講無約束、線性與約束非線性最佳化。兩者都可在讀本書之前打下最佳性條件和線性規劃的基礎，而本書前言正是把高等線性代數與線性規劃當作自然的先修內容。
Boyd 與 Vandenberghe 與它們的不同在於一切圍繞凸性組織：對偶、錐規劃和內點法居於核心，而不是後加的內容。書單中關於高等數學方法以及經濟與商業數學的另兩本書範圍更廣，最佳化只是其中一個主題，因此當專案需要認真地為凸問題建模並求解時，應選用本書。
如何使用本書
本書面向使用最佳化的研究人員、科學家和工程師，也適合研究生課程。作者稱，一個學季的研究生課程可以講完大部分內容但不深入，一個學期則可以安排更多應用並做一個小專案。前言說明所需背景僅為高等微積分和線性代數；懂一些分析和機率則能跟上每一處論證。
實用的閱讀安排：
- 核心： 第1章；第2、3章選讀（例子和保持凸性的運算比每個證明更重要）；第4、5章通讀。這四章承載建模與對偶的技能。
- 應用： 按興趣從第6至8章選讀，例如第6章講擬合與正則化，第7章講統計，第8章講幾何與分類。
- 演算法： 按順序讀第9至11章，因為每章都建立在前一章之上。第11.5節的複雜度分析初讀時可跳過；該節自己的小結稱其主要具有理論意義。
- 附錄： 附錄 A 用來查記號，實現 Newton 步和 KKT 系統求解前再讀附錄 C。
先做要求建模或證明凸性的習題，再做數值習題，並把每個建模都寫成標準形式。用求解器在小規模例項上檢驗建模，是檢驗理解最直接的辦法。
版本與來源
本導讀依據第一版（Cambridge University Press，2004），採用作者網站上釋出的版本，即 2009 年含勘誤的第七次印刷。官方免費版本見 https://web.stanford.edu/~boyd/cvxbook/。該版本由前言、完整目錄、全部節與小節標題、完整的引言，以及各章的選讀段落（包括第11章的複雜度小結和 Newton 步的實現說明）為依據。