Skip to main content
SpringerLink
Log in

Primal-dual nonlinear rescaling method with dynamic scaling parameter update

  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper we developed a general primal-dual nonlinear rescaling method with dynamic scaling parameter update (PDNRD) for convex optimization. We proved the global convergence, established 1.5-Q-superlinear rate of convergence under the standard second order optimality conditions. The PDNRD was numerically implemented and tested on a number of nonlinear problems from COPS and CUTE sets. We present numerical results, which strongly corroborate the theory.

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. Auslender, A., Comminetti, R., Haddou M.: Asymptotic analysis of penalty and barrier methods in convex and linear programming. Mathematics of Operations Research 22, 43–62 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  2. Bendsoe, M., Ben-Tal, A., Zowe, J.: Optimization Methods for Truss Geometry and Topology Design. Structural Optimization 7, 141–159 (1994)

    Article  Google Scholar 

  3. Ben-Tal, A., Yuzefovich, I., Zibulevski, M.: Penalty/Barrier Multiplier Method for minimax and constrained smooth convex problems. Research Report 9/92, Optimization Laboratory, Faculty of Industrial Engineering and Management, Technion, 1992

  4. Ben-Tal, A., Zibulevski, M.: Penalty-barrier methods for convex programming problems. SIAM Journal on Optimization, 7, 347–366 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bondarenko, A.S., Bortz, D.M., More J.J.: COPS: Large-scale nonlinearly constrained optimization problems. Mathematics and Computer Science Division, Argonne National Laboratory, Technical Report ANL/MCS-TM-237 (1999)

  6. Bongartz, I., Conn, A.R., Gould, N., Toint, Ph.L.: Constrained and unconstrained testing environment. http://www.cse.clrc.ac.uk/Activity/CUTE+74

  7. Breitfelt, M., Shanno D.: Experience with modified log-barrier method for nonlinear programming. Annals of Operations Research, 62, 439–464 (1996)

    Article  MathSciNet  Google Scholar 

  8. Cominetti, R., Dussault, J.-P.: A stable exponential-penalty algorithm with superlinear convergence. Journal of Optimization Theory and Applications, 83, (1994)

  9. Dussault, J.-P.: Augmented penalty algorithms. I.M.A. Journal on Numerical Analysis, 18, 355–372 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  10. Forsgren, A., Gill, P.: Primal-dual interior methods for nonconvex nonlinear programming. SIAM Journal on Optimization 8, 1132–1152 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  11. Gay, D.M., Overton, M.L., Wright, M.H.: A primal-dual interior method for nonconvex nonlinear programming, A primal-dual interior method for nonconvex nonlinear programming, Advances in Nonlinear Programming. Ed. Y. Yuan, Kluwer Academic Publishers, Dordrecht, pp. 31–56

  12. Gould, N.I.M.: On the accurate determination of search directions for simple differentiable penalty functions. I.M.A. Journal on Numerical Analysis, 6, 357–372 (1986)

    MATH  Google Scholar 

  13. Gould, N.I.M.: On the convergence of a sequential penalty function method for constrained minimization. SIAM Journal on Numerical Analysis, 26, 107–108 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  14. Gould, N.I.M., Orban, D., Sartenaer, A., Toint P.: Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM Journal on Optimization, 11, 974–1002 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  15. Kort, B.W., Bertsekas, D.P.: Multiplier methods for convex programming. Proceedings, IEEE Conference on Decision and Control. San Diego, California, pp. 428–432, 1973

  16. Lustig, I., Marsten, R., Shanno, D.: Computational experience with globally convergent primal-dual predictor-corrector algorithm for linear programming. Mathematical Programming 66, 23–135 (1994)

    Article  MathSciNet  Google Scholar 

  17. Megiddo, N.: Pathways to the optimal set in linear programming. in N. Megiddo, ed., Interior Point and Related Methods, Springer-Verlag, New York, Ch. 8, pp. 131–158, 1989

  18. Mehrotra, S.: On implementation of a primal-dual interior point method. SIAM Journal on Optimization 2, 575–601 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  19. Melman, A., Polyak, R.: The Newton Modified Barrier Method for QP Problems. Annals of Operations Research, 62, 465–519 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  20. Nash, S., Polyak, R., Sofer, A.: A numerical comparison of Barrier and Modified Barrier Method for Large-Scale Bound-Constrained Optimization. in “Large Scale Optimization, state of the art”, Ed. by W. Hager, D. Hearn and P. Pardalos, Kluwer Academic Publisher, pp. 319–338, 1994

  21. Ng, E., Peyton, B.W.: Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM Journal of Scientific Computing, 14, 1034–1056 (1993)

    Article  MATH  Google Scholar 

  22. Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York, 1999

  23. Polyak, B.T.: Iterative methods for optimization problems with equality constraints using Lagrange multipliers. Journal of computational mathematics and mathematical physics, 10, 1098–1106 (1970)

    MATH  Google Scholar 

  24. Polyak, R.: Modified Barrier Functions Theory and Methods. Mathematical Programming 54, 177–222 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  25. Polyak, R., Teboulle, M.: Nonlinear Rescaling and Proximal-like Methods in convex optimization. Mathematical Programming 76, 265–284 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  26. Polyak, R., Griva, I., Sobieski, J.: The Newton Log-Sigmoid method in Constrained Optimization. A Collection of Technical Papers, 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization 3, 2193–2201 (1998)

  27. Polyak, R.: Log-Sigmoid Multipliers Method in Constrained Optimization. Annals of Operations Research 101, 427–460 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  28. Polyak, R.: Nonlinear rescaling vs. smoothing technique in convex optimization. Mathematical Programming 92, 197–235 (2002)

    MATH  MathSciNet  Google Scholar 

  29. Polyak, R., Griva, I.: Primal-Dual Nonlinear Rescaling method for convex optimization. Technical Report 2002-05-01, George Mason University, to appear in JOTA in July 2004, (http://mason.gmu.edu/~rpolyak/papers.html).

  30. Shanno, D., Vanderbei, R.: An interior-point algorithm for nonconvex nonlinear programming. COAP 13, 231–252 (1999)

    MATH  MathSciNet  Google Scholar 

  31. Vanderbei, R.: Symmetric Quasidefinite Matrices. SIAM Journal on Optimization, 5, 100–113 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  32. Wright, S.: Primal-Dual Interior Points methods. SIAM, 1997

  33. Zhang, Y.: Solving Large-Scale Linear Programs by Interior-Point Methods Under MATLAB Environment. Dept. of Computational and Applied Mathmatics, Rice University, Houston, 1996

  34. Zhang, Y., Tapia, R., Dennis, J.: On the superlinear and quadratic convergence at primal-dual interior point linear programming algorithms. SIAM Journal on Optimization 2, 304–324 (1992)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, George Mason University, Fairfax, VA, 22030, USA

    Igor Griva

  2. Department of SEOR and Mathematical Sciences Department, George Mason University, Fairfax, VA, 22030, USA

    Roman A. Polyak

Authors
  1. Igor Griva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roman A. Polyak
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Roman A. Polyak.

Additional information

The research of the authors supported by the NSF Grant CCF-0324999

Rights and permissions

Reprints and permissions

About this article

Cite this article

Griva, I., Polyak, R. Primal-dual nonlinear rescaling method with dynamic scaling parameter update. Math. Program. 106, 237–259 (2006). https://doi.org/10.1007/s10107-005-0603-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-005-0603-6

Keywords

Search

Navigation