§ Linear & Quadratic Optimization

线性规划
Quant 面试指南

覆盖 LP 建模、对偶理论、KKT 条件、单纯形法，以及 Lasso-as-QP、无套利定价、投资组合优化等核心应用。

LP / QP / SOCP 强对偶 KKT Lasso 改写 无套利 Portfolio Opt.
01 — 基础

LP 建模

线性规划（LP）：在线性约束下最小化线性目标函数。标准不等式形式：

$$\min_{x \in \mathbb{R}^n} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \quad x \geq 0$$

其中 $c \in \mathbb{R}^n$ 为目标系数，$A \in \mathbb{R}^{m \times n}$，$b \in \mathbb{R}^m$。

各要素含义

要素作用Quant 类比
$c^\top x$目标函数（线性）负期望收益 / 成本
$Ax \leq b$不等式约束风险限额、预算、容量
$Cx = d$等式约束满仓约束、无套利条件
$x \geq 0$非负约束仅做多、非负权重

可行性与有界性

LP 恰好满足三种情形之一：可行且有界（存在最优解）、可行但无界（目标趋向 $-\infty$）、不可行（约束集为空）。

LP 基本定理
若 LP 存在最优解，则必有某个顶点（极点）也是最优解。单纯形法正是基于此——只需在顶点之间移动。
02 — 基础

标准形式与转化

标准形式
$$\min_x \; c^\top x \quad \text{s.t.} \quad Ax = b, \quad x \geq 0$$

任何 LP 均可转化为标准形式：

01
不等式 → 等式：引入松弛变量 $s \geq 0$，$a^\top x \leq b$ 变为 $a^\top x + s = b$。
02
自由变量：令 $x_j = x_j^+ - x_j^-$，$x_j^+, x_j^- \geq 0$，将无符号约束的变量拆成两个非负变量之差。
03
最大化 → 最小化：$\max c^\top x \equiv \min(-c^\top x)$。
04
$\geq$ 约束：乘以 $-1$ 或引入剩余变量（surplus variable）。

基本可行解（BFS）

对 $Ax = b$，$A \in \mathbb{R}^{m \times n}$，$\text{rank}(A) = m$：基本可行解将 $n-m$ 个变量设为 0（非基变量），解出剩余 $m$ 个（基变量）。BFS 对应可行多面体的顶点，单纯形法在相邻 BFS 之间移动。

03 — 基础

几何直觉

可行集 $\{x : Ax \leq b,\, x \geq 0\}$ 是一个凸多面体（convex polytope）。线性目标函数的等值面是一族平行超平面。最优解出现在等值超平面"刚好切到"多面体时——必在某个顶点（退化时在边或面上）。

几何关键事实
  • 可行集是凸集（半空间的交）
  • 有界时最优解必在顶点
  • 退化情形：目标平行某条边，多个最优顶点
  • 顶点 ↔ BFS 一一对应
凸多面体

$\mathcal{P} = \{x \geq 0 : Ax \leq b\}$ 由 $m+n$ 个超平面围成。顶点是 $n$ 个约束同时紧的交点，顶点数 $\leq \binom{m+n}{n}$。

04 — 理论

对偶理论 Duality

每个 LP（原问题）都对应一个对偶 LP。对偶理论是优化与金融中最重要的工具之一——对偶变量的经济意义是约束的影子价格。

原问题 PRIMAL
$$\min_{x} \; c^\top x$$ $$\text{s.t.} \quad Ax \geq b, \quad x \geq 0$$
对偶问题 DUAL
$$\max_{y} \; b^\top y$$ $$\text{s.t.} \quad A^\top y \leq c, \quad y \geq 0$$

原-对偶对应规则

原问题对偶问题
最小化最大化
第 $i$ 行 $\geq$ 约束对偶变量 $y_i \geq 0$
第 $i$ 行 $=$ 约束对偶变量 $y_i$ 自由
变量 $x_j \geq 0$第 $j$ 个对偶约束 $\leq$
变量 $x_j$ 自由第 $j$ 个对偶约束 $=$

弱对偶与强对偶

弱对偶 Weak Duality
对任意原可行 $x$ 和对偶可行 $y$：$c^\top x \geq b^\top y$。对偶最大化问题提供原最小化问题的下界。
强对偶 Strong Duality（LP）
若原问题存在最优解 $x^*$，则对偶也存在最优解 $y^*$，且 $c^\top x^* = b^\top y^*$。对偶间隙（duality gap）为零。
强对偶证明思路

