In this paper, we introduce a new effective matrix adaptation evolution strategy
(MADFO) for noisy derivative-free optimization problems. Like every MAES solver,
MADFO consists of three phases: mutation, selection and recombination. MADFO
improves the mutation phase by generating good step sizes, neither too small not
too large, that increase the probability of selecting mutation points with small inexact
function values in the selection phase. In the recombination phase, a recombination
point with lowest inexact function value found among all evaluated points so far may
be found by a new randomized non-monotone line search method and accepted as
the best point. If no best point is found, a heuristic point may be accepted as the best
point. We compare MADFO with state-of-the-art DFO solvers on noisy test problems
obtained by adding various kinds and levels of noise to all unconstrained CUTEst
test problems with dimensions n ≤ 20, and find that MADFO has the highest number
of solved problems
AbstractFor the unconstrained optimization of black box functions, this paper introduces a new randomized algorithm called . In practice, matches the quality of other state-of-the-art algorithms for finding, in small and large dimensions, a local minimizer with reasonable accuracy. Although our theory guarantees only local minimizers our heuristic techniques turn into an efficient global solver. In very thorough numerical experiments, we found in most cases either a global minimizer, or where this could not be checked, at least a point of similar quality to the best competitive global solvers. For smooth, everywhere defined functions, it is proved that, with probability arbitrarily close to 1, a basic version of our algorithm finds with function evaluations a point whose unknown exact gradient 2-norm is below a given threshold, where n is the dimension. In the smooth convex case, this number improves to and in the smooth (strongly) convex case to. This matches known recent complexity results for reaching a slightly different goal, namely the expected unknown exact gradient 2-norm is below a given threshold. Numerical results show that is effective and robust in comparison with the state-of-the-art local and global solvers on the unconstrained test problems of Gould et al. (Comput Optim Appl 60:545–557, 2014) for optimization and the test problems of Jamil and Yang (Int J Math Model Numer Optim 4:150, 2013) for global optimization with 2–5000 variables.
AbstractRecently, Neumaier and Azmi gave a comprehensive convergence theory for a generic algorithm for bound constrained optimization problems with a continuously differentiable objective function. The algorithm combines an active set strategy with a gradient-free line search along a piecewise linear search path defined by directions chosen to reduce zigzagging. This paper describes , an efficient implementation of this scheme. It employs new limited memory techniques for computing the search directions, improves by adding various safeguards relevant when finite precision arithmetic is used, and adds many practical enhancements in other details. The paper compares and several other solvers on the unconstrained and bound constrained problems from the collection and makes recommendations on which solver to use and when. Depending on the problem class, the problem dimension, and the precise goal, the best solvers are and .
MATRS: heuristic methods for noisy derivative-free bound-constrained mixed-integer optimization
(2025)
This paper introduces MATRS, a novel matrix adaptation trust-region strategy designed
to solve noisy derivative-free mixed-integer optimization problems with simple bounds
in low dimensions. MATRS operates through a repeated cycle of five phases: mutation,
selection, recombination, trust-region, and mixed-integer, executed in this sequence.
But if in the mutation phase a new best point (the point with the lowest inexact function
value among all evaluated points so far) is found, the selection, recombination, and
trust-region phases are skipped. Similarly, if the recombination phase finds a new best
point, the trust-region phase is skipped. The mixed-integer phase is always performed.
To search for a new best point, the mutation and recombination phases use extrapolation whereas the mixed-integer phase performs a mixed-integer line search along directionsn estimated to go into a valley. Numerical results on several collections of test problems show that MATRS is competitive with state-of-the-art derivative-free mixedinteger solvers.