×

On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems. (English) Zbl 1171.90548

Summary: Iterative solvers appear to be very promising in the development of efficient software, based on Interior Point methods, for large-scale nonlinear optimization problems. In this paper we focus on the use of preconditioned iterative techniques to solve the KKT system arising at each iteration of a Potential Reduction method for convex Quadratic Programming. We consider the augmented system approach and analyze the behaviour of the Constraint Preconditioner with the Conjugate Gradient algorithm. Comparisons with a direct solution of the augmented system and with MOSEK show the effectiveness of the iterative approach on large-scale sparse problems.

MSC:

90C51 Interior-point methods
65K10 Numerical optimization and variational techniques
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altman, A., Gondzio, J.: Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optim. Methods Softw. 11–12, 275–302 (1999) · Zbl 0957.90101
[2] Andersen, E.D., Gondzio, J., Meszaros, C., Xu, X.: Implementation of interior point methods for large scale linear programming. In: Terlaky T. (ed.) Interior Point Methods in Mathematical Programming, pp. 189–252. Kluwer Academic, Dordrecht (1996) · Zbl 0874.90127
[3] Andersen, E.D., Ye, Y.: A Computational study of the homogeneous algorithm for large-scale convex optimization. Comput. Optim. Appl. 10(3), 243–269 (1998) · Zbl 0914.90212
[4] Axelsson, O.: Preconditioning of indefinite problems by regularization. SIAM J. Numer. Anal. 16, 58–69 (1979) · Zbl 0416.65071
[5] Benson, H.Y., Shanno, D., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: jamming and numerical testing. Math. Program. Ser. A 99, 35–48 (2004) · Zbl 1055.90068
[6] Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numerica 14, 1–137 (2005) · Zbl 1115.65034
[7] Bergamaschi, L., Gondzio, J., Zilli, G.: Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl. 28(2), 149–171 (2004) · Zbl 1056.90137
[8] Byrd, R., Hribar, M.E., Nocedal, J.: An interior point method for large scale nonlinear programming. SIAM J. Optim. 9(4), 877–900 (1999) · Zbl 0957.65057
[9] Cafieri, S., D’Apuzzo, M., Marino, M., Mucherino, A., Toraldo, G.: Interior point solver for large-scale quadratic programming problems with bound constraints. J. Optim. Theory Appl. 129(1), 55–75 (2006) · Zbl 1139.90021
[10] Carpenter, T.J., Shanno, D.F.: An interior point method for quadratic programs based on conjugate projected gradients. Comput. Optim. Appl. 2, 5–28 (1993) · Zbl 0778.90048
[11] Czyzyk, J., Mehrotra, S., Wagner, M., Wright, S.J.: PCx User Guide (version 1.1). Technical report OTC 96/01, Optimization Technology Center, Argonne National Laboratory (1997). See also http://www-fp.mcs.anl.gov/otc/Tools/PCx/
[12] D’Apuzzo, M., Marino, M.: Parallel computational issues of an interior point method for solving large bound constrained quadratic programming problems. Parallel Comput. 29, 467–483 (2003)
[13] Dollar, H., Wathen, A.: Incomplete factorization constraint preconditioners for saddle-point matrices, Research Report NA-04/01. Numerical Analysis Group, Oxford University (2004) · Zbl 1105.65047
[14] Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Softw. 9(3), 302–325 (1983) · Zbl 0515.65022
[15] Durazzi, C., Ruggiero, V.: Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems. Numer. Linear Algebra Appl. 10(8), 673–688 (2003) · Zbl 1071.65512
[16] Durazzi, C., Ruggiero, V., Zanghirati, G.: Parallel interior-point method for linear and quadratic programs with special structure. J. Optim. Theory Appl. 110, 289–313 (2001) · Zbl 1006.90087
[17] Forsgren, A., Gill, P.E., Shinnerl, J.R.: Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization. SIAM J. Matrix Anal. Appl. 17, 187–211 (1996) · Zbl 0878.49021
[18] Freund, R.W., Jarre, F.: A QMR-based interior-point algorithm for solving linear programs. Technical report, AT&T Bell Laboratories and Institute für Angewandte Mathematik und Statistik (1995) · Zbl 0881.90094
[19] Freund, R.M., Mizuno, S.: Interior point methods: current status and future directions. In: Frenk H., et al. (eds.) High Performance Optimization, pp. 441–466. Kluwer Academic, Dordrecht (2000) · Zbl 0955.90149
[20] Gertz, E.M., Wright, S.J.: Object-oriented software for quadratic programming. ACM Trans. Math. Softw. 29, 58–81 (2003). See also http://www.cs.wisc.edu/ swright/ooqp/ · Zbl 1068.90586
[21] Gill, P.E., Murray, W., Ponceleon, B.D., Saunders, M.A.: Preconditioners for indefinite systems arising in optimization. SIAM J. Matrix Anal. Appl. 13, 292–311 (1992) · Zbl 0749.65037
[22] Gill, P.E., Murray, W., Saunders, M.A., Tomlin, J.A., Wright, M.H.: On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method. Math. Program. 36, 183–209 (1986) · Zbl 0624.90062
[23] Golub, G.H., Wathen, A.J.: An iteration for indefinite systems and its application to the Navier–Stokes equations. SIAM J. Sci. Comput. 19, 530–539 (1998) · Zbl 0912.76053
[24] Gondzio, J.: HOPDM (version 2.12)–a fast LP solver based on a primal–dual interior point method. Eur. J. Oper. Res. 85, 221–225 (1995). See also http://www.maths.ed.ac.uk/gondzio/software/hopdm.html · Zbl 0925.90284
[25] Gonzaga, C.C.: Path-following methods for linear programming. SIAM Rev. 34, 167–224 (1992) · Zbl 0763.90063
[26] Gould, N.I.M., Hribar, M.E., Nocedal, J.: On the solution of equality constrained quadratic programming problems arising in optimization. SIAM J. Sci. Comput. 23(4), 1375–1394 (2001) · Zbl 0999.65050
[27] Gould, N.I.M., Orban, D., Toint, P.L.: CUTEr and SifDec: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29(4), 373–394 (2003) · Zbl 1068.90526
[28] Han, C.G., Pardalos, P.M., Ye, Y.: Computational aspects of an interior point algorithm for quadratic programming problems with box constraints. In: Coleman T., Li Y. (eds.) Large-Scale Numerical Optimization. SIAM, Philadelphia (1990) · Zbl 0726.90067
[29] Haws, J., Mayer, C.: Preconditioning KKT systems. Technical report M&CT-Tech-01-021, The Boeing Co. (2001)
[30] Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984) · Zbl 0557.90065
[31] Karmarkar, N., Ramakrishnan, K.: Computational results of an interior point algorithm for large scale linear programming. Math. Program. 52, 555–586 (1991) · Zbl 0739.90042
[32] Keller, C., Gould, N., Wathen, A.: Constraint preconditioning for indefinite linear systems. SIAM J. Matrix Anal. Appl. 21(4), 1300–1317 (2000) · Zbl 0960.65052
[33] Kojima, M., Mizuno, S., Yoshise, A.: An \(O(\sqrt{(}n)L)\) iteration potential reduction algorithm for linear complementarity problems. Math. Program. 50, 331–342 (1991) · Zbl 0738.90077
[34] Lazarov, R.D., Vassilevski, P.S.: Preconditioning saddle-point problems arising from mixed finite element discretizations of elliptic equations. Numer. Linear Algebra Appl. 3(1), 1–20 (1996) · Zbl 0848.65079
[35] Luksan, L., Matonoha, C., Vlcek, J.: Interior-point method for non-linear non-convex optimization. Numer. Linear Algebra Appl. 11, 431–453 (2004) · Zbl 1164.90422
[36] Luksan, L., Vlcek, J.: Indefinitely preconditioned inexact Newton method for large sparse equality constrained nonlinear programming problems. Numer. Linear Algebra Appl. 5, 219–247 (1998) · Zbl 0937.65066
[37] Lustig, J., Marsten, R.E., Shanno, D.F.: On Implementing mehrotra’s predictor corrector interior point method for linear programming. SIAM J. Optim. 2, 435–449 (1992) · Zbl 0771.90066
[38] Lustig, J., Marsten, R.E., Shanno, D.F.: Interior point methods for linear programming: computational state of the art. ORSA J. Comput. 6(1), 1–15 (1994) · Zbl 0798.90100
[39] Mehrotra, S.: Implementations of affine scaling methods: Approximate solutions of systems of linear equations using preconditioned conjugate gradient method. ORSA J. Comput. 4(2), 102–118 (1992) · Zbl 0782.90067
[40] Mehrotra, S., Wang, J.: Conjugate gradient based implementation of interior point methods for network flow problems. In: Adams L., Nazareth L. (eds.) AMS Summer Conference Proceedings, pp. 124–142. SIAM, Philadelphia (1996) · Zbl 0865.65049
[41] Morales, J., Nocedal, J., Waltz, R., Liu, G., Goux, J.: Assessing the potential of interior methods for nonlinear optimization. Technical report OTC 2001/04, Optimization Technology Center (2001) · Zbl 1062.65063
[42] MOSEK ApS: The MOSEK optimization tools version 3.1 (revision 28). Users manual and reference (2002). See also http://www.mosek.com/
[43] Nesterov, Y., Nemirovskii, A.: Interior Point Polynomial Methods in Convex Programming. SIAM Series in Applied Mathematics. SIAM, Philadelphia (1994) · Zbl 0824.90112
[44] Oliveira, A.R., Sorensen, D.C.: Computational experience with a preconditioner for interior point methods for linear programming. Technical report TR97-28, Deptartment of Computational and Applied Mathematics, Rice University, Houston, TX (1997)
[45] Pardalos, P., Wolkowicz, H. (eds.): Topics in Semidefinite and Interior-Point Methods. American Mathematical Society, Providence (1998) · Zbl 0890.00019
[46] Perugia, I., Simoncini, V.: Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations. Numer. Linear Algebra Appl. 7(7/8), 585–616 (2000) · Zbl 1051.65038
[47] Portugal, L., Resende, M., Veiga, G., Judice, J.: An efficient implementation of the infeasible primal–dual network flow method. Technical report, AT&T Bell Laboratories, New Jersey (1994)
[48] Rozloznik, M., Simoncini, V.: Krylov subspace Methods for Saddle Point Problems with Indefinite Preconditioning. SIAM J. Matrix Anal. Appl. 24(2), 368–391 (2002) · Zbl 1021.65016
[49] Tanabe, K.: Centered Newton method for mathematical programming. In: Iri M., Yajima K. (eds.) System Modeling and Optimization: Proceedings of the 13th IFIP Conference. Lecture Notes in Control and Information Systems, vol. 113, pp. 197–206. Springer, New York (1988) · Zbl 0656.90085
[50] Todd, M.J.: Potential-reduction methods in mathematical programming. Math. Program. 76, 3–45 (1996) · Zbl 0881.90097
[51] Todd, M.J., Ye, Y.: A centered projective algorithm for linear programming. Math. Oper. Res. 15, 508–529 (1990) · Zbl 0722.90044
[52] Vanderbei, R.J.: Symmetric quasi-definite matrices. SIAM J. Optim. 5, 100–113 (1995) · Zbl 0822.65017
[53] Vanderbei, R.J.: LOQO User’s Manual (version 3.10). Technical report SOR-97-08, Department of Civil Engineering and Operations Research, Princeton University (1997). See also http://www.orfe.princeton.edu/\(\sim\)loqo/
[54] Waltz, R.A.: KNITRO 4.0 User’s Manual. Ziena Optimization, Evanston (2004). See also http://www.ziena.com/knitro.html
[55] Wright, M.H.: Interior methods for constrained optimization. In: Acta Numerica, vol. 1, pp. 341–407. Cambridge University Press, Cambridge (1992) · Zbl 0766.65053
[56] Wright, M.H.: Ill-conditioning and computational error in primal–dual interior methods for nonlinear programming. SIAM J. Optim. 9, 84–111 (1998) · Zbl 0957.65056
[57] Wright, S.J.: Primal–Dual Interior-Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031
[58] Wright, S.J.: Stability of augmented system factorizations in interior point methods. SIAM J. Matrix Anal. Appl. 18, 191–222 (1997) · Zbl 0878.65041
[59] Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley, New York (1997) · Zbl 0943.90070
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.