A Gentle Introduction to Optimization（最佳化入門）

引用

Guenin, B., Könemann, J., & Tunçel, L. (2014). A Gentle Introduction to Optimization. Cambridge University Press.

章節概要

本書篇幅不長，約 280 頁：七章正文加一篇關於計算複雜度的附錄，附有 140 多道習題。標有星號的節與章設計成可以略過而不影響後文，多數章節以「Further reading and notes（延伸閱讀與註記）」一節作結。序言指出，鬆弛、原始–對偶的思考方式、凸性與幾何詮釋是貫穿全書的主線。

第1章：導論

本章談的是建模，而不是求解。它從虛構公司 WaterTech 的一個小型生產規劃問題出發，區分問題的文字敘述與數學表述，並說明一個表述「正確」代表什麼。接著介紹線性規劃（包括多期模型）、整數規劃（指派問題與背包問題）、圖上的最佳化問題（最短路徑與最小成本完美配對，先以問題形式描述，再寫成整數規劃）以及非線性規劃，後者的例子包括替一項電子產品定價，以及尋找線性規劃的「中心」可行解。

第2章：求解線性規劃

本章從線性規劃的三種可能結果（不可行、無界、有最佳解）出發，把問題轉成標準等式形式，定義基底與典範形式，從單一次迭代開始逐步建立單形法，並以兩階段法求出初始可行解。單形法的表格（tableau）形式是標有星號的一節。本章最後討論多面體的幾何、凸性與極點，並從幾何角度詮釋單形法。序言說明，這樣的講法刻意著重主要概念，而不拘泥於實作細節。

第3章：透過例子理解對偶

對偶性透過兩個組合問題引入：最短路徑問題與二分圖中的最小成本完美配對。對每個問題，本章先找出直觀的下界，再把它轉成一般的弱對偶論證，並由此推導出演算法、證明其正確性。序言指出，兩個問題擇一講授即可。

第4章：對偶理論

在例子之後提出一般理論：線性規劃的弱對偶與強對偶、互補鬆弛條件，以及最佳性的幾何刻畫。Farkas 引理是標有星號的一節。

第5章：對偶的應用*

這是選讀的一章，包含三項應用：集合覆蓋問題的原始–對偶近似演算法及其與貪婪法的比較；對偶變數的經濟學詮釋；以及藉由全單模矩陣證明的最大流最小割定理。

第6章：求解整數規劃

本章比較整數規劃與其線性規劃鬆弛，介紹兩種經典解法：切割平面法（與單形法相連結）以及分支界限法。標有星號的一節以分離演算法處理旅行推銷員問題。

第7章：非線性最佳化

在舉出例子並說明某些非線性規劃極為困難之後，本章展開凸函數、上圖與等位集，藉由次梯度與支撐半空間對凸問題進行鬆弛，並證明一個 Karush–Kuhn–Tucker 定理：先處理可微的凸問題，再透過拉格朗日函數，最後推廣到非凸問題。標有星號的幾節討論非凸問題的凸鬆弛，以及線性規劃的多項式時間內點法。序言強調，KKT 定理只需線性代數與幾何即可得到，不必用到實分析。

附錄A：計算複雜度

簡要介紹演算法快慢的意義：大 O 符號、輸入規模、多項式時間與指數時間、P、NP 與 co-NP 類別、歸約與 NP 完全性，並以書中自己的演算法為例。

核心概念

第1–2章：建模與單形法

• 表述（formulation）：由變數、目標函數與限制式組成的數學模型；當它的可行解與文字敘述的可行解相互對應時，才算正確。
• 線性規劃、整數規劃與非線性規劃：三類表述；由於線性規劃最容易求解，本書盡可能把問題寫成線性規劃。
• 基底與典範形式：單形法在其間移動的頂點之代數描述。
• 極點：多面體的角點，賦予單形法每一次迭代幾何意義。

第3–5章：對偶

• 弱對偶：任何對偶可行解都為原問題的最佳值提供一個界。
• 強對偶與互補鬆弛：最佳解存在時，兩個最佳值相等，最佳解的配對滿足相應的零條件。
• 原始–對偶演算法：同時維持一個原始解與一個對偶解的方法，用於最短路徑、配對與集合覆蓋。
• 全單模矩陣：使線性規劃本身就有整數最佳解的限制式矩陣，由此得到最大流最小割定理。

第6章：整數規劃

• 鬆弛：拿掉整數限制而得到線性規劃，其最佳值為整數規劃的最佳值提供界。
• 切割平面法與分支界限法：縮小整數規劃與其鬆弛之間差距的兩種經典方法。

