Simplicial based Global Optimization branch and bound methods require tight bounds on the objective function value. Recently, a renewed interest appears on bound calculation based on Interval Arithmetic by Karhbet and Kearfott [Reliable Comput. 25 (2017) 53–73] and on exploiting second derivative bounds by Mohand [RAIRO Oper. Res. 55 (2021) S2373–S238]. The investigated question here is how partial derivative ranges can be used to provide bounds of the objective function value over the simplex. Moreover, we provide theoretical properties of how this information can be used from a monotonicity perspective to reduce the search space in simplicial branch and bound.
Keywords: Simplex, branch and bound, derivative
@article{RO_2021__55_3_2023_0,
author = {Hendrix, Eligius M. T. and -T\'oth, Boglarka G. and Messine, Frederic and Casado, Leocadio G.},
title = {On derivative based bounding for simplicial branch and bound},
journal = {RAIRO. Operations Research},
pages = {2023--2034},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {3},
doi = {10.1051/ro/2021081},
mrnumber = {4279919},
zbl = {1471.90167},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021081/}
}
TY - JOUR AU - Hendrix, Eligius M. T. AU - -Tóth, Boglarka G. AU - Messine, Frederic AU - Casado, Leocadio G. TI - On derivative based bounding for simplicial branch and bound JO - RAIRO. Operations Research PY - 2021 SP - 2023 EP - 2034 VL - 55 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021081/ DO - 10.1051/ro/2021081 LA - en ID - RO_2021__55_3_2023_0 ER -
%0 Journal Article %A Hendrix, Eligius M. T. %A -Tóth, Boglarka G. %A Messine, Frederic %A Casado, Leocadio G. %T On derivative based bounding for simplicial branch and bound %J RAIRO. Operations Research %D 2021 %P 2023-2034 %V 55 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021081/ %R 10.1051/ro/2021081 %G en %F RO_2021__55_3_2023_0
Hendrix, Eligius M. T.; -Tóth, Boglarka G.; Messine, Frederic; Casado, Leocadio G. On derivative based bounding for simplicial branch and bound. RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 2023-2034. doi: 10.1051/ro/2021081
[1] , , , and , On the minimum number of simplex shapes in longest edge bisection refinement of a regular -simplex. Informatica 26 (2015) 17–32. | MR | Zbl | DOI
[2] , and , The semi-continuous quadratic mixture design problem: Description and branch-and-bound approach. Eur. J. Oper. Res. 191 (2008) 803–815. | MR | Zbl | DOI
[3] and , An application of Lipschitzian global optimization to product design. J. Global Optim. 1 (1991) 389–401. | MR | Zbl | DOI
[4] , and , On function monotonicity in simplicial branch and bound. AIP conference proceedings 2070 (2019) 020007–4. | DOI
[5] and , Global Optimization (Deterministic Approaches). Springer, Berlin Heidelberg (1990). | MR | Zbl | DOI
[6] and , Range bounds of functions over simplices, for branch and bound algorithms. Reliable Comput. 25 (2017) 53–73. https://interval.louisiana.edu/reliable-computing-journal. | MR
[7] and , An algorithm for global optimization of Lipschitz continuous functions. J. Optim. Theory Appl. 57 (1988) 307–323. | MR | Zbl | DOI
[8] and , Enclosure methods for multivariate differentiable functions and application to global optimization. J. Universal Comput. Sci. 4 (1998) 589–603. | MR | Zbl
[9] , Tighter bound functions for nonconvex functions over simplexes. RAIRO Oper. Res. 55 (2021) S2373–S238. | MR | Zbl | DOI
[10] and , Simplicial Global Optimization. Springer, New York (2014). | MR | Zbl | DOI
[11] , The Computation of Fixed Points and Applications. Springer, Heidelberg (1976). | MR | Zbl | DOI
Cité par Sources :
