Creating optimization constraint with loop is too slow

10 views (last 30 days)
Emmanouil on 30 Jun 2020
Commented: Emmanouil on 30 Jun 2020
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

Matt J on 30 Jun 2020
Edited: Matt J on 30 Jun 2020
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 on 30 Jun 2020
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 on 30 Jun 2020
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 on 30 Jun 2020
Indeed! Thanks.