优化CVXPY中大规模半定规划(SDP)求解运行时长的技术咨询

问题背景 #

针对你的SDP模型：

• 变量：$p \times p$矩阵$V$、$num \times p$矩阵$X$（$num=d^2 \geq 6561$，你的场景中$p=2$）
• 约束：
  1. 块矩阵半正定约束（等价于$V \succeq X^T R^H R X$）
  2. 线性约束$X^T \text{dersmatrix} = I_p$
• 目标：$\min \text{trace}(W V)$
• 核心痛点：$num$过大导致求解速度极慢，块矩阵约束带来的大规模半正定变量是主要瓶颈

以下是针对该场景的可行优化方案：

一、消除大规模半正定约束，将SDP转化为QP（核心优化） #

若权重矩阵$W$是半正定的（通常权重矩阵满足该特性），原问题可直接简化：
因为要最小化$\text{trace}(W V)$，在$V \succeq X^T R^H R X$的约束下，最优解必然是$V = X^T R^H R X$（线性目标在凸约束边界取最小值）。

改写后的QP问题代码：

import cvxpy as cp
import scipy.sparse

# 提前计算稀疏形式的R^H R，避免重复运算
R_H_R = R.conj().T @ R
R_H_R = scipy.sparse.csr_matrix(R_H_R)

# 仅保留X作为优化变量
X = cp.Variable((num, p))

# 目标函数：直接用简化后的二次形式
objective = cp.trace(W @ X.T @ R_H_R @ X)

# 仅保留线性约束
constraints = [X.T @ dersmatrix == np.identity(p)]

prob = cp.Problem(cp.Minimize(objective), constraints)
prob.solve(solver=cp.MOSEK, verbose=True)

该方案完全消除了大规模半正定约束，将问题从SDP转为QP，MOSEK处理QP的速度远快于SDP。

二、充分利用R的稀疏性 #

已将R转为稀疏矩阵的基础上，进一步优化：

• 提前预计算$R^H R$的稀疏形式，避免求解过程中重复计算矩阵乘法
• 使用CVXPY的cp.quad_form函数处理二次项，它对稀疏矩阵的支持更高效：

# 针对p=2的场景，拆分二次项为列向量的二次形式
objective = cp.sum([cp.quad_form(X[:, k], R_H_R @ W[:, [k]]) for k in range(p)])

三、调整MOSEK求解器参数 #

针对大规模QP问题，通过参数调整加速收敛：

prob.solve(solver=cp.MOSEK, verbose=True,
           mosek_params={
               'MSK_IPAR_INTPNT_MAX_ITER': 100,  # 减少最大迭代次数（按需调整）
               'MSK_IPAR_INTPNT_TOL_REL_GAP': 1e-5,  # 放宽相对间隙容忍度
               'MSK_IPAR_INTPNT_SCALING': 3,  # 启用均值缩放（3对应MSK_SCALING_TYPE_MEAN）
               'MSK_IPAR_OPTIMIZER': 0  # 选择内点法（0对应MSK_OPTIMIZER_INTPNT）
           })

注：参数值可根据问题精度需求灵活调整，放宽精度能显著加快求解速度。

四、利用线性约束结构简化变量 #

通过QR分解消除线性约束，减少求解器的约束处理开销：

# 对dersmatrix做QR分解
Q, R_qr = np.linalg.qr(dersmatrix, mode='complete')
# 计算R_qr前p行的逆转置
R_inv_T = np.linalg.inv(R_qr[:p, :p]).T

# 定义新变量Y，自动满足线性约束
Y = cp.Variable((num - p, p))
X = Q @ cp.vstack([R_inv_T, Y])

# 目标函数不变，无需再添加线性约束
objective = cp.trace(W @ X.T @ R_H_R @ X)
prob = cp.Problem(cp.Minimize(objective))
prob.solve(solver=cp.MOSEK, verbose=True)

五、预处理矩阵提升数值稳定性 #

• 对R做截断SVD：若R存在大量小奇异值，可保留前k个主奇异值近似R，降低有效秩
• 对dersmatrix做列归一化：消除数值缩放差异，帮助求解器更稳定地迭代

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