Efficient composite heuristics for integer bound constrained noisy optimization

This paper discusses a composite algorithm for bound constrained noisy derivative-free optimization problems with integer variables. This algorithm is an integer variant of the matrix adaptation evolution strategy. An integer derivative-free line search strategy along affine scaling matrix directions is used to generate candidate points. Each affine scaling matrix direction is a product of the corresponding affine scaling matrix (adaptively determined in a heuristic way) and a direction from a positive spanning set, possibly enriched by another type of directions. If an integer derivative-free line search strategy cannot reduce the inexact function value along each weighted average of affine scaling matrix directions and its opposite direction, an integer trust region strategy is applied. The gradient of the model function is estimated by fitting and the Hessian of the model function is a symmetric matrix computed from an affine scaling matrix. The trust region subproblems are transformed into bound constrained integer triangular least squares problems, solved by a variant of Schnorr-Euchner search. Numerical results show that, compared to the state-of-the-art derivative-free integer solvers NOMAD, DFLint, and BFO, our algorithm is competitive on several collections of test problems.

Article

Download

View Efficient composite heuristics for integer bound constrained noisy optimization