New Underestimator for Twice Differentiable Functions with Bounded Variables

In this article, we propose a new technique of global optimization for an optimization problem with the second derivative of the objective that is bounded function of a single variable with box constraint. The method employs a piecewise underestimation, where the former is a continuous piecewise function underestimator. The purpose of this work is to find the right value of the lower bound in a competitive time. Our method converges to the global optimum. The numerical tests show clearly the impact of our contributions.

1. A. Djamel, N. Amel, L. T. H. An and Z. Ahmed, “A modified classical algorithm ALPT4C for solving a capacitated four-index transportation problem,” Acta MathematicaVietnamica, vol. 37, no. 3, pp. 379-390.
2. A. Djamel. (2010). Comparative study between digital methods for solving a transportation problem with capacity to four indices [Online]. Available: https://goo.gl/YFdwUJ
3. A. Djamel, N. Amel, Z. Ahmed, O. Mohand and L. T. H. “An, Quadratic branch and bound with alienor method for global optimization”, in XII Global Optimization Workshop, pp. 41-44, Sept. 2014.
4. C. S. Adjiman, I. P. Androulakis and C. A. Floudas, “A global optimization method, alpha BB, for general twice differentiable NLPs – II. Implementation and computational results,” An International Journal of Computer Applications in Chemical Engineering, vol. 22, no. 9, pp. 1159-1179, 1998.
5. A, Guillez., “Alienor fractal algorithm for multivariable mnimization problems,” Mathematical and Computer Modelling, vol. 14, pp. 245-247, 1990.
6. I. G. Akrotirianakis and C. A. Floudas, “Computational experience with a new class of convex underestimators: Boxconstrained NLP problems,” Journal of Global Optimization, vol. 29, no. 3, 249-264, 2004.
7. B. Y. Cherruault, “A new method for global optimization in two dimensions,” Interntional Journal of Bio-Medical Computing, vol. 38, no. 1, pp. 71-73, 1995.
8. S. Caratzoulas and C. A. Floudas, “A trigonometric convex underestimator for the base functions in Fourier space,” Journal of Optimization Theory and Applications, vol. 124, no. 2, pp. 339-362, 2005.
9. G. C. Philippe, The Finite Element Method for Elliptic Problems, New York, NY: Elsevier, North Holland, 1979.
11. C. De Boor, A Practical Guide to Splines. New York, NY: Springer-Verlag, 1978.
12. D. Guettal and A. Ziadi, “Reducing transformation and global optimization,” Applied Mathematics and Computation, vol. 218, no. 10, pp. 5848-5860, 2012.
13. F. Leslous, P. Marthon, O. Brahim and O. Mohand, “Nonconvex optimization based on DC programming and DCA in the search of a global optimum of a nonconvex function,” Journal of the Egyptian Mathematical Society, 2015.
14. F. Messine, “Global optimization methods based on interval analysis for problem solving constraint,” Doctoral dissertation, 2010.
15. H. A. Le Thi and M. Ouanes, “Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint,” Rairo-Operations Research, vol. 40, no. 3, pp. 285-302, 2006.
16. M. Rahal and A. Ziadi, “A new extension of Piyavskii’s method to Holder functions of several variables,” Applied mathematics and Computation, vol. 197, no. 2, pp. 478-488, 2012.
17. M. Ouanes, H. A. Le Thi, T. P. Nguyen and A. Zidna, “New quadratic lower bound for multivariate functions in global optimization,” Mathematics and Computers in Simulation, vol. 109, pp. 197-211, 2015.
19. M. Ouanes, “A new approach for nonconvex SIP,” International Journal of Applied Mathematics, vol. 81, no. 3, pp. 479-486, 2012.
20. M. Ouanes, “Acomined descent gradient method and descritization method for convex SIP,” International Journal of Applied Mathematics, vol. 25, no. 4, pp. 503-513, 2012.
21. M. Ouanes, “New underestimator for multivariate global optimization with box constraints,” International Journal of Pure and Applied Mathematics, vol. 84, no. 1, pp. 73-83, 2013.
22. N. Amel, A. Djamel and O. Mohand, “An efficient algorithm for the Bernstein polynomial approach to global optimization,” in JSLAROMAD II, Tiziouzou, Algeria, Oct 28-30, 2013, pp. 16-17.
23. T. Benneouala and Y. Cherruault, “Alienor method for global optimization with a large number of variables,” Kybernetes, vol. 34, no. 7/8, pp. 1104-1111, 2005.
24. Y. Cherruault, G. Mora, Global Optimization Theory Alpha-dense Curves. Villach, Austria: Economica, 2005.
25. E. Chrysanthos, C. Gounaris, A. Floudas, C. E. Gounaris and C. A. Floudas, “Tight convex underestimators for mathcal C2 continuous problems: I. Univariate Functions,” Journal of Global Optimization, vol. 42, no. 1, pp. 51-67, 2008.
26. A. Shpak, “Global optimization in one-dimensional case using analytically defined derivatives of objective function,” Computer Science Journal of Moldova, vol. 3, no. 8, pp. 168-184, 1995.
27. D. S. Yaroslav, “A one-dimensional deterministic global minimization algorithm,” Computational Mathematics and Mathematical Physics, vol. 35, no. 5, pp. 705-717, 1995.
28. D. S. Yaroslav, “Global one-dimensional optimization using smooth auxiliary functions,” Mathematical Programming, vol. 81, no. 1, pp. 127-146, 1998.
29. S. A. Piyavskii, “An algorithm for nding the absolute extremum of a function,” USSR Computational Mathematics and Mathematical Physics, vol. 12, no. 4, pp. 57-67, 1972.
30. P. M. Pardalos, H. E. Romeijn, Handbook of Global Optimization. London, UK: Springer Science & Business Media, 2002.
31. D. Lera and Y. D. Sergeyev, “Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives,” SIAM Journal on Optimization, vol. 23, no. 1, pp. 508-529, 2013.
32. D. E. Kvasov and Y. D. Sergeyev, “A univariate global search working with a set of Lipschitz constants for the first derivative,” Optimization Letters, vol. 3, no. 2, pp. 303-318, 2009.

A. Djamel, N. Amel and O. Mohand, “New underestimator for twice differentiable functions with bounded variables,” International Journal of Applied and Physical Sciences, vol. 3, no. 1, pp. 13-19, 2017.