Solving nonlinear programming problems usually involve difficulties to obtain a starting point that produces convergence to a local feasible solution, for which the objective function value is sufficiently good. A novel approach is proposed, combining metaheuristic techniques with modern deterministic optimization schemes, with the aim to solve a sequence of penalized related problems to generate convenient starting points. The metaheuristic ideas are used to choose the penalty parameters associated with the constraints, and for each set of penalty parameters a deterministic scheme is used to evaluate a properly chosen metaheuristic merit function. Based on this starting-point approach, we describe two different strategies for solving the nonlinear programming problem. We illustrate the properties of the combined schemes on three nonlinear programming benchmark-test problems, and also on the well-known and hard-to-solve disk-packing problem, that possesses a huge amount of local-nonglobal solutions, obtaining encouraging results both in terms of optimality and feasibility.
Mots-clés : Nonlinear programming problems, Starting point strategy, Metaheuristics, Penalty methods, Disk packing problem
@article{RO_2020__54_2_451_0,
author = {Penas, David R. and Raydan, Marcos},
title = {A metaheuristic penalty approach for the starting point in nonlinear programming},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {451--469},
publisher = {EDP-Sciences},
volume = {54},
number = {2},
year = {2020},
doi = {10.1051/ro/2019096},
mrnumber = {4069305},
zbl = {1443.90314},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2019096/}
}
TY - JOUR AU - Penas, David R. AU - Raydan, Marcos TI - A metaheuristic penalty approach for the starting point in nonlinear programming JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2020 SP - 451 EP - 469 VL - 54 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2019096/ DO - 10.1051/ro/2019096 LA - en ID - RO_2020__54_2_451_0 ER -
%0 Journal Article %A Penas, David R. %A Raydan, Marcos %T A metaheuristic penalty approach for the starting point in nonlinear programming %J RAIRO - Operations Research - Recherche Opérationnelle %D 2020 %P 451-469 %V 54 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2019096/ %R 10.1051/ro/2019096 %G en %F RO_2020__54_2_451_0
Penas, David R.; Raydan, Marcos. A metaheuristic penalty approach for the starting point in nonlinear programming. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 2, pp. 451-469. doi : 10.1051/ro/2019096. http://www.numdam.org/articles/10.1051/ro/2019096/
[1] Artelys, Knitro nonlinear optimization solver. https://www.artelys.com/en/optimization-tools/knitro (2019).
[2] , Optimization in computational systems biology. BMC Syst. Biol. 2 (2008) 1–47. | DOI
[3] , and , Knitro: an integrated package for nonlinear optimization. In: Large-scale Nonlinear Optimization. Springer (2006) 35–59. | DOI | MR | Zbl
[4] , Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Comput. Methods Appl. Mech. Eng. 191 (2002) 1245–1287. | DOI | MR | Zbl
[5] , and , In: 17 of LANCELOT: A Fortran Package for Large-scale Nonlinear Optimization (Release A). Springer Science & Business Media (2013).
[6] and , Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley and Sons, New York (1968). | MR
[7] GAMS World site. Cute models section. http://www.gamsworld.org/performance/princetonlib/htm/group5stat.htm (2019).
[8] , and , Global optimization of statistical functions with simulated annealing. J. Econ. 60 (1994) 65–99. | DOI | Zbl
[9] and , Nonlinearly constrained optimization using heuristic penalty methods and asynchronous parallel generating set search. Appl. Math. Res. Express 2010 (2010) 36–62. | Zbl
[10] and , Combined lp and quasi-newton methods for minimax optimization. Math. Program. 20 (1981) 49–62. | DOI | MR | Zbl
[11] . A Python implementation of CMA-ES. https://github.com/CMA-ES/pycma (2017).
[12] and , Evaluating the CMA evolution strategy on multimodal test functions. Springer (2004) 282–291.
[13] and , Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In: Proceedings of IEEE International Conference on Evolutionary Computation. IEEE (1996) 312–317. | DOI
[14] , and , Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol. Comput. 11 (2003) 1–18. | DOI
[15] , and , Constrained optimization via genetic algorithms. Simulation 62 (1994) 242–253. | DOI
[16] , A multi-start opposition-based particle swarm optimization algorithm with adaptive velocity for bound constrained global optimization. J. Global Optim. 55 (2013) 165–188. | DOI | MR | Zbl
[17] and , Pso optimization. In: Vol. 4 of Proc. IEEE Int. Conf. Neural Networks. IEEE Service Center, Piscataway, NJ (1995) 1941–1948.
[18] , and , Optimization by simulated annealing. Science 220 (1983) 671–680. | DOI | MR | Zbl
[19] , Particle swarm optimization (PSO) with constraint support. https://github.com/tisimst/pyswarm (2015).
[20] and , A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice. Comput. Methods Appl. Mech. Eng. 194 (2005) 3902–3933. | DOI | Zbl
[21] , Linear and Nonlinear Programming. Addison-Wesley, Menlo Park, CA (1984). | Zbl
[22] , Essentials of Metaheuristics, 2nd edition. Lulu. Available for free at http://cs.gmu.edu/sean/book/metaheuristics/ (2013).
[23] , , Efficient initial solution to extremal optimization algorithm for weighted maxsat problem. In: International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. Springer (2003) 592–603. | Zbl
[24] , Genetic algorithms for numerical optimization. Int. Trans. Oper. Res. 1 (1994) 223–240.
[25] and , Genetic algorithms for numerical optimization. Stat. Comput. 1 (1991) 75–91. | DOI
[26] and , Particle swarm optimization method for constrained optimization problems. Int. Technol.–Theory App.: New Trends Intell. Technol. 76 (2002) 214–220.
[27] , , , and , Parallel metaheuristics in computational biology: an asynchronous cooperative enhanced scatter search method. Proc. Comput. Sci. 51 (2015) 630–639. | DOI
[28] , , , , and , A parallel metaheuristic for large mixed-integer nonlinear dynamic optimization problems, with applications in computational biology. PLoS One 12 (2017) 1–32. | DOI
[29] , and , Particle swarm optimization. Swarm Intell. 1 (2007) 33–57. | DOI
[30] , A tolerant algorithm for linearly constrained optimization calculations. Math. Program. 45 (1989) 547–566. | DOI | MR | Zbl
[31] and , Experimental evaluation of heuristic optimization algorithms: a tutorial. J. Heuristics 7 (2001) 261–304. | DOI | Zbl
[32] , , and , Generation of initial guesses for optimal control problems with mixed integer dependent constraints. In: ICAS 29th International Conference (2014).
[33] , Vanderbei website. University of Princeton. https://vanderbei.princeton.edu/ampl/nlmodels/ (2019).
[34] and , A survey of simulated annealing as a tool for single and multiobjective optimization. J. Oper. Res. Soc. 57 (2006) 1143–1160. | DOI | Zbl
[35] , Metaheuristic Algorithms Python. https://github.com/tadatoshi/ (2015).
[36] , Metaheuristics: From Design to Implementation, 1st edition. Wiley (2009). ISBN 9780470278581. | Zbl
[37] , , , , and , Scatter search and local NLP solvers: a multistart framework for global optimization. INFORMS J. Comput. 19 (2007) 328–340. | DOI | MR | Zbl
[38] University of Magdeburg, The best known packings of equal circles in a square. http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html (2013).
[39] , Penalty function methods for constrained optimization with genetic algorithms. Math. Comput. App. 10 (2005) 45–56.
[40] , and , An initial guess for the levenberg–marquardt algorithm for conditioning a stochastic channel to pressure data. Math. Geol. 35 (2003) 67–88. | DOI | MR | Zbl
Cité par Sources :
