Overview of the Sequential Quadratic Programming (SQP) method and examples of algorithms and implementations

Overview of the Sequential Quadratic Programming (SQP) method

Sequential Quadratic Programming (SQP) is a numerical algorithm for solving non-linear constrained optimisation problems, where the objective function is optimised while satisfying constraints, by solving the quadratic programming problem (Quadratic Programming, QP) in a sequential manner. The solution is obtained by solving the quadratic programming problem (Quadratic Programming, QP) sequentially.

SQP is characterised by its ‘efficiency’ in that it often converges faster than other methods (e.g. gradient descent and interior point methods) because it finds solutions to constrained problems with high-order accuracy, its ‘versatility’ in that it can be applied to a variety of problems involving non-linear objective functions and constraints, and, in general, its second-order convergence to a local optimum solution. Convergence, which means that the problem has a quadratic convergence to a local optimum solution (if the problem satisfies the appropriate conditions).

The basic idea of SQP is to solve the following non-linear constrained optimisation problem
\[
\min_{x} \ f(x) \quad \text{subject to} \quad g_i(x) \leq 0, \ h_j(x) = 0
\]

– Objective function \( f(x) \): function you want to minimise
– Inequality constraint \( g_i(x) \): function that must satisfy a constraint
– Equality constraints \( h_j(x) \): strictly equal constraints

The steps of the SQP reflecting these are as follows.
1. second-order approximation of the problem around the current solution \( x_k \).
– 2. quadratically approximate the objective function \( f(x) \) (quadratic form).
– Linear approximation of the constraint function.
2. solve the quadratic programming problem (QP) based on this approximation and obtain the solution update quantity \( \Delta x_k \). 3.
3. update the solution: \( x_{k+1} = x_k + \alpha_k \Delta x_k \) (where \( \alpha_k \) is the appropriate step size).
4. repeat this process until convergence.

The mathematical background of the SQP method is that the optimality conditions are expressed using Lagrangian functions,
\[
\mathscr{L}(x, \lambda, \mu) = f(x) + \sum_{i} \lambda_i g_i(x) + \sum_{j} \mu_j h_j(x)
\] Where,
– \( \lambda_i \): the Lagrange multiplier of the inequality constraint \( g_i(x) \)
– \(\mu_j \): Lagrange multiplier of the equality constraint \(h_j(x) \)

The Hesse matrix of the Lagrangian function \( \nabla^2_{xx} \mathscr{L} \) is then used to solve the following quadratic programming problem
\[
\min_{\Delta x} \ \frac{1}{2} \Delta x^\top \nabla^2_{xx} \mathscr{L}(x_k) \Delta x + \nabla f(x_k)^\top \Delta x
\] The constraints are expressed as follows
\[
g_i(x_k) + \nabla g_i(x_k)^\top \Delta x \leq 0, \quad h_j(x_k) + \nabla h_j(x_k)^\top \Delta x = 0
\]

The advantages and disadvantages of SQP are as follows.

• Pros
  • Can handle constrained problems naturally.
  • High-order convergence and high accuracy.
  • Convergence is guaranteed in many cases due to a solid theoretical background.
• Disadvantages
  • High computational cost (especially when Hesse matrix computation or QP solving is required).
  • Can be inefficient for large problems.
  • Easily dependent on how the initial solution \(x_0 \) is chosen.

implementation example

An example of implementing the SQP method in Python is shown below. This example uses method=‘SLSQP’ (Sequential Least Squares Programming) in scipy.optimise.minimise, which is an efficient library implementation of the SQP algorithm.

Example: constrained optimisation problem

Problem set-up:\(\min_{x,y}f(x,y)=x^2+y^2\)

Constraints:

1. Inequality constraint: \(x+y-1\leq 0\)
2. Equality constraint: \(x-y=0\)

Code.

import numpy as np
from scipy.optimize import minimize

# objective function
def objective(x):
    return x[0]**2 + x[1]**2

# Inequality constraint: x + y - 1 <= 0
def constraint1(x):
    return 1 - (x[0] + x[1])

# Equality constraint: x - y = 0
def constraint2(x):
    return x[0] - x[1]

# initial value
x0 = [0.5, 0.5]

# Definition of constraints
constraints = [
    {"type": "ineq", "fun": constraint1},  # inequality constraint
    {"type": "eq", "fun": constraint2}    # equational constraint
]

# Perform optimisation
result = minimize(
    objective, 
    x0, 
    method="SLSQP", 
    constraints=constraints, 
    options={"disp": True}  # Convergence status output
)

# Display of results
print("optimal solution:", result.x)
print("objective function value:", result.fun)

Code description.

1. Objective function: defines the function \(f(x,y)=x^2+y^2\) that you want to minimise.
2. Constraints:
   • Inequality constraint: Define \(x+y-1\leq 0\) as the winding number constraint1.
   • Equality constraint:\(x-y=0\) is defined as function constraint.
3. Initial value (x0):
   • Sets the initial point ⌘(x=[0.5,0.5]\) to start the optimisation.
4. minimize function:
   • Use the SQP algorithm by specifying method=‘SLSQP’.
   • Set the constraints and initial values and run the optimisation.

Execution results.

Optimization terminated successfully.    (Exit mode 0)
            Current function value: 0.5
            Iterations: 2
            Function evaluations: 8
            Gradient evaluations: 2
optimal solution: [0.5 0.5]
objective function value: 0.5

Interpretation.

• Optimal solution:\(x=0.5,y=0.5\) The minimum value of the objective function is achieved while satisfying the constraints.
• Objective function value:\(f(0.5,0.5)=0.5\) This result is consistent with the theoretical optimal solution based on the problem setup.

