对应 note 3_prob.pdf。这一章的本质是"建模能力"——把一个真实问题改写成五大标准形（LP、QP、QCQP、SOCP、SDP）之一。

0. 一句话理解这一章

如果你能把一个问题写成 LP/QP/SOCP/SDP 中的某一种，那么它就有现成的求解器可以分钟内出结果。本章教你"翻译"——同时积累一套常用的"等价改写"技巧。

1. 知识地图

            标准形                           关系
            ─────────────────────────────────
            LP   (线性规划)                 ⊂
              ↓                              ⊂
            QP   (二次规划，Q ⪰ 0)          ⊂
              ↓                              ⊂
            QCQP (二次约束二次规划)         ⊂
              ↓                              ⊂
            SOCP (二阶锥规划)               ⊂
              ↓                              ⊂
            SDP  (半定规划)                 ─

            凸优化基础设施
            ─────────────────────────────────
            标准形 (P) min f0 s.t. f_i ≤ 0, h_j = 0
              ├── 凸问题：f_0, f_i 凸，h_j 仿射
              └── 重要事实：凸问题局部最优 = 全局最优 ✦

            一阶最优性（带可行域 X）：
              ∇f_0(x)^T (y − x) ≥ 0,  ∀y ∈ X

2. 优化问题的标准形

$$\begin{array}{rl}(P)min& f_0(x)\\ \text{s.t. }& f_i(x)\le 0,i=1,\dots ,m\\ & h_j(x)=0,j=1,\dots ,p\end{array}$$

• 域：$\mathcal{D}=\bigcap _i\text{dom}(f_i)\cap \bigcap _j\text{dom}(h_j)$。
• 可行域：$X=\{x\in \mathcal{D}:f_i\le 0,h_j=0\}$。
• 局部最优 / 全局最优。

凸优化问题的定义

$f_0,f_i$ 凸，$h_j$ 仿射（注意：等式约束必须是仿射！）。

关键性质：凸优化问题的局部最优解一定是全局最优解 ⭐

证明思路（要会）：用反证。假设有个 $y$ 比 $x^{\ast }$ 好，沿 $x^{\ast }\to y$ 走小步 $\lambda$，由凸性$f_0(x^{\ast }+\lambda (y-x^{\ast }))\le \lambda f_0(y)+(1-\lambda )f_0(x^{\ast })<f_0(x^{\ast })$，与 $x^{\ast }$ 局部最优矛盾。

一阶最优性条件（Theorem 1.1）⭐⭐

设 $f_0$ 凸可微，$X$ 为可行域。$x\in X$ 最优 ⇔

$$\mathrm{\nabla }{f}_0(x{)}^T(y-x)\ge 0,\mathrm{\forall }y\in X.$$

几何含义：$-\mathrm{\nabla }{f}_0(x)$ 必须落在 $X$ 在 $x$ 处的"法向方向"上（不指向可行域内部）。

无约束特例：$\mathrm{\nabla }{f}_0(x)=0$。

这条结论会在第 4 章拓展为 KKT，第 6 章被算法迭代式所近似。

---

3. 五大标准形（必背模板）

3.1 LP（线性规划）

$$min{c}^{T}x\text{s.t.}Ax=b,x\ge 0.$$

核心建模技巧：

1. 不等式 → 等式：$Bx\le d\to Bx+s=d,s\ge 0$（松弛变量）。
2. 自由变量 → 非负：$x=x^{+}-x^{-},x^{\pm }\ge 0$。
3. 绝对值 / max 形式：$min\underset{i}{max}(a_i^{T}x+b_i)\to mint\text{s.t.}{a}_i^{T}x+b_i\le t$。
4. 线性分式 $(c^{T}x+d)/(e^{T}x+f),e^{T}x+f>0$：用 Charnes-Cooper 变换 $y=x/(e^{T}x+f),z=1/(e^{T}x+f)$，得 $min{c}^{T}y+dz$ s.t. 各种线性约束 + $z\ge 0$。

