Summary of the impact

New optimization routines have been commercialised as a product by the Numerical Algorithms Group (NAG). These routines are based on research in the School of Mathematics at the University of Birmingham. NAG has confirmed that their expectation is that they will release this new product, under licence, in Mark 24 of the NAG C Library, to be made available in February 2014. The product is based on the PENNON software code developed by Michal Kocvara (Birmingham) and Michael Stingl (Erlangen). NAG are an international benchmark provider of numerical algorithms and software in mathematics, and as optimization becomes ubiquitous, the novel routines for nonlinear optimization will help NAG attract new customers and bring further benefits to industrial and commercial end users. Inclusion in the NAG Library will mean that this product is actively marketed to the company's worldwide client base which includes many major corporations in the finance sector and engineering industries (44% of NAG's £8.2m turnover in 2012/2013 was outside of the UK).

Underpinning research

The underpinning research for this case study has been conducted by Michal Kocvara (Professor of Mathematical Optimisation at Birmingham since January 2007) working with Michael Stingl (Erlangen).

Kocvara and Stingl's research programme has focused on the development of algorithms and software for nonlinear semidefinite and conic quadratic optimization. Over the last decade they have been developing a new algorithm for the solution of problems in linear and nonlinear semidefinite optimization, which was the first of its kind.

Based on this algorithm, Kocvara and Stingl have further developed a software package, PENNON (PENalty method for NONlinear and semidefinite programming). Currently, this is the only software available for nonlinear semidefinite optimization.

The particular aspects of this research programme carried out by Prof Kocvara following his appointment to Birmingham include the development of the general nonlinear algorithm and code PENNON. Recently, Kocvara and Fiala (NAG) have developed and released a free open source version of the code named PENLAB.PENNON is based on a generalized augmented Lagrangian method. Its uniqueness lies in a special penalty/barrier function which allows it to handle generic matrix inequalities side by side with nonlinear constraints. It can be used to solve problems such as linear semidefinite programming problems (SDP) or formulations with bilinear matrix inequalities (BMI) as well as fully nonlinear semidefinite programming problems (NLP-SDP).

Results of independent benchmarks, in the context of problems with linear constraints, demonstrate that the program is competitive to, and often better than, other programs developed by leading world researchers (see http://plato.la.asu.edu/bench.html, Semidefinite Programming and Nonlinear Programming). Moreover, in the context of problems with nonlinear constraints, PENNON is the only existing software available.

Various versions of the code (PENNON, PENSDP, PENBMI, PENNLP) were implemented at Argonne National Laboratories on the NEOS server that includes collection of most effective software for mathematical optimization (see http://neos-server.org). More than 300 licenses of the code have been awarded worldwide.

References to the research

(*) Authors in employment with sponsoring partner

Details of the impact

This research has led to the development of new optimization routines which have been commercialised as a product by the Numerical Algorithms Group (NAG). This product is based on the PENNON software code developed by Kocvara and Stingl. The Chief Technical Officer at NAG has confirmed that they expect to include it under licence in Mark 24 of the NAG C Library, available in February 2014. [source 1] These novel routines for nonlinear optimization will help NAG attract new customers, as well as bringing further benefits to industrial and commercial end users. Inclusion in the NAG Library will mean that this product is actively marketed to the company's worldwide client base which includes many major corporations in the finance sector and engineering industries. The company's annual financial statement demonstrates their international reach with 44% of their £8.2m turnover in 2012/2013 coming from outside of the UK, including 17% from the USA and Canada, 8% from Japan and 19% from Europe and the rest of the world. [source 2]

Market requirements

Semidefinite optimization is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modelled or approximated as semidefinite optimization problems. In automatic control theory, SDP's are used in the context of linear matrix inequalities. SDP is a special case of cone programming. The quickly growing number of applications in many research and industrial areas include robust optimization, control theory, relaxations and approximations to combinatorial optimization problems, optimization of mechanical structures in automotive and aerospace engineering, chemical engineering, image recognition, machine learning, financial engineering, and many others. Many of these problems are intrinsically nonlinear. However, the software currently available is only capable of solving problems with linear constraints. PENNON is the only software that can solve nonlinear problems.

NAG and PENNON

NAG is a well-established not-for-profit company with international reach that provide high quality methods for the solution of mathematical and statistical problems. Its products are widely used by major companies, universities, supercomputing sites and numerous independent software vendors in many parts of the world. The NAG Library is the oldest and best-known product of NAG, and is used by developers to add mathematical and statistical functionality to their applications, or to solve complicated mathematical problems. [source 3]

NAG closely collaborates with Birmingham's Optimization Group led by Kocvara. One of the outcomes of the collaboration will be a set of new routines in the NAG Libraries based on the Pennon optimization package. These routines will further include new algorithms for conic quadratic optimization that will be developed under the supervision of Michal Kocvara with the financial support by NAG. [source 4]

In NAG, work is underway on routines for linear and nonlinear semidefinite programming. This will include routines for dense and sparse scenarios, and can be applied to many problems in operations research and combinatorial optimization. In the next phase, the newly developed optimization library will be extended by routines for nonlinear second-order conic optimization

NAG turned to PENNON for this because of the increasing demand for reliable software for semidefinite and conic quadratic optimization and, based on the popularity and generality of PENNON, they decided to base the new implementation solely on this code. This allowed them to bring a product to market more quickly than would otherwise have been possible.

A further aspect of the impact achieved is the investment in further development made by NAG. This is through funding by NAG of a postdoctoral research fellow at Birmingham supervised by Michal Kocvara for two year who will develop new algorithms and software for this class of problems. NAG has agreed to pay the salary costs for the research fellow over the two years (£73,000) for the two year period. [source 5]

Sources to corroborate the impact

1. Corroboration from Chief Technical Officer, NAG, email dated 9^th October 2013
2. source: Financial Statements The Numerical Algorithms Group Limited for year ended 31/3/13. Company no: 1249803 (downloaded from Companies House)
3. www.nag.co.uk
4. www.nag.co.uk/collaboration-university-birmingham
5. Corroboration from Development Executive, Development and Alumni Office, University of Birmingham, email dated 8/10/2012