第7章與附錄A：非線性最佳化與複雜度

• 凸函數與次梯度：使非線性問題易於處理、並能以半空間進行鬆弛的結構。
• Karush–Kuhn–Tucker 條件：有限制的非線性問題之最佳性條件，本書透過幾何與拉格朗日函數推導。
• P、NP 與 NP 完全性：區分容易問題與困難問題的基本術語。

評析

優點

• 入門門檻低，終點紮實。 序言只要求大學一年級的線性代數，但本書一路講到對偶、整數規劃與 Karush–Kuhn–Tucker 定理。它的目標是替後續的最佳化課程打底，各章的「Further reading and notes」也指出繼續學習的方向。
• 先透過問題講對偶。 在第4章提出一般理論之前，第3章先從最短路徑與配對的直觀下界推出弱對偶與正確的演算法，使抽象結果有具體內容支撐。
• 適用於多種課程安排。 標有星號的內容可以略過，序言列出大約十種章節組合：著重建模與應用、只教線性規劃、資訊系適用的線性與離散最佳化、線性與非線性最佳化等。書稿在四年間由十二位教師使用，學生來自會計、商管一直到純數學與資訊科學等科系。
• 連續方法與組合、複雜度並重。 圖論問題、近似演算法、全單模性以及關於 P 與 NP 的附錄，與凸性和 KKT 條件同在一本短書之中，因此本書不只適合學習連續數學的學生，也適合作業研究與資訊科學的學生。

局限

• 非線性問題的演算法偏少。 第7章的重點在凸性與最佳性條件；除了標有星號的線性規劃內點法之外，目錄中看不到求解非線性問題的演算法。
• 刻意寫得精簡。 序言明言要讓內文簡潔，把較深入或旁支的主題放到標有星號的節與習題中，想在某一主題上深入的學生需要另找一本書。
• 解答只提供給教師。 出版社說明解答只提供給授課教師，自學者沒有可以對照的答案。
• 不涉及軟體。 目錄中沒有建模語言或求解器的內容，表述都以手寫推導，計算部分需要由課程另行補充。

在課程中的定位

在本課程的最佳化方向中，本書是最自然的第一本教科書。Alain Goriely 的 Applied Mathematics: A Very Short Introduction 篇幅短得多、幾乎不用公式，講述應用數學家如何建立與分析模型，適合在本書之前或同時作為背景閱讀。Ian Jacques 的 Mathematics for Economics and Business 與 Adam Ostaszewski 的 Advanced Mathematical Methods 則把最佳化當作面向經濟、商管等應用的數學方法工具箱的一部分，並不以線性規劃與對偶為核心。

想學演算法的讀者，下一步可以讀 Chong、Lu 與 Żak 的 An Introduction to Optimization：它更深入講解無限制與有限制的非線性最佳化以及線性規劃，也包含機器學習方面的應用，正好補上本書第7章的主要缺口。Boyd 與 Vandenberghe 的 Convex Optimization 對凸集、凸函數、對偶與演算法的處理更完整、要求也更高；讀完本書第4章與第7章的讀者，會覺得其中的想法並不陌生。

如何使用本書

本書適合修過一門線性代數入門課的數學、資訊科學、工程、商管或經濟系一、二年級學生；需要的只是矩陣運算與解線性方程組。對偶與演算法的正確性都經過證明，而不只是陳述，因此能讀懂簡短的證明會有幫助。

一學期課程的閱讀計畫：

• 核心： 第1章學建模，第2章學單形法（表格一節可略過），第3章兩個問題擇一，以及第4章。
• 接著選擇： 偏重離散最佳化讀第6章，偏重非線性最佳化讀第7章，或兩章都讀。第5章為選讀：經濟學詮釋一節適合商管與經濟系學生，集合覆蓋與最大流最小割適合資訊系學生。
• 建模課程可依序言建議讀第1、2、3、6、7章。若已學過單形法，可直接從第3章開始。
• 複雜度附錄可在熟悉單形法之後閱讀，它說明為何線性規劃被視為容易、整數規劃被視為困難。

最值得投入時間的是第1章的建模習題：寫出正確的模型是全書其餘部分仰賴的能力。可以像第1章那樣檢驗自己的模型：文字問題的每個可行解是否都對應到表述的一個可行解，反之亦然。由於解答只提供給教師，不妨用任一線性規劃求解器求解小型模型，以電腦核對答案，並把標有星號的習題留到第二輪再做。