Nonlinear Optimization: A Comparison of Two Competing Approaches
Active-set SQP vs. IPM
Jan Fiala & Benjamin Marteau (Numerical Algorithms Group)
Introduction

Sequential Quadratic Programming

Nonlinear programming is one of the main tools for mathematical modelling practitioners. The applications
span many industries and academic fields such as:

SQP methods try to guess which inequality constraints gk are binding and iteratively refine that guess. Nonbinding constraints can be discarded (have no influence) at the current iteration. The solver then works on thesmaller space (null space) of the remaining constraints.

• finance (portfolio optimization, model calibration)• multiphysics modelling (oil and gas reservoir modelling, meteorology, climate simulations, engineering)

1. Initialization• Build a quadratic model of the problem• Take a first guess of the set of active constraints• statistics (machine learning, data fitting)
Such models can be formulated as

2. Each iteration
minnx∈Rf (x)subject to h(x) = 0g(x) ≥ 0
where the objective f and constraints h and g are sufficiently smooth nonlinear functions. In modern large scale
applications, the number of variables n can be of an order of 104 or higher.
Solvers generally find a local solution (the best in a certain neighbourhood) satisfying the Karush–Kuhn–Tucker(KKT) optimality conditions. Two main competing approaches:• Solves the quadratic model, warm start it by theactive set estimation• Updates xk+1 and the guess of the active constraints• Builds a new quadratic model at xk+1

• Interior Point Method (IPM)
Both approaches play an important part in practice because of the fundamentally different ways of handlingconstraints.
In the rest of the poster, we compare two implementations of these methods in the NAG Library:• Work on the null space of the active constraints⇒ The more active constraints there are, the cheaper
the iterations become.
SQP solvers scale very well to large NLP problems
with a high number of constraints

Demonstration on a few selected problems from the CUTEst test set
Highly constrained problems
Name• active-set Sequential Quadratic Programming (SQP)

SQP properties• Perform lots of inexpensive iterations

No.
No.
SQPIPMvars constrs time (s) time (s)MINC441113 1033
0.28
7.60
READING8 2002 1000
9.78 251.12
NCVXQP6 10000 7500
3.60 613.38
MADSSCHJ 201
398
0.34
5.51

Loosely constrained problems
NameNo.
No.
SQP
IPM
vars constrs time (s) time (s)JIMACK
3549
0542.42 8.12
OSORIO
10201 202 303.00 0.78
TABLE81271
72
3.80
0.04
OBSTCLBL 10000
140.840.50

Recommendation of use

e04vh - nag opt sparse nlp solve (SQP) and e04st - nag opt handle solve ipopt (IPM)

Interior Point Method

The number of the constraints is not the only factor affecting the convergence of the solvers:

Inequality constraints are tricky to handle due to their “combinatorial” nature: either the inequality constraint
gk is binding (is active) or it has no influence (its associated dual variable is 0). This is expressed by the KKT
complementarity condition:µk gk (x) = 0 for each k(1)

IPM (e04st) advantages• Efficient on unconstrained or loosely constrained
problems

SQP (e04vh) advantages• Efficient on highly constrained problems• Can exploit 2nd derivatives

IPM does not tackle (1) directly, it works on its relaxation µk gk (x) = ν with ν > 0.

• Efficient for quadratic problems• Stays feasible with respect to the linear constraints
throughout the optimization

Each iteration• Performs one Newton iteration towards the solutionof the relaxed KKT system• Better use of multi-core architecture• Usually better results on pathological problems• New and simpler interface• Usually requires less function evaluations• Updates the current solution estimate and the relaxation parameter νIPM properties• Perform few computationally expensive iterations• Can capitalize on a good initial point• Rely on efficient underlying linear algebra• Infeasibility detection

IPM solvers scale very well to large NLP problems
with a small number of constraints• Allows warm starting

October 2017

optimization@nag.com

NAG introduces at Mark 26 an interior point method (e04st) complementing
the existing SQP solver (e04vh) for large NLP problems
www.nag.com