由单纯形法：最优时 reduced costs 满足 $\bar{c} = c - A^\top y \geq 0$，其中 $y = (B^\top)^{-1}c_B$ 为单纯形乘子。令其为对偶变量：$A^\top y \leq c$（对偶可行），$c^\top x^* = c_B^\top B^{-1}b = b^\top y^*$（无间隙）。$\blacksquare$

互补松弛条件 Complementary Slackness

互补松弛
原对偶对 $(x^*, y^*)$ 同时最优 $\iff$： $$y_i^* \,(a_i^\top x^* - b_i) = 0 \quad \forall i \qquad \text{（原约束松弛量} \times \text{对偶变量} = 0\text{）}$$ $$x_j^* \,(c_j - a_j^\top y^*) = 0 \quad \forall j \qquad \text{（对偶约束松弛量} \times \text{原变量} = 0\text{）}$$

直觉：若某约束不紧，则其影子价格为 0；若某对偶变量为正，则对应约束必紧。这是 LP 最重要的结构性质之一。

对偶变量的金融含义

对偶变量 $y_i$ 是影子价格（shadow price）：将约束 $i$ 的右端项放松一个单位，最优目标值的改善量。在投资组合优化中，预算约束的对偶变量是财富的边际效用；在无套利定价中，对偶变量就是风险中性概率。

05 — 理论

KKT 条件

对一般约束优化问题：

$$\min_x f(x) \quad \text{s.t.} \quad g_i(x) \leq 0, \quad h_j(x) = 0$$

KKT 条件是最优性的必要条件（当 $f, g_i$ 凸、$h_j$ 仿射时也充分）：

KKT 五个条件
$$\nabla f(x^*) + \sum_i \lambda_i \nabla g_i(x^*) + \sum_j \mu_j \nabla h_j(x^*) = 0 \quad \text{（稳定性）}$$ $$g_i(x^*) \leq 0, \quad h_j(x^*) = 0 \quad \text{（原可行性）}$$ $$\lambda_i \geq 0 \quad \text{（对偶可行性）}$$ $$\lambda_i g_i(x^*) = 0 \quad \forall i \quad \text{（互补松弛）}$$

LP 的 KKT

对 $\min c^\top x$ s.t. $Ax = b,\, x \geq 0$，引入等式乘子 $y$（自由）和非负约束乘子 $s \geq 0$，KKT 给出：

$$c - A^\top y - s = 0, \quad s \geq 0, \quad s_j x_j = 0 \;\forall j$$

这正好恢复互补松弛：$x_j = 0$（非基）或 $s_j = 0$（基变量，reduced cost 为零）二者必居其一。

QP 的 KKT

对 $\min \tfrac{1}{2}x^\top Q x + c^\top x$ s.t. $Ax \leq b$，$Q \succ 0$：

$$Qx^* + c + A^\top \lambda^* = 0, \quad \lambda^* \geq 0, \quad \lambda_i^*(a_i^\top x^* - b_i) = 0$$

$Q \succ 0$ 保证目标严格凸，KKT 既是必要条件也是充分条件，解唯一。

06 — 理论

单纯形法 Simplex Method

单纯形法沿可行多面体的顶点（BFS）移动，每步严格改善目标值（非退化情形）。

01
初始化：找一个初始 BFS（Phase I 法或 Big-M 法）。
02
计算 reduced costs：对非基变量 $j$，$\bar{c}_j = c_j - c_B^\top B^{-1} A_j$。
03
最优性检验：若所有非基 $\bar{c}_j \geq 0$，当前 BFS 即为最优，停止。
04
主元旋转（Pivot）：选入基变量（最负 $\bar{c}_j$）；选离基变量（最小比值规则 min-ratio test）；更新基矩阵 $B$。
05
重复直至最优或检测到无界（no leaving variable in min-ratio test）。

复杂度对比

方法理论最坏情形实际表现
单纯形 Simplex指数级（Klee-Minty 构造）经验接近多项式，工业界首选
椭球法 Ellipsoid多项式 $O(n^6 L)$实际很慢，理论意义大
内点法 Interior Point多项式 $O(n^{3.5} L)$大规模 LP/QP 首选
面试 tip：单纯形法理论指数、实践高效；内点法（障碍函数法）多项式时间，适合大规模问题。两者各有场景优势，需结合规模与结构选择。
07 — 扩展

二次规划 QP 与 SOCP

QP 定义
$$\min_x \; \frac{1}{2} x^\top Q x + c^\top x \quad \text{s.t.} \quad Ax \leq b, \quad Cx = d$$

$Q \succeq 0$ 时为凸 QP，全局可解；$Q \succ 0$ 时严格凸，解唯一。目标函数是二次型，约束仍是线性的——这是 LP 与 QP 的关键区别。

