Sequential Quadratic Programming

“Punishment was so severe that crime was very rare. – Lee Kuan Yew”

Summary:

Iteraively determine which inequality constraints are active at the current location and treat them as equality constraints. Establish KKT equations based on the objective function and all the ‘equality’ constraints like in Lagrangian Multiplier method, find and apply the update until convergence.

Intuition:

Treats the active inequality constraints at the current location as equality constraints.

Method:

  1. Choose an initial location, and initialize the active set of constraints based on the likely violations after taking a Naive step in the gradient direction.

  2. Linearize the constraint functions and the objective function at the current iterate. This can be done by approximating the constraint functions and the objective function with a Taylor series expansion.

  3. Solve the quadratic programming (QP) subproblem (using all available gradient-based methods), which is defined by the linearized constraints and objective function. The solution of the QP subproblem is used to compute the search direction for the next iteration.

  4. Perform a line search along the search direction to determine the step length for the next iteration. The line search should ensure that the constraints remain active.

  5. Update the active set to add/remove inequality contraints based on current location, using the same criteria as in step 1.

  6. Repeat steps 2-5 until convergence.

Reference:

Algorithm 5.4 http://flowlab.groups.et.byu.net/mdobook.pdf