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章那样检验自己的模型：文字问题的每个可行解是否都对应表述的一个可行解，反之亦然。由于解答只提供给教师，不妨用任意一个线性规划求解器求解小模型，用计算机核对答案，并把带星号的习题留到第二遍再做。