二阶锥规划 SOCP

$$\min c^\top x \quad \text{s.t.} \quad \|A_i x + b_i\|_2 \leq c_i^\top x + d_i \quad \forall i, \quad Fx = g$$

SOCP 比 QP 更一般。$Q \succeq 0$ 的 QP 可改写为 SOCP（将二次目标拆为范数约束）。常用于 tracking error 约束、VaR 近似、因子模型风险。

优化层级

LP $\subset$ QP $\subset$ SOCP $\subset$ SDP（半正定规划）—— 表达能力依次递增，求解难度也依次递增。

常用工具：CVXPY（Python 建模，后端 Gurobi / MOSEK / ECOS），scipy.optimize。

08 — 扩展 ★ 高频面试题

Lasso 改写为 QP

Lasso 本身不是 QP——$\ell_1$ 惩罚项是分段线性函数，在 $\beta_j = 0$ 处不可微。但通过引入辅助变量，可以精确等价地改写为 QP，从而用标准 QP solver 求解。

原始 Lasso

$$\min_\beta \; \|y - X\beta\|_2^2 + \lambda \|\beta\|_1$$

$\|\beta\|_1 = \sum_j |\beta_j|$ 是分段线性非光滑函数。正是这个非光滑性使 Lasso 产生稀疏解——最优点"卡"在 $\ell_1$ 球（菱形）的角上。

QP 改写方案

改写
引入辅助变量 $u \in \mathbb{R}^p$，令 $u_j \geq |\beta_j|$。等价的 QP： $$\min_{\beta,\, u} \; \|y - X\beta\|_2^2 + \lambda \sum_j u_j$$ $$\text{s.t.} \quad u_j \geq \beta_j, \quad u_j \geq -\beta_j \quad \forall j$$

目标函数关于 $\beta$ 是二次型，关于 $u$ 是线性的；约束全是线性不等式——这是标准 QP。

等价性证明 $P^* = Q^*$

证明

记原 Lasso 最优值 $P^* = \min_\beta \|y - X\beta\|_2^2 + \lambda\|\beta\|_1$，QP 最优值 $Q^* = \min_{\beta,u}\, \|y-X\beta\|_2^2 + \lambda\mathbf{1}^\top u$，约束 $u_j \geq |\beta_j|$。

($Q^* \leq P^*$)：对任意 $\beta$，令 $u_j = |\beta_j|$，则 $(\beta, u)$ 对 $Q$ 可行，目标值等于 Lasso 目标值。故 $Q^* \leq P^*$。

($Q^* \geq P^*$)：对 $Q$ 的任意可行解 $(\beta, u)$，有 $u_j \geq |\beta_j|$，故目标值 $\geq \|y-X\beta\|^2 + \lambda\|\beta\|_1 \geq P^*$。取下确界得 $Q^* \geq P^*$。

综合：$P^* = Q^*$。$\blacksquare$

紧性：最优解处 $u_j^* = |\beta_j^*|$

证明（反证法）

命题：若 $(\beta^*, u^*)$ 是 $Q$ 的最优解，则对所有 $j$ 有 $u_j^* = |\beta_j^*|$。

证明：由可行性，$u_j^* \geq |\beta_j^*|$ 对所有 $j$ 成立。只需证反方向 $u_j^* \leq |\beta_j^*|$。

反设存在 $j_0$ 使得 $u_{j_0}^* > |\beta_{j_0}^*|$，构造扰动：

$$\tilde{u}_j = \begin{cases} |\beta_{j_0}^*| & j = j_0 \\ u_j^* & j \neq j_0 \end{cases}$$

可行性：$\tilde{u}_{j_0} = |\beta_{j_0}^*| \geq |\beta_{j_0}^*|$ ✓，其余分量不变 ✓。

目标值：

$$\|y - X\beta^*\|_2^2 + \lambda \sum_j \tilde{u}_j = \|y - X\beta^*\|_2^2 + \lambda \sum_j u_j^* - \lambda \underbrace{(u_{j_0}^* - |\beta_{j_0}^*|)}_{>\,0} < Q^*$$

与 $(\beta^*, u^*)$ 最优矛盾。故 $u_j^* \leq |\beta_j^*|$，结合可行性得 $u_j^* = |\beta_j^*|$。$\blacksquare$

另一种方案：变量分裂

令 $\beta_j = \beta_j^+ - \beta_j^-$，$\beta_j^+, \beta_j^- \geq 0$，最优解处 $|\beta_j| = \beta_j^+ + \beta_j^-$。改写为：

$$\min_{\beta^+,\, \beta^- \geq 0} \; \|y - X(\beta^+ - \beta^-)\|_2^2 + \lambda \mathbf{1}^\top(\beta^+ + \beta^-)$$

