Why is the 'active-set' algorithm being removed from LSQLIN when the alternative 'interior-point' algorithm lacks the same performance?
6 views (last 30 days)
I'm providing an example of a problem that is typical in our use of LSQLIN. We solve a physics based problem where all the constraints are required to ensure a physically real solution. Solving problems like this are at the core of a much larger problem, where LSQLIN is called ~10,000 times per problem. As the LSQLIN ‘interior_point’ algorithm doubles computational time, the removal of ‘active-set’ makes our data processing speed slow down significantly. I understand that 'active-set' may not be available in the future. Does Mathworks plan on addressing what seems to be a downgrade of the LSQLIN to an inferior state? Will ‘interior-point’ ever offer the same performance as ‘active-set’?
Variables C, d, A and b can be loaded from the attached MAT-file. C: is full and 45x6 d: 45x1 A: 9x6 each row has 3 non-zero values. b: 9x1 zeros array
tic; x1 = lsqlin(C, d, A, b, , , , , , optimoptions(@lsqlin,'Algorithm', 'active-set','Display','off')); toc
tic; x2 = lsqlin(C, d, A, b, , , , , , optimoptions(@lsqlin,'Algorithm', 'interior-point','Display','off')); toc
Elapsed time is 0.002902 seconds.
Elapsed time is 0.006580 seconds.
Sailesh Sidhwani on 27 Jul 2017
'interior-point' handles large, sparse problems, as well as small dense problems. The algorithm satisfies bounds at all iterations, and can recover from NaN or Inf results. It is a large-scale algorithm. The algorithm can use special techniques for large-scale problems.
'active-set' can take large steps, which adds speed. The algorithm is effective on some problems with nonsmooth constraints. It is not a large-scale algorithm.
Large Scale vs Medium Scale Algorithms:
An optimization algorithm is large scale when it uses linear algebra that does not need to store, nor operate on, full matrices. This may be done internally by storing sparse matrices, and by using sparse linear algebra for computations whenever possible. Furthermore, the internal algorithms either preserve sparsity, such as a sparse Cholesky decomposition, or do not generate matrices, such as a conjugate gradient method.
In contrast, medium-scale methods internally create full matrices and use dense linear algebra. If a problem is sufficiently large, full matrices take up a significant amount of memory, and the dense linear algebra may require a long time to execute.
Please refer to the "Reasoning Behind the Recommendations" section on the link below:
C.T. Kelley on 23 Jan 2018
This is a problem for me. I have an ill-conditioned problem and the active set method does not use the normal equations as part of the KKT system. That is a big deal for me.
Is there a public-domain implementation of the Golub-Saunders 1969 algorithm in Matlab out there?