Suggestions on model and solvers

I would be happy for suggestions on how and where to implement the model for the data below (the plan is to extend to a much larger data set later so speed is of interest):

#Toy data
A = [1.0000 0 0.5000 0.5000 0.4714 0.2357;
    0 1.0000 0.5000 0 0.2357 0.5893;
    0.5000 0 0.2500 1.0000 0.5893 0.2946;
    0.5000 0 0.2500 1.0000 0.5893 0.2946;
    0.4714 0.2357 0.5893 0.5893 1.0000 0.6111;
    0.2357 0.5893 0.5303 0.2946 0.6111 1.0000]

g = [0.5 -0.2 0.3 0.2 0.0 -0.1]
s = [1 0 1 1 0 0]
d = [0 1 0 0 1 1]
F = 0.3

#Model
max c'*g

constr c'*A*c/2 ≤ F
       c'*s = 0.5
       c'*d = 0.5
       c ≥ 0

If your decision variable is indeed c, then this looks like a Quadratic Program (QP).
I would try my luck with JuMP.jl (see nonlinear modeling examples such as this one). You will need to select an appropriate solver from this list, i.e. one that supports QP.

2 Likes

The objective c'*g is linear, and the constraint c'*A*c/2 ≤ F is quadratic, so this is a quadratically-constrained problem, not linearly-constrained QP. The corresponding example in the JuMP doc would be this one.

If A is symmetric positive semi-definite, then the problem is convex and solvable fairly efficiently by several solvers such as Ipopt, CPLEX, Gurobi, Xpress, etc.

If A is not symmetric positive semi-definite, then the problem is non convex (and much more difficult to solve exactly). In that situation, Ipopt should give decent solution, though no guarantee of feasibility / optimality. Gurobi can solve non-convex QCPs to global optimality, potentially taking some time if the problem is large.

3 Likes

My bad I had switched the objective and constraints ^^ Edited my answer