Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Matrix-free interior point method

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods and imposes restrictions on the way the preconditioner is computed. A two-step approach is used to design a preconditioner. First, the Newton equation system is regularized to guarantee better numerical properties and then it is preconditioned. The preconditioner is implicit, that is, its computation requires only matrix-vector multiplications with the original problem data. The method is therefore well-suited to problems in which matrices are not explicitly available and/or are too large to be stored in computer memory. Numerical properties of the approach are studied including the analysis of the conditioning of the regularized system and that of the preconditioned regularized system. The method has been implemented and preliminary computational results for small problems limited to 1 million of variables and 10 million of nonzero elements demonstrate the feasibility of the approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Al-Jeiroudi, G., Gondzio, J.: Convergence analysis of inexact infeasible interior point method for linear optimization. J. Optim. Theory Appl. 141, 231–247 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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)

    Article  MathSciNet  Google Scholar 

  3. Andersen, E.D., Gondzio, J., Mészáros, 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).

    Chapter  Google Scholar 

  4. Bellavia, S.: An inexact interior point method. J. Optim. Theory Appl. 96, 109–121 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  5. Benzi, M., Golub, G., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bergamaschi, L., Gondzio, J., Venturin, M., Zilli, G.: Inexact constraint preconditioners for linear system arising in interior point methods. Comput. Optim. Appl. 36, 137–147 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bergamaschi, L., Gondzio, J., Zilli, G.: Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl. 28, 149–171 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  8. Castro, J., Cuesta, J.: Quadratic regularizations in an interior point method for primal block-angular problems. Math. Program. (2010). Published online 19 February 2010. doi:10.1007/s10107-010-0341-2

  9. Chen, S., Donoho, D., Saunders, M.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20, 33–61 (1998)

    Article  MathSciNet  Google Scholar 

  10. Colombo, M., Gondzio, J.: Further development of multiple centrality correctors for interior point methods. Comput. Optim. Appl. 41, 277–305 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Curtis, F., Nocedal, J., Wächter, A.: A matrix-free algorithm for equality constrained optimization problems with rank-deficient Jacobians. SIAM J. Optim. 20, 1224–1249 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. 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. Comput. Optim. Appl. 45, 283–310 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400–408 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  14. Dikin, I.I.: On the speed of an iterative process. Uprav. Sist. 12, 54–60 (1974)

    Google Scholar 

  15. Dollar, H., Gould, N., Schilders, W., Wathen, A.: Implicit-factorization preconditioning and iterative solvers for regularized saddle-point problems. SIAM J. Matrix Anal. Appl. 28, 170–189 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  16. Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Oxford University Press, New York (1987).

    Google Scholar 

  17. Ferris, M., Munson, T.: Interior point methods for massive support vector machines. SIAM J. Optim. 13, 783–804 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  18. Fletcher, R.: Conjugate gradient methods for indefinite systems. In: Watson, G. (ed.) Numerical Analysis Dundee 1975, pp. 73–89. Springer, Berlin, New York (1976).

    Google Scholar 

  19. Freund, R.W., Jarre, F.: A QMR-based interior-point algorithm for solving linear programs. Math. Program. 76, 183–210 (1997)

    MathSciNet  MATH  Google Scholar 

  20. Friedlander, M.P., Tseng, P.: Exact regularization of convex programs. SIAM J. Optim. 18, 1326–1350 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  21. Gill, P.E., Murray, W., Ponceleón, D.B., Saunders, M.A.: Preconditioners for indefinite systems arising in optimization. SIAM J. Matrix Anal. Appl. 13, 292–311 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  22. Gill, P.E., Saunders, M.A., Shinnerl, J.R.: On the stability of Cholesky factorization for symmetric quasi-definite systems. SIAM J. Matrix Anal. Appl. 17, 35–46 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  23. Gondzio, J., Toraldo, G. (eds.): Linear algebra issues arising in interior point methods. Comput. Optim. Appl. 36, 137–341 (2007). Special issue

    Article  MathSciNet  MATH  Google Scholar 

  24. Gould, N.I.M., Hribar, M.E., Nocedal, J.: On the solution of equality constrained quadratic problems arising in optimization. SIAM J. Sci. Comput. 23, 1375–1394 (2001)

    Article  MathSciNet  Google Scholar 

  25. Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. Frontiers in Applied Mathematics, vol. 16. SIAM, Philadelphia (1995).

    Book  MATH  Google Scholar 

  26. Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior-point algorithm for linear programming. Math. Program. 61, 263–280 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  27. Korzak, J.: Convergence analysis of inexact infeasible-interior-point-algorithm for solving linear programming problems. SIAM J. Optim. 11, 133–148 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  28. Lu, Z., Monteiro, R.D.S., O’Neal, J.W.: An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming. SIAM J. Optim. 17, 287–310 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  29. Lukšan, L., Vlček, J.: Indefinitely preconditioned inexact Newton method for large sparse equality constrained nonlinear programming problems. Numer. Linear Algebra Appl. 5, 219–247 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  30. 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)

    Article  MathSciNet  MATH  Google Scholar 

  31. Paige, C.C., Saunders, M.A.: LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8, 43–71 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  32. Rozlozník, M., Simoncini, V.: Krylov subspace methods for saddle point problems with indefinite preconditioning. SIAM J. Matrix Anal. Appl. 24, 368–391 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  33. Rusten, T., Winther, R.: A preconditioned iterative method for saddle point problems. SIAM J. Matrix Anal. Appl. 13, 887–904 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  34. Saunders, M.A.: Cholesky-based methods for sparse least squares: The benefits of regularization. In: Adams, L., Nazareth, J.L. (eds.) Linear and Nonlinear Conjugate Gradient-Related Methods. pp. 92–100. SIAM, Philadelphia (1996).

    Google Scholar 

  35. Silvester, D., Wathen, A.: Fast iterative solution of stabilised Stokes systems part ii: Using general block preconditioners. SIAM J. Numer. Anal. 31, 1352–1367 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  36. Stewart, G.W.: On scaled projections and pseudoinverses. Linear Algebra Appl. 112, 189–193 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  37. Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics and Maxwell Institute for Mathematical Sciences, The University of Edinburgh, Mayfield Road, Edinburgh, EH9 3JZ, UK

    Jacek Gondzio

Authors
  1. Jacek Gondzio
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jacek Gondzio.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gondzio, J. Matrix-free interior point method. Comput Optim Appl 51, 457–480 (2012). https://doi.org/10.1007/s10589-010-9361-3

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-010-9361-3

Keywords

Search

Navigation