[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Starting-point strategies for an infeasible potential reduction method

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We present two strategies for choosing a “hot” starting-point in the context of an infeasible potential reduction (PR) method for convex quadratic programming. The basic idea of both strategies is to select a preliminary point and to suitably scale it in order to obtain a starting point such that its nonnegative entries are sufficiently bounded away from zero, and the ratio between the duality gap and a suitable measure of the infeasibility is small. One of the two strategies is naturally suggested by the convergence theory of the PR method; the other has been devised to reduce the initial values of the duality gap and the infeasibility measure, with the objective of decreasing the number of PR iterations. Numerical experiments show that the second strategy generally performs better than the first, and both outperform a starting-point strategy based on the affine-scaling step.

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

Access this article

Subscribe and save

Springer+ Basic
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Byrd R., Nocedal J., Waltz R.: KNITRO: an integrated package for nonlinear optimization. In: Di Pillo, G., Roma, M. Large-Scale Nonlinear Optimization, pp. 35–59. Springer, Berlin (2006)

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

    Article  MATH  MathSciNet  Google Scholar 

  3. 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, 165–193 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  4. 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, 355–366 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  5. 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 (2007)

  6. 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, 55–75 (2006)

    Article  MATH  MathSciNet  Google Scholar 

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

  8. Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  9. Gertz E.M., Nocedal J., Sartenaer A.: Starting-point strategy for nonlinear interior methods. Appl. Math. Lett. 17, 945–952 (2004)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

  12. Mehrotra S.: On the implementation of a primal-dual interior point method. SIAM J. Optim. 2, 575–601 (1992)

    Article  MATH  MathSciNet  Google Scholar 

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

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

    Article  MathSciNet  Google Scholar 

  15. Wright S.J.: Primal-dual interior-point methods. SIAM, Philadelphia (1997)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

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. Starting-point strategies for an infeasible potential reduction method. Optim Lett 4, 131–146 (2010). https://doi.org/10.1007/s11590-009-0150-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-009-0150-9

Keywords

Navigation