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

On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods

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

Abstract

The solution of KKT systems is ubiquitous in optimization methods and often dominates the computation time, especially when large-scale problems are considered. Thus, the effective implementation of such methods is highly dependent on the availability of effective linear algebra algorithms and software, that are able, in turn, to take into account specific needs of optimization. In this paper we discuss the mutual impact of linear algebra and optimization, focusing on interior point methods and on the iterative solution of the KKT system. Three critical issues are addressed: preconditioning, termination control for the inner iterations, and inertia control.

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. Axelsson, O.: Preconditioning of indefinite problems by regularization. SIAM J. Numer. Anal. 16(1), 58–69 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  2. Axelsson, O., Neytcheva, M.: Preconditioning methods for linear systems arising in constrained optimization problems. Numer. Linear Algebra Appl. 10(1), 3–31 (2003)

    Article  MATH  MathSciNet  Google Scholar 

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

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

    Article  MATH  MathSciNet  Google Scholar 

  5. Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 418–477 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  6. Benzi, M., Simoncini, V.: On the eigenvalues of a class of saddle point matrices. Numer. Math. 103(2), 173–196 (2006)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

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

    Article  MATH  MathSciNet  Google Scholar 

  10. Bunch, J.R., Kaufman, L.: Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comput. 31, 163–179 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  11. Bunch, J.R., Parlett, B.N.: Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8(4), 639–655 (1971)

    Article  MathSciNet  Google Scholar 

  12. Byrd, R., Nocedal, J., Waltz, R.: KNITRO: an integrated package for nonlinear optimization. In: Di Pillo, G., Roma, M. (eds.) Large-Scale Nonlinear Optimization. Springer Series in Nonconvex Optimization and Its Applications, vol. 83, pp. 35–59. Springer, New York (2006)

    Chapter  Google Scholar 

  13. 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  MATH  MathSciNet  Google Scholar 

  14. 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. 38(1), 27–45 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  15. Cafieri, S., D’Apuzzo, M., De Simone, V., di Serafino, D.: Stopping criteria for inner iterations in inexact potential reduction methods: a computational study. Comput. Optim. Appl. 36(2–3), 165–193 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  16. Cafieri, S., D’Apuzzo, M., De Simone, V., di Serafino, D., Toraldo, G.: Convergence analysis of an inexact potential reduction method for convex quadratic programming. J. Optim. Theory Appl. 135(3), 355–366 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  17. Cafieri, S., D’Apuzzo, M., De Simone, V., di Serafino, D.: On the use of an approximate constraint preconditioner in a potential reduction algorithm for quadratic programming. In: Cutello, V., Fotia, G., Puccio, L. (eds.) Applied and Industrial Mathematics in Italy II. Series on Advances in Mathematics for Applied Sciences, vol. 75, pp. 220–230. World Scientific, Singapore (2000)

    Google Scholar 

  18. Carpenter, T., Shanno, D.N.: An interior point method for quadratic programs based on conjugate projected gradients. Comput. Optim. Appl. 2(1), 5–28 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  19. Cheng, S., Higham, N.: A modified Cholesky algorithm based on a symmetric indefinite factorization. SIAM J. Matrix Anal. Appl. 20(2), 513–561 (1998)

    Article  MathSciNet  Google Scholar 

  20. Conn, A., Gould, N.I.M., Orban, D., Toint, P.L.: A primal-dual trust-region algorithm for non-convex nonlinear programming. Math. Program. Ser. B 87(2), 215–249 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  21. Dembo, R., Steihaug, T.: Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26(2), 190–212 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  22. Dembo, R., Eisentat, S., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19(3), 400–408 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  23. Dollar, H.S.: Constraint-style preconditioners for regularized saddle-point problems. SIAM J. Matrix Anal. Appl. 29(2), 672–684 (2007)

    Article  MathSciNet  Google Scholar 

  24. Dollar, H.S., Wathen, A.J.: Approximate factorization constraint preconditioners for saddle-point matrices. SIAM J. Sci. Comput. 27(5), 1555–1572 (2006)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  26. Dollar, H.S., Gould, N.I.M., Schilders, W., Wathen, A.J.: Using constraint preconditioners with regularized saddle-point systems. Comput. Optim. Appl. 36(2–3), 249–270 (2007)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

  29. Fletcher, R.: Factorizing symmetric indefinite matrices. Linear Algebra Appl. 14(3), 257–272 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  30. Forsgren, A.: Inertia-controlling factorizations for optimization algorithms. Appl. Numer. Math. 43(1–2), 91–107 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  31. Forsgren, A., Gill, P.E., Murray, W.: On the identification of local minimizers in inertia-controlling methods for quadratic programming. SIAM J. Matrix Anal. Appl. 12(4), 730–746 (1991)

    Article  MATH  MathSciNet  Google Scholar 

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

  33. Forsgren, A., Gill, P.E., Griffin, J.: Iterative solution of augmented systems arising in interior methods. SIAM J. Optim. 18(2), 666–690 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  34. Freund, R.W., Jarre, F.: A QMR-based interior-point algorithm for solving linear programs. AT&T Bell Laboratories and Institute für Angewandte Mathematik und Statistik, Tech. Rep. (1995)

  35. Freund, R., Nachtigal, N.: QMR: a quasi-minimal residual method for non Hermitian linear systems. Numer. Math. 60(3), 315–339 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  36. Freund, R., Nachtigal, N.: Software for simplified Lanczos and QMR algorithms. Appl. Numer. Math. 19(3), 319–341 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  37. Gertz, E.M., Wright, S.J.: Object-oriented software for quadratic programming. ACM Trans. Math. Softw. 29(1), 58–81 (2003). See also http://www.cs.wisc.edu/~swright/ooqp/

    Article  MATH  MathSciNet  Google Scholar 

  38. Gill, P.E., Murray, W., Wright, M.H.: Practical Optimization. Academic, New York (1981)

    MATH  Google Scholar 

  39. 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(2), 183–209 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  40. Gill, P.E., Murray, W., Wright, M.H.: Numerical Linear Algebra and Optimization, vol. I. Addison-Wesley, Reading (1990)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  42. Golub, G.H., Greif, C.: Techniques for solving general KKT systems. SCCM Program, Computer Science Dept., Stanford University, SCCM-00-11 (2000)

  43. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)

    MATH  Google Scholar 

  44. Gondzio, J.: HOPDM. A fast LP solver based on a primal-dual interior point method. Eur. J. Oper. Res. 85, 221–225 (1995)

    Article  MATH  Google Scholar 

  45. Gondzio, J., Grothey, A.: Exploiting structure in parallel implementation of interior point methods for optimization. School of Mathematics, University of Edinburgh, Tech. Rep. MS-04-004 (December 2004), revised in July 2005

  46. Gondzio, J., Grothey, A.: Parallel interior point solver for structured quadratic programs: application to financial planning problems. Ann. Oper. Res. 152(1), 319–339 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  47. Gondzio, J., Hager, W.W., Toraldo, G. (eds.): Special Issue on Linear Algebra Issues Arising in Interior Point Methods. Comput. Optim. Appl. 36(2–3) (2007)

  48. Gould, N.I.M.: On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem. Math. Program. 32(1), 90–99 (1985)

    Article  MATH  Google Scholar 

  49. Gould, N.I.M., Toint, P.L.: SQP methods for large-scale nonlinear programming. In: Powell, M., Scholtes, S. (eds.) System Modelling and Optimization: Methods, Theory and Applications, pp. 149–178. Kluwer, Dordrecht (2000)

    Google Scholar 

  50. Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Solving the trust-region subproblem using the Lanczos methods. SIAM J. Optim. 9(2), 504–525 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  51. 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), 1376–1395 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  52. Gould, N.I.M., Orban, D., Toint, P.L.: Numerical methods for large-scale nonlinear optimization. Acta Numer. 14, 299–361 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  53. Higham, N.J., Cheng, S.: Modifying the inertia of matrices arising in optimization. Linear Algebra Appl. 275–276, 261–279 (1998)

    Article  MathSciNet  Google Scholar 

  54. IMA Conference on Numerical Linear Algebra and Optimisation, University of Birmingham, UK September 13–15, 2007, http://www.ima.org.uk/Conferences/numlinalg/numlinalghome.htm

  55. International Conference on Numerical Optimization and Numerical Linear Algebra, Lhasa, Tibet, China, August 8–12, 2005, http://lsec.cc.ac.cn/~yyx/nlao2005.html

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

    Google Scholar 

  57. Karmakar, N., Ramakrishnan, K.: Computational results of an interior point algorithm for large scale linear programming. Math. Program. 52(1–3), 555–586 (1991)

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  59. Lin, C.-J., Moré, J.J.: Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21(1), 24–45 (1999)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  61. Lukšan, L., Matonoha, C., Vlček, J.: Interior-point method for non-linear non-convex optimization. Numer. Linear Algebra Appl. 11(5–6), 431–453 (2004)

    MATH  MathSciNet  Google Scholar 

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

    MathSciNet  Google Scholar 

  63. Mittelmann, H.D.: Decision tree for optimization software. http://plato.asu.edu/guide.html (2007)

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

    Article  MATH  MathSciNet  Google Scholar 

  65. MOSEK ApS: The MOSEK optimization tools version 3.1 (Revision 28). Users manual and reference (2002). See also http://www.mosek.com/

  66. NEOS Guide: Optimization software. http://www-fp.mcs.anl.gov/OTC/Guide/SoftwareGuide/

  67. Nocedal, J.: On the solution of very large nonlinear optimization problems. Talk at the Eighth SIAM Conference on Optimization, Stockholm, 2005

  68. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operation Research. Springer, Berlin (1999)

    Book  MATH  Google Scholar 

  69. O’Leary, D.: Symbiosis between linear algebra and optimization. J. Comput. Appl. Math. 123(1–2), 447–465 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  70. Oliveira, A., Sorensen, D.: A new class of preconditioners for large-scale linear systems from interior point methods for linear programming. Linear Algebra Appl. 394(1), 1–24 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  71. Optimization Online home page, http://www.optimization-online.org/

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

  73. Portugal, L., Resende, M., Veiga, G., Judice, J.: An efficient implementation of the infeasible primal-dual network flow method. AT & T Bell Laboratories, New Jersey, Tech. Rep. (1994)

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

  75. Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7(3), 856–869 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  76. Schnabel, R.B., Eskow, E.: A revised modified Cholesky factorization algorithm. SIAM J. Optim. 9(4), 1135–1148 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  77. SIAM Conference on Optimization, Minisymposium MS10: Numerical Linear Algebra Issues in Interior Point Methods, Stockholm, May 15–19, 2005, http://www.siam.org/meetings/op05/

  78. Silvester, D., Wathen, A.J.: Fast iterative solution of stabilized stokes systems. Part II: Using general block preconditioners. SIAM J. Numer. Anal. 31(5), 1352–1367 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  79. Simoncini, V., Szyld, D.: Recent computational developments in Krylov subspace methods for linear systems. Numer. Linear Algebra Appl. 14(1), 1–59 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  80. Vanderbei, R.J.: Symmetric quasi-definite matrices. SIAM J. Optim. 5(1), 100–113 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  81. Vanderbei, R.J.: An interior point code for quadratic programming. Optim. Methods Softw. 11–12, 451–484 (1999)

    Article  MathSciNet  Google Scholar 

  82. Vanderbei, R.J., Shanno, D.N.: An interior point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13(1–3), 231–252 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  83. Wächter, A., Biegler, L.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  84. Wright, M.H.: Ill-conditioning and computational error in primal-dual interior methods for nonlinear programming. SIAM J. Optim. 9(1), 84–111 (1998)

    Article  MATH  Google Scholar 

  85. Wright, S.J.: Stability of augmented system factorizations in interior point methods. SIAM J. Matrix Anal. Appl. 18(1), 191–222 (1997)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Second University of Naples, Caserta, Italy

    Marco D’Apuzzo, Valentina De Simone & Daniela di Serafino

Authors
  1. Marco D’Apuzzo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Valentina De Simone
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniela di Serafino
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniela di Serafino.

Rights and permissions

Reprints and permissions

About this article

Cite this article

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). https://doi.org/10.1007/s10589-008-9226-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-008-9226-1

Keywords

Search

Navigation