Parallel interior-point solver for structured quadratic programs: Application to financial planning problems |
| |
Authors: | Jacek Gondzio Andreas Grothey |
| |
Institution: | (1) School of Mathematics, University of Edinburgh, Edinburgh, EH9 3JZ, United Kingdom |
| |
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.
Supported by the Engineering and Physical Sciences Research Council of UK, EPSRC grant GR/R99683/01 |
| |
Keywords: | Structure exploitation Stochastic programming Portfolio optimization Interior point methods |
本文献已被 SpringerLink 等数据库收录! |