SQP Sequential Quadratic Programming

Sequential Quadratic Programming (SQP) is an optimization algorithm used to solve nonlinear programming problems. It is particularly effective for solving constrained optimization problems where both the objective function and the constraints are nonlinear.

The basic idea behind SQP is to iteratively approximate the nonlinear optimization problem by a series of quadratic programming subproblems. At each iteration, SQP solves a quadratic programming subproblem that approximates the original problem and updates the solution based on the obtained solution.

Let's break down the steps involved in the SQP algorithm:

Initialization:

SQP starts by initializing an initial feasible solution. This can be done by applying heuristics, using previous solutions, or any other method that satisfies the constraints.

Quadratic Programming (QP) Subproblem:

At each iteration, SQP constructs a quadratic programming subproblem by approximating the original problem. The subproblem is defined as follows:

• Objective Function: The objective function of the subproblem is a quadratic approximation of the original objective function, often obtained by using a second-order Taylor series expansion. This approximation is valid in a small neighborhood around the current solution.
• Constraints: The constraints of the subproblem consist of the original constraints, approximated using linear or quadratic models. These models are also based on Taylor series expansions and are valid in the neighborhood around the current solution.The objective function and constraints are formulated as a quadratic programming problem, which is a special case of an optimization problem where the objective function is quadratic and the constraints are linear.

Solving the QP Subproblem:

The quadratic programming subproblem is then solved to obtain the optimal solution. Various optimization algorithms can be used to solve the QP subproblem, such as the interior-point method or active-set method.

Update Solution:

After obtaining the solution to the QP subproblem, SQP updates the current solution based on the obtained solution. This update is typically performed by taking a step towards the optimal solution of the QP subproblem, which improves the objective function value and satisfies the constraints to a certain extent.

Convergence Check:

SQP checks for convergence criteria to determine whether to terminate the algorithm or proceed to the next iteration. Convergence is usually determined by examining the change in the objective function value, the violation of constraints, or the norm of the step taken.

Iteration:

If the convergence criteria are not met, SQP proceeds to the next iteration by repeating steps 2 to 5. The process continues until convergence is achieved or a predefined termination condition is satisfied.

Termination:

SQP terminates when one of the following conditions is met: the convergence criteria are satisfied, a maximum number of iterations is reached, or a specific termination condition specified by the user is triggered.

Overall, the SQP algorithm combines the principles of quadratic programming and sequential optimization to iteratively solve nonlinear programming problems with constraints. By approximating the problem using quadratic models and updating the solution iteratively, SQP aims to find an optimal solution that satisfies the constraints and minimizes (or maximizes) the objective function.