### Interior point methods adopted by leading optimization software

**Submitting Institutions**

University of Edinburgh,Heriot-Watt University

**Unit of Assessment**

Mathematical Sciences**Summary Impact Type**

Technological**Research Subject Area(s)**

Mathematical Sciences: Applied Mathematics, Numerical and Computational Mathematics

Information and Computing Sciences: Computation Theory and Mathematics

**Download original**

PDF**Summary of the impact**

Research by Gondzio (Maxwell Institute) on algorithms for large-scale optimization has led to major advances in the design of interior point methods (IPMs). The advances include new ways of exploiting centrality (1996-2008) as well as special preconditioning (2004) and warmstarting (2003, 2008) techniques. These techniques make it possible to solve more difficult optimization problems more quickly. Some of these have been implemented by all major commercial providers of optimization software including IBM, Gurobi, Mosek and FICO. The techniques have therefore had an economic impact on these companies and on thousands of their customers worldwide who now benefit from faster, more reliable methods to solve their challenging optimization tasks.

**Underpinning research**

**Interior point methods.** IPMs are an essential component of the
optimization software used throughout the world. Although they were
initially only applied to solve linear optimization problems, their
potential advantages in other contexts were quickly recognised and they
have been extended to other classes of problems: quadratic, nonlinear,
conic, and semi-definite. IPMs reached maturity in the 1990s and since
then they have been included in all the major commercial optimization
solvers. It is widely accepted that IPMs outperform all earlier
optimization methods on a broad range of complex problems, especially when
instances are very large.

