ONE-DIMENSIONAL GLOBAL OPTIMIZATION BASED ON STATISTICAL MODELS James M. Calvin Department of Computer and Information Science New Jersey Institute of Technology Newark, NJ 07102-1982, USA Antanas Žilinskas Institute of Mathematics and Informatics, VMU Akademijos str. 4 Vilnius, LT2600, Lithuania Abstract This paper presents a review of global optimization methods based on statistical models of multimodal functions. The theoretical and methodological aspects are emphasized. Keywords: Optimization, statistical models, convergence 1. Introduction Global optimization is one of the most important subjects for applications and at the same time one of the most difficult subjects in optimization and even computing in general. Because of the practical importance of the field and the shortage of mathematical theory (compared with local optimization theory),many heuristic methods were proposed by the experts of different applied subjects. Mathematical investigation in the field began using a standard approach of computing: a class of problems is defined by means of postulating features of an objective function and convergence of a method is investigated. A class of Lipshitz functions with known Lipshitz constant is the most popular class of functions. Special methods were investigated for minimization of concave and quadratic functions, for example. Although in many papers it is not formally emphasized, the minimax approach was used. In light of pessimistic results implying exponential complexity of the proposed algorithms, investigation of optimal algorithms became important. However, it was proved that optimal algorithms also have exponential complexity. The minimax approach can not escape exponential complexity because a broad class of multimodal functions contains pathological examples. Moreover, it became clear that in the minimax setting adaptation can not help. The first paper on a global optimization algorithm justified by arguments of average rationality was [1]. However, extension of the model used by H. Kushner to the multi-dimensional case was difficult. The model also appeared to be inappropriate for many real optimization problems because of the nondifferentiability of the sample functions. The extension of the method to smooth function models was also prevented by computational difficulties. Therefore,the development of a global optimization approach based on statistical models from the very beginning seemed difficult theoretically as well as from the point of view of algorithmic implementation. The problem of optimal algorithms became important for the statistical model approach as well as for the minimax approach. Bayesian methods were formulated by J. Mockus in [2], and further developed in [3]. In this paper we present a review of one-dimensional global optimization methods based on statistical models. In the one-dimensional case the implementation is much closer to the theoretical schema than in the multi-dimensional case. The reviews of earlier results may be found in the following publications covering broader subjects on statistical models in global optimization:[3–8]. 2. Statistical Models 3. Methods 4. Convergence 5. Convergence Rates 6. Testing and Applications ......
摘要:本文综述了基于全局优化方法的统计多通道功能模型。这个理论和方法等方面加以了强调。
1. 简介
2.统计模型
3.方法
4收敛
5收敛效率
