Extensions of a Multistart Clustering Algorithm for Constrained Global Optimization Problems

In this work we have developed and implemented GLOBALm, an extension of a well-known clustering multistart algorithm for solving nonlinear optimization problems with constraints. The proposed approach makes use of an exact penalty function in the global phase for the selection of the initial points from which the local search is started.

We have also incorporated some local optimization methods, including a new derivative-free solver which can handle nonlinear constraints without requiring the setting of any penalty parameter. This solver uses a filter approach based on the concept of non-domination, and it has proved to be more robust than the original algorithm for non-smooth and noisy problems. The performance and robustness of the new solver was tested with two sets of challenging benchmark problems, showing excellent results.

References

Ali M., Storey C., Törn A. (1997), Application of stochastic global optimization algorithms to practical problems. J. Optim. Theory Appl. 95:545-563.

Ali, M.M., C. Khompatraporn and Z. Zabinsky (2005) A Numerical Evaluation of Several Stochastic Algorithms on Selected Continuous Global Optimization Test Problems. Journal of Global Optimization 31:635-672.

Balsa-Canto, E.; Vassiliadis, V. S.; Banga, J. R. (2005) Dynamic Optimization of Single- and Multi-Stage Systems Using a Hybrid Stochastic-Deterministic Method. Industrial and Engineering Chemistry Research 44(5): 1514-1523.

Banga, J. R., E. Balsa-Canto, C. G. Moles and A. A. Alonso (2005) Dynamic optimization of bioprocesses: Efficient and robust numerical strategies. Journal of Biotechnology 117(4):407-419.

Banga, J.R. and Seider, W.D. (1996). Global Optimization of Chemical Processes using Stochastic Algorithms. In Floudas, C.A.; Pardalos, P.M. (Editors). State of the Art in Global Optimization: Computation Methods and Applications, pp. 563-583. Kluwer Academic Publisher: Dordrecht.

Banga, J.R. and Singh, R. P. (1994). Optimization of Air Drying of Foods. Journal of Food Engineering, 23, 189-211.

Banga, J.R., Moles, C.G., Alonso, A.A. (2003) Global optimization of bioprocesses using stochastic and hybrid methods. In "Frontiers In Global Optimization ", C.A. Floudas and P. M. Pardalos, (Eds.), Nonconvex Optimization and Its Applications, vol. 74, pp. 45-70, Kluwer Academic Publishers, ISBN 1-4020-7699-1.

Biegler, L.T., Grossmann, I.E. (2004) Retrospective on optimization. Computers and Chemical Engineering 28(8):1169-1192.

Boender, C.G.E., Rinnooy Kan, A.H.G., Timmer, G.T., and Stougie, L. (1982). A Stochastic Method for Global Optimization. Mathematical Programming, 22, 125-140.

Carrasco, E.F. and J. R. Banga (1998) A hybrid method for the optimal control of chemical processes. IEE Conf. Publ. 455(2):925-930.

Chachuat, B., Singer, A.B., Barton, P.I. (2006) Global methods for dynamic optimization and mixed-integer dynamic optimization. Industrial and Engineering Chemistry Research 45 (25):8373-8392.

Csendes, T. (1988). Nonlinear parameter estimation by global optimization. Efficiency and reliability. Acta Cybernetica, 8, 361-370.

Edgar, T.F., Himmelblau, D.M., and Lasdon, L.S. (2001). Optimization of Chemical Processes. McGraw Hill, Boston.

Esposito WR, Floudas CA. (2000) Deterministic global optimization in nonlinear optimal control problems. J Global Optim. 17:97-126

Fletcher, R. and Leyffer, S. (2002). Nonlinear Programming without a Penalty Function. Mathemtaical Programming, 91, 239-269.

Floudas, C.A. (2005) Research challenges, opportunities and synergism in systems engineering and computational biology. AIChE Journal 51(7):1872-1884.

Floudas, C.A., Akrotirianakis, I.G., Caratzoulas, S., Meyer, C.A., Kallrath, J. (2005) Global optimization in the 21st century: Advances and challenges. Computers and Chemical Engineering 29:1185-1202.

Gill, P.E., Murray, W., and Wright, M.H. (1981). Practical Optimization. Academic Press, New York.

Grossmann, I.E., Biegler, L.T. (2004) Part II. Future perspective on optimization. Computers and Chemical Engineering 28(8):1193-1218.

Guus, C.; Boender, E.; Romeijn, H. E. (1995) Stochastic methods. In Handbook of global optimization, ed.; Horst, R.; Pardalos, P. M. (eds.) Kluwer Academic Publishers: Dordrecht.

Huyer, W. (2004). A comparison of some algorithms for bound constrained global optimization. Technical report. University of Vienna. Available at http://www.mat.univie.ac.at/~neum/glopt/contrib/compbound.pdf

Katare, S., Bhan, A., Caruthers, J.M., Delgass, W.N., Venkatasubramanian, V. (2004) A hybrid genetic algorithm for efficient parameter estimation of large kinetic models. Computers and Chemical Engineering 28(12):2569-2581

