ΑΒΒ explained

αΒΒ 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

Let a function

{f(\boldsymbol{x})\inC^2}

be a function of general non-linear non-convex structure, defined in a finite box

X=\{\boldsymbol{x}\inR^{n:\boldsymbol{x}}^{L\leq\boldsymbol{x}\leq\boldsymbol{x}}^U\}

.Then, a convex underestimation (relaxation)

L(\boldsymbol{x})

of this function can be constructed over

by superposing a sum of univariate quadratics, each of sufficient magnitude to overcome the non-convexity of

{f(\boldsymbol{x})}

everywhere in

, as follows:

	i=n
L(\boldsymbol{x})=f(\boldsymbol{x})+\sum
	i=1

\alpha_i(x

	L

	i

-x_i)(x

	U

	i

-x_i)

L(\boldsymbol{x})

is called the

\alphaBB

underestimator for general functional forms. If all

\alpha_i

are sufficiently large, the new function

L(\boldsymbol{x})

is convex everywhere in

. Thus, local minimization of

L(\boldsymbol{x})

yields a rigorous lower bound on the value of

{f(\boldsymbol{x})}

in that domain.

Calculation of

\boldsymbol{\alpha}

There are numerous methods to calculate the values of the

\boldsymbol{\alpha}

vector.It is proven that when

\alpha

i=max\{0,-	1
	2

	min
λ
	i

, where

	min
λ
	i

is a valid lower bound on the

-th eigenvalue of the Hessian matrix of

{f(\boldsymbol{x})}

, the

L(\boldsymbol{x})

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

H(X)

be the interval Hessian matrix of

{f(X)}

over the interval

. Then,

\foralld_i>0

a valid lower bound on eigenvalue

λ_i

may be derived from the

-th row of

H(X)

as follows:

	min
λ
	i

=\underline{h_ii

}-\sum_(\max(|\underline|,|\overline|\frac)

Notes and References

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