Sequential quadratic programming

From optimization
Revision as of 20:07, 24 May 2015 by Ben Goodman (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Introduction

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:
 min f(x) <br/>
s.t. h(x) = 0 <br/>
and g(x) <= 0
with f(x), h(x), and g(x) each potentially non-linear.

Background

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_new = x_old - 
=SQP Algorithms=
=Convergence Analysis=
=Example=