An Algorithm for Global Optimization Using Formula Manupulation

Affiliation(s)

Department of Computer and Information Engineering, Nippon Institute of Technology, Saitama, Japan.

Division of Integrated Sciences, J. F. Oberlin University, Tokyo, Japan.

Department of Computer and Information Engineering, Nippon Institute of Technology, Saitama, Japan.

Division of Integrated Sciences, J. F. Oberlin University, Tokyo, Japan.

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.

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.

T. Shohdohji and F. Yano, "An Algorithm for Global Optimization Using Formula Manupulation,"

References

[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.

[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.