IDEAS home Printed from https://ideas.repec.org/a/spr/topjnl/v28y2020i3d10.1007_s11750-020-00549-y.html
   My bibliography  Save this article

Non-monotone derivative-free algorithm for solving optimization models with linear constraints: extensions for solving nonlinearly constrained models via exact penalty methods

Author

Listed:
  • Ubaldo M. García-Palomares

    (Universidad Simón Bolívar
    Universidad de Vigo)

Abstract

This paper describes a non-monotone direct search method (NMDSM) that finds a stationary point of linearly constrained minimization problems. At each iteration the algorithm uses NMDSM techniques on the Euclidean space $${\mathbb {R}}^n$$ R n spanned by n variables carefully selected from the $$n+m$$ n + m variables formulated by the model under analysis. These variables are obtained by simple rules and are handled with pivot transformations frequently used in the solution of linear systems. A new weaker 0-order non smooth necessary condition is suggested, which transmute to other stationarity conditions, depending upon the kind of differentiability present in the system. Convergence with probability 1 is proved for non smooth functions. The algorithm is tested numerically on a set of small to medium size problems that have exhibited serious difficulties for their solution by other optimization techniques. The paper also considers possible extensions to non-linearly constrained problems via exact penalty function and a slightly modified algorithm satisfactorily solved a multi-batch multi-product plant that was modeled as a MINLP.

