AM  Vol.3 No.11 , November 2012
An Algorithm for Global Optimization Using Formula Manupulation
Abstract: Constrained nonlinear optimization problems are well known as very difficult problems. In this paper, we present a new algorithm for solving such problems. Our proposed algorithm combines the Branch-and-Bound algorithm and Lipschitz constant to limit the search area effectively; this is essential for solving constrained nonlinear optimization problems. We obtain a more appropriate Lipschitz constant by applying the formula manipulation system of each divided area. Therefore, we obtain a better approximate solution without using a lot of searching points. The efficiency of our proposed algorithm has been shown by the results of some numerical experiments.
Cite this paper: T. Shohdohji and F. Yano, "An Algorithm for Global Optimization Using Formula Manupulation," Applied Mathematics, Vol. 3 No. 11, 2012, pp. 1601-1606. doi: 10.4236/am.2012.311221.

[1]   T. Shohdohji, “An Algorithm for Obtaining a Global Optimum for One Variable Multi-Modal Functions (In Japanese),” Journal of the Operations Research Society of Japan, Vol. 19, No. 4, 1976, pp. 295-307.

[2]   J. Pinter, “Globally Convergent Methods for n-Dimensional Multi-Extremal Optimization,” Optimization, Vol. 17, No. 2, 1986, pp. 187-202. doi:10.1080/02331938608843118

[3]   J. Pinter, “Extended Univariate Algorithms for n-Dimensional Global Optimization,” Computing, Vol. 36, No. 12, 1986, pp. 91-103. doi:10.1007/BF02238195

[4]   J. Pinter, “Branch-and-Bound Algorithms for Solving Global Optimization Problems with Lipschitzian Structure,” Optimization, Vol. 19, No. 1, 1988, pp. 101-110. doi:10.1080/02331938808843322

[5]   A. H. G. Rinnooy Kan and G. T. Timmer, “Global Optimization,” In: G. L. Nemhauser, A. H. G. Rinnooy Kan and M. J. Todd, Eds., Handbooks in Operations Research and Management Science, Volume 1: Optimization, Elsevier Science Publishers B. V., Amsterdam, 1989, pp. 631-662.

[6]   T. Shohdohji, “Global Optimization Algorithm Using Branch-and-Bound Method,” Electrical Proceedings of the 16th International Conference on Production Research (ICPR-16), Prague, 9 July-3 August 2001.

[7]   B. O. Shubert, “A Sequential Method Seeking the Global Maximum of a Function,” SIAM Journal on Numerical Analysis, Vol. 9, No. 3, 1972, pp. 379-388. doi:10.1137/0709036

[8]   T. Shohdohji, “An Algorithm for Obtaining Global Optima for Multi-Variable Multi-Modal Functions (In Japanese),” Journal of the Operations Research Society of Japan, Vol. 20, No. 4, 1977, pp. 311-320.

[9]   T. Shohdohji and Y. Yazu, “A New Algorithm for Nonlinear Programming Problem,” Proceedings of International Workshop on Intelligent Systems Resolutions— The 8th Bellman Continuum, National Tsing-Hua University, Hsinchu, Taiwan, 11-12 December 2000, pp. 229233.

[10]   T. Ibaraki, “On the Computational Efficiency of Branchand-Bound Algorithms,” Journal of Operations Research Society of Japan, Vol. 20, No. 1, 1977, pp. 16-35.

[11]   T. Ibaraki, “Branch-and-Bound Procedure and State—Space Representation of Combinatorial Optimization Problems,” Information and Control, Vol. 36, No. 1, 1978, pp. 1-27. doi:10.1016/S0019-9958(78)90197-3

[12]   E. L. Lawler and D. E. Wood, “Branch-and-Bound Methods: A Survey,” Operations Research, Vol. 14, No. 4, 1966, pp. 699-719. doi:10.1287/opre.14.4.699

[13]   T. L. Morin and R. E. Marsten, “Branch-and-Bound Strategies for Dynamic Programming,” Operations Research, Vol. 24, No. 4, 1976, pp. 611-627. doi:10.1287/opre.24.4.611

[14]   L. C. W. Dixon and G. P. Szego, Eds., “Towards Global Optimization 2,” North-Holland Publishing Company, Amsterdam, 1978, p. 97.

[15]   A R. E. Bellman, “Dynamic Programming,” Princeton University Press, Princeton, New Jersey, 1957.