Optiver面试攻略：VO真题解答与OA面经

这是一道典型的组合优化问题，在实际的量化交易中非常常见。由于题目要求选择一个资产子集来最大化夏普比率，并且没有给出具体的约束条件和风险的定义（例如是协方差矩阵还是简单的标准差），我们假设资产风险是标准差，且约束主要是指资产数量或总投资额。

问题抽象与数学模型

夏普比率（Sharpe Ratio, $S$）的定义是： 其中 $E(R_p)$ 是投资组合的预期收益，$\sigma_p$ 是投资组合的风险（标准差），$R_f$ 是无风险利率（在竞争性编程中，通常假设 $R_f = 0$ 以简化问题）。因此，目标是最大化 $\frac{E(R_p)}{\sigma_p}$。 假设我们有 $N$ 个资产，决策变量是二元的：$x_i \in \{0, 1\}$，表示是否选择资产 $i$。

• 组合收益 $E(R_p) = \sum_{i=1}^{N} x_i E(R_i)$，其中 $E(R_i)$ 是资产 $i$ 的预期收益。
• 组合风险 $\sigma_p$ 的计算取决于资产间的相关性。
  • 独立资产假设 (简化版)： 如果资产独立，则 $\sigma_p = \sqrt{\sum_{i=1}^{N} x_i^2 \sigma_i^2} = \sqrt{\sum_{i=1}^{N} x_i \sigma_i^2}$，其中 $\sigma_i$ 是资产 $i$ 的标准差。
  • 相关资产（真实情况）： $\sigma_p = \sqrt{\sum_{i=1}^{N} \sum_{j=1}^{N} x_i x_j \sigma_{ij}}$，其中 $\sigma_{ij}$ 是资产 $i$ 和 $j$ 的协方差。

由于这是一个子集选择问题，决策变量是离散的（0或1），并且目标函数通常是非线性的（因为有平方根和除法），这是一个非线性的整数规划（Mixed-Integer Non-Linear Programming, MINLP）问题，属于NP-hard问题。

基于贪心或回溯搜索

面对 NP-hard 的子集选择问题，尤其在竞争性编程或 OA 中，往往需要考虑近似算法、启发式搜索或约束较小时的暴力搜索：

1. 约束较小时（资产数量 $N$ 较小，如 $N \le 20$）： 可以使用回溯法（Backtracking）或状态压缩动态规划（Bitmask DP）进行暴力枚举所有 $2^N$ 个子集，计算每个子集的夏普比率，并取最大值。
2. 约束较大时（资产数量 $N$ 较大）： 暴力枚举不可行。如果资产间的相关性被忽略（即假设独立），目标函数变得更易处理，可以尝试贪心算法或动态规划。如果不能忽略相关性，则需要启发式搜索，如模拟退火（Simulated Annealing）或遗传算法（Genetic Algorithm），但这些在 OA 题中通常超出范围，除非题目有特定的简化。

假设资产独立且使用回溯搜索

为了给出一个可执行的解题过程，我们采纳 OA 题中常见的简化：假设资产独立，且资产数量 $N$ 较小，使用回溯搜索（Depth-First Search, DFS）：

1. 初始化： 维护一个全局变量 max_sharpe记录找到的最大夏普比率。
2. DFS 函数定义： DFS(index, current_return, current_variance)
   • index: 当前考虑的资产序号。
   • current_return: 当前已选择资产的总预期收益。
   • current_variance: 当前已选择资产的总方差（$\sum \sigma_i^2$）。
3. 递归终止条件：
   • 如果 index == N（所有资产都已考虑完毕），则计算当前组合的夏普比率：  
     $$S = \frac{current\_return}{\sqrt{current\_variance}}$$
       如果 $current\_variance = 0$，则 $S$ 设为 $\infty$（如果 $current\_return > 0$）或 0。 更新 max_sharpe = max(max_sharpe, S)。
4. 递归步骤（对于第 $index$ 个资产）：
   • 不选择资产 $index$： 调用 DFS(index + 1, current_return, current_variance)
   • 选择资产 $index$：
     • 更新收益：new_return = current_return + E(R_index)
     • 更新方差：new_variance = current_variance + \sigma_{index}^2
     • 调用 DFS(index + 1, new_return, new_variance)

约束处理： 如果有限制（如“最多选择 K 个资产”），可以在 DFS 函数中添加一个计数器参数，并在递归选择资产时检查是否超过 $K$。

解题

最终的解题答案是回溯搜索（DFS）过程中找到的最大 max_sharpe 值，以及对应产生该最大夏普比率的资产子集。 如果输入数据为： | 资产 | 收益 $E(R_i)$ | 风险 $\sigma_i$ | $\sigma_i^2$ | | :—: | :—: | :—: | :—: | | A | 0.10 | 0.05 | 0.0025 | | B | 0.20 | 0.10 | 0.0100 | | C | 0.15 | 0.05 | 0.0025 | 暴力枚举的结果将是： | 组合 | $E(R_p)$ | $\sigma_p$ | $S$ | | :—: | :—: | :—: | :—: | | {B, C} | 0.35 | $\sqrt{0.0125} \approx 0.1118$ | $\approx 3.13$ | | … | … | … | … | 通过完整的 DFS 遍历，我们能保证找到能最大化夏普比率的资产子集。 这道题的核心难度在于子集选择（离散决策）和非线性目标函数（夏普比率）。如果题目没有明确给出简化（如资产独立），并允许投资比例（权重 $w_i \in [0, 1]$），那么它会变成一个连续变量的二次规划问题，可以使用更高效的数值优化方法（如牛顿法或内点法）解决，这又是另一类经典的马科维茨优化问题。但对于 $0/1$ 的子集选择，在资产数量较小时，回溯搜索是最直接和可靠的方法。