×

Interior-point solver for large-scale quadratic programming problems with bound constraints. (English) Zbl 1139.90021

Summary: In this paper, we present an interior-point algorithm for large and sparse convex quadratic programming problems with bound constraints. The algorithm is based on the potential reduction method and the use of iterative techniques to solve the linear system arising at each iteration. The global convergence properties of the potential reduction method are reassessed in order to take into account the inexact solution of the inner system. We describe the iterative solver, based on the conjugate gradient method with a limited-memory incomplete Cholesky factorization as preconditioner. Furthermore, we discuss some adaptive strategies for the fill-in and accuracy requirements that we use in solving the linear systems in order to avoid unnecessary inner iterations when the iterates are far from the solution. Finally, we present the results of numerical experiments carried out to verify the effectiveness of the proposed strategies. We consider randomly generated sparse problems without a special structure. Also, we compare the proposed algorithm with the MOSEK solver.

MSC:

90C20 Quadratic programming
90C51 Interior-point methods

Software:

BLAS; KNITRO; TRON; Mosek; OOPS; CG+; LOQO; ESSL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] BYRD, R. H., HRIBAR, M. E., and NOCEDAL, J., An Interior-Point Algorithm for Large-Scale Nonlinear Programming, SIAM Journal on Optimization, Vol. 9, No. 4, pp. 877–900, 1999. · Zbl 0957.65057
[2] BYRD, R. H., GILBERT, J. C., and NOCEDAL J., A Trust-Region Method Based on Interior-Point Techniques for Nonlinear Programming, Mathematical Programming, Vol. 89A, No. 1, pp. 149–185, 2000. · Zbl 1033.90152
[3] BYRD, R. H., NOCEDAL J., and WALTZ, R. A., Feasible Interior Methods Using Slacks for Nonlinear Optimization, Computational Optimization and Applications, Vol. 26, No. 1, pp. 35–61, 2003. · Zbl 1053.90119
[4] D’APUZZO, M., and MARINO, M., Parallel Computational Issues of an Interior-Point Method for Solving Large Bound-Constrained Quadratic Programming Problems, Parallel Computing, Vol. 29, No. 4, pp. 467–483, 2003.
[5] GONDZIO, J., and SARKISSIAN, R., Parallel Interior-Point Solver for Structured Linear Programs. Mathematical Programming, Vol. 96, No. 3, pp. 561–584, 2003. · Zbl 1023.90039
[6] PARDALOS, P. M., and RESENDE, M. G. C., Interior-Point Methods for Global Optimization, Interior-Point Methods in Mathematical Programming, Edited by T. Terlaky. Kluwer Academic Publishers, Dordrecht, Netherlands, pp. 467–500, 1996. · Zbl 0874.90172
[7] SHANNO, D. F., and VANDERBEI, R. J., An Interior-Point Algorithm for Nonconvex Nonlinear Programming, Computational Optimization and Applications, Vol. 13, No. 1–3, pp. 231–252, 1999. · Zbl 1040.90564
[8] SHANNO, D. F., and VANDERBEI, R. J., Interior-Point Methods for Nonconvex Nonlinear Programming: Orderings and Higher-Order Methods, Mathematical Programming, Vol. 87, No. 2, pp. 303–316, 2000. · Zbl 1054.90091
[9] BENSON, H. Y., SHANNO, D. F., and Vanderbei, R. J., Interior-Point Methods for Nonconvex Nonlinear Programming: Jamming and Numerical Testing, Mathematical Programming, Vol. 99, No. 6, pp. 35–48, 2004. · Zbl 1055.90068
[10] MORALES, J. L., and NOCEDAL, J., Assessing the Potential of Interior Methods for Nonlinear Optimization, Large-Scale PDE-Constrained Optimization, Edited by L. T. Biegler et al., Springer Verlag, Berlin, Germany, Vol. 30, pp. 167–183, 2003. · Zbl 1062.65063
[11] ANDERSEN, E. D., and ANDERSEN, K. D., The MOSEK Interior-Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm, High Performance Optimization, Edited by H. Frenk, K. Roos, T. Terlaky, and S. Zhang, Kluwer Academic Publishers, Dordrecht, Netherlands, pp. 197–232, 2000. · Zbl 1028.90022
[12] VANDERBEI, R. J., LOQO: An Interior-Point Code for Quadratic Programming, Optimization Methods and Software, Vol. 12, No. 5, pp. 451–484, 1999. · Zbl 0973.90518
[13] WRIGHT, M. H., III-Conditioning and Computational Error in Interior Methods for Nonlinear Programming, SIAM Journal on Optimization, Vol. 9, No. 1, pp. 84–111, 1998. · Zbl 0957.65056
[14] O’LEARY, D. P., Symbiosis between Linear Algebra and Optimization, Journal of Computational and Applied Mathematics, Vol. 123, Nos. 1–2, pp. 447–465. 2000. · Zbl 0964.65069
[15] WALTZ, R. A., and NOCEDAL, J., KNITRO User’s Manual, Report 2003/05, Optimization Technology Center, Northwestern University, Evanston, Illinois, 2003.
[16] WANG, W., and O’LEARY, D. P., Adaptive Use of Iterative Methods in Predictor-Corrector Interior-Point Methods for Linear Programming, Numerical Algorithms, Vol. 25, Nos. 1–4, pp. 387–406, 2000. · Zbl 0977.65054
[17] SAAD, Y., Iterative Methods for Sparse Linear Systems, 2nd Edition, SIAM, Philadelphia, Pennsylvania, 2003. · Zbl 1031.65046
[18] LIN, C. J., and MORÉ, J. J., Incomplete Cholesky Factorizations with Limited Memory, SIAM Journal on Statistical and Scientific Computing, Vol. 21, No. 1, pp. 24–45, 1999. · Zbl 0941.65033
[19] BERGAMASCHI, L., GONDZIO, J., and ZILLI, G., Preconditioning Indefinite Systems in Interior-Point Methods for Optimization, Computational Optimization and Applications, Vol. 28, No. 2, pp. 149–171, 2004. · Zbl 1056.90137
[20] DURAZZI, C., and RUGGIERO, V., Indefinitely Preconditioned Conjugate Gradient Method for Large Sparse Equality and Inequality Constrained Quadratic Problems, Numerical Linear Algebra with Applications, Vol. 10, No. 8, pp. 673–688, 2003. · Zbl 1071.65512
[21] HRIBAR, M. E., GOULD, N. I. M., and NOCEDAL, J., On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization, SIAM Journal on Statistical and Scientific Computing, Vol. 23, No. 4, pp. 1375–1394, 2001. · Zbl 0999.65050
[22] KELLER, C., GOULD, N. I. M., and WATHEN, A. J., Constraint Preconditioning for Indefinite Linear Systems, SIAM Journal on Matrix Analysis and Applications, Vol. 21, No. 4, pp. 1300–1317, 2000. · Zbl 0960.65052
[23] HAN, C. G., PARDALOS, P. M., and YE, Y., Computational Aspects of an Interior-Point Algorithm for Quadratic Programming Problems with Box Constraints, Large-Scale Numerical Optimization, Edited by T. Coleman and Y. Li, SIAM, Philadelphia, Pennsylvania, pp. 92–112, 1990.
[24] TODD, M. J., and YE, Y., A Centered Projective Algorithm for Linear Programming. Mathematics of Operational Research, Vol. 15, No. 3, pp. 508–529, 1990. · Zbl 0722.90044
[25] YE, Y., An O(n 3 L) Potential Reduction Algorithm for Linear Programming, Mathematical Programming, Vol. 50, No. 2, pp. 239–258, 1991. · Zbl 0734.90057
[26] KOJIMA, M., MIZUNO, S., and YOSHISE, A., An \(O(\sqrt{n}L)\) Iteration Potential Reduction Algorithm for Linear Complementarity Problems, Mathematical Programming, Vol. 50, No. 3, pp. 331–342, 1991. · Zbl 0738.90077
[27] LIN, C. J., and MORÉ, J. J., Newton’s Method for Large Bound-Constrained Optimization Problems, SIAM Journal on Optimization, Vol. 9, No. 4, pp. 1100–1127, 1999. · Zbl 0957.65064
[28] DONGARRA, J. J., DU CROZ, J., DUFF, I. S., and HAMMARLING, S., A Set of Level 3 Basic Linear Algebra Subprograms, ACM Transactions on Mathematical Software, Vol. 16, No. 1, pp. 1–17, 1990. · Zbl 0900.65115
[29] MORÉ, J. J., and TORALDO, G., On the Solution of Large Quadratic Programming Problems with Bound Constraints, SIAM Journal on Optimization, Vol. 1, No. 1, pp. 93–113, 1991. · Zbl 0752.90053
[30] MORÉ, J. J., and TORALDO, G., Algorithms for Bound-Constrained Quadratic Programming Problems, Numerische Mathematik, Vol. 55, No. 4, pp. 377–400, 1989. · Zbl 0675.65061
[31] IMB EDITOR, ESSL for AIX V4. 1: Guide and References, IBM Pubblications, 2003.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.