第 4 章 · 凸优化问题：标准形与变形记

把第 2-3 章的积木装配成"问题的家族"：线性规划、二次规划、二次约束二次规划、半定规划、锥规划。更重要的手艺是变形记：把一个问题改写成它凸的等价形式。

问题家族与凸性检查

• LP：线性目标 + 线性约束——最古老最成熟；标准应用： diet 问题、运输、资源分配、博弈的混合策略；
• QP/QCQP：二次目标（$+$ 二次约束）；凸 QP（$P \succeq 0$）覆盖最小二乘带约束、马科维茨投资组合（协方差半正定的天然应用）；
• SOCP：二阶锥约束 $\|Ax + b\|_2 \le c^Tx + d$——鲁棒最小二乘、投资组合的更精细变体；
• SDP：半定矩阵变量 + LMI 约束——控制论（李雅普诺夫稳定性）、组合优化的 SDP 松弛、图分割；SDP 是最通用的凸问题类（LP、QP、SOCP 都是其特例）；
• 几何规划：正项式目标的 log 变换后变凸——电路设计（晶体管尺寸）的标配。

变形记：揭示隐藏的凸性

建模实例的三个经典：Chebyshev 中心（最大内切球）、线性分式规划、投资组合（均值-方差前沿的 QP 表述）。

• 消除变量（等式约束代入）、引入变量（epigraph 变形 $\min t$ s.t. $f(x) \le t$）；
• 凹最大化 → 凸最小化（加负号）；分式规划（线性分式保凸）；
• 惩罚与约束的互换：$\ell_1$ 范数 = 绝对值之和 = LP 变形（稀疏回归的凸性来源）；$\ell_\infty$ 同理；
• 非凸问题的凸松弛：整数约束 → 线性/半定松弛（得到下界，分支定界的骨架）——"松弛出界 + 分支逼近"是现代混合整数求解的通用架构。

老师的提醒

• 建模的肌肉记忆：$\|x\|_1 \le t \Leftrightarrow -t \le x_i \le t$（LP 化）、二次约束 → SOCP 化、矩阵不等式 → SDP 化——三张变换卡贴在手边。
• 判断"该用哪一类"的次序：能 LP 不 QP、能 QP 不 SOCP、能 SOCP 不 SDP——求解器的规模与稳健性随通用性下降。

自检

• LP/QP/SOCP/SDP 的标准形与包含关系？
• 用 epigraph 变形处理 $\min_x \max_i f_i(x)$。
• 投资组合问题的 QP 模型（目标与约束）？

更深一层：问题家族的"求解器规模等级"

凸问题家族的包含关系值得做成速查卡：LP ⊂ QP ⊂ SOCP ⊂ SDP——LP（线性）最古老最成熟，QP（二次目标）覆盖最小二乘带约束与投资组合，SOCP（二阶锥）覆盖鲁棒最小二乘，SDP（半定矩阵）是最通用的凸问题类（控制论的李雅普诺夫稳定性、组合优化的松弛、量子信息）。选型原则：能 LP 不 QP、能 QP 不 SOCP、能 SOCP 不 SDP——求解器的规模与稳健性随通用性下降。

变形记的手艺清单值得随身：消除变量（等式约束代入）、引入变量（epigraph 变形 $\min t$ s.t. $f(x) \le t$——把不可导目标移进约束）、$\ell_1$ 范数 = LP 变形（稀疏回归的凸性来源）、分式规划（线性分式保凸）。"同一问题有多个凸表述，选对表述直接决定求解效率"——建模层的功力就体现在这里。

推导细读：非凸问题的"凸松弛"

非凸问题的凸松弛是应用数学的"合法越狱"：整数约束 → 线性/半定松弛（得到下界，分支定界的骨架）、秩最小化 → 核范数松弛（矩阵补全）、二次约束非凸 QCQP → SDP 松弛。"松弛出界 + 分支逼近"是现代混合整数求解的通用架构——松得好的松弛给出紧的下界，松得差的松弛给出无用的下界。SDP 松弛的著名成功案例：Goemans-Williamson 最大割算法（0.878 近似比——"松弛 + 随机取整"的理论巅峰）。

