An interior point method and Sherman--Morrison formula for solving large scale convex quadratic problems with diagonal Hessians

Abstract

We develop an approach for solving large scale convex quadratic problems with quadratic matrices subject to linear equalities and box-constraints. These problems appear in real-life applications. At first glance, this is a simple convex optimisation problem. However, the size of this problem (\(10^9~\)variables and \(10^6~\)constraints for some applications) makes it very challenging to apply traditional convex optimisation techniques. Therefore, one needs to develop a specific algorithm for solving such kind of problems. We apply a combination of the Interior Point method and Sherman--Morrison formula to solve this problem. We test our approach on smaller size datasets (\(1000~\)variables and \(100~\)constraints). Our numerical experiments show that this combination is efficient, fast and computationally stable. This approach is suitable for large scale convex quadratic optimisation problems. References

• E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen. LAPACK Users' Guide. Society for Industrial and Applied Mathematics, Philadelphia, third edition, 1999.
• M. S. Bartlett. An inverse matrix adjustment arising in discriminant analysis. Ann. Math. Statist., 22(1):107–111, 03 1951. doi:10.1214/aoms/1177729698
• S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, USA, 2010.
• Jack Dongarra, Mathieu Faverge, Hatem Ltaief, and Piotr Luszczek. High performance matrix inversion based on lu factorization for multicore architectures. In Proceedings of the 2011 ACM international workshop on Many task computing on grids and supercomputers, pages 33–42. ACM, 2011.
• G. E. Forsythe, M. A. Malcolm, and C. B. Moler. Computer Methods for Mathematical Computations. Prentice-Hall, Englewood Cliffs, N.J., 1977. Cited in Ake Bjorck's bibliography on least squares, ftp://math.liu.se/pub/references
• Gene H. Golub and Robert J. Plemmons. Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition. Linear Algebra and Its Applications, 34:3–28, 1980. doi:10.1016/0024-3795980)90156-1
• G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 1996.
• Jacek Gondzio and Andreas Grothey. Exploiting structure in parallel implementation of interior point methods for optimization. Technical report, School of Mathematics, University of Edinburgh, Edinburgh, 2004.
• Magnus R. Hestenes. Multiplier and gradient methods. J. Optimization Theory Appl., 4:303–320, 1969. doi:10.1007/BF00927673
• Magnus R. Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Standards, 49:409–436, 1952. http://www.sam.math.ethz.ch/ mhg/Latsis2002/jr49-6.pdf
• Narendra Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373–395, 1984. doi:10.1145/800057.808695
• Seung-Jean Kim, Kwangmoo Koh, Michael Lustig, Stephen Boyd, and Dimitry Gorinevsky. An interior-point method for large-scale L1-regularized least squares. Selected Topics in Signal Processing, IEEE Journal of, 1(4):606–617, 2007. doi:10.1109/JSTSP.2007.910971
• Yurii Nesterov and Arkadii Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming, volume 13 of SIAM Studies in Applied mathematics. 1993.
• J. Nocedal and S. Wright. Numerical Optimization. Springer-Verlag, Inc., New York, 2006.
• M. J. D. Powell. A method for nonlinear constraints in minimization problems. In R. Fletcher, editor, Optimization, pages 283–298. New York, NY, 1969. http://www.ams.org/mathscinet-getitem?mr=42:7284
• Sherman Robinson, Andrea Cattaneo, and Moataz El-Said. Updating and estimating a social accounting matrix using cross entropy methods. TMD discussion papers 58, International Food Policy Research Institute, 2000. http://ideas.repec.org/p/fpr/tmddps/58.html
• Jack Sherman and Winifred J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Statistics, 21:124–127, 1950. doi:10.1214/aoms/1177729893