第 1 章 · 优化问题：语言与定位

这本书的第一件事是把"优化"这个日常词变成精确的语言：目标函数、约束、可行域、最优值。更重要的是预告全书的核心论点——凸性是分水岭：凸问题可以被高效地全局求解，非凸问题原则上没有这种保证。

优化问题的标准形

术语装配：可行点、可行域、最优值 $p^*$、最优解。局部 vs 全局：非凸问题困在局部极小，凸问题的一切局部最优即全局最优——这是凸性一次兑现全部承诺的地方。

凸性的定义与直观

集合凸：任取两点连线仍在集合内。函数凸：任取两点弦在函数图上方：

凸问题 = 凸目标 + 凸不等式约束 + 仿射等式约束。判别的机械工具：一阶条件 $f(y) \ge f(x) + \nabla f(x)^T(y - x)$（切线在下方）、二阶条件 $\nabla^2 f \succeq 0$（海森半正定）。

为什么要专门学凸优化

历史的注脚：LP（线性规划）从 1947 年单纯形法到 1984 年内点法，是凸优化从"计算技巧"升格为"数学学科"的标本。

• 理论：对偶理论完整、KKT 条件成为充要、全局最优有证书；
• 算法：内点法多项式时间解到高精度（$O(\sqrt{\kappa}\log(1/\epsilon))$ 量级）；
• 应用：大量非凸问题有凸松弛（近似或精确），识别"伪装的凸问题"是全书训练的核心眼力。

老师的提醒

• 拿到任何问题第一问：凸吗？——检查目标海森与约束函数的凸性，比先想算法重要一个量级。
• 判别凸性时保留"一阶条件的图像"：凸函数处处被切线从下方支撑——草图即可排除大多数非凸。

自检

• 写出优化问题标准形与凸问题的定义。
• 一阶/二阶凸性判据？
• 凸优化为什么保证局部 = 全局？

更深一层：凸性是"可解性"的分界线

凸优化的全部力量来自一条定理：凸问题的任何局部最优即全局最优——这一个性质把"解的寻找"从"搜索"降级为"下山"。更深一层的理解值得展开：局部最优即全局最优不是凸性的全部礼物——对偶理论完整（强对偶、KKT 是充要）、全局最优有证书（对偶可行性给出可验证的最优性证明）、内点法多项式时间解到高精度（$O(\sqrt{\kappa}\log(1/\epsilon))$ 量级）。凸性 = 可解性、可验证性、可证明性的三合一——这就是为什么 Boyd 的书开篇就宣告"识别凸问题"是全书的核心训练。

局部 vs 全局的分野值得做成决策卡：非凸问题困在局部极小（多起点/退火/启发式），凸问题一切局部最优即全局最优——拿到任何问题第一问："凸吗？"——检查目标海森与约束函数的凸性，比先想算法重要一个量级。

推导细读：一阶条件的几何证明

凸函数的一阶条件 $f(y) \ge f(x) + \nabla f(x)^T(y - x)$ 的几何读法是切线在函数图下方——凸函数处处被它的切线从下方支撑。证明的代数版（从定义式对 $\theta$ 求导再取极限）干净利落，但几何图像更有用：凸函数没有"局部极小值陷阱"——任何点如果梯度为零（切线水平），整个函数都在这条水平线之上，立刻得全局最小。一阶条件的几何直觉 + 二阶条件的代数判定（海森半正定），是凸性检查的双保险。

在真实世界里：凸优化的"商业版图"

凸优化的商业版图值得画出：金融（马科维茨投资组合 = QP——协方差半正定的天然应用）、机器学习（SVM/logistic 回归/Lasso 全是凸问题）、信号处理（压缩感知 = $\ell_1$ 最小化恢复稀疏信号）、电力（最优潮流 OPF 的凸松弛）、控制（MPC = 每步解一个 QP）。"能凸就凸"是工程优化的第一原则——把非凸问题"凸化"（松弛/变换）是应用数学工程师的最高技艺。

专题深入：优化问题的"四件套与分类学"完整版

Boyd 第一章的形式化：优化问题四件套（目标函数 $f_0(x)$、约束不等式 $f_i(x) \le 0$、等式约束 $h_i(x) = 0$、可行域）+ 三个基本量（**最优值 $p^*$、最优解集、ε-次优解）——后续全部理论围着这三个量转。分类学的完整树：线性 vs 非线性（目标与约束的函数类别）、凸 vs 非凸（凸优化 = 局部最优即全局最优——可解性的分水岭）、光滑 vs 非光滑、连续 vs 离散（整数规划一般是 NP-hard——"凸是连续问题的可解边界、线性规划是其最内圈"）；问题的等价变形术（变量替换消除等式约束、epigraph 技巧把目标转约束、变量消元——"把问题整理成标准形"本身就是一门手艺：SVM 的对偶化、几何规划的变量代换、最小二乘的各种马甲（正则化、加权、约束 LS）——认识"伪装的问题"是第一章的实战技能）。求解-验证-灵敏度的完整循环**（解出 $p^*$ 后的敏感度分析：$p^*(u)$ 对约束扰动的导数——对偶变量的又一重身份）。

推导细读：最小二乘与线性规划的"双原型"完整版

第一章的两个原型问题值得解剖：最小二乘 $\min\|Ax - b\|_2^2$（正规方程 $A^TAx = A^Tb$ 闭式解、几何解释（正交投影）、统计解释（高斯噪声的 MLE）、数值解法（QR 分解——"三种语言说同一个问题"：代数/几何/统计，各自给出不同扩展方向：加权（异方差）、正则（先验）、约束（工程限制））；线性规划 $\min c^Tx$ s.t. $Gx \le h$（多面体可行域 + 顶点搜索——单纯形法的几何是"沿棱走"，内点法的几何是"穿心而过"；LP 的万能建模语言：运输、饮食、调度、博弈均衡——"约束写对，求解器就是免费的"是 LP 时代的口号，凸优化时代改写为"凸则可解"）。两个原型的"次原型"：几何规划（log 变换后变凸）、二次约束二次规划（QCQP）、半定规划（SDP——LP 的矩阵推广，控制与组合优化的现代利器）。

工程案例细节：凸建模语言的工程出口工程版

第一章的工程出口：CVX/CVXPY 的建模 DSL（"先写数学、求解器自动处理"——CVXPY 三行解一个投资组合问题，内点法/ADMM 的选择对用户透明）；投资组合优化（Markowitz 均值-方差：$\min w^T\Sigma w$ s.t. $\mu^Tw \ge r_{\min}$、$\mathbf 1^Tw = 1$——二次规划在金融的百年应用；约束变体（做空限制、换手惩罚、风险平价）全部是 QP 变形）；凸优化的"隐形统治"（每台手机每秒都在解凸问题：功率控制的几何规划、MPC 的 QP、压缩感知的 l1——Chandrasekaran 的名言"convex optimization is secretly everywhere"）；模型预测控制（MPC 每个控制周期解一个 QP——"控制器的实时优化化"是现代工业控制的范式转移）。第一章的立场：优化不是数学游戏，是"把工程决策写成凸问题"的翻译学。