第 1 道题（讲义证 LP-fractional ↔ LP）的核心：两个方向都要构造可行解 + 比较目标值。

3.2 QP（二次规划，凸需 $Q⪰0$）

$$min\frac{1}{2}{x}^{T}Qx+c^{T}x\text{s.t.}Ax=b,x\ge 0.$$

典型应用：

• Markowitz 投资组合：$min{x}^T\mathrm{\Sigma }x$ s.t. ${\overline{p}}^{T}x\ge r_{min},e^{T}x=1,x\ge 0$。
• SVM（线性可分）：$min\frac{1}{2}\parallel \omega {\parallel }^2$ s.t. ${\omega }^T{x}_i+\beta \ge 1$（A 类）/ $\le -1$（B 类）。
  • 核心思想：最大间隔 → 缩放归一化 $\underset{i}{min}|{\omega }^T{x}_i+\beta |=1$ → 凸 QP。

3.3 QCQP

$$min\frac{1}{2}{x}^T{P}_{0}x+q_0^{T}x+r_0\text{s.t.}\frac{1}{2}{x}^T{P}_{i}x+q_i^{T}x+r_i\le 0,Ax\le b.$$

凸需 $P_i⪰0$。$P_i=0$ 时退化为 LP；约束端 $P_i=0$ 时退化为 QP。

3.4 SOCP（二阶锥规划）⭐⭐⭐

$$min{f}^{T}x\text{s.t.}\parallel A_{i}x+b_i{\parallel }_2\le c_i^{T}x+d_i,Fx=g.$$

为何重要：SOCP 包含 LP、凸 QP、QCQP，但比 SDP 简单得多。作业里出现频率最高的建模目标。

SOCP 经典等价改写：

• 凸 QP $min\parallel Ax-b{\parallel }^2$ → $mint$ s.t. $\parallel Ax-b\parallel \le \sqrt{t}$（再用双曲技巧降到 SOC）。
• 双曲约束（hw07.1 直接考）：$$x^{T}x\le yz,y\ge 0,z\ge 0⟺{\Vert \left(\begin{array}{c}2x\\ y-z\end{array}\right)\Vert }_2\le y+z.$$这条恒等式是把 $x^{T}x/y$ 这种"二次/线性"分式改写成 SOC 的关键。
• 范数分式 $\frac{\parallel Fx+g{\parallel }^2}{a^{T}x+b}\le t$ → $(Fx+g{)}^T(Fx+g)\le t(a^{T}x+b)$ → 双曲 → SOC。
• 几何均值 $(\prod _i{u}_i{)}^{1/m}\ge t$：可以归并为 $O(m)$ 个双曲约束（hw07.1(b)）。
• 椭球不确定下的鲁棒 LP：把 $\underset{a\in \mathcal{E}}{sup}{a}^{T}x$ 算成 ${\overline{a}}^{T}x+\parallel P^{T}x{\parallel }_2$，转成 SOC。
• 概率约束 LP（高斯不确定）：$Pr(a^{T}x\le b)\ge \eta$ → ${\overline{a}}^{T}x+{\mathrm{\Phi }}^{-1}(\eta )\parallel {\mathrm{\Sigma }}^{1/2}x\parallel \le b$。

3.5 SDP（半定规划）

$$minC\bullet X\text{s.t.}{A}_i\bullet X=b_i,X⪰0.$$

内积 $A\bullet B=\text{tr}(A^{T}B)$。

SDP 建模常用技巧：

• Schur 补：把"分式 + 二次型"塞进 $\left(\begin{array}{cc}Y& x\\ x^T& r\end{array}\right)⪰0$。
• PSD 锥的对偶仍是 PSD 锥（自对偶）。
• rank-1 松弛：$X=x{x}^T$ 凸放松为 $X⪰x{x}^T$（QCQP 的 SDR）。

---

4. 鲁棒优化（robust LP）

