Crash start of interior point methods. (English) Zbl 1346.90813
Summary: The starting point used by an interior point algorithm for linear and convex quadratic programming may significantly influence the behaviour of the method. A widely used heuristic to construct such a point consists of dropping variable nonnegativity constraints and computing a solution which minimizes the Euclidean norm of the primal (or dual) point while satisfying the appropriate primal (or dual) equality constraints, followed by shifting the variables so that all their components are positive and bounded away from zero. In this Short Communication a new approach for finding a starting point is proposed. It relies on a few inexact Newton steps performed at the start of the solution process. A formal justification of the new heuristic is given and computational results are presented to demonstrate its advantages in practice. Computational experience with a large collection of small- and medium-size test problems reveals that the new starting point is superior to the old one and saves 20–40% of iterations needed by the primal-dual method. For larger and more difficult problems this translates into remarkable savings in the solution time.
Keywords:
interior point methods; initial point; crash start; linear programming; quadratic programmingSoftware:
IPMReferences:
| [1] | Bellavia, S., Inexact interior point method, Journal of Optimization Theory and Applications, 96, 109-121 (1998) · Zbl 0897.90182 |
| [2] | Bixby, R. E., Implementing the simplex method: The initial basis, ORSA Journal on Computing, 4, 267-284 (1992) · Zbl 0759.90063 |
| [3] | Bocanegra, S.; Campos, F.; Oliveira, A., Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods, Computational Optimization and Applications, 36, 149-164 (2007) · Zbl 1148.90350 |
| [4] | Castro, J., A specialized interior-point algorithm for multicommodity network flows, SIAM Journal on Optimization, 10, 852-877 (2000) · Zbl 0955.90087 |
| [5] | D’Apuzzo, M.; De Simone, V.; di Serafino, D., On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods, Computational Optimization and Applications, 45, 283-310 (2010) · Zbl 1187.90194 |
| [6] | Dembo, R. S.; Eisenstat, S. C.; Steihaug, T., Inexact newton methods, SIAM Journal on Numerical Analysis, 19, 400-408 (1982) · Zbl 0478.65030 |
| [7] | Durazzi, C.; Ruggiero, V., Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems, Numerical Linear Algebra with Applications, 10, 673-688 (2003) · Zbl 1071.65512 |
| [8] | Gill, P. E.; Murray, W.; Ponceleón, D. B.; Saunders, M. A., Preconditioners for indefinite systems arising in optimization, SIAM Journal on Matrix Analysis and Applications, 13, 292-311 (1992) · Zbl 0749.65037 |
| [9] | Gondzio, J., Interior point methods 25 years later, European Journal of Operational Research, 218, 587-601 (2012) · Zbl 1244.90007 |
| [10] | Gondzio, J., Matrix-free interior point method, Computational Optimization and Applications, 51, 457-480 (2012) · Zbl 1241.90179 |
| [11] | Gondzio, J., Convergence analysis of an inexact feasible interior point method for convex quadratic programming, SIAM Journal on Optimization, 23, 1510-1527 (2013) · Zbl 1286.65075 |
| [12] | Gonzaga, C. C., Path-following methods for linear programming, SIAM Review, 34, 167-224 (1992) · Zbl 0763.90063 |
| [13] | Gould, N. I.M.; Reid, J. K., New crash procedures for large-scale systems of linear constraints, Mathematical Programming, 45, 475-501 (1989) · Zbl 0692.90089 |
| [14] | Hall, J. A.J., Towards a practical parallelisation of the simplex method, Computational Management Science, 7, 139-170 (2010) · Zbl 1185.90149 |
| [15] | Lukšan, L.; Vlček, J., Indefinitely preconditioned inexact newton method for large sparse equality constrained nonlinear programming problems, Numerical Linear Algebra with Applications, 5, 219-247 (1998) · Zbl 0937.65066 |
| [16] | Maros, I.; Mitra, G., Startegies for creating advanced bases for large-scale linear programming problems, INFORMS Journal on Computing, 10, 248-260 (1998) · Zbl 1034.90515 |
| [17] | Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM Journal on Optimization, 2, 575-601 (1992) · Zbl 0773.90047 |
| [18] | 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 and its Applications, 394, 1-24 (2005) · Zbl 1071.65088 |
| [19] | Skajaa, A.; Andersen, E.; Ye, Y., Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems, Mathematical Programming Computation, 5, 1-25 (2013) · Zbl 1269.90080 |
| [20] | Wright, S. J., Primal-Dual Interior-Point Methods (1997), SIAM: SIAM Philadelphia · Zbl 0863.65031 |
| [21] | Ye, Y.; Todd, M.; Mizuno, S., An \(o(\sqrt{n} L)\) - iteration homogeneous and self-dual linear programming algorithm, Mathematics of Operations Research, 19, 53-67 (1994) · Zbl 0799.90087 |
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.
