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