Jump to content

αΒΒ

From Wikipedia, the free encyclopedia

αΒΒ is a second-order deterministic global optimization algorithm for finding the optima of general, twice continuously differentiable functions.[1][2] The algorithm is based around creating a relaxation for nonlinear functions of general form by superposing them with a quadratic of sufficient magnitude, called α, such that the resulting superposition is enough to overcome the worst-case scenario of non-convexity of the original function. Since a quadratic has a diagonal Hessian matrix, this superposition essentially adds a number to all diagonal elements of the original Hessian, such that the resulting Hessian is positive-semidefinite. Thus, the resulting relaxation is a convex function.

Theory

[edit]

Let a function be a function of general non-linear non-convex structure, defined in a finite box . Then, a convex underestimation (relaxation) of this function can be constructed over by superposing a sum of univariate quadratics, each of sufficient magnitude to overcome the non-convexity of everywhere in , as follows:

is called the underestimator for general functional forms. If all are sufficiently large, the new function is convex everywhere in . Thus, local minimization of yields a rigorous lower bound on the value of in that domain.

Calculation of

[edit]

There are numerous methods to calculate the values of the vector. It is proven that when , where is a valid lower bound on the -th eigenvalue of the Hessian matrix of , the underestimator is guaranteed to be convex.

One of the most popular methods to get these valid bounds on eigenvalues is by use of the Scaled Gerschgorin theorem. Let be the interval Hessian matrix of over the interval . Then, a valid lower bound on eigenvalue may be derived from the -th row of as follows:

References

[edit]
  1. ^ "A global optimization approach for Lennard-Jones microclusters." Journal of Chemical Physics, 1992, 97(10), 7667-7677
  2. ^ "αBB: A global optimization method for general constrained nonconvex problems." Journal of Global Optimization, 1995, 7(4), 337-363