Sequential quadratic programming

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization. SQP methods are used on mathematical problems for which the objective function and the constraints are twice continuously differentiable.

SQP methods solve a sequence of optimization subproblems, each of which optimizes a quadratic model of the objective subject to a linearization of the constraints. If the problem is unconstrained, then the method reduces to Newton's method for finding a point where the gradient of the objective vanishes. If the problem has only equality constraints, then the method is equivalent to applying Newton's method to the first-order optimality conditions, or Karush–Kuhn–Tucker conditions, of the problem.

Algorithm basics[edit]

Consider a nonlinear programming problem of the form:

The Lagrangian for this problem is[1]

where and are Lagrange multipliers. At an iterate , a basic sequential quadratic programming algorithm defines an appropriate search direction as a solution to the quadratic programming subproblem

Note that the term in the expression above may be left out for the minimization problem, since it is constant.

Alternative approaches[edit]

Implementations[edit]

SQP methods have been implemented such well known numerical environments as MATLAB and GNU Octave. There also exist numerous software libraries, including open source

  • SciPy (de facto standard for scientific Python) has scipy.optimize.minimize(method=’SLSQP’) solver.
  • NLopt (C/C++ implementation, with numerous interfaces including Python, R, MATLAB/Octave), implemented by Dieter Kraft as part of a package for optimal control, and modified by S. G. Johnson.[2][3]
  • LabVIEW
  • KNITRO[4] (C, C++, C#, Java, Python, Fortran)
  • NPSOL (Fortran)
  • SNOPT (Fortran)
  • NLPQL (Fortran)
  • MATLAB

SuanShu (Java)

See also[edit]

Notes[edit]

  1. ^ Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer. ISBN 978-0-387-30303-1.
  2. ^ Kraft, Dieter (Sep 1994). "Algorithm 733: TOMP–Fortran modules for optimal control calculations". Transactions on Mathematical Software. 20 (3): 262–281. CiteSeerX 10.1.1.512.2567. doi:10.1145/192115.192124. Retrieved 1 February 2019.
  3. ^ Kraft, Dieter (July 1988). "A software package for sequential quadratic programming". Technical Report DFVLR-FB 88-28. Oberpfaffenhofen: Institut für Dynamik der Flugsysteme. Retrieved 1 February 2019.
  4. ^ KNITRO User Guide: Algorithms

References[edit]

External links[edit]