×

zbMATH — the first resource for mathematics

A primal-dual regularized interior-point method for convex quadratic programs. (English) Zbl 1279.90193
Summary: Interior-point methods in augmented form for linear and convex quadratic programming require the solution of a sequence of symmetric indefinite linear systems which are used to derive search directions. Safeguards are typically required in order to handle free variables or rank-deficient Jacobians. We propose a consistent framework and accompanying theoretical justification for regularizing these linear systems. Our approach can be interpreted as a simultaneous proximal-point regularization of the primal and dual problems. The regularization is termed exact to emphasize that, although the problems are regularized, the algorithm recovers a solution of the original problem, for appropriate values of the regularization parameters.

MSC:
90C51 Interior-point methods
90C20 Quadratic programming
90C05 Linear programming
90C06 Large-scale problems in mathematical programming
90C25 Convex programming
65F22 Ill-posedness and regularization problems in numerical linear algebra
65F50 Computational methods for sparse matrices
PDF BibTeX XML Cite
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, 275-302, (1999) · Zbl 0957.90101
[2] Altman, A., Gondzio, J. Higher order primal dual method (2009). http://www.maths.ed.ac.uk/ gondzio/software/hopdm.html · Zbl 0775.90285
[3] Anjos, M.F.; Burer, S., On handling free variables in interior-point methods for conic linear optimization, SIAM J. Optim., 18, 1310-1325, (2007) · Zbl 1165.90682
[4] Armand, P., Benoist, J.: Uniform boundedness of the inverse of a jacobian matrix arising in regularized interior-point methods. Math. Program. (2011). doi:10.1007/s10107-011-0498-3 · Zbl 1260.49058
[5] Bellavia, S.; Gondzio, J.; Morini, B., Regularization and preconditioning of KKT systems arising in nonnegative least-squares problems, Numer. Linear Algebra Appl., 16, 39-61, (2009) · Zbl 1224.65151
[6] Bunch, J.R.; Parlett, B.N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8, 639-655, (1971)
[7] Castro, J., Cuesta, J.: Quadratic regularizations in an interior-point method for primal block-angular problems. Math. Programm., 1-31 (2010). doi:10.1007/s10107-010-0341-2 · Zbl 1176.90457
[8] Czyzyk, J., Mehrotra, S., Wagner, M., Wright, S.J.. PCx user guide version 1.1. Technical Report OTC 96/01, Optimization Technology Center, Evanston (1996). http://www.mcs.anl.gov/OTC/Tools/PCx
[9] Fletcher R.: Practical Methods of Optimization, 2nd edn. Wiley, Chichester (1987) · Zbl 0905.65002
[10] Friedlander, M.P.; Leyffer, S., Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs, SIAM J. Sci. Comput., 30, 1706-1729, (2008) · Zbl 1179.65065
[11] Friedlander, M.P.; Tseng, P., Exact regularization of convex programs, SIAM J. Optim., 18, 1326-1350, (2007) · Zbl 1176.90457
[12] Gertz, E.M.; Wright, S.J., Object-oriented software for quadratic programming, ACM Trans. Math. Softw., 29, 58-81, (2003) · Zbl 1068.90586
[13] Gill, P.E., Murray, W., Ponceleón, D.B., Saunders, M.A.: Solving reduced KKT systems in barrier methods for linear and quadratic programming. Technical Report SOL 91-7, Systems Optimization Laboratory, Stanford University, Stanford (1991) · Zbl 0795.90041
[14] Gill, P.E.; Saunders, M.A.; Shinnerl, J.R., On the stability of Cholesky factorization for symmetric quasidefinite systems, SIAM J. Matrix Anal. Appl., 17, 35-46, (1996) · Zbl 0878.49020
[15] Gondzio, J.: Matrix-free interior point method. Comput. Optim. Appl., 1-24 (2011). doi:10.1007/s10589-010-9361-3 · Zbl 0904.90117
[16] Gould, N.I.M.; Orban, D.; Toint, P.L., Cuter and sifdec, a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Softw., 29, 373-394, (2003) · Zbl 1068.90526
[17] Harwell Subroutine Library: A collection of Fortran codes for large-scale scientific computation. AERE Harwell Laboratory (2000). http://www.numerical.rl.ac.uk/hsl · Zbl 0878.49020
[18] Karypis, G.; Kumar, V., Multilevel \(k\)-way partitioning scheme for irregular graphs, J. Parallel Distrib. Comput., 48, 96-129, (1998)
[19] Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20, 359-392, (1999) · Zbl 0915.68129
[20] Kojima, M.; Megiddo, N.; Mizuno, S., A primal-dual infeasible-interior-point algorithm for linear programming, Math. Program., 61, 263-280, (1993) · Zbl 0808.90093
[21] Mangasarian, O.L.; Meyer, R.R., Nonlinear perturbation of linear programs, SIAM J. Control Optim., 17, 745-752, (1979) · Zbl 0432.90047
[22] Maros, I., Mészáros, C.: A repository of convex quadratic programming problems. Optim. Methods Softw. 11, 12, 671-681 (1999) (Special Issue on Interior Point Methods) · Zbl 0973.90520
[23] Mehrotra, S., On the implementation of a primal-dual interior-point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[24] Mészáros, C., On free variables in interior point methods, Optim. Methods Softw., 9, 121-139, (1998) · Zbl 0904.90117
[25] Mittelmann, H.: http://plato.la.asu.edu/ftp/ampl_files/qpdataampl (2006) · Zbl 1176.90457
[26] Netlib. http://netlib.org/lp (2011)
[27] Ng, E.G., Peyton, B.W.: Block sparse cholesky algorithms on advanced uniprocessor computers. SIAM J. Sci. Comput. 14(5), 1034-1056 (1993). doi:10.1137/0914063. http://link.aip.org/link/?SCE/14/1034/1 · Zbl 0785.65015
[28] Oliveira, A.R.L.; Sorensen, D.C., A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Linear Algebra Appl., 394, 1-24, (2005) · Zbl 1071.65088
[29] Orban, D.: NLPy—a large-scale optimization toolkit in Python. Technical Report Cahier du GERAD G-2010-xx, GERAD, Montréal (2010). http://nlpy.sourceforge.net/. · Zbl 1224.65151
[30] Rockafellar, R.T., The multiplier method of hestenes and powell applied to convex programming, J. Optim. Theory Appl., 12, 555-562, (1973) · Zbl 0254.90045
[31] Rockafellar, R.T., Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 97-116, (1976) · Zbl 0402.90076
[32] Rusten, T., Winther, R.: A preconditioned iterative method for saddlepoint problems. SIAM J. Matrix Anal. Appl. 13(3), 887-904 (1992). doi:10.1137/0613054. http://link.aip.org/link/?SML/13/887/1 · Zbl 0760.65033
[33] Saunders, M.A., Solution of sparse rectangular systems using LSQR and CRAIG, BIT, 35, 588-604, (1995) · Zbl 0844.65029
[34] Saunders, M.A.; Adams, L. (ed.); Nazareth, J.L. (ed.), Cholesky-based methods for sparse least squares: the benefits of regularization, 92-100, (1996), Philadelphia · Zbl 0865.65022
[35] Saunders, M.A.: PDCO: Primal-dual interior method for convex objectives (2010). http://www.stanford.edu/group/SOL/software/pdco.html
[36] Saunders, M.A., Tomlin, J.A.: Solving regularized linear programs using barrier methods and KKT systems. SOL Report 96-4, Dept. of EESOR, Stanford University (1996) · Zbl 0432.90047
[37] Setiono, R., Interior proximal point algorithm for linear programs, J. Optim. Theory Appl., 74, 425-444, (1992) · Zbl 0795.90041
[38] Setiono, R., Interior dual proximal point algorithm for linear programs, Eur. J. Oper. Res., 77, 96-110, (1994) · Zbl 0810.90092
[39] Silvester, D., Wathen, A.: Fast iterative solution of stabilised Stokes systems part II: using general block preconditioners. SIAM J. Numer. Anal. 31(5), 1352-1367 (1994). doi:10.1137/0731070. http://link.aip.org/link/?SNA/31/1352/1
[40] Vanderbei, R.J., Interior-point methods: algorithms and formulations., ORSA J. Comput, 6, 32-34, (1994) · Zbl 0800.90697
[41] Vanderbei, R.J., Symmetric quasi-definite matrices, SIAM J. Optim., 5, 100-113, (1995) · Zbl 0822.65017
[42] Wright, S.J., Implementing proximal point methods for linear programming, J. Optim. Theory Appl., 65, 531-554, (1990) · Zbl 0676.90042
[43] Wright S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.