Abstract This study focuses on exhaustive global optimization algorithms over a simplicial feasible set with simplicial partition sets. Bounds on the objective function value and its partial derivative are based on interval automatic differentiation over the interval hull of a simplex. A monotonicity test may be used to decide to either reject a simplicial partition set or to reduce its simplicial dimension to a relative border (at the boundary of the feasible set) facet (or face) by removing one (or more) vertices. A monotonicity test is more complicated for a simplicial sub-set than for a box, because its orientation does not coincide with the components of the gradient. However, one can focus on directional derivatives (DD). In a previous study, we focused on either basic directions, such as centroid to vertex or vertex to vertex directions, or finding the best directional derivative by solving an LP or MIP. The research question of this paper refers to using local search (LS) based sampling of directions from vertex to facet. Results show that most of the monotonic DD found by LP are also found by LS, but with much less computational cost. Notice that finding a monotone direction does not require to find the direction in which a derivative bound is the steepest.

Abstract Branch and Bound (B&B) algorithms in Global Optimization are used to perform an exhaustive search over the feasible area. One choice is to use simplicial partition sets. Obtaining sharp and cheap bounds of the objective function over a simplex is very important in the construction of efficient Global Optimization B&B algorithms. Although enclosing a simplex in a box implies an overestimation, boxes are more natural when dealing with individual coordinate bounds, and bounding ranges with Interval Arithmetic (IA) is computationally cheap. This paper introduces several linear relaxations using gradient information and Affine Arithmetic and experimentally studies their efficiency compared to traditional lower bounds obtained by natural and centered IA forms and their adaption to simplices. A Global Optimization B&B algorithm with monotonicity test over a simplex is used to compare their efficiency over a set of low dimensional test problems with instances that either have a box constrained search region or where the feasible set is a simplex. Numerical results show that it is possible to obtain tight lower bounds over simplicial subsets.

The aim of this work is to study the Simplex Cover (SC) problem, which is to determine whether a given simplex is covered by spheres centered at its vertices. We show that the SC problem is equivalent to a global optimization problem. We investigate its characteristics.

Characterization of trajectory structure of fitness landscapes is a major problem of evolutionary computation theory. In this paper a hardness measure of fitness landscapes is introduced which is based on statistical properties of trajectories. These properties are approximated with the help of a heuristic based on the transition probabilities between the elements of the search space. This makes it possible to compute the measure for some well-known functions: a ridge function, a long path function, a fully deceptive function and a combinatorial problem: the subset sum problem. Using the same transition probabilities the expected number of evaluations needed to reach the global optimum from any point in the space are approximated and examined for the above problems.