On the Convergence of Adaptive Stochastic Search Methods for Constrained and Multi-objective Black-Box Optimization

详细信息    查看全文

• 作者：Rommel G. Regis
• 关键词：Constrained optimization ; Multi ; objective optimization ; Random search ; Convergence ; Evolutionary programming ; 65K05 ; 90C29
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：170
• 期：3
• 页码：932-959
• 全文大小：574 KB
• 参考文献：1.Baba, N.: Convergence of a random optimization method for constrained optimization problems. J. Optim. Theory Appl. 33(4), 451–461 (1981)MathSciNet CrossRef MATH
  2.Price, W.L.: Global optimization by controlled random search. J. Optim. Theory Appl. 40(3), 333–348 (1983)MathSciNet CrossRef MATH
  3.Fonseca, C.M., Fleming, P.J.: Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. In: Forrest, S. (ed.) Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 416–423. Morgan Kaufmann, San Mateo, CA (1993)
  4.Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)CrossRef
  5.Solis, F.J., Wets, R.J.B.: Minimization by random search techniques. Math. Oper. Res. 6(1), 19–30 (1981)MathSciNet CrossRef MATH
  6.Pinter, J.D.: Global Optimization in Action. Kluwer Academic Publishers, Dordrecht (1996)CrossRef MATH
  7.Stephens, C.P., Baritompa, W.: Global optimization requires global information. J. Optim. Theory Appl. 96(3), 575–588 (1998)MathSciNet CrossRef MATH
  8.Spall, J.C.: Introduction to Stochastic Search and Optimization. Wiley, New Jersey (2003)CrossRef MATH
  9.Zabinsky, Z.B.: Stochastic Adaptive Search in Global Optimization. Springer US, New York (2003). http://​www.​springer.​com/​us/​book/​9781402075261?​cm_​mmc=​sgw-_​-ps-_​-book-_​-1-4020-7526-X
  10.Birbil, S., Fang, S.C., Sheu, R.L.: On the convergence of a population-based global optimization algorithm. J. Global Optim. 30(2–3), 301–318 (2004)MathSciNet CrossRef MATH
  11.Pinter, J.D.: Convergence properties of stochastic optimization procedures. Optim. J. Math. Program. Oper. Res. 15(3), 405–427 (1984)MathSciNet MATH
  12.Baba, N., Takeda, H., Miyake, T.: Interactive multi-objective programming technique using random optimization method. Int. J. Syst. Sci. 19(1), 151–159 (1988)MathSciNet CrossRef MATH
  13.Hanne, T.: On the convergence of multiobjective evolutionary algorithms. Eur. J. Oper. Res. 117, 553–564 (1999)CrossRef MATH
  14.Rudolph, G., Agapie, A.: Convergence properties of some multi-objective evolutionary algorithms. In: Proceedings of the 2000 Congress on Evolutionary Computation (CEC 2000), vol. 2, pp. 1010–1016. IEEE, La Jolla, CA (2000)
  15.Laumanns, M., Thiele, L., Deb, K., Zitzler, E.: Combining convergence and diversity in evolutionary multiobjective optimization. Evol. Comput. 10(3), 263–282 (2002)CrossRef
  16.Schüetze, O., Laumanns, M., Coello, C.A.C., Dellnitz, M., Talbi, E.: Convergence of stochastic search algorithms to finite size pareto set approximations. J. Global Optim. 41(4), 559–577 (2008)MathSciNet CrossRef MATH
  17.Brockhoff, D.: Theoretical aspects of evolutionary multiobjective optimization. In: Auger, A., Doerr, B. (eds.) Theory of Randomized Search Heuristics: Foundations and Recent Developments, pp. 101–139. World Scientific Publishing Co., Inc., River Edge, NJ (2011). http://​dl.​acm.​org/​citation.​cfm?​id=​1996312
  18.Regis, R.G.: Convergence guarantees for generalized adaptive stochastic search methods for continuous global optimization. Eur. J. Oper. Res. 207(3), 1187–1202 (2010)MathSciNet CrossRef MATH
  19.Resnick, S.I.: A Probability Path. Birkhäuser, Boston (1999)MATH
  20.Hansen, N.: The cma evolution strategy: a comparing review. In: Lozano, J.A., Nga, P.L., Inza, I., Bengoetxea, E. (eds.) Towards a New Evolutionary Computation: Advances in Estimation of Distribution Algorithms, pp. 75–102. Springer-Verlag Berlin Heidelberg (2006). http://​www.​springer.​com/​us/​book/​9783540290063
  21.Fang, K.T., Zhang, Y.T.: Generalized Multivariate Analysis. Science Press, Springer, Beijing (1990)MATH
  22.Regis, R.G.: Evolutionary programming for high-dimensional constrained expensive black-box optimization using radial basis functions. IEEE Trans. Evol. Comput. 18(3), 326–347 (2014)CrossRef
  23.Bäck, T., Rudolph, G., Schwefel, H.-P.: Evolutionary programming and evolution strategies: similarities and differences. In: Fogel, D.B., Atmar, J.W. (eds.) Proceedings of the Second Annual Conference on Evolutionary Programming, pp. 11–22. Evolutionary Programming Society, La Jolla, CA (1993)
  24.Miettinen, K.: Nonlinear Multiobjective Optimization. Kluwer Academic Publisher, Boston, MA (1999)MATH
  25.Geoffrion, A.M.: Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22(3), 618–630 (1968)MathSciNet CrossRef MATH
  26.Soland, R.M.: Multicriteria optimization: a general characterization of efficient solutions. Decis. Sci. 10(1), 26–38 (1979)CrossRef
  27.Yu, P.L.: A class of solutions for group decision problems. Manag. Sci. 19(8), 936–946 (1973)MathSciNet CrossRef MATH
  28.Zeleny, M.: Compromise programming. In: Cochrane, J.L., Zeleny, M. (eds.) Multiple Criteria Decision Making, pp. 262–301. University of South Carolina Press, Columbia, SC (1973)
  29.Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 3rd edn. Wiley, New York (2006)CrossRef MATH
  
• 作者单位：Rommel G. Regis (1)
  
  1. Department of Mathematics, Saint Joseph’s University, Philadelphia, PA, 19131, USA
  
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operations Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878
• 卷排序：170

文摘

Stochastic search methods for global optimization and multi-objective optimization are widely used in practice, especially on problems with black-box objective and constraint functions. Although there are many theoretical results on the convergence of stochastic search methods, relatively few deal with black-box constraints and multiple black-box objectives and previous convergence analyses require feasible iterates. Moreover, some of the convergence conditions are difficult to verify for practical stochastic algorithms, and some of the theoretical results only apply to specific algorithms. First, this article presents some technical conditions that guarantee the convergence of a general class of adaptive stochastic algorithms for constrained black-box global optimization that do not require iterates to be always feasible and applies them to practical algorithms, including an evolutionary algorithm. The conditions are only required for a subsequence of the iterations and provide a recipe for making any algorithm converge to the global minimum in a probabilistic sense. Second, it uses the results for constrained optimization to derive convergence results for stochastic search methods for constrained multi-objective optimization. Keywords Constrained optimization Multi-objective optimization Random search Convergence Evolutionary programming