Next, specific applications are discussed.

Application examples

The SQP method is widely used to efficiently solve constrained non-linear optimisation problems in.

1. robot control.

• Application: robot arm motion planning and path optimisation. The robot reaches the target position while avoiding obstacles and minimising energy consumption.
• Specific examples:
  • Constraints: inequality constraints to avoid obstacles. Range constraints on the robot’s joint angles and speed.
  • Objective function: minimising energy consumption or minimising travel time.
• Example: optimising the task of a robot arm to smoothly grasp an object in 3D space and transport it to a given position.

2. aircraft design

• Application: optimisation of aircraft wing geometry and engine layout. Aerodynamic constraints are taken into account while aiming to minimise flight efficiency and fuel consumption.
• Specific examples:
  • Constraints: physical conditions of the lift and drag coefficients of the wing. Strength conditions of the structure.
  • Objective function: maximisation of the aircraft’s range. Minimising fuel consumption.
• Example: design of optimum wing shape under certain cruise conditions.

3. automotive engineering

• Application: suspension design and kinematic performance optimisation of vehicles. Optimum design for improved crash safety.
• Specific examples
  • Constraints: vehicle body stiffness and weight balance constraints. Design constraints to meet crash test conditions.
  • Objective function: to improve ride comfort while minimising vibration. Maximise energy absorption performance in the event of a crash.
• Example: optimising vehicle stability and cornering performance on highways.

4. chemical engineering

• Application: optimisation of chemical process parameters. Minimisation of production costs and maximisation of product quality.
• Specific examples.
  • Constraints: temperature and pressure operating range constraints. Equilibrium conditions and reaction rate constraints for chemical reactions.
  • Objective function: maximisation of product yield. Minimising reaction times and energy costs.
• Example: optimising the operating conditions of a distillation column in a petroleum refinery plant.

5. machine learning

• Application: hyperparameter optimisation of machine learning models. Consideration of regularisation and fairness using constrained optimisation.
• Specific examples.
  • Constraints: parameter range constraints of the model. Error and bias constraints.
  • Objective functions: maximising accuracy and minimising loss functions.
• Examples: training of fairness-oriented classification models with reduced data bias.

6. economics and finance

• Application: optimisation of asset management portfolios. Minimising risk while maximising company profits.
• Specific examples
  • Constraints: asset-specific investment ratio constraints. Total capital constraints.
  • Objective function: maximisation of investment returns. Minimising risk (diversification).
• Example: construction of a risk-managed portfolio considering a variety of financial assets.

7. medical sector

• Application: dose optimisation in radiotherapy. Design of medical devices.
• Specific examples.
  • Constraints: upper dose limits for healthy tissue. Lower dose limit constraints for cancer cells.
  • Objective function: minimisation of total dose.
• Example: design of optimal radiation patterns for cancer treatment.

8. energy systems

• Application: optimisation of energy supply in power grids. Efficient use of renewable energy sources.
• Specific examples
  • Constraints: demand and supply balance conditions. Output fluctuation constraints for renewable energies.
  • Objective function: minimisation of generation costs. Minimisation of greenhouse gas emissions.
• Example: optimisation of local energy management using photovoltaics and storage batteries.

reference book

The following is a list of reference books related to the Sequential Quadratic Programming (SQP) method.

1. basic reference books
Numerical Optimisation
– Author(s): Jorge Nocedal, Stephen J. Wright
– Publisher: Springer
– Features.
– Provides detailed coverage of the theory and implementation of non-linear optimisation, including SQP methods.
– Provides a rich mathematical background and numerical implementation examples of optimisation algorithms.
– Suitable for beginners and advanced readers.

‘Introduction to Optimisation Methods’

2. applied reference books
Practical Methods of Optimisation
– Author: R. Fletcher
– Publisher: Wiley
– Features.
– Applications of non-linear optimisation methods, with a focus on the SQP method.
– Includes numerical examples and methods of application to real-world problems.

Convex Optimisation.
– Authors: Stephen Boyd, Lieven Vandenberghe
– Publisher: Cambridge University Press
– Features.
– Focuses on convex optimisation theory, but also deals with some aspects of SQP methods.
– A free electronic version is available, with detailed explanations of formulas and concepts.

3. reference books specialising in programming and implementation.
Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes
– Author: Lorenz T. Biegler
– Publisher: SIAM
– Features.
– Explains how to apply SQP methods to real-world problems such as chemical engineering.
– Concrete examples of implementation and numerical experiments.

‘Pyomo — Optimization Modeling in Python’

Introduction to Applied Optimisation
– Author: Urmila Diwekar
– Publisher: Springer
– Features.
– Focuses on applications of non-linear optimisation, including examples of SQP method implementations.
– Many engineering applications are covered.

4. advanced reference book.
‘Nonlinear Programming’
– Author: Dimitri P. Bertsekas
– Publisher: Athena Scientific
– Features.
– Explains the advanced theory of nonlinear optimisation.
– It also details the mathematical properties of the SQP method and convergence theory.

Engineering Optimisation: Theory and Practice
– Author: Singiresu S. Rao
– Publisher: Wiley
– Features.
– Applications of optimisation methods to engineering problems.
– Covers a number of optimisation methods, including SQP methods.

5. open source resources
– ‘Optimisation Methods for Large-Scale Systems’
– Free online lectures and resources (e.g. MIT OpenCourseWare).
– Often include slides and implementation code to learn the basics of SQP methods.