Skip to main content
SpringerLink
Log in

Stopping criteria for inner iterations in inexact potential reduction methods: a computational study

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

Abstract

We focus on the use of adaptive stopping criteria in iterative methods for KKT systems that arise in Potential Reduction methods for quadratic programming. The aim of these criteria is to relate the accuracy in the solution of the KKT system to the quality of the current iterate, to get computational efficiency. We analyze a stopping criterion deriving from the convergence theory of inexact Potential Reduction methods and investigate the possibility of relaxing it in order to reduce as much as possible the overall computational cost. We also devise computational strategies to face a possible slowdown of convergence when an insufficient accuracy is required.

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

Access this article

Log in via an institution

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

    Google Scholar 

  2. Bellavia, S.: Inexact interior point method. J. Optim. Theory Appl. 96, 109–121 (1998)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  5. Boisvert, R., Pozo, R., Remington, K., Barrett, R., Dongarra, J.: Matrix Market: a web resource for test matrix collections. In: Boisvert, R. (ed.) The Quality of Numerical Software: Assessment and Enhancement, pp. 125–137. Chapman & Hall, London (1997). See also the Matrix Market home page, http://math.nist.gov/MatrixMarket/

    Google Scholar 

  6. Cafieri, S., D’Apuzzo, M., De Simone, V., di Serafino, D.: On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems. Comput. Optim. Appl. (to appear)

  7. Cafieri, S., D’Apuzzo, M., De Simone, V., di Serafino, D., Toraldo, G.: On the convergence of inexact potential reduction algorithms for convex quadratic programming. J. Optim. Theory Appl. 133(2), (2007)

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  10. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Technical Report ANL/MCS-P861-1200, Argonne National Laboratory (2001)

  11. Dollar, H.S.: Extending constraint preconditioners for saddle point problems. Technical Report NA-05/02. Oxford University Computing Laboratory (2005) SIAM J. Matrix Anal. Appl. (submitted)

  12. Dollar, H.S., Gould, N.I.M., Wathen, A.J.: On implicit-factorization constraint preconditioners. Technical Report, RAL-TR-2004-036. Rutherford Appleton Laboratory (2004)

  13. Dollar, H.S., Gould, N.I.M., Schilders, W.H.A., Wathen, A.J.: On iterative methods and implicit-factorization preconditioners for regularized saddle-point systems. Technical Report, RAL-TR-2005-011. Rutherford Appleton Laboratory (2005)

  14. Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Software 9(3), 302–325 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  16. Forsgren, A., Gill, P.E., Griffin, J.D.: Iterative solution of augmented systems arising in interior methods. Technical Report NA-05-03, UCSD Department of Mathematics (2005)

  17. Forsgren, A., Gill, P.E., Wright, M.H.: Interior methods for nonlinear optimization. SIAM Rev. 44(4), 525–597 (2002)

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  20. Haws, J., Mayer, C.: Preconditioning KKT systems. Technical Report M&CT-Tech-01-021, the Boeing Co. (2001)

  21. Ito, S.: Inexact implementation of interior point algorithms for optimal control problems. Lect. Notes Numer. Appl. Anal. 14, 245–248 (1995)

    Google Scholar 

  22. Keller, C., Gould, N., Wathen, A.: Constraint preconditioning for indefinite linear systems. SIAM J. Matrix Anal. Appl. 21(4), 1300–1317 (2000)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  25. Mizuno, S., Kojima, M., Todd, M.J.: Infeasible-interior-point primal–dual potential-reduction algorithms for linear programming. SIAM J. Optim. 5, 52–67 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  26. Pardalos, P.M., Resende, M.G.C.: Interior point methods for global optimization problems. In: Terlaky, T. (ed.) Interior Point Methods of Mathematical Programming, pp. 467–500. Kluwer Academic, Dordrecht (1996)

    Google Scholar 

  27. Pardalos, P.M., Resende, M.G.C. (eds.): Handbook of Applied Optimization. Oxford University Press, Oxford (2002)

    MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  30. Baryamureeba, V., Steihaug, T.: On the convergence of an inexact primal–dual interior point method for linear programming. Reports in Informatics No. 188, Department of Informatics, University of Bergen, Norway (2000)

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

    Google Scholar 

  32. Todd, M.J.: Potential-reduction methods in mathematical programming. Math. Program. 76, 3–45 (1996)

    Article  MathSciNet  Google Scholar 

  33. Todd, M.J., Ye, Y.: A centered projective algorithm for linear programming. Math. Oper. Res. 15, 508–529 (1990)

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Second University of Naples, via Vivaldi 43, I-81100, Caserta, Italy

    S. Cafieri, M. D’Apuzzo, V. De Simone & D. di Serafino

Authors
  1. S. Cafieri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. D’Apuzzo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. V. De Simone
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. D. di Serafino
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Cafieri.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cafieri, S., D’Apuzzo, M., De Simone, V. et al. Stopping criteria for inner iterations in inexact potential reduction methods: a computational study. Comput Optim Appl 36, 165–193 (2007). https://doi.org/10.1007/s10589-006-9007-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-006-9007-7

Keywords

Search

Navigation