纯 QP，$2p$ 个非负变量，无需额外不等式约束。两种方案完全等价。

核心技巧：$|\cdot|$ 是分段线性函数 → 辅助变量线性化 → 改写为 QP 或 LP。同样适用于：$\ell_1$ 损失回归（分位数回归）、绝对偏差最小化、含绝对值的投资组合交易成本项。
09 — 扩展

整数规划 Integer Programming

当某些变量必须取整数：$x_j \in \mathbb{Z}$（ILP）或 $x_j \in \{0,1\}$（BIP）。LP 松弛（去掉整数约束）给出目标值的下界。

核心概念

概念描述
LP 松弛去掉整数约束，解是 ILP 最优值的下界
分支定界 Branch & Bound对分数值变量分叉枚举子问题
割平面 Cutting Planes添加有效不等式（Gomory cuts）收紧 LP 松弛
整数间隙 Integrality GapLP 松弛与 ILP 最优值之比，衡量松弛质量

Quant 相关场景

手数（round lots）约束、交易调度、带基数限制的指数复制（最多持有 $k$ 只股票），以及最小仓位规模的组合构建，均需要 MIP。

10 — 应用

投资组合优化 Portfolio Optimization

Markowitz 均值-方差（QP）

$$\min_w \; w^\top \Sigma w \quad \text{s.t.} \quad \mu^\top w \geq r_{\min}, \quad \mathbf{1}^\top w = 1, \quad w \geq 0$$

$\Sigma \succ 0$ 时为严格凸 QP，最优解唯一。约束 $\mathbf{1}^\top w = 1$ 为等式；$\mu^\top w \geq r_{\min}$ 在有效前沿上为紧约束（active constraint）。扫描 $r_{\min}$ 即可画出有效前沿。

对偶变量的金融含义

收益约束 $\mu^\top w \geq r_{\min}$ 的 Lagrange 乘子是风险-收益权衡率（Sharpe 斜率的倒数）；预算约束 $\mathbf{1}^\top w = 1$ 的乘子是资本的边际成本（marginal cost of capital）。

含交易成本（QP 扩展）

$$\min_w \; w^\top \Sigma w + \lambda \sum_j c_j |w_j - w_j^0|$$

交易成本中的 $|\cdot|$ 用与 Lasso 完全相同的辅助变量技巧改写为线性约束，整体仍是 QP。

因子模型（SOCP）

设 $\Sigma = BFB^\top + D$（因子结构），含 tracking error 约束 $\|B(w - w_b)\|_2 \leq \epsilon$ 的风险最小化变为 SOCP。

11 — 应用

无套利与状态价格 No-Arbitrage Pricing

问题设置

设 $S$ 个状态，$N$ 种资产，收益矩阵 $D \in \mathbb{R}^{S \times N}$，价格向量 $p \in \mathbb{R}^N$。投资组合 $\theta \in \mathbb{R}^N$ 构成套利当且仅当：

$$p^\top \theta \leq 0 \quad \text{且} \quad D\theta \geq 0, \quad D\theta \neq 0$$

即零成本建仓，所有状态下收益非负，且至少一个状态下严格为正。

资产定价基本定理（有限状态）
无套利 $\iff$ 存在严格正的状态价格向量 $\psi \gg 0$ 使得 $p = D^\top \psi$。由 LP 对偶，这等价于某个对偶 LP 可行——对偶变量正比于状态价格。

套利检测的 LP 公式化

$$\max_\theta \; \mathbf{1}^\top D\theta \quad \text{s.t.} \quad p^\top \theta \leq 0, \quad D\theta \geq 0$$

若最优值 $> 0$，套利存在。对偶变量正比于状态价格 $\psi$。

风险中性定价

归一化：$q_s = \psi_s / \sum_s \psi_s$ 给出风险中性概率 $q \in \Delta^{S-1}$，资产满足 $p_n = \frac{1}{1+r_f}\mathbb{E}^Q[D_n]$。

12 — 应用

交易执行策略 Execution Scheduling

VWAP 调度（LP）

设 $x_t$ 为第 $t$ 期交易量，$V_t$ 为市场成交量预测，在完成总量 $X$ 的同时最小化市场冲击成本：

$$\min_x \sum_t \lambda_t x_t \quad \text{s.t.} \quad \sum_t x_t = X, \quad 0 \leq x_t \leq \kappa V_t$$

$\lambda_t$ 为各时段单位冲击成本，纯 LP。若 $\lambda_t$ 均一，最优策略是在成交量峰值时段集中下单。

