Vectorize quadcon in matlab for many cones
Answered
I have a socp with millions of cones.
It seems that currently, it's only possible to add a quadcon one-by-one in a loop. This is effective only for small problems:
Moreover, a formulation of a cone must be as a quad cone, which requires to multiply the cone matrix by its transpose. This is inefficient programmatically and numerically.
Nothing has been seemed to improve in the past 7 years:
https://support.gurobi.com/hc/en-us/community/posts/360048464832-How-to-effectively-implement-quadratic-constraints-over-80-000
-
-
Gurobi Staff
Hi Zohar,
Adding multiple quadratic constraints in a single API call is not a feature in any of our APIs. Can you point to an example in another solver API that demonstrates the functionality you are after?
Moreover, a formulation of a cone must be as a quad cone, which requires to multiply the cone matrix by its transpose. This is inefficient programmatically and numerically.
This can be avoided, as mentioned in my response to your other post.
- Riley
0 -
-
Mosek, e.g. (untested):
clear prob; K = 4; % number of cones d = 2; % dimension of x inside each cone (so cone size = d+1 = 3) n = K*(d+1); % total variables % Objective: minimize sum of all t_k c = zeros(n,1); c(1:(d+1):n) = 1; % every (d+1)-th variable is a t_k prob.c = c; prob.a = sparse([]); % no linear constraints prob.blc = []; prob.buc = []; prob.blx = -inf(n,1); prob.bux = inf(n,1); % ----- Build cones ----- % Each cone uses variables: % cone k → indices (k-1)*(d+1) + [1, 2, ..., d+1] prob.cones.type = repmat(mosek.ct.quad, 1, K); prob.cones.subptr = 1:(d+1):((d+1)*K); sub = zeros(1, n); for k = 1:K base = (k-1)*(d+1); sub(base+1 : base+(d+1)) = base+1 : base+(d+1); end prob.cones.sub = sub; % ----- Solve ----- [r,res] = mosekopt('minimize', prob);Yalmip supports it as well, but the gurobi implementation is a slow loop.
(Yeah, I mentioned the numerical issue twice for some reason.)
0 -
-
It seems that currently, it's only possible to add a quadcon one-by-one in a loop. This is effective only for small problems
What is the time you'd need to call it effective? Here is a simple experiment I did: Create problem with 100.000 quadratic constraints each comprising 100 variables, creating the data one-by-one in a Matlab for loop:
function qcp() t_start = tic(); % Number of quadratic constraints q = 100000; % Number of variables n = 100000; % Number of variables participating in each quadratic constraint qclen = 100; model.A = sparse(0, n); for k = 1:q model.quadcon(k).Qrow = 1:qclen; model.quadcon(k).Qcol = 1:qclen; model.quadcon(k).Qval = rand(1, qclen); model.quadcon(k).q = sparse(n, 1); model.quadcon(k).rhs = 1.0; end fprintf('Matlab model building time %.2fsec.\n', toc(t_start)); params.timelimit = 0; result = gurobi(model, params); endWith Matlab 2019a on a 5 year old AMD box I get
Matlab model building time 1.08sec.Doesn't look too bad to me? I'm sure you can adapt this pattern to host the indices for the cones in
model.quadcon(k).Qrowandmodel.quadcon(k).Qcoland put the corresponding +1.0/-1.0 coefficients in themodel.quadcon(k).Qvalarray.Good luck!
0 -
-
From a closer look, indeed the quadcon wasn't the culprit.
Thanks
0
Please sign in to leave a comment.
Comments
4 comments