A metaheuristic penalty approach for the starting point in nonlinear programming

Penas, David R.; Raydan, Marcos

RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 2, pp. 451-469.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

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.

[1] Artelys, Knitro nonlinear optimization solver. https://www.artelys.com/en/optimization-tools/knitro (2019).

[2] J.R. Banga, Optimization in computational systems biology. BMC Syst. Biol. 2 (2008) 1–47. | DOI

[3] R.H. Byrd, J. Nocedal and R.A. Waltz, Knitro: an integrated package for nonlinear optimization. In: Large-scale Nonlinear Optimization. Springer (2006) 35–59. | DOI | MR | Zbl

[4] C.A.C. Coello, 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] A.R. Conn, G. Gould and P.L. Toint, In: 17 of LANCELOT: A Fortran Package for Large-scale Nonlinear Optimization (Release A). Springer Science & Business Media (2013).

[6] A.V. Fiacco and G.P. Mccormick, 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] W.L. Goffe, G.D. Ferrier and J. Rogers, Global optimization of statistical functions with simulated annealing. J. Econ. 60 (1994) 65–99. | DOI | Zbl

[9] J.D. Griffin and T. Kolda, Nonlinearly constrained optimization using heuristic penalty methods and asynchronous parallel generating set search. Appl. Math. Res. Express 2010 (2010) 36–62. | Zbl

[10] J. Hald and K. Madsen, Combined lp and quasi-newton methods for minimax optimization. Math. Program. 20 (1981) 49–62. | DOI | MR | Zbl

[11] N. Hansen. A Python implementation of CMA-ES. https://github.com/CMA-ES/pycma (2017).

[12] N. Hansen and S. Kern, Evaluating the CMA evolution strategy on multimodal test functions. Springer (2004) 282–291.

[13] N. Hansen and A. Ostermeier, 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] N. Hansen, S.D. Müller and P. Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol. Comput. 11 (2003) 1–18. | DOI

[15] A. Homaifar, C.X. Qi and S.H. Lai, Constrained optimization via genetic algorithms. Simulation 62 (1994) 242–253. | DOI

[16] M. Kaucic, 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] J. Kennedy and R. Eberhart, Pso optimization. In: Vol. 4 of Proc. IEEE Int. Conf. Neural Networks. IEEE Service Center, Piscataway, NJ (1995) 1941–1948.

[18] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing. Science 220 (1983) 671–680. | DOI | MR | Zbl

[19] A. Lee, Particle swarm optimization (PSO) with constraint support. https://github.com/tisimst/pyswarm (2015).

[20] K.S. Lee and Z.W. Geem, 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] D.G. Luenberger, Linear and Nonlinear Programming. Addison-Wesley, Menlo Park, CA (1984). | Zbl

[22] S. Luke, Essentials of Metaheuristics, 2nd edition. Lulu. Available for free at http://cs.gmu.edu/sean/book/metaheuristics/ (2013).

[23] M.E.-B. Menai, M. Batouche, 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] Z. Michalewicz, Genetic algorithms for numerical optimization. Int. Trans. Oper. Res. 1 (1994) 223–240.

[25] Z. Michalewicz and C.Z. Janikow, Genetic algorithms for numerical optimization. Stat. Comput. 1 (1991) 75–91. | DOI

[26] K.E. Parsopoulos and M.N. Vrahatis, Particle swarm optimization method for constrained optimization problems. Int. Technol.–Theory App.: New Trends Intell. Technol. 76 (2002) 214–220.

[27] D.R. Penas, P. González, J.A. Egea, J.R. Banga and R. Doallo, Parallel metaheuristics in computational biology: an asynchronous cooperative enhanced scatter search method. Proc. Comput. Sci. 51 (2015) 630–639. | DOI

[28] D.R. Penas, D. Henriques, P. González, R. Doallo, J. Saez-Rodriguez and J.R. Banga, A parallel metaheuristic for large mixed-integer nonlinear dynamic optimization problems, with applications in computational biology. PLoS One 12 (2017) 1–32. | DOI

[29] R. Poli, J. Kennedy and T. Blackwell, Particle swarm optimization. Swarm Intell. 1 (2007) 33–57. | DOI

[30] M. Powell, A tolerant algorithm for linearly constrained optimization calculations. Math. Program. 45 (1989) 547–566. | DOI | MR | Zbl

[31] R.L. Rardin and R. Uzsoy, Experimental evaluation of heuristic optimization algorithms: a tutorial. J. Heuristics 7 (2001) 261–304. | DOI | Zbl

[32] M. Rieck, M. Richter, M. Bittner and F. Holzapfel, Generation of initial guesses for optimal control problems with mixed integer dependent constraints. In: ICAS 29th International Conference (2014).

[33] J. Robert, Vanderbei website. University of Princeton. https://vanderbei.princeton.edu/ampl/nlmodels/ (2019).

[34] B. Suman and P. Kumar, A survey of simulated annealing as a tool for single and multiobjective optimization. J. Oper. Res. Soc. 57 (2006) 1143–1160. | DOI | Zbl

[35] T. Takahashi, Metaheuristic Algorithms Python. https://github.com/tadatoshi/ (2015).

[36] E. Talbi, Metaheuristics: From Design to Implementation, 1st edition. Wiley (2009). ISBN 9780470278581. | Zbl

[37] Z. Ugray, L. Lasdon, J. Plummer, F. Glover, J. Kelly and R. Martí, 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] Ö. Yeniay, Penalty function methods for constrained optimization with genetic algorithms. Math. Comput. App. 10 (2005) 45–56.

[40] F. Zhang, A.C. Reynolds and D.S. Oliver, 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