**Multiple centrality correctors**. Since the mid-1990s, Gondzio and
co-workers have been developing new methods for IPMs. A key insight of
their research was the recognition of the role of centrality in the
practical behaviour of IPMs. This led them to design the first successful
practical method exploiting centrality (Gondzio, *Computational
Optimization and Applications*, **6**, 137-156, 1996). The
technique of multiple centrality correctors of Gondzio was refined in
collaboration with Colombo, then a PhD student of Gondzio at the Maxwell
Institute [1]. The method was shown to outperform the standard algorithms
used at the time for solving difficult optimization problems. Special
preconditioners for iterative (Krylov subspace) solvers in IPMs were
subsequently developed by Gondzio in collaboration with Bergamaschi and
Zilli [2]. The use of these preconditioners was shown to be particularly
attractive when solving some difficult quadratic optimization problems.
IPMs owe their success to the way in which they deal with the
complementarity condition *x*_{i}* s*_{j}
= 0 for all *j*. IPMs perturb this condition and replace it with *x*_{i}*
s*_{j} = µ, where the parameter µ is driven to zero.
To avoid guessing the partitioning into active and inactive inequality
constraints, the algorithm forces a systematic reduction of µ. The
partition of vectors *x* and *s* into zero and nonzero
elements is gradually revealed as the algorithm progresses. The theory of
IPMs requires that all complementarity products remain close to µ or at
least display the same magnitude. This feature is commonly known as a good
`centrality' property. However, standard steps in the Newton direction may
destroy the centrality of the iterates. The technique of centrality
correctors remedies this drawback by using a sequence of corrective
actions which re-centre all complementarity products.

**Warmstarting techniques**. Gondzio and Grothey (also Maxwell
Institute) developed new approaches to warmstarting (reoptimization) of
interior point methods [3-4]. These are relevant to numerous situations
when a series of somewhat similar problems needs to be solved. The
warmstarting techniques were demonstrated to be particularly attractive in
the context of portfolio optimization. Taken together, the techniques
developed by Gondzio and collaborators have led to recognised improvements
of IPMs, making them faster and able to solve larger problems.

**Attribution.** The research was led by J. Gondzio at the Maxwell
Institute (MI) from 1998 on. A. Grothey was a PDRA of Gondzio on two EPSRC
projects (starting in 1999) see below) before taking up an academic
position in the MI (from 2005). M. Colombo, was a PhD student of Gondzio
in the MI (graduated in 2007). External collaborators L. Bergamaschi and
G. Zilli are at the University of Padova.

**References to the research**

Those marked with a * best indicate the quality of the research.

[1]* Colombo, M. and Gondzio, J., Further development of multiple
centrality correctors for interior point methods, *Computational
Optimization and Applications*, **41**, 277-305 (2008). http://dx.doi.org/10.1007/s10589-007-9106-0

[2]* Bergamaschi, L., Gondzio, J. and Zilli, G., Preconditioning
indefinite systems in interior point methods for optimization, *Computational
Optimization and Applications*, **28**, 149-171 (2004). http://dx.doi.org/10.1023/B:COAP.0000026882.34332.1b

[3] Gondzio, J. and Grothey, A., Reoptimization with the primal-dual
interior point method, *SIAM Journal on Optimization*, **13**,
842-864 (2003). http://dx.doi.org/10.1137/S1052623401393141

[4]* Gondzio, J. and Grothey, A., A new unblocking technique to warmstart
interior point methods based on sensitivity analysis, *SIAM Journal on
Optimization*, **19**, 1184-1210 (2008). http://dx.doi.org/10.1137/060678129

**Grants**

EPSRC grant GR/M68169, Parallel solutions of structured linear programs with interior point methods, £51K (1999).

EPSRC grant GR/R99683/01, Parallel solution of large scale structured nonlinear programs with interior point methods, £145K (2005).

**Details of the impact**

Linear optimization and quadratic optimization are at the heart of numerous industrial and commercial applications of mathematics. These arise in very different problems and in broad variety of sectors of the economy — finance, energy, telecommunications, transport, manufacturing, to mention but a few. Although many such problems involve some form of nonlinearity, the need to find a compromise between modelling accuracy and ability to solve the resulting optimization problem often necessitates using simplifying assumptions and employing the modelling based on linear and quadratic optimization. As a result, millions of optimization problems are solved every day and the vast majority of them, 90-95%, rely on linear or quadratic optimization models.

The ability to solve such problems efficiently is therefore crucial. In many situations, optimization problems have to be solved in real-time; this is for example the case when optimizing portfolios in high-frequency trading, when optimizing the usage of electricity transmission networks following the changes in energy demand, assigning frequencies to mobile phone communications, scheduling crew for sea or air transport, etc. The corresponding businesses are worth billions of pounds and any improvement in their operations achieved by optimization is of great value to the companies and to society. An indication of the size of the optimization software market is provided by the investment made in recent years by major companies: in 2009, IBM (market capital $220B) acquired ILOG, then owner of Cplex software for $340M (see http://www-03.ibm.com/press/us/en/pressrelease/26403.wss); in 2008 Fair Isaac (FICO, market capital $1.7B) acquired DASH, owner of the software Xpress (see http://www.fico.com/en/Company/News/Pages/01-22-2008.aspx).

Fast optimization solvers that can deliver reliable answers to challenging problems in acceptable time frames are the key to the successes of Cplex, DASH and others. The methods developed by Gondzio, specifically the technique of multiple centrality corrections [1], special preconditioners for KKT systems [2] and warmstarting techniques [3-4] have influenced the design of these modern optimization software. Multiple centrality corrections, in particular, have been implemented in all major commercial optimization solvers: IBM-Cplex, Gurobi, MOSEK, FICO Xpress, and in numerous academic optimization solvers: PCx, BPMPD, HOPDM, OOQP and OOPS [5-9]. Their use contributes to these codes' ability to solve difficult optimization problems. In some cases their use is essential to ensure that a problem can be solved at all. Their importance is reflected in a remark by a senior executive from Gurobi Optimization who stated that `it is not possible to build a competitive interior point code without centrality correctors' [6].

The following optimization solvers, which together dominate the optimization market, use multiple centrality corrections:

- IBM ILOG CPLEX Optimizer [5]

http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ - Gurobi Optimization [6]

http://www.gurobi.com/ - MOSEK [7]

http://www.mosek.com/ - FICO Xpress Optimization Suite [8]

http://www.fico.com/en/Products/DMTools/Pages/FICO-Xpress-Optimization-Suite.aspx - PCx [9]

http://pages.cs.wisc.edu/~swright/PCx/ - OOQP [9]

http://pages.cs.wisc.edu/~swright/ooqp/reference-manual/classGondzioSolver.html

Gondzio's research has therefore had an economic impact on the companies commercialising these solvers, and on their numerous customers across the world.

**Sources to corroborate the impact **

[5] Manager in the Optimization and Mathematical Software Business Analytics and Mathematical Science group of IBM Research USA will confirm that the centrality correctors are used in IBM-Cplex barrier.

[6] Senior executive of Gurobi Optimization will confirm that it is not possible to build a competitive interior point code without centrality correctors.

[7] Senior executive of MOSEK Optimization will confirm that the MOSEK optimization software employs a modified version of the centrality correctors.

[8] Senior software engineer at FICO Xpress will confirm that the underpinning research was useful to developing their software.

[9] Professor at University Wisconsin-Madison will confirm the benefits of using the centrality correctors in research optimization software.