Sequential quadratic programming

Sequential quadratic programming

Sequential quadratic programming (SQP) is one of the most popular and robust algorithms for nonlinear continuous optimization. The method is based on solving a series of subproblems designed to minimize 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. A number of packages (including NPSOL, NLPQL, OPSYC, OPTIMA, MATLAB, and SQP) are founded on this approach.

Algorithm basics

Consider a nonlinear programming problem of the form:

:minlimits_{x}; f(x),;; mbox{s.t.}; b(x) ge 0,; c(x) = 0.

The Lagrangian for this problem is

:L(x,lambda,sigma) = f(x) - lambda^Tb(x) - sigma^Tc(x),

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

:minlimits_{d}; f(x_k) + abla f(x_k)^Td + frac{1}{2} d^T abla_{xx}^2 L(x_k,lambda_k,sigma_k) d,;; mbox{s.t.}; b(x_k) + abla b(x_k)^Td ge 0,; c(x_k) + abla c(x_k)^Td = 0.

ee also

* Secant method
* Newton's method

External links

* [http://www.math.mtu.edu/~msgocken/ma5630spring2003/lectures/sqp1/sqp1.pdf Introduction to sequential quadratic programming]
* [http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/continuous/constrained/nonlinearcon/section2_1_1.html Sequential Quadratic Programming]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… …   Wikipedia

  • Nonlinear programming — In mathematics, nonlinear programming (NLP) is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized,… …   Wikipedia

  • SQP — sequential quadratic programming …   Medical dictionary

  • SQP — • sequential quadratic programming …   Dictionary of medical acronyms & abbreviations

  • Mathematical optimization — For other uses, see Optimization (disambiguation). The maximum of a paraboloid (red dot) In mathematics, computational science, or management science, mathematical optimization (alternatively, optimization or mathematical programming) refers to… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… …   Wikipedia

  • Convex optimization — Convex minimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. Given a real vector space X together with a convex, real valued function defined on a convex subset of X, the problem is to find …   Wikipedia

  • optimization — /op teuh meuh zay sheuhn/ 1. the fact of optimizing; making the best of anything. 2. the condition of being optimized. 3. Math. a mathematical technique for finding a maximum or minimum value of a function of several variables subject to a set of …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”