### 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

#### Keywords

large scale convex quadratic problems, interior point methods, Sherman-Morrison formula, social accounting matrices

DOI: http://dx.doi.org/10.21914/anziamj.v56i0.7574

**Remember,**for most actions you have to record/upload into this online system

**and then**inform the editor/author via clicking on an email icon or Completion button.

ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.