Sequential quadratic programming

From optimization
Revision as of 18:13, 25 May 2015 by Ben Goodman (Talk | contribs)

Jump to: navigation, search

Authored by: Ben Goodman (ChE 345 Spring 2016)
Steward: Dajun Yue and Fenqi You



Sequential quadratic programming (SQP) combines two fundamental algorithms for solving non-linear optimization problems: an active set method and Newton’s method. The approach creates quadratic sub-problems using the active set method, and these subproblems reveal the best improvement to be made to a current guess. Newton’s method can then find the solution to this sub-problem in one iteration because it is quadratic. The added efficiency from this dual approach makes SQP appropriate for larger non-linear problems and problems with high non-linearity in the constraints.

The abstracted, general problem below will be used for the remainder of this page to explain and discuss SQP:
 \text{min f(x)}
 \text{s.t. h(x) = 0}
 \text{and g(x)} \le 0

with f(x), h(x), and g(x) each potentially non-linear.


Previous knowledge of the component methods is helpful in understanding sequential quadratic programming. Briefly, the active set method confines the search for optimal solutions to regions where the objective function is increasing significantly with respect to constraint functions. Lagrangian Parameters and KKT conditions provide the framework to find these regions and converge to the optimum solution. Newton’s method is an algorithm for converging to critical values of any function with improvement steps that follow the form below:
x_{k+1} Failed to parse(lexing error): \text{= x_k -}

\frac{\nabla f}{\nabla^2 f}  

Briefly, the idea with this algorithm is to improve a guess in proportion to how quickly the function is changing at the guess and inversely proportional to how the function is accelerating at the guess.

The final concept fundamental to SQP is Taylor Series expansions; the idea that any function can be well represented by an infinite series of polynomial terms. This concept extends to expressing derivatives as a series of polynomial deviations from a given starting point with each term scaled by the analytical derivative evaluated at the starting point. When the deviation is small, one or two terms can be used with adequate accuracy. This concept allows highly non-linear problems to be handled using linear and quadratic methods.

SQP Algorithm

The active set method alone must be performed with only the first order term of the Taylor Series so that the resulting sub-problem is linear. Newton's method in tandem allows the second order term of the Taylor Series to be added, forming a quadratic sub-problem, because Newton's method converges in one iteration for quadratic problems.
As with the active set method alone, the Lagrangian function is used under KKT conditions:
L(x,\lambda,\mu)\text{ = f(x) +}
The KKT conditions form the system of equations below. In the active set method alone, this system is solved directly for values of x and \lambda
In SQP, the system is not solved but rather fed the incumbent guess for x and \lambda, and these computed values then scale the first order improvement parameter p from the Taylor series. Similarly, the second derivative of the Lagrangian function is fed the incumbent guess and scales the second order term for p_x. p_{\lambda} is scaled in the second order term by the derivative of the complementary KKT condition. Thus, the second-order parameters form the gradient (evaluated for each variable) of the first-order parameters. The system to solve is then:

Convergence Analysis