计算科学 - 具有分段线性目标的开源二次规划 - 吾爱随笔录

我正在寻找一个开源求解器来解决具有附加分段线性目标的二次规划问题，如下所示。问题相当小（是一个维度为 120 的向量）。 $\mathbf{x}$

max_{x} : x^{T} q_{0} - x^{T} P_{0} x - f (x)

$\begin{equation*} \max_{x}: \mathbf{x}^{T} \mathbf{q_0} - \mathbf{x^{T}} P_0 \mathbf{x} - f(\mathbf{x}) \end{equation*}$

请注意，上面的 $P_0$ 是半正定的，对于 $f$ 是分段线性的，但不是凸的。对于每个，，将是坐标点的向量，例如 $\mathbf{x}$ $x_i$ $i \in \left\{1, ..., 120\right\}$ $f(x)$

[(x_0, y_0), (x_1, y_1), ..., (x_N, y_N)]

对于任何给定的 $x_i$ ， $f(x_i)$ 如下所示。

由于 $f$ 不依赖于 $\mathbf{x}$ 中的任何交叉项，因此上述优化也可以写为

max_{x} : x^{T} q_{0} - x^{T} P_{0} x - (f (x_{1}) + . . . + f (x_{120}))

$\begin{equation*} \max_{x}: \mathbf{x}^{T} \mathbf{q_0} - \mathbf{x^{T}} P_0 \mathbf{x} - (f(x_1) + ... + f(x_{120})) \end{equation*}$

也形式的线性约束。 $A\mathbf{x} < \mathbf{b}$

我在 Gurobi 中制定了这个问题，这个问题相当简单，但希望将其与开源求解器进行比较。环顾四周，GLPK 似乎可以解决这个问题，但我没有使用这个库的经验，所以希望能获得一些与这个或替代解决方案相关的信息。

使用 matlab API 的 gurobi 示例问题如下所示。

N = 2;

q_0 = [-3.31e3, -5.07e3];
P_0 = [-0.90e-04  -0.63e-04;
       -0.63e-04  -0.90e-04];

x = [-2.0000e9, -1.0000e9, -0.8000e9, -0.6000e9, -0.4000e9, -0.2500e9,...
    -0.1000e9, -0.0500e9, -0.0250e9, -0.0100e9, -0.0010e9, 0, 0.0010e9,...
    0.0100e9, 0.0250e9, 0.0500e9, 0.1000e9, 0.2500e9, 0.4000e9,...
    0.6000e9, 0.8000e9, 1.0000e9, 2.0000e9];

y = [2.938964e6, 0.753364e6, 0.488104e6, 0.280144e6, 0.129472e6,...
    0.053766e6, 0.011007e6, 0.003751e6, 0.001435e6, 0.000465e6,...
    0.000037e6, 0, 0.000037e6, 0.000465e6, 0.001435e6, 0.003751e6,...
    0.011007e6, 0.053766e6, 0.129472e6, 0.280144e6, 0.488104e6,...
    0.753364e6, 2.938964e6];

params.outputflag = 0;

%formulate model
model.obj = zeros(N, 1);
model.Q = sparse(P_0);
model.A = sparse(zeros(1, N));
model.sense = '=';
model.rhs = 0;
model.ub = repmat(1e9, N, 1);
model.lb = repmat(-1e9, N, 1);
model.modelsense = 'max';

% piecewise tcosts
for i = 1:2
    model.pwlobj(i).var = i;
    model.pwlobj(i).x   = x;
    model.pwlobj(i).y   = x * q_0(i) - y;
end

result = gurobi(model, params);