<commit_before># BiteOpt - Stochastic Function Optimizer #

## Contents ##

* [Introduction](#introduction)
* [Comparison](#comparison)
* [Notes](#notes)
* [CBiteOpt (biteopt.h)](#cbiteopt-biteopth)
* [CBiteOptDeep (biteopt.h)](#cbiteoptdeep-biteopth)
* [Limitations](#limitations)
* [Constraint programming](#constraint-programming)
* [Convergence proof](#convergence-proof)
* [Tested uses](#tested-uses)
* [Examples](#examples)
* [Users](#users)
* [Method description](#method-description)

## Introduction ##

BITEOPT is a free open-source stochastic non-linear bound-constrained
derivative-free optimization strategy. The name "BiteOpt" is an acronym for
"BITmask Evolution OPTimization".

The benefit of this strategy 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 strategies, this strategy requires optimization attempts
with different random seeds. The stochastic nature of the method allows it to
automatically "fall" into different competing minima with each run. If there
are no competing minima in a function (or the true/global minimum is rogue and
cannot be detected), this strategy in absolute majority of runs will return
the same optimum.

## Comparison ##

This "black-box" strategy was tested on 400+ 1-10 dimensional optimization
problems and performed well, and it successfully solves even 600-dimensional
test problems found in some books. Due to its design this strategy may be
particularly good at improving an existing sub-optimal local solution.

This strategy was compared with the results of this paper (on 241 published C
non-convex problems, convex problems were not evaluated): [Comparison of derivative-free optimization algorithms](http://archimedes.cheme.cmu.edu/?q=dfocomp)
This strategy was able to solve 78% of non-convex problems in 10 attempts, 2500
iterations each. For 1-2 dimensional problems, this strategy's success rate is
99%. For 3-9 dimensional problems the success rate is 70%, for 10-30
dimensional problems the success rate is 86%, for >30 dimensional problems the
success rate is 38%. With a huge iteration budget (1 million) this strategy
solves 93% of problems (CBiteOptDeep solves 95% with M=25). On a comparable
test function suite and conditions outlined at this page:
[global_optimization](http://infinity77.net/global_optimization/multidimensional.html)
(excluding several ill-defined and overly simple functions, and including
several complex functions, use test2.cpp to run the test) this strategy's
success rate is >91% while the average number of objective function
evaluations is ~340.

## Notes ##

Strategy's hyper-parameters (probabilities) were pre-selected and should not
be changed.

It is usually necessary to run the optimization process several times with
different random seeds since the process may get stuck in a local minimum.
Running 10 times is a minimal general requirement. This strategy is hugely
probabilistic and it depends on its initial state, which is selected randomly.
In most cases it is more efficient to rerun the optimization with a new random
seed than to wait for the optimization process to converge. Based on the
results of optimization of the test corpus, for 2-dimensional functions it is
reasonable to expect convergence in 1000 iterations (in a successful attempt),
for 10-dimensional functions it is reasonable to expect convergence in 5000
iterations (harder functions may require more iterations to converge). Most
classic 2-dimensional problems converge in 400 iterations or less, at 1e-6
precision.

## CBiteOpt (biteopt.h) ##

BiteOpt stochastic optimization class. Implements a stochastic non-linear
bound-constrained derivative-free optimization strategy. It maintains a
cost-ordered population list of previously evaluated solutions that are
evolved towards a lower cost. 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 strategy to space solution vectors apart
from each other thus making them cover a larger parameter search space
collectively. Beside that, parameter randomization and the "step in the
right direction" operation are used that move the solutions into position
with a probabilistically lower objective function value.

## CBiteOptDeep (biteopt.h) ##

Deep stochastic optimization class. Based on an array of M CBiteOpt
objects. This "deep" strategy pushes the newly-obtained solution to the
next CBiteOpt object which is then optimized. This strategy while
increasing the convergence time by a factor of about sqrt(M) is able to
solve even the most noisy non-linear functions.

This strategy is most effective on stochastic functions or functions with
huge fluctuations near the global solution that are not very expensive to
calculate and that have a large iteration budget. Tests have shown that on
smooth functions that have many strongly competing minima this strategy
increases the chance to find a global solution by a factor of sqrt(M)
relative to the CBiteOpt class, but still requires several runs at
different random seeds. However, the number of required runs in most cases
is lower by about sqrt(M). So, in many cases it's more efficient to
increase the iteration budget by a factor of sqrt(M) which will in turn
increase the chance to find a global optimum by a factor of sqrt(M) and
also reduce the number of optimization attempts by the same number.  In
practice, the chance to find a global optimum is increased even more
considerably with this "deep" strategy.

## Limitations ##

The required number of optimization attempts is usually proportional to the
number of strongly competing minima in a function. Rogue optimums may not be
found by this strategy. A rogue optimum is an optimum that has a very small,
almost undetectable area of descent and is placed apart from other competing
minima. The strategy favors minimum with a larger area of descent. The
Damavandi test function is a perfect example of the limitation of this
strategy (this test function is solved by this strategy, but requires a lot
of iterations). In practice, however, rogue optimums can be considered as
undesired outliers that rely on unstable parameter values (if such parameters
are used in real-world system that has a certain parameter value precison, a
system may leave the "rogue" optimal regime easily).

To some degree this strategy is immune to noise in the objective function.
While this strategy was designed to be applied to continuous functions, it is
also immune to discontinuities to some degree, and it can solve problems that
utilize parameter value rounding (integer parameters). This strategy can't
acceptably solve high-dimensional problems that are implicitly or explicitly
combinatorial (e.g. Perm and Lennard-Jones atom clustering problems). Also
problems with many competing minima without a pronounced global descent
towards global minimum (e.g. Bukin N.6 problem) may not be solved acceptably
as in most cases they require exhaustive search.

## Constraint programming ##

Mixed integer programming can be achieved by using rounded parameter values in
the objective function while value constraints can be implemented as
penalties, in this way: constraint c1:x1+2.0\*x2-3.0\*x3<=0 can be used to
adjust objective function value: cost+=(c1<=0?0:100000+c1*9999), with 100000
penalty base and 9999 constraint scale chosen to assure no interaction with the
expected "normal" objective function values while providing a useful gradient.
Note that if the solution's value is equal or higher than the penalty base
it means either a feasible solution was not found or the chosen constraint
scale does not generate a useful gradient. See constr.cpp for an example of
constraint programming. constr2.cpp is an example of non-linear constraint
programming with both non-equalities and equalities.

The minimal and maximal allowed parameter values (bounds) should be specified
in a way to cover a wider value range, in order to reduce boundary effects
that may reduce convergence. It maybe beneficial to specify bounds in a way so
that the expected optimum is located at the center of the search space.

## Convergence proof ##

Considering the structure of the strategy and the fact that on every
iteration only improving solutions are accepted into the population, with ever
decreasing upper bound on the objective function value, it is logically
impossible for the strategy to be divergent.

## Tested uses ##

This optimization strategy was tested for the following applications beside
synthetic benchmarking:

1. Hyperparameter optimization of complex non-linear black-box systems.<commit_msg>Fixed some typos in the readme file.<commit_after># BiteOpt - Stochastic Function Optimizer #

## Contents ##

* [Introduction](#introduction)
* [Comparison](#comparison)
* [Notes](#notes)
* [CBiteOpt (biteopt.h)](#cbiteopt-biteopth)
* [CBiteOptDeep (biteopt.h)](#cbiteoptdeep-biteopth)
* [Limitations](#limitations)
* [Constraint programming](#constraint-programming)
* [Convergence proof](#convergence-proof)
* [Tested uses](#tested-uses)
* [Examples](#examples)
* [Users](#users)
* [Method description](#method-description)

## Introduction ##

BITEOPT is a free open-source stochastic non-linear bound-constrained
derivative-free optimization strategy. The name "BiteOpt" is an acronym for
"BITmask Evolution OPTimization".

The benefit of this strategy 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 strategies, this strategy requires optimization attempts
with different random seeds. The stochastic nature of the method allows it to
automatically "fall" into different competing minima with each run. If there
are no competing minima in a function (or the true/global minimum is rogue and
cannot be detected), this strategy in absolute majority of runs will return
the same optimum.

## Comparison ##

This "black-box" strategy was tested on 400+ 1-10 dimensional optimization
problems and performed well, and it successfully solves even 600-dimensional
test problems found in some books. Due to its design this strategy may be
particularly good at improving an existing sub-optimal local solution.

This strategy was compared with the results of this paper (on 241 published C
non-convex problems, convex problems were not evaluated): [Comparison of derivative-free optimization algorithms](http://archimedes.cheme.cmu.edu/?q=dfocomp)
This strategy was able to solve 78% of non-convex problems in 10 attempts, 2500
iterations each. For 1-2 dimensional problems, this strategy's success rate is
99%. For 3-9 dimensional problems the success rate is 70%, for 10-30
dimensional problems the success rate is 86%, for >30 dimensional problems the
success rate is 38%. With a huge iteration budget (1 million) this strategy
solves 93% of problems (CBiteOptDeep solves 95% with M=25). On a comparable
test function suite and conditions outlined at this page:
[global_optimization](http://infinity77.net/global_optimization/multidimensional.html)
(excluding several ill-defined and overly simple functions, and including
several complex functions, use test2.cpp to run the test) this strategy's
success rate is >91% while the average number of objective function
evaluations is ~340.

## Notes ##

Strategy's hyper-parameters (probabilities) were pre-selected and should not
be changed.

It is usually necessary to run the optimization process several times with
different random seeds since the process may get stuck in a local minimum.
Running 10 times is a minimal general requirement. This strategy is hugely
probabilistic and it depends on its initial state, which is selected randomly.
In most cases it is more efficient to rerun the optimization with a new random
seed than to wait for the optimization process to converge. Based on the
results of optimization of the test corpus, for 2-dimensional functions it is
reasonable to expect convergence in 1000 iterations (in a successful attempt),
for 10-dimensional functions it is reasonable to expect convergence in 5000
iterations (harder functions may require more iterations to converge). Most
classic 2-dimensional problems converge in 400 iterations or less, at 1e-6
precision.

## CBiteOpt (biteopt.h) ##

BiteOpt stochastic optimization class. Implements a stochastic non-linear
bound-constrained derivative-free optimization strategy. It maintains a
cost-ordered population list of previously evaluated solutions that are
evolved towards a lower cost. 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 strategy to space solution vectors apart
from each other thus making them cover a larger parameter search space
collectively. Beside that, parameter randomization and the "step in the
right direction" operation are used that move the solutions into position
with a probabilistically lower objective function value.

## CBiteOptDeep (biteopt.h) ##

Deep stochastic optimization class. Based on an array of M CBiteOpt
objects. This "deep" strategy pushes the newly-obtained solution to the
next CBiteOpt object which is then optimized. This strategy while
increasing the convergence time by a factor of about sqrt(M) is able to
solve even a very noisy non-linear functions.

This strategy is most effective on stochastic functions or functions with
huge fluctuations near the global solution that are not very expensive to
calculate and that have a large iteration budget. Tests have shown that on
smooth functions that have many strongly competing minima this strategy
increases the chance to find a global solution by a factor of sqrt(M)
relative to the CBiteOpt class, but still requires several runs at
different random seeds. However, the number of required runs in most cases
is lower by about sqrt(M). So, in many cases it's more efficient to
increase the iteration budget by a factor of sqrt(M) which will in turn
increase the chance to find a global optimum by a factor of sqrt(M) and
also reduce the number of optimization attempts by the same number.  In
practice, the chance to find a global optimum is increased even more
considerably with this "deep" strategy.

## Limitations ##

The required number of optimization attempts is usually proportional to the
number of strongly competing minima in a function. Rogue optimums may not be
found by this strategy. A rogue optimum is an optimum that has a very small,
almost undetectable area of descent and is placed apart from other competing
minima. The strategy favors minimum with a larger area of descent. The
Damavandi test function is a perfect example of the limitation of this
strategy (this test function is solved by this strategy, but requires a lot
of iterations). In practice, however, rogue optimums can be considered as
undesired outliers that rely on unstable parameter values (if such parameters
are used in real-world system that has a certain parameter value precision, a
system may leave the "rogue" optimal regime easily).

To some degree this strategy is immune to noise in the objective function.
While this strategy was designed to be applied to continuous functions, it is
also immune to discontinuities to some degree, and it can solve problems that
utilize parameter value rounding (integer parameters). This strategy can't
acceptably solve high-dimensional problems that are implicitly or explicitly
combinatorial (e.g. Perm and Lennard-Jones atom clustering problems). Also
problems with many competing minima without a pronounced global descent
towards global minimum (e.g. Bukin N.6 problem) may not be solved acceptably
as in most cases they require exhaustive search.

## Constraint programming ##

Mixed integer programming can be achieved by using rounded parameter values in
the objective function while value constraints can be implemented as
penalties, in this way: constraint c1:x1+2.0\*x2-3.0\*x3<=0 can be used to
adjust objective function value: cost+=(c1<=0?0:100000+c1*9999), with 100000
penalty base and 9999 constraint scale chosen to assure no interaction with the
expected "normal" objective function values while providing a useful gradient.
Note that if the solution's value is equal to or higher than the penalty base
it means either a feasible solution was not found or the chosen constraint
scale does not generate a useful gradient. See constr.cpp for an example of
constraint programming. constr2.cpp is an example of non-linear constraint
programming with both non-equalities and equalities.

The minimal and maximal allowed parameter values (bounds) should be specified
in a way to cover a wider value range, in order to reduce boundary effects
that may reduce convergence. It may be beneficial to specify bounds in a way
so that the expected optimum is located at the center of the search space.

## Convergence proof ##

Considering the structure of the strategy and the fact that on every
iteration only improving solutions are accepted into the population, with ever
decreasing upper bound on the objective function value, it is logically
impossible for the strategy to be divergent.

## Tested uses ##

This optimization strategy was tested for the following applications beside
synthetic benchmarking:

1. Hyperparameter optimization of complex non-linear black-box systems.
{'fraction_non_alphanumeric': 0.044606154871680924, 'fraction_numerical': 0.011998666814798355, 'mean_word_length': 5.1359918200409, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '549507', 'n_tokens_mistral': 4531, 'n_tokens_neox': 4048, 'n_words': 2549}