Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Sequential quadratic programming
Summary
Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization which may be considered a quasi-Newton method. 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.
Consider a nonlinear programming problem of the form:
The Lagrangian for this problem is
where and are Lagrange multipliers.
The standard Newton's Method searches for the solution by iterating the following equation:
However, because the matrix is generally singular (and therefore non-invertible), the Newton step cannot be calculated directly. Instead the basic sequential quadratic programming algorithm defines an appropriate search direction at an iterate , 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 under the operator.
Together, the SQP algorithm starts by first choosing the initial iterate , then calculating and . Then the QP subproblem is built and solved to find the Newton step direction which is used to update the parent problem iterate using . This process is repeated for until the parent problem satisfies a convergence test.
Sequential linear programming
Sequential linear-quadratic programming
Augmented Lagrangian method
SQP methods have been implemented in well known numerical environments such as MATLAB and GNU Octave. There also exist numerous software libraries, including open source:
SciPy (de facto standard for scientific Python) has scipy.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.