凸优化问题与标准形式 — 凸优化

开篇场景（Hook）：一位 PM 的两份委托书

周一上午，你在一家沪深300 指数增强私募基金的研究台收到两份新增的客户委托书。第一份要求满仓多头、 $\mathbf{1}^T w = 1$ 、 $w \ge 0$ 、行业偏离度上限 ±3%（一组线性不等式）——干净的二次规划（quadratic program, QP）：二次目标 + 仿射约束，求解器十秒出结果。第二份加了一句「持仓数不得超过 50 只」，可行集变离散，问题从 QP 退化成混合整数规划（mixed-integer program, MIP），从十秒跳到几小时。两份金融含义差得不多，数学上却踩到了同一条线——凸性。（标准差形式的跟踪误差（tracking error）上限是二阶锥约束，落到 SOCP，本节后半段展开。）

标准形式

一个凸优化问题（convex optimization problem）的标准形式（standard form）写作：

\begin{aligned} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \le 0, \quad i = 1, \dots, m \\ & A x = b \end{aligned}

要满足凸性，三个条件缺一不可：(1) 目标 $f_0$ 是凸函数（convex function）；(2) 每个不等式约束 $f_i$ 都是凸函数；(3) 等式约束必须是仿射（affine）的，即写成 $A x = b$ ，不允许任何非线性形式。

这三条带来两个结构性结论。第一，可行集（feasible set）是若干凸集的交集——交运算保凸是上一课已经证过的事实，所以可行集仍然是凸的。第二，在凸可行集上极小化凸目标，每个局部极小都是全局极小。这一性质是凸优化值得专门拎出来讲的全部理由：找到任何一阶下降不再发生的点，就已经站在全局最优上。

第三条尤其要警惕：等式必须仿射。哪怕 $g(x)$ 本身凸，把 $g(x) = 0$ 写进约束也会破坏凸性——它等价于 $g(x) \le 0$ 与 $-g(x) \le 0$ 同时成立，而 $-g$ 在 $g$ 凸时一般不再凸。诊断练习会用一个球面约束把这件事坐实。

四个标准问题类

凸优化的实战里有一条从弱到强的递进链：

\text{LP} \subset \text{QP} \subset \text{SOCP} \subset \text{SDP}

每一层都比上一层多一种约束语言，但都没跳出凸优化的框架。下表把四类凸问题与它们的离散外推 MIP 放在一起，便于你拿到新委托书时第一时间归类。

类别	目标	约束	量化场景
LP（线性规划）	$c^T x$	$A x \le b$	现金账户的多头限额、税后现金流的线性分配
QP（二次规划）	$\tfrac{1}{2} x^T P x + q^T x$ ， $P \succeq 0$	$A x \le b$ ， $C x = d$	沪深300 上的均值方差优化（mean-variance optimization）
SOCP（二阶锥规划）	线性	$\lVert A_i x + b_i \rVert_2 \le c_i^T x + d_i$	跟踪误差以年化标准差形式给出的上限
SDP（半定规划）	线性	$\sum_i x_i F_i + G \succeq 0$	把噪声协方差矩阵收缩到半正定锥
MIP（混合整数规划）	任意	含 $x_i \in \{0, 1\}$ 等离散变量	「持仓数 ≤ 50」（非凸，跳出凸优化框架）

包含关系一句话各自带过：LP 是 $P = 0$ 的退化 QP；凸 QP 通过 epigraph 改写嵌入 SOCP——引入 $t$ ，目标推到约束 $\tfrac{1}{2} x^T P x + q^T x \le t$ ，再写成 $(L^T x, t)$ 上的 SOC 约束（ $P = LL^T$ ），原目标线性化；SOC 又等价于 $2 \times 2$ 半正定（PSD）块，所以 SOCP $\subset$ SDP。MIP 不在这条链上——离散变量整体打破凸性。

SOCP 约束：为什么不平方

二阶锥（second-order cone）约束的标准写法是：

\lVert A x + b \rVert_2 \le c^T x + d

两边平方得到 $\lVert A x + b \rVert_2^2 \le (c^T x + d)^2$ ，在 $c^T x + d \ge 0$ 时刻画的是同一个凸集——但已不是标准 SOC 约束，求解器无法识别为锥，退回到一般二次约束路径，丢失内点法在 SOC 上的算法优势。建模差别很实际： $\lVert R w - r_b \rVert_2 \le \tau$ 是 SOCP；平方形式等价，但工具链会退回到 QP。

