<img src="other/biteopt-title-image.jpg" width="700">

BITEOPT - Derivative-Free Optimization Method

Introduction

BITEOPT is a free open-source stochastic non-linear bound-constrained derivative-free optimization method (algorithm, heuristic, or strategy) for global optimization. The name "BiteOpt" is an acronym for "BITmask Evolution OPTimization".

The benefit of this method is a relatively high robustness: it can successfully optimize a wide range of multi-dimensional test functions. Another benefit is a low convergence time which depends on the complexity of the objective function. Hard (multi-modal) problems may require many optimization attempts to reach optimum.

Instead of iterating through different "starting guesses" to find optimum like in deterministic methods, this method requires optimization attempts with different random seeds. The stochastic nature of the method allows it to automatically "fall" into different competing minima on each attempt. If there are no competing minima in a function present (or the true/global minimum is rogue and cannot be detected), this method in absolute majority of attempts returns the same optimum.

BiteOpt uses self-optimization techniques making it objective function-agnostic. In its inner workings, BiteOpt uses objective function value's ranking, and not the actual value. BiteOpt is a multi-faceted example of a "probabilistic computing" system.

Python binding is available as a part of fcmaes library

Sponsoring

If you are regularly using BiteOpt in a commercial environment, you may consider donating/sponsoring the project. Please contact the author via aleksey.vaneev@gmail.com or info@voxengo.com. A solver for AMPL NL models is available commercially.

Comparison

This "black-box" optimization method was tested on 2000+ 1- to 60-dimensional optimization problems and performed well, and it successfully solves even 600-dimensional test problems found in some textbooks. But the main focus of the method is to provide fast solutions for computationally expensive "black-box" problems of medium dimensionality (up to 60).

This method was compared with the results of this paper (on 244 published C non-convex smooth problems, convex and non-convex non-smooth problems were not evaluated): Comparison of derivative-free optimization algorithms. This method was able to solve 76% of non-convex smooth problems in 10 attempts, 2500 iterations each. It comes 2nd in the comparison on non-convex smooth problems (see Fig.9 in the paper). With a huge iteration budget (up to 1 million) this method solves 97% of problems.

On a comparable test function suite and conditions outlined at this page: global_optimization (excluding several ill-defined and overly simple functions, and including several complex functions, use test2.cpp to run the test) this method's attempt success rate is >94% (with 100% of functions solved) while the average number of objective function evaluations is ~370.

At least in these comparisons, this method performs better than plain CMA-ES which is also a well-performing stochastic optimization method. As of version 2021.1, BiteOpt's "solvability" exceeds CMA-ES on synthetic function sets that involve random coordinate axis rotations and offsets (e.g., BBOB suite). BiteOptDeep (e.g., with M=8) considerably outperforms CMA-ES in "solvability".

As a matter of sport curiosity, BiteOpt is able to solve, in reasonable time, almost all functions proposed in classic academic literature on global optimization. This is quite a feat for a derivative-free method (not to be confused with large-scale analytic and gradient-based global optimization methods). Of course, BiteOpt is capable of more than that. If you have a reference to a function (with a known solution) published in literature that BiteOpt can't solve, let the author know.

BiteOpt (state at commit 124) took 2nd place (1st by sum of ranks) in BBComp2018-1OBJ-expensive competition track. Since the time of that commit the method improved in many aspects, especially in low-dimensional convergence performance. Commit 124 can be considered as "baseline effective" version of the method (it is also maximally simple), with further commits implementing gradual improvements, but also adding more complexity.

Also, BiteOpt (state at commit 256) took 2nd place (3rd by sum of ranks) in BBComp2019-1OBJ competition track.

CBiteOpt (biteopt.h)

BiteOpt optimization class. Implements a stochastic non-linear bound-constrained derivative-free optimization method. It maintains a cost-ordered population list of previously evaluated solutions that are evolved towards a lower cost (objective function value). On every iteration, the highest-cost solution in the list can be replaced with a new solution, and the list reordered. A population of solutions allows the method to space solution vectors apart from each other thus making them cover a larger parameter search space collectively. Beside that, a range of parameter randomization and the "step in the right direction" (Differential Evolution "mutation") operations are used that move the solutions into positions with a probabilistically lower objective function value.

Since version 2021.1 BiteOpt uses a companion optimizer - SpherOpt - which works independently and provides "reference points" to BiteOpt. Such companion improves BiteOpt's convergence properties considerably, especially when the parameter space is rotated. Since version 2021.15 BiteOpt uses an additional companion optimizer - NMSeqOpt - which increases diversity of generated solutions.

Since version 2021.3 BiteOpt became a self-optimizing method not requiring any fune-tuning from the user nor the author.

CBiteOptDeep (biteopt.h)

Deep optimization class. Based on an array of M CBiteOpt objects. This "deep" method pushes the newly-obtained solution to the random CBiteOpt object which is then optimized. This method, while increasing the convergence time, is able to solve complex multi-modal functions.

This method is most effective on complex functions, possibly with noisy fluctuations near the global solution, that are not very expensive to evaluate and that have a large iteration budget. Tests have shown that on smooth functions that have many strongly competing minima this "deep" method considerably increases the chance to find a global solution, relative to the CBiteOpt class, but still requires several attempts with different random seeds. When using this method, the required iteration budget usually increases by a factor of M^0.5, but the number of required optimization attempts usually decreases. In practice, it is not always possible to predict the convergence time increase of the CBiteOptDeep class, but increase does correlate to its M parameter. For some complex functions the use of CBiteOptDeep even decreases convergence time. For sure, the CBiteOptDeep class often produces better solutions than the CBiteOpt class.

Notes

BiteOpt is a completely self-optimizing method. It does not feature user-adjustable hyper-parameters. Even population size adjustments may not be effective.

It is usually necessary to run the optimization process several times, with different random seeds, since the process may get stuck at a local minimum. Running 10 times is a minimal general requirement. The required number of optimization attempts is usually proportional to the number of strongly competing minima in a function.

This method is hugely-probabilistic, and it depends on its initial state, which is selected randomly. In most cases it is more efficient to attempt to optimize with a new random seed than to wait for the optimization process to converge. Based on the results of optimization of the test-set, for 2-dimensional functions, it is reasonable to expect convergence in 800 iterations (in a successful attempt); for 10-dimensional functions, it is reasonable to expect convergence in 8000 iterations (harder functions may require more iterations to converge). Most classic 2-dimensional problems converge in 400 iterations or less, at 10^-6 precision. On average, every doubling of dimensions requires tripling of iteration budget. Complex multi-modal problems require a magnitudes larger iteration and attempt budget.

Each attempt may generate an equally-usable candidate solution (not necessarily having the least cost), permitting the researcher to select a solution from any attempt based on his/her own considerations. In this light, it may be incorrect to assume that least-performing attempts are "wasted". In practice, least-performing attempts may give more acceptable parameter values within the search space compared to the best-performing attempts.

Note that derivative-free optimization methods in general provide "asymptotic" solutions for complex functions. Thus it is reasonable to assume that BiteOpt gives an optimal solution with some implicit tolerance factor. Given a large enough function evaluation budget, BiteOpt usually does find an optimal solution which can be cross-checked with other solvers, but a solution of a new unexplored function must be treated as "asymptotically optimal".

Also note that in some problem areas like ESA GTOP problem suite the attempt budget should be as high as 1000 or more (beside using the BiteOptDeep