MATLAB: Is the lsqlin interior-point algorithm slower in R2017a compared to R2016b

Optimization Toolboxr2016br2017a

Running the lsqlin interior-point algorithm for specific optimization problems is much slower in R2017a than it was in R2016b.
Example:
n=2000;
A(:,1)=(1:n)';
A(:,2)=ones(n,1);
b=rand(2000,1);
tic; x1 = lsqlin(A,b,A,b,[],[],[],[],[],optimoptions(@lsqlin,'Algorithm', 'active-set')); toc 
tic; x2 = lsqlin(A,b,A,b,[],[],[],[],[],optimoptions(@lsqlin,'Algorithm', 'interior-point')); toc
returns 
Elapsed time is 0.021589 seconds.
Elapsed time is 3.926372 seconds. (!)

Best Answer

This is due to changes that were made in "quadprog" for R2017a.
In the R2017a release we introduced a specialized algorithm for problems where the H matrix in quadprog is full. 
Under the hood, the lsqlin function reduces its least squares problem to a quadratic program and calls quadprog. 
For lsqlin, if the C matrix (using doc notation) is full, then our new algorithm will be used. If the C matrix is sparse, the old algorithm is used.
In this case, the problem is ill conditioned for interior point methods because there are way too many inequality constraints. 
In fact, this is the reason the new algorithm is much slower. 
For "N" linear constraints, "N^2" zero elements are added to the algorithm's internal formulation. 
For the sparse algorithm, these zeros are not stored; but they are in the full algorithm. 
Converting the "A" matrix to sparse format is the easy workaround:
 
tic; x2 = lsqlin(sparse(A),b,A,b,[],[],[],[],[],struct('Algorithm', 'interior-point')); toc
This will use the old interior point algorithm in R2016b.
By far the best thing to do would be reducing the number of inequality constraints.
 
Related Question