Sequential Quadratic Programming

Optimization · Axiom Academy

LESSON Sequential Quadratic Programming Newton's Method for Constrained Optimization 1. Newton's Method for Constrained Optimization Consider the constrained optimization problem: The KKT conditions provide necessary conditions for optimality. SQP applies Newton's method to these conditions, treating them as a system of nonlinear equations to solve. At each iteration, we linearize the constraints and form a quadratic model of the Lagrangian around the current point. 2. The QP Subproblem at Each Iteration At iteration k with current point x k , SQP solves the following quadratic program to find search direction d: Here, B k approximates the Hessian of the Lagrangian, capturing curvature information. The linearized constraints ensure the direction respects constraint boundaries. 3. BFGS Approximation of Lagrangian Hessian Computing the true Hessian of the Lagrangian is expensive. Instead, SQP uses BFGS updates to build a quasi-Newton approximation: This update ensures B k remains positive definite and captures curvature information using only first-order derivatives. 4. Merit Functions for Step Acceptance Not every QP solution leads to progress. We use a merit function to decide whether to accept step d k : This l 1 penalty function balances objective improvement with constraint violation. The penalty parameter r must be sufficiently large. A line search finds step size alpha such that x k+1 = x k + alpha d k achieves sufficient decrease in the merit function.

This is the written version of the interactive lesson above. See the full Optimization course.