使用pyscipopt求解投资组合MINLP问题有没有更高效的方案？

你当前求解的是带整数约束的安全第一准则投资组合优化问题，对应数学模型如下：

原始代码运行效率极低的核心原因及优化方案如下：

核心问题原因 #

• 约束构造引入了非凸非线性结构，导致求解复杂度飙升
  你当前写的约束中同时存在两类高复杂度项：

1. 两个二元变量stocks_portfolio[i] * stocks_portfolio[j]的双线性项，150个可选标的下仅两两组合的双线性项超过2万余个，属于非凸项
2. 方差开平方根的非线性运算
   两类非凸结构不属于标准凸优化问题范畴，SCIP求解此类非凸MINLP需要大量分支定界迭代，耗时会指数级上升

• 协方差矩阵不符合数学要求
  你随机生成的协方差矩阵既不对称也不满足半正定要求，求解器会频繁进入不可行域搜索，浪费大量算力
• 未利用问题本身的凸结构做等价转换
  你要最小化的指标是Roy安全第一准则的变形，可以等价转换为混合整数二阶锥规划（MISOCP），这类凸问题的求解难度远低于通用非凸MINLP

可行优化方案 #

1. 问题等价重写为MISOCP形式 #

你要最小化的目标stand_in = min (t - μ^T x)/sqrt(x^T Σ x)，可以等价改写为二阶锥约束：
设σ ≥ sqrt(x^T Σ x)
则约束可以改写为t - μ^T x ≤ stand_in * σ
二阶锥约束是标准凸约束，SCIP原生支持MISOCP求解，速度可提升10~100倍

2. 修正协方差矩阵生成逻辑 #

生成协方差矩阵时保证对称半正定，生成代码调整为：

rand_mat = np.random.normal(0, 0.3, (noptions, noptions))
cov_mat = rand_mat @ rand_mat.T + np.eye(noptions)*1e-3 # 加小项保证严格半正定

3. 调整求解器参数开启加速 #

设置SCIP的SOCP求解开关、时间上限等参数，减少无效迭代

优化后示例代码 #

from pyscipopt import Model, quicksum
import numpy as np
import pandas as pd
from random import uniform

model = Model()
model.setParam('misc/usesoclp', 1) # 开启SOCP线性化加速
model.setParam('limits/time', 300) # 设置5分钟时间上限，可自行调整

t = 20000
noptions = 150
stocks_df = pd.DataFrame(np.zeros((noptions,4)), columns = ['ids','Mean','cost','stdev'])
stocks_df['ids'] = range(noptions)
stocks_df['Mean'] = [uniform(500,2500) for _ in range(noptions)]
stocks_df['cost'] = [stocks_df.loc[i,'Mean']*uniform(50,250) for i in range(noptions)]
stocks_df['stdev'] = [stocks_df.loc[i,'Mean']*uniform(0.2,0.5) for i in range(noptions)]

# 修正协方差矩阵生成逻辑
rand_mat = np.random.normal(0, 0.3, (noptions, noptions))
cov_mat = rand_mat @ rand_mat.T + np.eye(noptions)*1e-3

# 定义变量
x = [model.addVar(vtype='B', name=f'x_{i}') for i in range(noptions)]
stand_in = model.addVar(vtype='C', name='obj')
sigma = model.addVar(vtype='C', lb=0, name='sigma') # 标准差为非负值

# 基础约束
model.addCons(quicksum(x[i] for i in range(noptions)) == 15)
model.addCons(quicksum(stocks_df.loc[i, 'cost']*x[i] for i in range(noptions)) <= 600000)

# 等价SOCP约束1：sigma平方大于等于组合方差
model.addCons(sigma*sigma >= quicksum(x[i]*x[j]*cov_mat[i,j] for i in range(noptions) for j in range(noptions)))
# 等价SOCP约束2：t减组合均值小于等于目标值乘标准差
model.addCons(t - quicksum(stocks_df.loc[i, 'Mean']*x[i] for i in range(noptions)) <= stand_in * sigma)

model.setObjective(stand_in, 'minimize')
model.optimize()

# 提取最优持仓
portfolios = [i for i in range(noptions) if model.getVal(x[i]) > 0.9]

如果不需要严格全局最优解，还可以使用遗传算法、模拟退火等启发式算法求解，速度会比精确求解器快很多。

内容的提问来源于stack exchange，提问作者Steven Kelly