Suggested Citation

  • Ubaldo M. García-Palomares, 2020. "Non-monotone derivative-free algorithm for solving optimization models with linear constraints: extensions for solving nonlinearly constrained models via exact penalty methods," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(3), pages 599-625, October.
  • Handle: RePEc:spr:topjnl:v:28:y:2020:i:3:d:10.1007_s11750-020-00549-y
    DOI: 10.1007/s11750-020-00549-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11750-020-00549-y
    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/s11750-020-00549-y?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. Charles Audet & Sébastien Le Digabel & Mathilde Peyrega, 2015. "Linear equalities in blackbox optimization," Computational Optimization and Applications, Springer, vol. 61(1), pages 1-23, May.
    2. G. Di Pillo & S. Lucidi & F. Rinaldi, 2012. "An approach to constrained global optimization based on exact penalty functions," Journal of Global Optimization, Springer, vol. 54(2), pages 251-260, October.
    3. I. D. Coope & C. J. Price, 2000. "Frame Based Methods for Unconstrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 107(2), pages 261-274, November.
    4. David Easterling & Layne Watson & Michael Madigan & Brent Castle & Michael Trosset, 2014. "Parallel deterministic and stochastic global minimization of functions with very many minima," Computational Optimization and Applications, Springer, vol. 57(2), pages 469-492, March.
    Full references (including those not matched with items on IDEAS)

    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. David W. Dreisigmeyer, 2018. "Direct Search Methods on Reductive Homogeneous Spaces," Journal of Optimization Theory and Applications, Springer, vol. 176(3), pages 585-604, March.
    2. Benjamin Dyke & Thomas J. Asaki, 2013. "Using QR Decomposition to Obtain a New Instance of Mesh Adaptive Direct Search with Uniformly Distributed Polling Directions," Journal of Optimization Theory and Applications, Springer, vol. 159(3), pages 805-821, December.
    3. A. Sanchez & Diego Martinez, 2011. "Optimization in Non-Standard Problems. An Application to the Provision of Public Inputs," Computational Economics, Springer;Society for Computational Economics, vol. 37(1), pages 13-38, January.
    4. G. Di Pillo & G. Liuzzi & S. Lucidi & V. Piccialli & F. Rinaldi, 2016. "A DIRECT-type approach for derivative-free constrained global optimization," Computational Optimization and Applications, Springer, vol. 65(2), pages 361-397, November.
    5. C.J. Price & I.D. Coope, 2003. "Frame-Based Ray Search Algorithms in Unconstrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 116(2), pages 359-377, February.
    6. C.J. Price & I.D. Coope & D. Byatt, 2002. "A Convergent Variant of the Nelder–Mead Algorithm," Journal of Optimization Theory and Applications, Springer, vol. 113(1), pages 5-19, April.
    7. Benjamin Van Dyke, 2014. "Equal Angle Distribution of Polling Directions in Direct-Search Methods," Journal of Optimization, Hindawi, vol. 2014, pages 1-15, July.
    8. Ana Maria A. C. Rocha & M. Fernanda P. Costa & Edite M. G. P. Fernandes, 2017. "On a smoothed penalty-based algorithm for global optimization," Journal of Global Optimization, Springer, vol. 69(3), pages 561-585, November.
    9. Ana Rocha & M. Costa & Edite Fernandes, 2014. "A filter-based artificial fish swarm algorithm for constrained global optimization: theoretical and practical issues," Journal of Global Optimization, Springer, vol. 60(2), pages 239-263, October.
    10. Javaid Ali & Muhammad Saeed & Muhammad Farhan Tabassam & Shaukat Iqbal, 2019. "Controlled showering optimization algorithm: an intelligent tool for decision making in global optimization," Computational and Mathematical Organization Theory, Springer, vol. 25(2), pages 132-164, June.
    11. Árpád Bűrmen & Jernej Olenšek & Tadej Tuma, 2015. "Mesh adaptive direct search with second directional derivative-based Hessian update," Computational Optimization and Applications, Springer, vol. 62(3), pages 693-715, December.
    12. Gianni Pillo & Stefano Lucidi & Francesco Rinaldi, 2015. "A Derivative-Free Algorithm for Constrained Global Optimization Based on Exact Penalty Functions," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 862-882, March.
    13. S. Gratton & C. W. Royer & L. N. Vicente & Z. Zhang, 2019. "Direct search based on probabilistic feasible descent for bound and linearly constrained problems," Computational Optimization and Applications, Springer, vol. 72(3), pages 525-559, April.
    14. M. Fernanda P. Costa & Rogério B. Francisco & Ana Maria A. C. Rocha & Edite M. G. P. Fernandes, 2017. "Theoretical and Practical Convergence of a Self-Adaptive Penalty Algorithm for Constrained Global Optimization," Journal of Optimization Theory and Applications, Springer, vol. 174(3), pages 875-893, September.
    15. M. Joseane F. G. Macêdo & Elizabeth W. Karas & M. Fernanda P. Costa & Ana Maria A. C. Rocha, 2020. "Filter-based stochastic algorithm for global optimization," Journal of Global Optimization, Springer, vol. 77(4), pages 777-805, August.
    16. C. J. Price & M. Reale & B. L. Robertson, 2016. "Stochastic filter methods for generally constrained global optimization," Journal of Global Optimization, Springer, vol. 65(3), pages 441-456, July.
    17. M. Fernanda P. Costa & Ana Maria A. C. Rocha & Edite M. G. P. Fernandes, 2018. "Filter-based DIRECT method for constrained global optimization," Journal of Global Optimization, Springer, vol. 71(3), pages 517-536, July.
    18. Y. Diouane & S. Gratton & L. Vicente, 2015. "Globally convergent evolution strategies for constrained optimization," Computational Optimization and Applications, Springer, vol. 62(2), pages 323-346, November.
    19. Charles Audet & Andrew R. Conn & Sébastien Le Digabel & Mathilde Peyrega, 2018. "A progressive barrier derivative-free trust-region algorithm for constrained optimization," Computational Optimization and Applications, Springer, vol. 71(2), pages 307-329, November.
    20. Anurag Jayswal & Sarita Choudhury, 2016. "An Exact Minimax Penalty Function Method and Saddle Point Criteria for Nonsmooth Convex Vector Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 169(1), pages 179-199, April.

    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:topjnl:v:28:y:2020:i:3:d:10.1007_s11750-020-00549-y. 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.