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\) spanned by n variables carefully selected from the \(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.
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11750-020-00549-y/MediaObjects/11750_2020_549_Fig1_HTML.png)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11750-020-00549-y/MediaObjects/11750_2020_549_Fig2_HTML.png)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11750-020-00549-y/MediaObjects/11750_2020_549_Fig3_HTML.png)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11750-020-00549-y/MediaObjects/11750_2020_549_Fig4_HTML.png)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11750-020-00549-y/MediaObjects/11750_2020_549_Fig5_HTML.png)
Similar content being viewed by others
References
Abramson MA, Audet C, Couture G, Dennis Jr JE, Le Digabel S. The NOMAD project. http://www.gerad.ca/nomad
Abramson MA, Brezhneva OA, Dennis Jr JE, Pingel RI (2008) Pattern search in the presence of degenerate linear constraints. Optim Methods Softw 23(3):297–319
Audet C, Dennis JE Jr (2003) Analysis of generalized pattern searches. SIAM J Optim 13:889–903
Audet C, Le Digabel S, Peyrega M (2015) Linear equalities in blackbox optimization. Comput Optim Appl 61(1):1–23
Belotti P, Kirches C, Leyffer S, Linderoth J, Luedke J, Mahajan A (2013) Mixed-Integer nonlinear optimization. Acta Numer 22:1–131
Burachik RS, Rubinov A (2005) On the absence of duality gap for Lagrange-type functions. J Ind Manag Optim 1(1):33–38
Conn AR, Scheinberg K, Vicente Luís N (2009) Introduction to derivative-free optimization. MPS-SIAM series on optimization. SIAM. ISBN 978-0-898716-68-9 edition
Coope ID, Price CJ (2000) Frame based methods for unconstrained optimization. Optim Theory Appl 107(2):261–274
Di Pillo G, Grippo L (1988) On the exactness of a class of nondifferentiable penalty functions. Optim Theory Appl 57(3):399–410
Di Pillo G, Lucidi S, Rinaldo F (2012) An approach to constrained global optimization based on exact penalty functions. J Global Optim 54(2):251–260
Dolan ED, Moré JJ, Munson TS (2004) Benchmarking optimization software with COPS 3.0. Argonne National Laboratory Technical Report ANL/MCS-TM-273. ++
Easterling DR, Watson LT, Madigan ML, Castle BS, Trosset MW (2014) Parallel deterministic and stochastic global minimization of functions with very many minima. Comput Optim Appl 57:469–492
Fasano G, Liuzzi G, Lucidi S, Rinaldi F (2014) A linesearch-based derivative-free approach for nonsmooth constrained optimization. SIAM J Optim 24(3):959–992
Fenqi Y, Grossmann I (2009) Mixed-Integer nonlinear programming models for the optimal design of multi-product batch plant. http://www.minlp.org/library/problem/index.php?i=48
García-Palomares UM (2020) A unified convergence theory for Non monotone Direct Search Methods (DSMs) with extensions to DFO with mixed and categorical variables. submitted
García-Palomares UM, Rodríguez JF (2002) New sequential and parallel derivative-free algorithms for unconstrained minimization. SIAM J Optim 13(1):79–96
García-Palomaress UM, González-Castaño FJ, Burguillo Rial JC (2006) A combined global & local search (CGLS) approach to global optimization. J Global Optim 34:409–426
García-Palomares UM, Rodríguez-Hernández PS (2019) Unified approach for solving box-constrained models with continuous or discrete variables by non monotone direct search methods. Optim Lett 13(1):95–111
García-Palomares UM, García-Urrea IJ, Rodríguez-Hernández PS (2013) On sequential and parallel non-monotone derivative free algorithms for box constrained optimization. Optim Methods Softw 28(6):1233–1261
García-Urrea IJ (2010) Método de Búsqueda Directa no monótona para Optimizar una Función Objetivo Sujeta a Restricciones Lineales. Doctoral Dissertation, Universidad Simón Bolívar, Venezuela, http://159.90.80.55/tesis/000151094.pdf
Gramacy RB, Gray GA, Le Digabel S, Lee HKH, Ranjan P, Wells G, Wild SM (2014) Modeling an augmented lagrangian for improved Blackbox constrained optimization. arXiv preprint. arXiv:1403.4890
Grossmann IE, Sargent RW (1979) Optimal design of multipurpose chemical plants. Ind Eng Chem Process Des Dev 18:343–348
Kocis GR, Grossmann IE (1988) Global optimization of nonconvex mixed-integer non-linear programming (MINLP) problems in process synthesis. Ind Eng Chem Res 27(8):1407–1421
Kolda TG, Torczon VJ (2004) On the convergence of asynchronous parallel pattern search. SIAM J Optim 14(4):939–964
Kolda TG, Lewis RM, Torczon VJ (2003) Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev 45(3):385–482
Laguna M, Martí R (2002) Experimental testing of advanced scatter search designs for global optimization of multimodal functions
Larson J, Wild SM (2015) A batch, derivative-free algorithm for finding multiple local minima. Argonne National Lab/MCS-P5228-1114, May 2015
Le Digabel S (2011) NOMAD user guide, version 3.5.0. March 2011
Le Digabel S (2011) Algorithm 909: Nomad: nonlinear optimization with the mads algorithm. ACM Trans Math Softw 37(4):1–15
Lewis RM, Torczon VJ (2000) Pattern search methods for linearly constrained minimization. SIAM J Optim 10:917–941
Lucidi S, Sciandrone M (2002) On the global convergence of derivative-free methods for unconstrained optimization. SIAM J Optim 13(1):97–116
Pachón A (2015) La asignación de recursos en OFDMA derivados de la formulación y la solución de un modelo de optimizacíon con variables continuas y variables booleanas. Tesis Doctoral, Dpto. Ingeniería Telemática, Universidad de Vigo
Poland J (2000) Three different algorithms for generating uniformly distributed random points on the N-sphere. Unpublished. http://wwwalg.ist.hokudai.ac.jp/jan/randsphere.pdf
Sarkar D, Modak JM (2006) Optimal design of multiproduct batch chemical plant using NSGA-II. Asia-Pac J Chem Eng 1:13–20
Torczon VJ (1989) Multi-directional search: a direct search algorithm for parallel machines. PhD thesis, Rice University, Houston,TX
Torczon VJ (1991) On the convergence of multidirectional search algorithm. SIAM J Optim 1:123–145
Törn A, Ali M, Viitanen S (1999) Stochastic global optimization: problem classes and solution techniques. J Global Optim 14:437–447
Tsoulos IG, Lagaris IE (2006) MinFinder: locating all the local minima of a function. Comput Phys Commun 174:166–179
Acknowledgements
This research has been partially funded by the Universidad Simón Bolívar and by the Universidade de Vigo through grant R2014/037 from the Galician Regional Government. Spain. Thanks to an anonymous referee who read the previous version and suggested modifications that enhanced the presentation of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
García-Palomares, U.M. Non-monotone derivative-free algorithm for solving optimization models with linear constraints: extensions for solving nonlinearly constrained models via exact penalty methods. TOP 28, 599–625 (2020). https://doi.org/10.1007/s11750-020-00549-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-020-00549-y
Keywords
- Non monotone direct search method
- 0-Order stationarity
- Linear and non linear constraints
- Exact penalty functions