In this work, we propose a new underestimator in branch and bound algorithm for solving univariate global optimization problems. The new underestimator is a combination of two underestimators, the classical one used in αBB method (see Androulakis et al. [J. Glob. Optim. 7 (1995) 337–3637]) and the quadratic underestimator developed in Hoai An and Ouanes [RAIRO: OR 40 (2006) 285–302]. We show that the new underestimator is tighter than the two underestimators. A convex/concave test is used to accelerate the convergence of the proposed algorithm. The convergence of our algorithm is shown and a set of test problems given in Casado et al. [J. Glob. Optim. 25 (2003) 345–362] are solved efficiently.
Mots clés : Global optimization, αBB method, quadratic underestimator, Branch and Bound
@article{RO_2018__52_1_177_0,
author = {Ouanes, Mohand and Chebbah, Mohammed and Zidna, Ahmed},
title = {Combination of two underestimators for univariate global optimization},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {177--186},
publisher = {EDP-Sciences},
volume = {52},
number = {1},
year = {2018},
doi = {10.1051/ro/2018013},
mrnumber = {3812475},
zbl = {1397.65090},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2018013/}
}
TY - JOUR AU - Ouanes, Mohand AU - Chebbah, Mohammed AU - Zidna, Ahmed TI - Combination of two underestimators for univariate global optimization JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 177 EP - 186 VL - 52 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2018013/ DO - 10.1051/ro/2018013 LA - en ID - RO_2018__52_1_177_0 ER -
%0 Journal Article %A Ouanes, Mohand %A Chebbah, Mohammed %A Zidna, Ahmed %T Combination of two underestimators for univariate global optimization %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 177-186 %V 52 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2018013/ %R 10.1051/ro/2018013 %G en %F RO_2018__52_1_177_0
Ouanes, Mohand; Chebbah, Mohammed; Zidna, Ahmed. Combination of two underestimators for univariate global optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 1, pp. 177-186. doi : 10.1051/ro/2018013. http://www.numdam.org/articles/10.1051/ro/2018013/
[1] , and , A global optimization method, αBB, for general twice-differentiable constrained NLPs II. Implementation and computational results. Comput. Chem. Eng. 22 (1998) 1159–1179. | DOI
[2] , , and , A global optimization method, αBB, for general twice-differentiable constrained NLPs I theoretical advances. Comput. Chem. Eng. 22 (1998) 1137–1158. | DOI
[3] , and , αBB: A global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7 (1995) 337–363. | DOI | MR | Zbl
[4] , , and , New interval analysis support functions using gradient information in a global minimization algorithm. J. Glob. Optim. 25 (2003) 345–362. | DOI | MR | Zbl
[5] , A Practical Method Guide to Splines. Applied Mathematical Sciences. Springer Verlag (1978). | DOI | MR | Zbl
[6] and , A review of recent advances in global optimization. J. Glob. Optim. 45 (2009) 3–38. | DOI | MR | Zbl
[7] and , Tight convex underestimator for C2-continuous problems: I. Univariate functions. J. Glob. Optim. 42 (2008) 51–67. | DOI | MR | Zbl
[8] and , Tight convex underestimators for C2-continuous problems: II. Multivariate functions. J. Glob. Optim. 42 (2008) 69–89. | DOI | MR | Zbl
[9] and , Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint. RAIRO: OR 40 (2006) 285–302. | DOI | Numdam | MR | Zbl
[10] and , An information global minimization algorithm using the local improvement technique. J. Glob. Optim. 48 (2010) 99–112. | DOI | MR | Zbl
[11] and , Finite exact Branch-and-Bound algorithms for concave minimization over polytopes. J. Glob. Optim. 18 (2000) 107–128. | DOI | MR | Zbl
[12] , , and , New quadratic lower bound for multivariate functions in global optimization. Math. Comput. Simul. 109 (2015) 197–211. | DOI | MR | Zbl
[13] and , Optimal centers in branch-and-prune algorithms for univariate global optimization. Appl. Math. Comput. 169 (2005) 247–277. | MR | Zbl
Cité par Sources :
