×

Non-monotone derivative-free algorithm for solving optimization models with linear constraints: extensions for solving nonlinearly constrained models via exact penalty methods. (English) Zbl 1467.90088

Summary: 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.

MSC:

90C56 Derivative-free methods and methods using generalized derivatives
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Software:

DFL; NOMAD; COPS; MinFinder; DFN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramson MA, Audet C, Couture G, Dennis Jr JE, Le Digabel S. The NOMAD project. http://www.gerad.ca/nomad
[2] Abramson, MA; Brezhneva, OA; Dennis, JE Jr; Pingel, RI, Pattern search in the presence of degenerate linear constraints, Optim Methods Softw, 23, 3, 297-319 (2008) · Zbl 1162.90588
[3] Audet, C.; Dennis, JE Jr, Analysis of generalized pattern searches, SIAM J Optim, 13, 889-903 (2003) · Zbl 1053.90118
[4] Audet, C.; Le Digabel, S.; Peyrega, M., Linear equalities in blackbox optimization, Comput Optim Appl, 61, 1, 1-23 (2015) · Zbl 1311.90185
[5] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedke, J.; Mahajan, A., Mixed-Integer nonlinear optimization, Acta Numer, 22, 1-131 (2013) · Zbl 1291.65172
[6] Burachik, RS; Rubinov, A., On the absence of duality gap for Lagrange-type functions, J Ind Manag Optim, 1, 1, 33-38 (2005) · Zbl 1135.90428
[7] 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 · Zbl 1163.49001
[8] Coope, ID; Price, CJ, Frame based methods for unconstrained optimization, Optim Theory Appl, 107, 2, 261-274 (2000) · Zbl 0983.90074
[9] Di Pillo, G.; Grippo, L., On the exactness of a class of nondifferentiable penalty functions, Optim Theory Appl, 57, 3, 399-410 (1988) · Zbl 0621.90078
[10] Di Pillo, G.; Lucidi, S.; Rinaldo, F., An approach to constrained global optimization based on exact penalty functions, J Global Optim, 54, 2, 251-260 (2012) · Zbl 1259.90099
[11] Dolan ED, Moré JJ, Munson TS (2004) Benchmarking optimization software with COPS 3.0. Argonne National Laboratory Technical Report ANL/MCS-TM-273. ++
[12] Easterling, DR; Watson, LT; Madigan, ML; Castle, BS; Trosset, MW, Parallel deterministic and stochastic global minimization of functions with very many minima, Comput Optim Appl, 57, 469-492 (2014) · Zbl 1304.90162
[13] Fasano, G.; Liuzzi, G.; Lucidi, S.; Rinaldi, F., A linesearch-based derivative-free approach for nonsmooth constrained optimization, SIAM J Optim, 24, 3, 959-992 (2014) · Zbl 1302.90207
[14] 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
[15] 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
[16] García-Palomares, UM; Rodríguez, JF, New sequential and parallel derivative-free algorithms for unconstrained minimization, SIAM J Optim, 13, 1, 79-96 (2002) · Zbl 1049.90133
[17] García-Palomares, UM; González-Castaño, FJ; Burguillo Rial, JC, A combined global & local search (CGLS) approach to global optimization, J Global Optim, 34, 409-426 (2006) · Zbl 1149.90426
[18] García-Palomares, UM; Rodríguez-Hernández, PS, Unified approach for solving box-constrained models with continuous or discrete variables by non monotone direct search methods, Optim Lett, 13, 1, 95-111 (2019) · Zbl 1417.90119
[19] García-Palomares, UM; García-Urrea, IJ; Rodríguez-Hernández, PS, On sequential and parallel non-monotone derivative free algorithms for box constrained optimization, Optim Methods Softw, 28, 6, 1233-1261 (2013) · Zbl 1278.65088
[20] 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
[21] 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
[22] Grossmann, IE; Sargent, RW, Optimal design of multipurpose chemical plants, Ind Eng Chem Process Des Dev, 18, 343-348 (1979)
[23] Kocis, GR; Grossmann, IE, Global optimization of nonconvex mixed-integer non-linear programming (MINLP) problems in process synthesis, Ind Eng Chem Res, 27, 8, 1407-1421 (1988)
[24] Kolda, TG; Torczon, VJ, On the convergence of asynchronous parallel pattern search, SIAM J Optim, 14, 4, 939-964 (2004) · Zbl 1073.90046
[25] Kolda, TG; Lewis, RM; Torczon, VJ, Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev, 45, 3, 385-482 (2003) · Zbl 1059.90146
[26] Laguna M, Martí R (2002) Experimental testing of advanced scatter search designs for global optimization of multimodal functions · Zbl 1093.90092
[27] Larson J, Wild SM (2015) A batch, derivative-free algorithm for finding multiple local minima. Argonne National Lab/MCS-P5228-1114, May 2015
[28] Le Digabel S (2011) NOMAD user guide, version 3.5.0. March 2011 · Zbl 1365.65172
[29] Le Digabel, S., Algorithm 909: Nomad: nonlinear optimization with the mads algorithm, ACM Trans Math Softw, 37, 4, 1-15 (2011) · Zbl 1365.65172
[30] Lewis, RM; Torczon, VJ, Pattern search methods for linearly constrained minimization, SIAM J Optim, 10, 917-941 (2000) · Zbl 1031.90048
[31] Lucidi, S.; Sciandrone, M., On the global convergence of derivative-free methods for unconstrained optimization, SIAM J Optim, 13, 1, 97-116 (2002) · Zbl 1027.90112
[32] 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
[33] 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
[34] Sarkar, D.; Modak, JM, Optimal design of multiproduct batch chemical plant using NSGA-II, Asia-Pac J Chem Eng, 1, 13-20 (2006)
[35] Torczon VJ (1989) Multi-directional search: a direct search algorithm for parallel machines. PhD thesis, Rice University, Houston,TX
[36] Torczon, VJ, On the convergence of multidirectional search algorithm, SIAM J Optim, 1, 123-145 (1991) · Zbl 0752.90076
[37] Törn, A.; Ali, M.; Viitanen, S., Stochastic global optimization: problem classes and solution techniques, J Global Optim, 14, 437-447 (1999) · Zbl 0952.90030
[38] Tsoulos, IG; Lagaris, IE, MinFinder: locating all the local minima of a function, Comput Phys Commun, 174, 166-179 (2006) · Zbl 1196.90087
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.