IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v178y2018i2d10.1007_s10957-018-1320-7.html
   My bibliography  Save this article

Second-Order Optimality Conditions and Improved Convergence Results for Regularization Methods for Cardinality-Constrained Optimization Problems

Author

Listed:
  • Max Bucher

    (Technische Universität Darmstadt)

  • Alexandra Schwartz

    (Technische Universität Darmstadt)

Abstract

We consider nonlinear optimization problems with cardinality constraints. Based on a continuous reformulation, we introduce second-order necessary and sufficient optimality conditions. Under such a second-order condition, we can guarantee local uniqueness of Mordukhovich stationary points. Finally, we use this observation to provide extended local convergence theory for a Scholtes-type regularization method, which guarantees the existence and convergence of iterates under suitable assumptions. This convergence theory can also be applied to other regularization schemes.

Suggested Citation

  • Max Bucher & Alexandra Schwartz, 2018. "Second-Order Optimality Conditions and Improved Convergence Results for Regularization Methods for Cardinality-Constrained Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 178(2), pages 383-410, August.
  • Handle: RePEc:spr:joptap:v:178:y:2018:i:2:d:10.1007_s10957-018-1320-7
    DOI: 10.1007/s10957-018-1320-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-018-1320-7
    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/s10957-018-1320-7?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. Holger Scheel & Stefan Scholtes, 2000. "Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensitivity," Mathematics of Operations Research, INFORMS, vol. 25(1), pages 1-22, February.
    2. Peter Kirst & Fabian Rigterink & Oliver Stein, 2017. "Global optimization of disjunctive programs," Journal of Global Optimization, Springer, vol. 69(2), pages 283-307, October.
    3. Walter Murray & Howard Shek, 2012. "A local relaxation method for the cardinality constrained portfolio optimization problem," Computational Optimization and Applications, Springer, vol. 53(3), pages 681-709, December.
    4. Dimitris Bertsimas & Romy Shioda, 2009. "Algorithm for cardinality-constrained quadratic optimization," Computational Optimization and Applications, Springer, vol. 43(1), pages 1-22, May.
    5. Lei Guo & Gui-Hua Lin & Jane J. Ye, 2013. "Second-Order Optimality Conditions for Mathematical Programs with Equilibrium Constraints," Journal of Optimization Theory and Applications, Springer, vol. 158(1), pages 33-64, July.
    6. Lukáš Adam & Martin Branda, 2016. "Nonlinear Chance Constrained Problems: Optimality Conditions, Regularization and Solvers," Journal of Optimization Theory and Applications, Springer, vol. 170(2), pages 419-436, August.
    7. D.P. Bertsekas & A.E. Ozdaglar, 2002. "Pseudonormality and a Lagrange Multiplier Theory for Constrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 114(2), pages 287-343, August.
    8. Dinakar Gade & Simge Küçükyavuz, 2013. "Formulations for dynamic lot sizing with service levels," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(2), pages 87-101, March.
    9. Martin Branda & Max Bucher & Michal Červinka & Alexandra Schwartz, 2018. "Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization," Computational Optimization and Applications, Springer, vol. 70(2), pages 503-530, June.
    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. Ademir A. Ribeiro & Mael Sachine & Evelin H. M. Krulikovski, 2022. "A Comparative Study of Sequential Optimality Conditions for Mathematical Programs with Cardinality Constraints," Journal of Optimization Theory and Applications, Springer, vol. 192(3), pages 1067-1083, March.
    2. S. Lämmel & V. Shikhman, 2022. "On nondegenerate M-stationary points for sparsity constrained nonlinear optimization," Journal of Global Optimization, Springer, vol. 82(2), pages 219-242, February.

    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. Martin Branda & Max Bucher & Michal Červinka & Alexandra Schwartz, 2018. "Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization," Computational Optimization and Applications, Springer, vol. 70(2), pages 503-530, June.
    2. Christian Kanzow & Andreas B. Raharja & Alexandra Schwartz, 2021. "Sequential optimality conditions for cardinality-constrained optimization problems with applications," Computational Optimization and Applications, Springer, vol. 80(1), pages 185-211, September.
    3. Christian Kanzow & Andreas B. Raharja & Alexandra Schwartz, 2021. "An Augmented Lagrangian Method for Cardinality-Constrained Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 189(3), pages 793-813, June.
    4. Jize Zhang & Tim Leung & Aleksandr Aravkin, 2018. "A Relaxed Optimization Approach for Cardinality-Constrained Portfolio Optimization," Papers 1810.10563, arXiv.org.
    5. Nguyen Huy Chieu & Gue Myung Lee, 2014. "Constraint Qualifications for Mathematical Programs with Equilibrium Constraints and their Local Preservation Property," Journal of Optimization Theory and Applications, Springer, vol. 163(3), pages 755-776, December.
    6. Nasim Dehghan Hardoroudi & Abolfazl Keshvari & Markku Kallio & Pekka Korhonen, 2017. "Solving cardinality constrained mean-variance portfolio problems via MILP," Annals of Operations Research, Springer, vol. 254(1), pages 47-59, July.
    7. Madani Bezoui & Mustapha Moulaï & Ahcène Bounceur & Reinhardt Euler, 2019. "An iterative method for solving a bi-objective constrained portfolio optimization problem," Computational Optimization and Applications, Springer, vol. 72(2), pages 479-498, March.
    8. Jane J. Ye & Jin Zhang, 2014. "Enhanced Karush–Kuhn–Tucker Conditions for Mathematical Programs with Equilibrium Constraints," Journal of Optimization Theory and Applications, Springer, vol. 163(3), pages 777-794, December.
    9. Alberto Ramos, 2019. "Two New Weak Constraint Qualifications for Mathematical Programs with Equilibrium Constraints and Applications," Journal of Optimization Theory and Applications, Springer, vol. 183(2), pages 566-591, November.
    10. Lili Pan & Ziyan Luo & Naihua Xiu, 2017. "Restricted Robinson Constraint Qualification and Optimality for Cardinality-Constrained Cone Programming," Journal of Optimization Theory and Applications, Springer, vol. 175(1), pages 104-118, October.
    11. Minjiao Zhang & Simge Küçükyavuz & Saumya Goel, 2014. "A Branch-and-Cut Method for Dynamic Decision Making Under Joint Chance Constraints," Management Science, INFORMS, vol. 60(5), pages 1317-1333, May.
    12. Stefan Scholtes, 2004. "Nonconvex Structures in Nonlinear Programming," Operations Research, INFORMS, vol. 52(3), pages 368-383, June.
    13. Stein, Oliver, 2012. "How to solve a semi-infinite optimization problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 312-320.
    14. Roberto Andreani & José Mario Martínez & Alberto Ramos & Paulo J. S. Silva, 2018. "Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 693-717, August.
    15. Giorgio, 2019. "On Second-Order Optimality Conditions in Smooth Nonlinear Programming Problems," DEM Working Papers Series 171, University of Pavia, Department of Economics and Management.
    16. Birbil, S.I. & Bouza, G. & Frenk, J.B.G. & Still, G.J., 2003. "Equilibrium Constrained Optimization Problems," Econometric Institute Research Papers ERS-2003-085-LIS, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. Zhang, Fang & Lu, Jian & Hu, Xiaojian & Meng, Qiang, 2023. "Integrated deployment of dedicated lane and roadside unit considering uncertain road capacity under the mixed-autonomy traffic environment," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    18. Andreas Ehrenmann & Karsten Neuhoff, 2009. "A Comparison of Electricity Market Designs in Networks," Operations Research, INFORMS, vol. 57(2), pages 274-286, April.
    19. Gui-Hua Lin & Mei-Ju Luo & Jin Zhang, 2016. "Smoothing and SAA method for stochastic programming problems with non-smooth objective and constraints," Journal of Global Optimization, Springer, vol. 66(3), pages 487-510, November.
    20. Ken Kobayashi & Yuichi Takano & Kazuhide Nakata, 2021. "Bilevel cutting-plane algorithm for cardinality-constrained mean-CVaR portfolio optimization," Journal of Global Optimization, Springer, vol. 81(2), pages 493-528, October.

    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:joptap:v:178:y:2018:i:2:d:10.1007_s10957-018-1320-7. 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.