Almgren-Chriss 模型（QP）

最小化期望执行成本与其方差的加权和。方差项（来自价格风险）关于 $x_t$ 是二次的，整体变为 QP。扫描风险厌恶参数可画出执行策略的有效前沿，对应 implementation shortfall 的边际成本。

13 — 面试题

典型例题

例题 1：将 $\ell_1$ 回归改写为 LP

题目
将 $\min_\beta \sum_i |y_i - x_i^\top \beta|$ 改写为线性规划。
解答

令 $r_i = y_i - x_i^\top \beta$，分裂 $r_i = r_i^+ - r_i^-$，$r_i^+, r_i^- \geq 0$，则 $|r_i| = r_i^+ + r_i^-$。LP：

$$\min_{\beta,\, r^+,\, r^-} \;\mathbf{1}^\top(r^+ + r^-) \quad \text{s.t.} \quad X\beta + r^+ - r^- = y, \quad r^+, r^- \geq 0$$

目标线性，约束线性，纯 LP。$\blacksquare$

例题 2：写出投资组合 LP 的对偶

题目
原问题：$\min_w c^\top w$ s.t. $\mathbf{1}^\top w = 1$，$Rw \geq r_{\min}\mathbf{1}$，$w \geq 0$。写出对偶并解释变量含义。
解答

引入乘子 $\nu$（自由）对应 $\mathbf{1}^\top w = 1$，$\lambda \geq 0$ 对应 $Rw \geq r_{\min}\mathbf{1}$。对偶：

$$\max_{\lambda \geq 0,\, \nu} \; r_{\min}\mathbf{1}^\top \lambda + \nu \quad \text{s.t.} \quad R^\top \lambda + \nu\mathbf{1} \leq c$$

$\lambda_i$：场景 $i$ 收益约束的影子价格。$\nu$：预算增加一单位的边际目标改善量（资本的边际回报率）。$\blacksquare$

例题 3：Lasso 是 QP 吗？如何用 QP solver 求解？

题目
$\min_\beta \|y - X\beta\|^2 + \lambda\|\beta\|_1$ 是二次规划吗？如何用 QP solver 求解？
解答

不是直接的 QP：$\|\beta\|_1 = \sum_j |\beta_j|$ 是分段线性函数，非光滑，目标函数不是标准二次型。

改写为 QP：引入 $u \geq 0$，约束 $u_j \geq \beta_j$，$u_j \geq -\beta_j$：

$$\min_{\beta,u} \|y-X\beta\|^2 + \lambda\mathbf{1}^\top u \quad \text{s.t.} \quad u_j \geq \pm\beta_j \;\forall j$$

目标关于 $\beta$ 是二次型，关于 $u$ 是线性；约束线性——标准 QP。

紧性：最优解处 $u_j^* = |\beta_j^*|$。若 $u_{j_0}^* > |\beta_{j_0}^*|$，令 $\tilde{u}_{j_0} = |\beta_{j_0}^*|$ 仍可行但目标值严格更小，与最优性矛盾。$\blacksquare$

例题 4：验证互补松弛条件

题目
LP：$\min 2x_1 + 3x_2$ s.t. $x_1 + x_2 \geq 4$，$x_1 + 2x_2 \geq 6$，$x_1, x_2 \geq 0$。原最优解 $(2,2)$，求对偶最优并验证互补松弛。
解答

对偶：$\max 4y_1 + 6y_2$ s.t. $y_1 + y_2 \leq 2$，$y_1 + 2y_2 \leq 3$，$y_1, y_2 \geq 0$。

原最优 $(2,2)$ 处两约束均紧：$2+2=4$ ✓，$2+4=6$ ✓。由互补松弛，$y_1, y_2 > 0$，故两个对偶约束也紧。联立 $y_1+y_2=2$，$y_1+2y_2=3$，解得 $y^* = (1,1)$。

强对偶验证：$4(1)+6(1)=10 = 2(2)+3(2)=10$ ✓。$\blacksquare$

例题 5：影子价格的经济含义

题目
投资组合 LP 中，预算约束 $\mathbf{1}^\top w = 1$ 对应的对偶变量 $\nu = 0.15$，含义是什么？
解答

$\nu = 0.15$ 是预算的影子价格：若预算从 1 增加到 $1 + \varepsilon$，最优期望收益增加 $0.15\varepsilon$。

经济含义：在当前最优配置下，额外投入一美元的边际期望收益为 15%，即最优组合的边际资本回报率（marginal return on capital）。$\blacksquare$

线性规划 Linear Programming — Quant 面试指南  ·  Princeton MFin  ·  LP · QP · SOCP · 对偶 · KKT · Lasso