主问题：$a_i\in {\mathcal{U}}_i$ 不确定，$min{c}^{T}x$ s.t. $a_i^{T}x\le b_i\mathrm{\forall }{a}_i\in {\mathcal{U}}_i$。

不确定集合	等价形式
椭球 ${\mathcal{E}}_i=\{\overline{a}+Pu:|u|\le 1\}$	SOCP：${\overline{a}}^{T}x+|P^{T}x|\le b$
多面体 ${\mathcal{U}}_i=\{a:Da\le e\}$	LP（用 LP 强对偶）
高斯随机（chance constraint）	SOCP（用 ${\mathrm{\Phi }}^{-1}$）

第 5 章的对偶视角能把"对所有 $a$ 成立"转成"存在某 $\lambda$ 使得..."——这就是鲁棒对偶 (robust counterpart) 的方法。

---

5. 作业题型对照（从 A3 + hw07）

作业	题面	考点
A3.5	Huber 损失最小化 → QP	把 $H_{\delta }(r)=\underset{u,v\ge 0,|s|\le \delta }{min}\dots$ 拆分：引入辅助变量 $u_i,v_i$ 表示 $r_i=u_i+v_i$，$|u_i|\le \delta$，目标 $\frac{1}{2}{u}_i^2+\delta v_i$；写成标准 QP 形式（带框约束 / 绝对值约束的进一步拆分）
A3.6	$min\sum |a_i-x{|}_2^2$	(a) 解析最优（求和展开 + 求导 → $x^{\ast }=\frac{1}{m}\sum a_i$）；(b) 因目标函数是单一二次而非"$\sum t_i$ s.t. $|a_i-x|\le t_i$"，所以直接是 QP 而非 SOCP——但可以写成 SOCP：$min\sum t_i^2\to min{\mathbf{1}}^{T}s$ s.t. $t_i^2\le s_i,|a_i-x|\le t_i$（要求你考察转化是否真正必要）
hw07.1	验证 $x^{T}x\le yz⟺|2x;y-z|\le y+z$	双方平方展开 + 用 $y\ge 0,z\ge 0$
hw07.1(a)	调和均值最大化 $\sum 1/(a_i^{T}x-b_i{)}^{-1}$	引入 $t_i\le 1/(a_i^{T}x-b_i)⟺t_i(a_i^{T}x-b_i)\ge 1,t_i,a_i^{T}x-b_i\ge 0$（双曲约束） → 用上述等价 → 写成 SOCP
hw07.1(b)	几何均值最大化	一种递归"分组 SOC"技巧：$t_1{t}_2\ge u^2$ 是双曲；多个的话两两配对（$O(m)$ 个 SOC），最后用一个变量统一比较
hw07.2	$(Ax+b{)}^T(I+B\text{diag}(x)B^T{)}^{-1}(Ax+b)$	题目 hint 让你引入 $v,w$ 化成 $min{v}^{T}v+w^T\text{diag}(x{)}^{-1}w$ s.t. $v+Bw=Ax+b$；其中 $w_i^2/x_i$ 是经典双曲，再 SOC 化
hw07.3	SOS 多项式 + 控制最小值 → SDP	hint 已经把方法说得很清楚：把 $p(t)-\gamma =z(t{)}^{T}Qz(t),Q⪰0$；通过比较系数把 $Q$ 与 $x$ 关联，再加 $l_i\le p(t_i)\le u_i$

复习要点：A3 + hw07 几乎只考一件事——LP/QP/SOCP/SDP 的等价改写。掌握下面三种"招式"基本能解决一切：

1. 变量代换：分式（$z=1/(\dots )$）、自由变量拆分（$x=x^{+}-x^{-}$）、引入 $t$ 表"目标的上界"。
2. Schur 补：处理 $x^T{Y}^{-1}x\le t$、$(Ax+b{)}^{T}F(x{)}^{-1}(Ax+b)\le t$（A6.3 同样思路）。
3. 双曲 SOC：$uv\ge w^2$ 的恒等式。

---

6. 解题"招式手册"

招式 1：见到目标 $max/min$ 函数 → 引入 $t$ 抹平

