1
$\begingroup$

I am looking for an open source solver to solve the a quadratic programming problem with an additional piecewise linear objective, as show below. The problem is fairly small ($\mathbf{x}$ is a vector of dimension 120).

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

Note that above $P_0$ is positive semidefinite and $f$ is piecewise linear for each variable in $\mathbf{x}$ but not convex. For each $x_i$, $i \in \left\{1, ..., 120\right\}$, $f(x)$ would be a vector of coordinate points, e.g.

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

For any given $x_i$, $f(x_i)$ looks something like the following.

enter image description here

Since $f$ does not depend on any cross terms in $\mathbf{x}$, the above optimization could also be written as

\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*}

The are also linear constraints of the form $A\mathbf{x} < \mathbf{b}$ are added.

I have formulated the problem in Gurobi which is fairly straightforward but was hoping to compare this to an open source solver. Looking around it seems like GLPK would work for this, but I have no experience using this library so was hoping for a bit of info related to this or alternative solutions.

A sample problem for gurobi using the matlab API is shown below.

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);
$\endgroup$
  • 1
    $\begingroup$ In what form are you give $f(x)$? Are there additional constraints? $\endgroup$ – Brian Borchers Oct 11 '16 at 14:48
  • $\begingroup$ @BrianBorchers responded inline to comment $\endgroup$ – mgilbert Oct 11 '16 at 15:04
  • 1
    $\begingroup$ Are the $y_{i}$ precise values or are they noisy? $\endgroup$ – Brian Borchers Oct 11 '16 at 15:11
  • $\begingroup$ I am slightly confused by how to interpret noisy here. The function $f$ is an approximation to reality, and in that sense is noisy. However from the perspective of this problem $f$ is a piecewise linear function, not a function which I am approximating using a piecewise linear function, and in that sense the $y_i$s are exact. $\endgroup$ – mgilbert Oct 11 '16 at 15:18
  • $\begingroup$ If the $y_{i}$ are measured values with measurement errors, then you most likely want to smooth the surface rather than using piecewise linear interpolation of the measured values. You could for example use a smoothed spline interpolation. $\endgroup$ – Brian Borchers Oct 11 '16 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.