Study of a primal-dual algorithm for equality constrained minimization | Computational Optimization and Applications Skip to main content

Advertisement

Springer Nature Link
Log in

Study of a primal-dual algorithm for equality constrained minimization

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

Abstract

The paper proposes a primal-dual algorithm for solving an equality constrained minimization problem. The algorithm is a Newton-like method applied to a sequence of perturbed optimality systems that follow naturally from the quadratic penalty approach. This work is first motivated by the fact that a primal-dual formulation of the quadratic penalty provides a better framework than the standard primal form. This is highlighted by strong convergence properties proved under standard assumptions. In particular, it is shown that the usual requirement of solving the penalty problem with a precision of the same size as the perturbation parameter, can be replaced by a much less stringent criterion, while guaranteeing the superlinear convergence property. A second motivation is that the method provides an appropriate regularization for degenerate problems with a rank deficient Jacobian of constraints. The numerical experiments clearly bear this out. Another important feature of our algorithm is that the penalty parameter is allowed to vary during the inner iterations, while it is usually kept constant. This alleviates the numerical problem due to ill-conditioning of the quadratic penalty, leading to an improvement of the numerical performances.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

References

  1. Armand, P.: A quasi-Newton penalty barrier method for convex minimization problems. Comput. Optim. Appl. 26(1), 5–34 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  2. Armand, P., Benoist, J., Orban, D.: Dynamic updates of the barrier parameter in primal-dual methods for nonlinear programming. Comput. Optim. Appl. 41(1), 1–25 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  3. Armand, P., Benoist, J., Orban, D.: From global to local convergence of interior methods for nonlinear optimization. Optim. Methods Softw. 28(5), 1051–1080 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  4. Benchakroun, A., Dussault, J.P., Mansouri, A.: A two parameter mixed interior-exterior penalty algorithm. ZOR—Math. Methods Oper. Res. 41(1), 25–55 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  5. Benson, H.Y., Shanno, D.F.: Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts. Comput. Optim. Appl. 40(2), 143–189 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  6. Benson, H.Y., Vanderbei, R.J., Shanno, D.F.: Interior-point methods for nonconvex nonlinear programming: filter methods and merit functions. Comput. Optim. Appl. 23(2), 257–272 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  7. Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Computer Science and Applied Mathematics. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York (1982)

    Google Scholar 

  8. Biegler, L.T.: Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes, MOS-SIAM Series on Optimization, vol. 10. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2010)

    Book  Google Scholar 

  9. Bousquet, E.: Optimisation non linéaire et application au réglage d’un réseau de télescopes. Ph.D. thesis, Université de Limoges, École Doctorale S2i (2009)

  10. Broyden, C.G., Attia, N.F.: A smooth sequential penalty function method for solving nonlinear programming problems. In: System Modelling and Optimization (Copenhagen, 1983). Lecture Notes in Control and Information Sciences, vol. 59, pp. 237–245. Springer, Berlin (1984)

  11. Broyden, C.G., Attia, N.F.: Penalty functions, Newton’s method and quadratic programming. J. Optim. Theory Appl. 58(3), 377–385 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  12. Byrd, R.H., Gilbert, J.C., Nocedal, J.: A trust region method based on interior point techniques for nonlinear programming. Math. Program. 89(1, Ser. A), 149–185 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  13. Byrd, R.H., Marazzi, M., Nocedal, J.: On the convergence of Newton iterations to non-stationary points. Math. Program. 99(1, Ser. A), 127–148 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  14. Byrd, R.H., Nocedal, J., Waltz, R.A.: Feasible interior methods using slacks for nonlinear optimization. Comput. Optim. Appl. 26(1), 35–61 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  15. Byrd, R.H., Nocedal, J., Waltz, R.A.: KNITRO: An integrated package for nonlinear optimization. In: Large-Scale Nonlinear Optimization. Nonconvex Optimization and Its Applications, vol. 83, pp. 35–59. Springer, New York (2006)

  16. Chen, L., Goldfarb, D.: Interior-point \(l_2\)-penalty methods for nonlinear programming with strong global convergence properties. Math. Program. 108(1, Ser. A), 1–36 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  17. Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2000)

    Book  MATH  Google Scholar 

  18. Courant, R.: Variational methods for the solution of problems of equilibrium and vibrations. Bull. Am. Math. Soc. 49, 1–23 (1943)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  20. Debreu, G.: Definite and semidefinite quadratic forms. Econometrica 20, 295–300 (1952)

    Article  MATH  MathSciNet  Google Scholar 

  21. Dennis Jr, J.E., Schnabel, R.B.: Numerical methods for unconstrained optimization and nonlinear equations. Prentice Hall Series in Computational Mathematics. Prentice Hall Inc., Englewood Cliffs (1983)

    Google Scholar 

  22. Dolan, E., Moré, J., Munson, T.: Benchmarking optimization software with COPS 3.0. Tech. rep., Argonne National Laboratory (2004)

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

    Article  MATH  MathSciNet  Google Scholar 

  24. Duff, I.S.: Ma57—a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30, 118–144 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  25. Fiacco, A.V., McCormick, G.P.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. Wiley, New York (1968)

    MATH  Google Scholar 

  26. Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, Chichester (1987)

    MATH  Google Scholar 

  27. Forsgren, A., Gill, P.E.: Primal-dual interior methods for nonconvex nonlinear programming. SIAM J. Optim. 8(4), 1132–1152 (1998)

    Article  MATH  MathSciNet  Google Scholar 

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

  29. Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming, 2nd edn. Brooks/Cole (2002)

  30. Gertz, E.M., Gill, P.E.: A primal-dual trust region algorithm for nonlinear optimization. Math. Program. 100(1, Ser. B), 49–94 (2004)

    MATH  MathSciNet  Google Scholar 

  31. Gill, P.E., Robinson, D.P.: A primal-dual augmented Lagrangian. Comput. Optim. Appl. 51(1), 1–25 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  32. Goldfarb, D., Polyak, R., Scheinberg, K., Yuzefovich, I.: A modified barrier-augmented Lagrangian method for constrained minimization. Comput. Optim. Appl. 14(1), 55–74 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  33. Gould, N., Orban, D., Toint, P.: CUTEr and SifDec: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29(4), 373–394 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  34. Gould, N., Orban, D., Toint, P.: An interior-point \(\ell _1\)-penalty method for nonlinear optimization. Tech. Rep. RAL-TR-2003-022, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England (2003)

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

    Article  MATH  MathSciNet  Google Scholar 

  36. Gould, N.I.M.: On the accurate determination of search directions for simple differentiable penalty functions. IMA J. Numer. Anal. 6(3), 357–372 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  37. Gould, N.I.M.: On the convergence of a sequential penalty function method for constrained minimization. SIAM J. Numer. Anal. 26(1), 107–128 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  38. Griva, I., Shanno, D.F., Vanderbei, R.J., Benson, H.Y.: Global convergence of a primal-dual interior-point method for nonlinear programming. Algorithmic Oper. Res. 3(1), 12–29 (2008)

    MATH  MathSciNet  Google Scholar 

  39. Murray, W.: Analytical expressions for the eigenvalues and eigenvectors of the Hessian matrices of barrier and penalty functions. J. Optim. Theory Appl. 7, 189–196 (1971)

    Article  MATH  Google Scholar 

  40. Nemirovski, A.S., Todd, M.J.: Interior-point methods for optimization. Acta Numer. 17, 191–234 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  41. Nocedal, J., Wright, S.J.: Numerical optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)

    Google Scholar 

  42. Shanno, D.F., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods. Math. Program. 87(2, Ser. B), 303–316 (2000). Studies in algorithmic optimization

  43. Tits, A.L., Wächter, A., Bakhtiari, S., Urban, T.J., Lawrence, C.T.: A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties. SIAM J. Optim. 14(1), 173–199 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  44. Vanderbei, R.J., Shanno, D.F.: An interior-point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13(1–3), 231–252 (1999). Computational optimization–a tribute to Olvi Mangasarian, Part II

  45. Wächter, A., Biegler, L.T.: Failure of global convergence for a class of interior point methods for nonlinear programming. Math. Program. 88(3, Ser. A), 565–574 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  46. Wächter, A., Biegler, L.T.: Line search filter methods for nonlinear programming: local convergence. SIAM J. Optim. 16(1), 32–48 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  47. Wächter, A., Biegler, L.T.: Line search filter methods for nonlinear programming: motivation and global convergence. SIAM J. Optim. 16(1), 1–31 (2005)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  49. Waltz, R.A., Morales, J.L., Nocedal, J., Orban, D.: An interior algorithm for nonlinear optimization that combines line search and trust region steps. Math. Program. 107(3, Ser. A), 391–408 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  50. Wright, M.H.: The interior-point revolution in optimization: history, recent developments, and lasting consequences. Bull. Am. Math. Soc. (N.S.) 42(1), 39–56 (2005)

    Article  MATH  Google Scholar 

  51. Yamashita, H., Yabe, H.: An interior point method with a primal-dual quadratic barrier penalty function for nonlinear optimization. SIAM J. Optim. 14(2), 479–499 (2003)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

We would like to thank Elsa Bousquet [9] for discussions on a primitive version of the algorithm and Michel Bouard for his serious efforts to implement the optimization software SPDOPT. We also thanks the referees for their valuable efforts in reading the paper and their helpful critical comments.

Author information

Authors and Affiliations

  1. Université de Limoges - Laboratoire XLIM, Limoges, France

    Paul Armand, Joël Benoist, Riadh Omheni & Vincent Pateloup

Authors
  1. Paul Armand
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joël Benoist
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Riadh Omheni
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Vincent Pateloup
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paul Armand.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 70 KB)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Armand, P., Benoist, J., Omheni, R. et al. Study of a primal-dual algorithm for equality constrained minimization. Comput Optim Appl 59, 405–433 (2014). https://doi.org/10.1007/s10589-014-9679-3

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-014-9679-3

Keywords

Mathematics Subject Classification

Search

Navigation