把组合优化写成 QP

回到周一那份「干净的」委托书。一个带预算约束的均值方差优化问题写作：

\min_w \quad \tfrac{1}{2} w^T \Sigma w - \mu^T w \quad \text{s.t.} \quad \mathbf{1}^T w = 1

其中 $w \in \mathbb{R}^n$ 是组合优化（portfolio optimization）的权重向量、 $\mu$ 是预期超额收益、 $\Sigma$ 是协方差矩阵（covariance matrix）。 $\Sigma \succeq 0$ 是这个问题成为凸问题的关键——它来自协方差矩阵定义本身（任何样本协方差都是半正定的），无需额外假设。预算约束 $\mathbf{1}^T w = 1$ 仿射，符合标准形式。

CN 的公募多头限制 $w \ge 0$ 加进来仍保持凸性——每个 $-w_i \le 0$ 都是仿射不等式；私募多空相当于放松 $w \ge 0$ ，结构上仍是 QP。但「持仓数 ≤ 50」这条无法写成任何 $f_i(w) \le 0$ 的凸约束：它在数 $w$ 的非零分量个数（ $\ell_0$ 「范数」），属于离散约束，把问题推到 MIP。这正是开头两份委托书的分界线。

把上面 QP 中的 $\Sigma$ 换成 $X^T X$ 、 $\mu$ 换成 $X^T y$ ，QP 就退化成普通最小二乘（ordinary least squares）问题；它的一阶最优条件正是正规方程（normal equations） $X^T X \beta = X^T y$ 。下面的练习把这个映射做实。

诊断：哪一条破了凸性？

写下三个候选优化问题，找出每一个里破坏凸性的那一行：

$\min_w w^T \Sigma w$ ，s.t. $w^T w = 1$ —— 等式 $w^T w = 1$ 是非仿射的（球面，不是平面）。即便 $w^T w$ 本身是凸函数，等式约束也立刻破坏凸性。
$\min_x x^T P x$ ，其中 $P$ 的某个特征值为 $-0.3$ —— $P$ 不是半正定的，目标函数在某些方向上向下开口，整个目标都不凸。
$\min_w w^T \Sigma w$ ，s.t. $\lVert w \rVert_0 \le 50$ —— $\ell_0$ 「范数」不是凸函数（事实上它在原点之外几乎处处取 1，是离散的），这条约束把问题推到 MIP。

练好这三类「为什么不凸」的辨认能力，比记住一长串可凸的特例更有价值——求解器最终告诉你「不可解」时，你能立刻指出是哪一行，再回头和 PM 谈判松绑。

Exercise

把无约束最小二乘 $\min_\beta \lVert y - X\beta \rVert_2^2$ 改写成标准形式的 QP。(i) 写出 $P$ 与 $q$ 的表达式；(ii) 用一句话解释为什么对任意实矩阵 $X$ 都有 $X^T X \succeq 0$。

提示

展开平方：

\lVert y - X\beta \rVert_2^2 = (y - X\beta)^T (y - X\beta)

。把它整理成

\tfrac{1}{2} \beta^T P \beta + q^T \beta

再加上一个与

\beta

无关的常数；常数项不影响最小化的位置。

提示

对任意

\beta

，看

\beta^T (X^T X) \beta

等于哪个向量的

\ell_2

范数的平方——这一观察直接给出

X^T X

的半正定性，与

X

是否可逆、是否方阵都无关。你写出的

P

、

q

与正规方程

X^T X \beta = X^T y

一一对应。

通向下一课：从形式到证书

到这里你能识别一个问题是不是凸的、能从权重与协方差矩阵里读出标准形式的三层结构、也能在三类常见的「非凸陷阱」里指出关键的那一行。但形式只是入场券——你还没有任何工具断言「这个 $w^\star$ 一定是最优解」，也说不出「松开预算约束 1bp 能多赚多少」。下一课把拉格朗日函数（Lagrangian）、对偶问题（dual problem）与 KKT 条件搬上来：标准形式给出问题，KKT 给出最优性的证书，对偶变量给出每条约束的边际定价。