3

这是一个新手问题。我正在尝试最小化以下 QP 问题：

x'Qx + b'x + c，对于 Ax >= lb 其中：

  1. x 是坐标向量，
  2. Q 是一个稀疏、强对角占优的对称矩阵，通常大小为 500,000 x 500,000 到 1M x 1M
  3. b 是常数向量
  4. c 是一个常数
  5. A 是单位矩阵
  6. lb 是一个包含向量 x 下界的向量

以下是我尝试过的软件包：

  1. Optim.jl：他们有一个简单的“盒子”约束的原始内点算法。我尝试过使用 inner_optimizer，将其设置为 GradientDescent()/ConjugateGradient()。无论如何，这对我的问题集来说似乎很慢。

  2. IterativeSolver.jl：他们有一个共轭梯度求解器，但他们没有办法为 QP 问题设置约束。

  3. MathProgBase.jl：他们有一个用于二次规划的专用求解器，称为 Ipopt()。它对于通常在 3Kx3K 矩阵左右的小型数据集非常有效，但对于我正在查看的那种数据集来说它需要的时间太长了。我知道将线性系统求解器从 MUMPS 更改为 HSL 或 WSMP 可能会产生显着的改进，但是有没有办法通过 Julia 将第三方线性系统求解器添加到 Ipopt() 中？

  4. OSQP.jl：对于我感兴趣的数据集，这又需要很长时间才能收敛。

另外我想知道是否有人使用过大型数据集，他们能否提出一种方法来使用现有的包在 Julia 中快速解决这种规模的问题？

4

1 回答 1

3

您可以尝试使用不同参数的 OSQP 求解器来加速针对您的特定问题的收敛。尤其是：

  • 如果您有多个内核，MKL Pardiso可以显着减少执行时间。您可以在此处找到有关如何安装它的详细信息（它基本上包括运行默认的 MKL 安装程序）。之后就可以在OSQP中使用如下

    model = OSQP.Model()
OSQP.setup!(model; P=Q, q=b, A=A, l=lb, u=ub, linsys_solver="mkl pardiso")
results = OSQP.solve!(model)

  • 迭代次数取决于您的步长 rho。OSQP 会自动更新它以尝试找到最好的。如果您有特定问题，您可以禁用自动检测并自己玩。这是尝试不同的示例rho

    model = OSQP.Model()
OSQP.setup!(model; P=Q, q=b, A=A, l=lb, u=ub, linsys_solver="mkl pardiso",
            adaptive_rho=false, rho=1e-3)
results = OSQP.solve!(model)

    我建议您尝试不同的rho值，可能在1e-06 and 1e06.

  • 您可以通过重新调整问题数据来减少迭代，这样矩阵的条件数就不会太高。这可以显着减少迭代次数。

我很确定如果遵循这 3 个步骤，您可以使 OSQP 工作得很好。如果您愿意分享您的数据（我是开发人员之一），我很高兴为您的问题尝试 OSQP。

MathProgBase.jl稍微不相关，您可以使用and调用 OSQP JuMP.jl。它还支持MathOptInterface.jl将替换MathProgBase.jl为最新版本的 JuMP 的最新软件包。

于 2018-07-12T18:51:48.090 回答