在真实世界里：建模实例的三个经典

三个建模实例值得逐个会：Chebyshev 中心（最大内切球——LP 的标准教学例）、线性分式规划（$f = \frac{c^Tx + d}{e^Tx + f}$ 的线性分式变换保凸——投资组合的夏普比率最大化）、投资组合（均值-方差前沿的 QP 表述——马科维茨的现代实现）。每个实例都是"问题翻译为凸问题"的范本——掌握翻译的手艺，比背任何求解器 API 都值钱。

专题深入：标准形与"凸化的变形记"完整版

第四章的实操核心是识别与变形：凸优化标准形（min 凸目标 + 不等式约束凸 + 等式约束仿射）与 LP/QP/SOCP/SDP 的嵌套家族（"每个家族的求解器复杂度与表达力"：LP 最内、SDP 最外——表达力递增、求解速度递减；建模的功力是用最低层级表达问题：二次目标该写成 QP 就别升 SOCP）。凸化的常用变形术全表：epigraph（目标进约束：$\min t$ s.t. $f(x) \le t$——max 目标的 SOCP 化）、约束消除、变量替换（几何规划的 log 变换：正项式变凸——通信功率控制与电路设计的教科书技巧）、函数的凸下界/松弛（组合问题的凸松弛：整数约束松弛 + 舍入——"松弛-解-舍入"三段论是近似算法的标准模式：MaxCut 的 SDP 松弛（Goemans-Williamson 0.878 近似比））。可行性与坏条件（Slater 条件预告强对偶（第五章）、问题缩放与数值稳定——"好问题 = 凸 + 良条件"，缩放不当让好求解器失败）。

推导细读：几类标准问题的"完整解剖"完整版

第四章标准问题的完整解剖：QP（凸二次目标 + 仿射约束——Hessian 半正定的检查、KKT 线性方程组的可解性；Markowitz、MPC、SVM 的原形）；SOCP（二阶锥 $\|(x, t)\|_2 \le s$——鲁棒优化与范数球约束的自然语言（最小化最大范数、Chebyshev 中心）；"QP 的锥化"：$\|Ax - b\| \le t$ 变 SOCP）；鲁棒与随机优化（不确定参数的最坏情况/期望——"椭圆不确定集 → SOCP" 是鲁棒优化的标准翻译）；几何规划（正项式 posynomial + 单项式等式——log 变换后的凸问题；GP 的无形身影：放大器设计、包络优化）；半定规划（对称矩阵锥上的线性目标——控制、组合、特征值优化的统一语言；内点法每迭代解一个牛顿系统——"多项式时间可解"的现代含义）。"建模即翻译：从业务约束到锥约束"——第四章是翻译手册的正文。

工程案例细节：变形术的产业出口工程版

第四章的工程出口：投资组合的完整建模栈（均值-方差 QP → 加交易成本与换手约束 → 鲁棒版（协方差不确定 → SOCP）——AQR 等量化基金的凸优化生产线；Black-Litterman 与约束 MVO 的合规化改造）；信号处理的 l1 革命（压缩感知基追踪 $\min\|x\|_1$ s.t. $Ax = b$ 的 LP 化、l1 与 SOCP 的融合（l1-l2）——MRI 加速成像的医疗级应用）；鲁棒控制（H-infinity 的 LMIs、增益调度——飞控与电力系统稳定器的凸设计）；功率系统（最优潮流的 SOCP 松弛（"非凸 AC-OPF 的凸化"是电网计算十年来的主战场——DistFlow 分支流模型的 SOCP 松弛在配网精确）；机器学习训练的凸内核（线性分类器的凸损失、深度学习"凸外壳"的讨论——最后一层通常是凸的：损失对 logits 凸）。变形术的价值量化：同一个业务问题，建模水平决定它是"秒解"还是"算不动"。