Inductive Approach to Minimizing Algorithmically the Given Objective Function. G.B. Digo., N.B Digo

Abstract. The multidimensional global optimization problems particularity consists in its unsolvable at general case and multiextremal objective function. The situation when objective function is given algorithmically over n-dimensional parallelepiped, it satisfies the Lipschitz condition with unknown Lipschitz constant and its values reception (calculation in some point of feasible domain of optimizing parameters) requires of considerable calculating resources is considered. A priori information about Lipschitzian of objective function allows using algorithms variant from exhaustive search, in particular, bisection method, based on non-uniform covering of feasible domain and used the supposition about objective function minimum estimate existence in the feasible domain. In addition unknown constant Lipschitz estimation problem arises. The cases using global estimation of constant Lipschitz evaluating over all feasible domain and local estimations of constant Lipschitz calculating over all separated subdomains of feasible domain are considered. On basis of inductive approach possibility of alternate transition from local information to global information (and on the contrary) at adaptive estimation of local Lipschitz constants over different subsets of current partition (dividing) of search domain is suggested.

Keywords. Multidimensional global optimization, algorithmically the given objective function, bisection method, non-uniform covering of feasible domain, inductive approach, adaptive estimation of global and local Lipschitz constants.

References.

1. Orlyanskaya I.V. Current Approaches to the Construction of Global Optimization Methods Investigated in Russia, 5, 2097-2108, 2002.  http://zhurnal.ape.relarn.ru/articles/2002/189.pdf. (in Russian)

2. Batischev D.I. Searching method of optimal designing, Moscow: Sovetskoe radio. 1975. (in Russian)

3. Zhigljavsky A.A., Zilinskas A.G. Methods for finding of the global extremum, Moscow: Nauka.1991. (in Russian)

4. Evtushenko Yu. Numerical methods for finding global extreme (case of a non-uniform mesh). Computational Mathematics and Mathematical Physics, - 1971. Vol. 11, N 6, pp. 38-54. (in Russian)

5. Evtushenko Yu. and Ratkin V. (), Bisection method for global optimization, Izvestija Akademii Nauk AN USSR, Tehnicheskaya Kibernetika, - 1987. No 1, pp. 119-128 (in Russian)

6. A. Molinaro, C. Pizzuti, Ya.D. Sergeyev. Acceleration tools for diagonal information global optimization algorithms // Computational Optimization and Applications. – 2001. Vol. 18, no 1, pp. 5-26.

7. Ivakhnenko A. G., Madala H.R. Inductive learning algorithms for complex systems modeling.-London, Tokyo: CRC Press, 1994.

8. Yaroslav D. Sergeyev and Dmitri E. Kvasov. Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants // SIAM: Journal of Optimization. – 2006. Vol. 16, no 3, pp. 910-937.

9. D. R. Jones, C. D. Perttunen, and B. E. Stuckman. Lipschitzian optimization without the Lipschitz constant // Journal of Optimization Theory and Applications. – 1993. – Vol. 79, no 1, pp. 157-181.

10. Strongin R.G. Numerical Methods on Multiextremal Problems, Moscow: Nauka.1978. (in Russian)

11. Kvasov D.E. and Sergeyev Ya.D. Multidimensional global optimization algorithm based on adaptive diagonal curves. Computational Mathematics and Mathematical Physics, - 2003. Vol. 43, no 1, pp. 42–59. (in Russian)

12. Digo G.B., Digo N.B. Algorithmically given function global extremum search by the bisection methods and in the case of a non-uniform mesh: efficiency analysis // In: Proceeding of the VII International Conference “System Identification and Control Problems” SICPRO’08. Moscow, January 28-31, 2008. V.A. Trapeznikov Institute of Control Sciences/ Moscow: V.A. Trapeznikov Institute of Control Sciences, 2008. pp 512-525.