SLSQP

Rosenbrock function generated by Grapher.SLSQP [1-2] is a sequential quadratic programming (SQP) optimization algorithm written by Dieter Kraft in the 1980s. It can be used to solve nonlinear programming problems that minimize a scalar function:

\( f(\mathbf{x}) \)

subject to general equality and inequality constraints:

\( \begin{array}{rl} g_j(\mathbf{x}) = \mathbf{0} & j = 1, \dots ,m_e \end{array} \)

\( \begin{array}{rl} g_j(\mathbf{x}) \ge \mathbf{0} & j = m_e+1, \dots ,m \end{array} \)

and to lower and upper bounds on the variables:

\( \begin{array}{rl} l_i \le x_i \le u_i & i = 1, \dots ,n \end{array} \)

SLSQP was written in Fortran 77, and is included in PyOpt (called using Python wrappers) and NLopt (as an f2c translation of the original source). It is also included as one of the solvers in two of NASA’s trajectory optimization tools (OTIS and Copernicus).

The code is pretty old school and includes numerous obsolescent Fortran features such as arithmetic IF statements, computed and assigned GOTO statements, statement functions, etc. It also includes some non-standard assumptions (implicit saving of variables and initialization to zero).

So, the time is ripe for refactoring SLSQP. Which is what I’ve done. The refactored version includes some new features and bug fixes, including:

  • It is now thread safe. The original version was not thread safe due to the use of saved variables in one of the subroutines.
  • It should now be 100% standard compliant (Fortran 2008).
  • It now has an easy-to-use object-oriented interface. The slsqp_class is used for all interactions with the solver. Methods include initialize(), optimize(), and destroy().
  • It includes updated versions of some of the third-party routines used in the original code (BLAS, LINPACK, and NNLS).
  • It has been translated into free-form source. For this, I used the sample online version of the SPAG Fortran Code Restructuring tool to perform some of the translation, which seemed to work really well. The rest I did manually. Fixed-form source (FORTRAN 77 style) is terrible and needs to die. There’s no reason to be using it 25 years after the introduction of free-form source (yes, I’m talking to you Claus 😀).
  • The documentation strings in the code have been converted to FORD format, allowing for nicely formatted documentation to be auto-generated (which includes MathJax formatted equations to replace the ASCII ones in the original code). It also generates ultra-slick call graphs like the one below.
  • A couple of bug fixes noted elsewhere have been applied (see here and here).

SLSQP call graph generated by FORD.

The original code used a “reverse communication” interface, which was one of the workarounds used in old Fortran code to make up for the fact that there wasn’t really a good way to pass arbitrary data into a library routine. So, the routine returns after called, requests data, and then is called again. For now, I’ve kept the reverse communication interface in the core routines (the user never interacts with them directly, however). Eventually, I may do away with this, since I don’t think it’s particularly useful anymore.

The new code is on GitHub, and is released under a BSD license. There are various additional improvements that could be made, so I’ll continue to tinker with it, but for now it seems to work fine. If anyone else finds the new version useful, I’d be interested to hear about it.

See Also

  1. Dieter Kraft, “A Software Package for Sequential Quadratic Programming”, DFVLR-FB 88-28, 1988.
  2. Dieter Kraft, “Algorithm 733: TOMP–Fortran Modules for Optimal Control Calculations,” ACM Transactions on Mathematical Software, Vol. 20, No. 3, p. 262-281 (1994).
Posted in Algorithms Tagged with: , , ,
3 comments on “SLSQP
  1. Stefano says:

    Wonderful work, as always!

  2. Cyrus Magnin says:

    The sentence “It should now be 100% standard compliment (Fortran 2008)”, in reference to the attributes of SLSQP, should really say “compliant” instead of “compliment”

Leave a Reply

Your email address will not be published. Required fields are marked *

*