Khompatraporn, C., Pinter, J.D., Zabinsky, Z.B. (2005) Comparative assessment of algorithms and software for global optimization. Journal of Global Optimization 31(4):613-633.

Klepeis, J.L., Pieja, M.J., Floudas, C.A. (2003) Hybrid global optimization algorithms for protein structure prediction: Alternating hybrids. Biophysical Journal 84 (2 I), pp. 869-882

Locatelli, M. and Schoen, F. (1999). Random Linkage: a Family of Acceptance/Rejection Algorithms for Global Optimization. Mathematical Programming, 85, 379-396.

Marín-Sanguino, A. and Torres, N.V. (2000). Optimization of Tryptophan Production in Bacteria. Design of a Strategy for Genetic Manipulation of the Tryptophan Operan for Tryptophan Flux Maximization. Biotechnology Progress, 16(2), 133-145.

Moles, C.G., Gutierrez, G., Alonso, A.A. and Banga, J.R. (2003). Integrated Process Design and Control via Global Optimization: a Wastewater Treatment Plant Case Study. Chemical Engineering Research & Design, 81, 507-517.

Mongeau, M., Karsenty, H., Rouzé, V., and Hiriart-Urruty, J.-B. (1998). A comparison of public-domain software for black box global optimization. Technical report LAO 98-01, Universit’e Paul Sabatier, Toulouse, France.

Papamichail I, Adjiman CS (2004) Global optimization of dynamic systems. Comput Chem Eng. 28:403-415.

Papamichail I, Adjiman CS. (2002) A rigorous global optimization algorithm for problems with ordinary differential equations. J Global Optim. 24:1-33.

Renders, J.-M., Flasse, S.P. (1996) Hybrid methods using genetic algorithms for global optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 26(2):243-258.

Rinnooy Kan, A.H.G. and Timmer, G.T. (1987a). Stochastic Global Optimization Methods, Part I: Clustering Methods. Mathematical Programming, 39, 27-56.

Rinnooy Kan, A.H.G. and Timmer, G.T. (1987b). Stochastic Global Optimization Methods, Part II: Multi Level Methods. Mathematical Programming, 39, 57-78.

Runarsson, T.P. and Yao, X. (2000). Stochastic Ranking for Constrained Evolutionary Optimization. IEEE Trans. Evol. Comput, 4, 287-294.

Sahinidis, N.V., Tawarmalani, M. (2000) Applications of global optimization to process and molecular design. Computers and Chemical Engineering 24(9-10):2157-2169.

Singer AB, Barton PI. (2006) Global optimization with nonlinear ordinary differential equations. J Global Optim. 34:159-190.

Timmer, G.T. (1984). Global Optimization: a Stochastic Approach. Ph.D. Thesis, Erasmus University, Rotterdam.

Törn, M.,M. Ali and S. Viitanen (1999) Stochastic Global Optimization: Problem Classes and Solution Techniques. Journal of Global Optimization, 14, 437-447.

Ye, Y. (1989). SOLNP Users’ Guide – A Nonlinear Optimization Program in MATLAB. University of Iowa.

Appendix I

Multistart UNIRANDI vs. Multistart Filter-UNIRANDI

If UNIRANDI is selected as the local solver (e.g. for problems involving a non-smooth objective function), the penalty weight has to be adjusted so that the final solution is feasible. In order to overcome this drawback, we have tested the new implementation of this solver which incorporates the filter approach.

For each of the problems, a set of 100 initial points was randomly generated within the bounds and these sets were used by both algorithms. Filter-UNIRANDI was applied with two values of the parameter max_ndir. The probability prob_pf of using a point from the Filter to generate trial points is fixed at 1.

As it is shown in Table A1 and the histograms of solutions depicted in Figures A1 to A8, the Filter-UNIRANDI algorithm is more robust than the original method in the sense that there are more points from which the solver converges to the vicinity of the global minimum. This is in part a consequence of using the filter as a criterion to decide when to change the step length, since as long as new points enter the filter more search directions are tried. In this regard, it can be seen that increasing the value of the parameter max_ndir does not improve significantly the results (only a slight improvement in the median value is observed, but with an excessive increase in the mean number of function evaluations).

The key feature is the generation of trial points around infeasible points to explore other regions of the search space, which allows the solver to escape from local minima. The histograms of solutions shown in Figures A1 to A8 illustrate clearly the benefits of this approach.

Table A1. Comparison between Multistart UNIRANDI and Multistart Filter-UNIRANDI

Figure A1. Histogram of solutions for the problem TRP obtained using UNIRANDI.

Figure A2. Histogram of solutions for the problem TRP obtained using Filter-UNIRANDI (max_ndir = 3 and rtol_dom = 10^-3).

Figure A3. Histogram of solutions for the problem FPD obtained using UNIRANDI.

Figure A4. Histogram of solutions for the problem FPD obtained using Filter-UNIRANDI (max_ndir = 3 and rtol_dom = 10^-3).