After declaring my model, cvx_end does several presolve steps before passing to the solver. My model gets stuck in eliminate.m, specifically the loop of ‘STEP 3: Look for variables that we can eliminate without increasing fill-in’. What could be the reason for this? As I don’t get any error messages, just an infinite loop, it’s hard to see what exactly the problem is.
One things that is possibly related: While constructing my model I loop through a data structure with constraints and objectives, and each row of the data structure requires a different number of variables. That is, I might have variables x(i,1)…x(i, n_i) and x(j,1),…,x(j,n_j), with n_i and n_j different. I tried the approach of How to create a couple of matrix variables with different dimension? where I declare a large matrix of variables with max(n_j) columns. This creates variables that do not end up in the model. Setting dummy constraints on those variables does not resolve the issue. Is it possible that the above is related to my infinite loop in the presolve? If not, what could be the cause? Thanks in advance for any help!
Hi Mark,
Thanks for the reply. Below is the code that reproduces the problem.
It loads a matlab data file, can I upload this or send it to you?
I’m using CVX 2.2.
clear
load('mwe_cvx_data'); %load MWE data
num_criteria = length(data);
m = data(1).A.size(2); %number of columns for each matrix A
cvx_begin
%Initialize variable x
variable x(m)
subject to
x>=0;
%Initialize variable y
variable y(num_criteria)
%determine max col size
max_n = 0;
for k=1:num_criteria
n_k = data(k).A.size(1);
if n_k > max_n
max_n = n_k;
end
end
%Initialize variable matrix d
variable d(num_criteria,max_n)
%Initialize objective expression
expression obj_expr(1)
%Each k is associated with a matrix A, with constant number of columns but
%varying number of rows. We set constraint d = A*x. Variable d is
%subsequently used in defining constraints or objective functions.
for k=1: num_criteria
n_k = data(k).A.size(1);
row = data(k).A.row;
col = data(k).A.col;
val = data(k).A.val;
A = sparse(row,col,val, n_k, m);
subject to
d(k, 1:n_k)' == A*x;
constraint = data(k).constraint;
bound = data(k).bound;
weight = data(k).weight;
type = data(k).type;
if data(k).minimize == 1
factor = 1;
else
factor = -1;
end
switch type
case 1 %Linear criteria
if constraint %Constrain the minimum or maximum value
if factor==1
subject to
d(k, 1:n_k) <= bound;
else
subject to
d(k, 1:n_k) >= bound;
end
else %variable y represents the maximum or minimum value in the objective
obj_expr = obj_expr + factor*weight*y(k);
if factor==1
subject to
d(k, 1:n_k) <= y(k);
else
subject to
d(k, 1:n_k) >= y(k);
end
end
case 2 %Log-sum-exp criteria
parameters = data(k).parameters;
target_val = parameters(1);
a = parameters(2);
if constraint
subject to
log_sum_exp(-a*(d(k,1:n_k) - target_val)) <= log(n_k*bound);
else
obj_expr = obj_expr + factor*weight*y(k);
subject to
log_sum_exp(-a*(d(k,1:n_k) - target_val)) <= log(n_k*y(k));
end
end
end
minimise(obj_expr);
cvx_end
WARNING: The following files/directories are missing:
C:\Program Files\cvx\sedumi\.travis.yml
These omissions may prevent CVX from operating properly.
This seems to suggest there is a problem with your CVX installation. Try reinstalling. Also, perhaps you can try a different solver and see what happens.
Thanks for the reply. I got some new insights I wanted to share, which is why I removed the previous post.
Indeed, there is the warning on SeDuMi (this one: Installing CVX Version 2.2 Build 1148). Reinstalling CVX did not remove the warning. However, as suggested in that post, this is unlikely to cause any issue if SeDuMi is not used.
Changing solver to MOSEK did not solve the problem. After some more experiments, I noted that the presolve does terminate, only the time increases exponentially. Below is a simpler MWE.
If I increase the parameter m (i.e., the number of rows of matrices A1 and A2), the presolve time increases as follows:
m=100: time=0.2 sec
m=200: time=2.7 sec
m=400: time=12 sec
m=800: time=52 sec
m=1600: time=235 sec.
For any reasonably large problem with matrices A1,…,A50 and m around 2000 for each, this presolve step takes over 30min, whereas solving the model (using different implementations) takes 4 minutes.
clear
load('mwe_cvx_data'); %Load matrix A1 and A2
[m,n] = size(A1); %m=1600, n=600
cvx_begin
%Initialize variable x
variable x(n)
%Initialize objective variable y
variable y
%Initialize variable matrix d
variable d(m,2)
%Objective is epigraph of sum of exponentials (via log_sum_exp)
minimise(y);
subject to
d(:,1) == A1*x;
d(:,2) == A2*x;
log_sum_exp(-0.4*(d(:,2) - 40)) <= log(m*y); %epigraph constraint
d(:,1) <= 35.0;
x>=0;
cvx_end
Okay, that’s good to know, thanks for the help. Is there any rule of thumb for the types of functions/models that we can expect to have large building times? For my current model it seems as if including the log-sum-exp (or generally any non-linear criteria) makes the model building time explode. However, (if I understand correctly) the presolve still only checks linear systems.
There is a little confusion regarding what you are calling “presolve”. Generally, presolve is used to mean the initial “stuff”: the solver does i(before commencing the main algorithm) to try to make the problem easier to solve with its main algorithm, such as tightening bounds, and eliminating variables and constraints. What CVX does in generating the problem to send to the solver is usually not called “resolve”, but might be called CVX modeling time. I was referring to the CVX modeling time. Generally, the larger the problem, the greater the CVX modeling time. Nonlinearity probably takes more time than linear things, but I can not tell you the relative time for dealing with various nonlinearities, other than bigger size usually takes longer, maybe a lot longer.
With ‘presolve’ I was referring to the what CVX does in the function ‘eliminate.m’, which is called by ‘cvx_end’ before the model is passed to the solver. The steps described in ‘eliminate.m’ are the steps you would typically see in a presolve step. So I think we’re referring to the same thing.
I’m a bit surprised by the large difference in the CVX modeling time between linear and nonlinear models. Anyway, thanks for the help!