Creating optimization constraint with loop is too slow

I want to create optimization constraints using Problem-based Optimization in MATLAB.

I understand the vectorization is the proposed way to go as stated here https://www.mathworks.com/help/optim/ug/improve-formulation-or-solution.html

However, in many optimization problems, vectorization is not possible due to the problem nature, therefore loops are needed.

I have noticed that the loops involving optimization variables are too slow.

In the example below, a loop with 1000 iterations that includes a single optimization variable consumes around 7 seconds.

Is this the expected behaviour for generating optimization constraints over loops?

I understand that MATLAB is built on vectorization principles, however 7 seconds for a 1000 iteration loop is extremely slow.

% set
I = "i" + (1:1000)' ;

% positive continuous variable defined over set I
k = optimvar ( 'k' , I , 'LowerBound' , 0 )       ; 

% Constraint with loop ~7s
tic
Constraint_test = optimconstr ( I ) ;
for i = 1 : length(I)
    Constraint_test(i) = 2 * k(i) + 3 <= 10 ;
end
toc

% Constraint vectorized ~0.01s
tic
Constraint_test_vec = 2 * k + 3 <= 10 ;
toc

Answer 1

[Matt J]

The problem-based framework is not built for speed. It's built to make setting up small problems easy. So, it's already questionable that you are using it for a problem with 1000 variables. In any case, you have chosen a strange indexing space for your optimvars. It would be better to do,

k = optimvar ( 'k' , [1000,1] , 'LowerBound' , 0 )       ; 

tic;
 Constraint_test =2*k+3<=10
toc %Elapsed time is 0.015064 seconds.

Even better, recognize that your constraint is equivalent to the simple upper bound k(i)<=3.5, and just do

k = optimvar ( 'k' , [1000,1] , 'LowerBound' , 0 ,'UpperBound',3.5)       ; 

[Emmanouil]

Dear Matt,

Thanks for your answer. Of course there are much more efficient ways to generate this specific constraint (also like the vectorized approach I presented alongside). However, my intention was to demonstrate the speed limitations of generating constraints via a loop. What I can keep from your answer is that problem-based framework is appropriate for small problems (when looping is needed). This was not obvious to me from the relative MATLAB documentation.

[Matt J]

What I can keep from your answer is that problem-based framework is appropriate for small problems (when looping is needed).

Well, that and also named indexing is measurably slower than numeric indexing. Compare:

tic;
k = optimvar ( 'k' , [1000,1] , 'LowerBound' , 0 )       ; 
Constraint_test=optimconstr(1000);
toc; %Elapsed time is 0.002234 seconds.

tic;
for i=1:1000
 Constraint_test(i) =2*k(i)+3<=10;
end
toc %Elapsed time is 4.043479 seconds.

I = "i" + (1:1000)' ;

tic
k = optimvar ( 'k' , I, 'LowerBound' , 0 )       ; 
Constraint_test = optimconstr ( I ) ;
toc; %Elapsed time is 0.038034 seconds.

tic;
for i = 1 : length(I)
    Constraint_test(i) = 2 * k(i) + 3 <= 10 ;
end
toc %Elapsed time is 5.774542 seconds.

[Emmanouil]

Indeed! Thanks.

[Unai Aldasoro Marcellan]

Which would be the suggested alternative to problem-based framework for large scale problems in Matlab?

[Matt J]

@Unai Aldasoro Marcellan You would choose a solver appropriate to the form of your problem, see

https://www.mathworks.com/help/optim/ug/problems-handled-by-optimization-toolbox-functions.html

and call it directly.

[Alan Weiss]

Large scale problems can indeed be solved efficiently in the problem-based approach. See, for example, Plan Nuclear Fuel Disposal Using Multiobjective Optimization. I would not want to try to set up that problem using the solver-based approach.

There are several suggestions in the documentation for setting up problems efficiently. In particular, see Improve Problem-Based Organization and Performance. And using vectorized calls for creating objective and constraints is usually the most efficient, though the recent static analysis capabilities often do very well.

Alan Weiss

MATLAB mathematical toolbox documentation