$$min\underset{i}{max}{f}_i(x)\to mint\text{s.t.}{f}_i(x)\le t.$$

适用于：piecewise-linear、Chebyshev approximation、LP 对偶里"max 转 LP"。

招式 2：见到分式 ${\displaystyle \frac{a^{T}x+b}{c^{T}x+d}}$ → Charnes-Cooper

令 $z=1/(c^{T}x+d),y=zx$，分母变 1，分子变线性。LP 分式 → LP。

招式 3：见到二次（或 $\parallel \cdot {\parallel }^2$）→ "目标加 t" + 双曲 → SOC

$$\parallel Fx+g{\parallel }^2\le t⟺\left(\begin{array}{cc}I& Fx+g\\ (Fx+g{)}^T& t\end{array}\right)⪰0\text{或}\parallel Fx+g\parallel \le \sqrt{t}\text{（SOC）}.$$

招式 4：见到 $x^T{Y}^{-1}x$（$Y\succ 0$）→ Schur 补

$$x^T{Y}^{-1}x\le t⟺\left(\begin{array}{cc}Y& x\\ x^T& t\end{array}\right)⪰0,Y⪰0.$$

招式 5：见到 $\underset{a\in \mathcal{U}}{sup}{a}^{T}x$ → 内部最大化 + 对偶（鲁棒优化）

• $\mathcal{U}$ 椭球 → $\parallel P^{T}x\parallel$（无需对偶，直接闭式）。
• $\mathcal{U}$ 多面体 $\{a:Da\le e\}$ → 用 LP 强对偶（注意：这里要 $max$ 的对偶，得到 $min$ 形式）。

招式 6：见到 $Pr(\text{不等式})\ge \eta$（高斯随机参数）→ ${\mathrm{\Phi }}^{-1}$ + SOCP

---

7. 自检清单

• [ ] 凸问题的局部 = 全局最优？怎么证？
• [ ] 一阶最优性 $\mathrm{\nabla }{f}_0(x{)}^T(y-x)\ge 0$ 的几何意义？无约束特例是什么？
• [ ] LP 标准形里的所有改写技巧（松弛、自由变量、max-LP）？
• [ ] 双曲约束 $uv\ge w^2⟺\parallel 2w;u-v\parallel \le u+v$？
• [ ] $x^T{Y}^{-1}x\le t$ 的 Schur 补改写？
• [ ] $\parallel Ax+b{\parallel }^2\le t$ 的 SOC 改写？
• [ ] 椭球 / 多面体 / 高斯不确定下的鲁棒 LP？
• [ ] LP ⊂ QP ⊂ QCQP ⊂ SOCP ⊂ SDP 的顺序与转化方向？

8. 常见陷阱

1. 凸 QP 的等式约束必须仿射——不可以放二次等式。
2. "分式"目标若分母可正可负，必须先约束分母 > 0（Linear-fractional 的 dom 限制）。
3. SOCP 与 QCQP 的等价：每个凸 QCQP 都可写成 SOCP，但反之未必（讲义里有提示）。
4. SDP 的对偶仍是 SDP，但 LP 的对偶是 LP（不进入 SOCP），SOCP 的对偶仍是 SOCP——别在层级上写串了。
5. "max 形式"的目标在 LP 中：$minmax$ → 引 $t$ 之后约束变多但仍是 LP；$maxmin$ 不是 LP（这是为什么有对偶）。
6. A3.6 的"是不是 SOCP"是个陷阱题：直接的 $\sum \parallel a_i-x{\parallel }^2$ 是 QP，不是天然的 SOCP，但可以"等价改写"成 SOCP——具体写法和"是否值得改写"都要思考。

---

9. 接下来怎么学

1. 把 §3 五大模板和 §6 六个招式默写一遍。
2. 完成 A3 与 hw07 的所有题（重点 hw07.1, hw07.2, hw07.3）。
3. 进入 4_最优性条件，把"建模"过渡到"求解"。