IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v69y2018i1d10.1007_s10589-017-9937-2.html
   My bibliography  Save this article

Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points

Author

Listed:
  • E. G. Birgin

    (University of São Paulo)

  • G. Haeser

    (University of São Paulo
    Stanford University)

  • A. Ramos

    (Federal University of Paraná)

Abstract

Augmented Lagrangian methods with convergence to second-order stationary points in which any constraint can be penalized or carried out to the subproblems are considered in this work. The resolution of each subproblem can be done by any numerical algorithm able to return approximate second-order stationary points. The developed global convergence theory is stronger than the ones known for current algorithms with convergence to second-order points in the sense that, besides the flexibility introduced by the general lower-level approach, it includes a loose requirement for the resolution of subproblems. The proposed approach relies on a weak constraint qualification, that allows Lagrange multipliers to be unbounded at the solution. It is also shown that second-order resolution of subproblems increases the chances of finding a feasible point, in the sense that limit points are second-order stationary for the problem of minimizing the squared infeasibility. The applicability of the proposed method is illustrated in numerical examples with ball-constrained subproblems.

Suggested Citation

  • E. G. Birgin & G. Haeser & A. Ramos, 2018. "Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points," Computational Optimization and Applications, Springer, vol. 69(1), pages 51-75, January.
    • Handle: RePEc:spr:coopap:v:69:y:2018:i:1:d:10.1007_s10589-017-9937-2
    DOI: 10.1007/s10589-017-9937-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-017-9937-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-017-9937-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Birgin, E. G. & Martinez, J. M. & Ronconi, D. P., 2005. "Optimizing the packing of cylinders into a rectangular container: A nonlinear approach," European Journal of Operational Research, Elsevier, vol. 160(1), pages 19-33, January.
    2. Ernesto G. Birgin & Emerson V. Castelani & André L. M. Martinez & J. M. Martínez, 2011. "Outer Trust-Region Method for Constrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 150(1), pages 142-155, July.
    3. E. Birgin & J. Martínez & L. Prudente, 2015. "Optimality properties of an Augmented Lagrangian method on infeasible problems," Computational Optimization and Applications, Springer, vol. 60(3), pages 609-631, April.
    4. Emerson Castelani & André Martinez & J. Martínez & B. Svaiter, 2010. "Addressing the greediness phenomenon in Nonlinear Programming by means of Proximal Augmented Lagrangians," Computational Optimization and Applications, Springer, vol. 46(2), pages 229-245, June.
    5. E. G. Birgin & L. F. Bueno & J. M. Martínez, 2016. "Sequential equality-constrained optimization for nonlinear programming," Computational Optimization and Applications, Springer, vol. 65(3), pages 699-721, December.
    6. Francisco Facchinei & Stefano Lucidi, 1998. "Convergence to Second Order Stationary Points in Inequality Constrained Optimization," Mathematics of Operations Research, INFORMS, vol. 23(3), pages 746-766, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Didier Aussel & Anton Svensson, 2019. "Towards Tractable Constraint Qualifications for Parametric Optimisation Problems and Applications to Generalised Nash Games," Journal of Optimization Theory and Applications, Springer, vol. 182(1), pages 404-416, July.
    2. Muhammad Omair & Mohammed Alkahtani & Kashif Ayaz & Ghulam Hussain & Johannes Buhl, 2022. "Supply Chain Modelling of the Automobile Multi-Stage Production Considering Circular Economy by Waste Management Using Recycling and Reworking Operations," Sustainability, MDPI, vol. 14(22), pages 1-26, November.
    3. Luís Felipe Bueno & Gabriel Haeser & Luiz-Rafael Santos, 2020. "Towards an efficient augmented Lagrangian method for convex quadratic programming," Computational Optimization and Applications, Springer, vol. 76(3), pages 767-800, July.
    4. Gabriel Haeser, 2018. "A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms," Computational Optimization and Applications, Springer, vol. 70(2), pages 615-639, June.
    5. Roberto Andreani & Ellen H. Fukuda & Gabriel Haeser & Daiana O. Santos & Leonardo D. Secchin, 2024. "Optimality Conditions for Nonlinear Second-Order Cone Programming and Symmetric Cone Programming," Journal of Optimization Theory and Applications, Springer, vol. 200(1), pages 1-33, January.
    6. Nguyen T. V. Hang & Boris S. Mordukhovich & M. Ebrahim Sarabi, 2022. "Augmented Lagrangian method for second-order cone programs under second-order sufficiency," Journal of Global Optimization, Springer, vol. 82(1), pages 51-81, January.
    7. Qihang Lin & Runchao Ma & Yangyang Xu, 2022. "Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization," Computational Optimization and Applications, Springer, vol. 82(1), pages 175-224, May.
    8. Muhammad Omair & Misbah Ullah & Baishakhi Ganguly & Sahar Noor & Shahid Maqsood & Biswajit Sarkar, 2019. "The Quantitative Analysis of Workers’ Stress Due to Working Environment in the Production System of the Automobile Part Manufacturing Industry," Mathematics, MDPI, vol. 7(7), pages 1-18, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. E. G. Birgin & L. F. Bueno & J. M. Martínez, 2016. "Sequential equality-constrained optimization for nonlinear programming," Computational Optimization and Applications, Springer, vol. 65(3), pages 699-721, December.
    2. E. Birgin & J. Martínez & L. Prudente, 2014. "Augmented Lagrangians with possible infeasibility and finite termination for global nonlinear programming," Journal of Global Optimization, Springer, vol. 58(2), pages 207-242, February.
    3. Shun Arahata & Takayuki Okuno & Akiko Takeda, 2023. "Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems," Computational Optimization and Applications, Springer, vol. 86(2), pages 555-598, November.
    4. Paul Armand & Ngoc Nguyen Tran, 2019. "An Augmented Lagrangian Method for Equality Constrained Optimization with Rapid Infeasibility Detection Capabilities," Journal of Optimization Theory and Applications, Springer, vol. 181(1), pages 197-215, April.
    5. Ernesto G. Birgin & Emerson V. Castelani & André L. M. Martinez & J. M. Martínez, 2011. "Outer Trust-Region Method for Constrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 150(1), pages 142-155, July.
    6. Andretta, M. & Birgin, E.G., 2013. "Deterministic and stochastic global optimization techniques for planar covering with ellipses problems," European Journal of Operational Research, Elsevier, vol. 224(1), pages 23-40.
    7. Galiev, Shamil I. & Lisafina, Maria S., 2013. "Linear models for the approximate solution of the problem of packing equal circles into a given domain," European Journal of Operational Research, Elsevier, vol. 230(3), pages 505-514.
    8. Zeng, Zhizhong & Yu, Xinguo & He, Kun & Huang, Wenqi & Fu, Zhanghua, 2016. "Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container," European Journal of Operational Research, Elsevier, vol. 250(2), pages 615-627.
    9. T N Wong & P S Chow & D Sculli, 2006. "A heuristic for sea-freight container selection, cargo allocation and cargo orientation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(12), pages 1452-1463, December.
    10. Huang, Wenqi & Ye, Tao, 2011. "Global optimization method for finding dense packings of equal circles in a circle," European Journal of Operational Research, Elsevier, vol. 210(3), pages 474-481, May.
    11. Gabriel Haeser, 2018. "A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms," Computational Optimization and Applications, Springer, vol. 70(2), pages 615-639, June.
    12. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    13. Castillo, Ignacio & Kampas, Frank J. & Pintér, János D., 2008. "Solving circle packing problems by global optimization: Numerical results and industrial applications," European Journal of Operational Research, Elsevier, vol. 191(3), pages 786-802, December.
    14. Luís Felipe Bueno & Gabriel Haeser & Luiz-Rafael Santos, 2020. "Towards an efficient augmented Lagrangian method for convex quadratic programming," Computational Optimization and Applications, Springer, vol. 76(3), pages 767-800, July.
    15. Nadav Hallak & Marc Teboulle, 2020. "Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach," Journal of Optimization Theory and Applications, Springer, vol. 186(2), pages 480-503, August.
    16. Hakim Akeb & Mhand Hifi, 2010. "A hybrid beam search looking-ahead algorithm for the circular packing problem," Journal of Combinatorial Optimization, Springer, vol. 20(2), pages 101-130, August.
    17. C. P. Brás & J. M. Martínez & M. Raydan, 2020. "Large-scale unconstrained optimization using separable cubic modeling and matrix-free subspace minimization," Computational Optimization and Applications, Springer, vol. 75(1), pages 169-205, January.
    18. Fu, Zhanghua & Huang, Wenqi & Lü, Zhipeng, 2013. "Iterated tabu search for the circular open dimension problem," European Journal of Operational Research, Elsevier, vol. 225(2), pages 236-243.
    19. Niblett, Matthew R. & Church, Richard L., 2015. "The disruptive anti-covering location problem," European Journal of Operational Research, Elsevier, vol. 247(3), pages 764-773.
    20. E. G. Birgin & R. D. Lobato & J. M. Martínez, 2017. "A nonlinear programming model with implicit variables for packing ellipsoids," Journal of Global Optimization, Springer, vol. 68(3), pages 467-499, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:69:y:2018:i:1:d:10.1007_s10589-017-9937-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.