#
Parallel Interior Point Solver for Structured Quadratic Programs:

Application to Financial Planning Problems

###
Technical Report MS 2003-001

**
J. Gondzio and
A. Grothey
**

**
Abstract
**

Many practical large-scale optimization problems are not only sparse,
but also display some form of block-structure such as primal or dual
block angular structure. Often these structures are nested:
each block of the coarse top level structure is block-structured itself.
Problems with these characteristics appear
frequently in stochastic programming but also in other areas such as
telecommunication network modelling.

We present a linear algebra library tailored for problems with such
structure that is used inside an interior point solver for convex
quadratic programming problems.
Due to its object-oriented design it can be used to exploit virtually
any nested block structure arising in practical problems, eliminating
the need for highly specialised linear algebra modules needing to be
written for every type of problem separately. Through a careful
implementation we achieve almost automatic parallelisation of the
linear algebra.

The efficiency of the approach is illustrated
on several problems arising in the financial planning,
namely in the asset and liability management.
The problems are modelled as multistage decision processes
and by nature lead to nested block-structured problems.
By taking the variance of the random variables into account
the problems become non-separable quadratic programs.
A reformulation of the problem is proposed which reduces density
of matrices involved and by these means significantly
simplifies its solution by an interior point method.
The object-oriented parallel solver achieves high efficiency
by careful exploitation of the block sparsity of these problems.
As a result a problem with over 50 million decision variables
is solved in just over 2 hours on a parallel computer with 16 processors.
The approach is by nature scalable and the parallel implementation
achieves nearly perfect speed-ups on a range of problems.

**
Key words:
**
Quadratic Programming, Financial Planning Problems,
Interior Point Methods, Parallel Computing, Object-Oriented Programming.

**
Text
**

PDF MS03-001.pdf.

**
History:
**

Written: April 16, 2003, revised in December 12, 2003.

Published: *Annals of Operations Research* 152 (2007) No 1, pp. 319-339.

**
Related Software:
**

OOPS
Object-Oriented Parallel Solver.