αΒΒ

αΒΒ 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 ${\displaystyle {f({\boldsymbol {x}})\in C^{2}}}$ be a function of general non-linear non-convex structure, defined in a finite box ${\displaystyle X=\{{\boldsymbol {x}}\in \mathbb {R} ^{n}:{\boldsymbol {x}}^{L}\leq {\boldsymbol {x}}\leq {\boldsymbol {x}}^{U}\}}$. Then, a convex underestimation (relaxation) ${\displaystyle L({\boldsymbol {x}})}$ of this function can be constructed over ${\displaystyle X}$ by superposing a sum of univariate quadratics, each of sufficient magnitude to overcome the non-convexity of ${\displaystyle {f({\boldsymbol {x}})}}$ everywhere in ${\displaystyle X}$, as follows:

${\displaystyle L({\boldsymbol {x}})=f({\boldsymbol {x}})+\sum _{i=1}^{i=n}\alpha _{i}(x_{i}^{L}-x_{i})(x_{i}^{U}-x_{i})}$

${\displaystyle L({\boldsymbol {x}})}$ is called the ${\displaystyle \alpha {\text{BB}}}$ underestimator for general functional forms. If all ${\displaystyle \alpha _{i}}$ are sufficiently large, the new function ${\displaystyle L({\boldsymbol {x}})}$ is convex everywhere in ${\displaystyle X}$. Thus, local minimization of ${\displaystyle L({\boldsymbol {x}})}$ yields a rigorous lower bound on the value of ${\displaystyle {f({\boldsymbol {x}})}}$ in that domain.

Calculation of ${\displaystyle {\boldsymbol {\alpha }}}$

There are numerous methods to calculate the values of the ${\displaystyle {\boldsymbol {\alpha }}}$ vector. It is proven that when ${\displaystyle \alpha _{i}=\max\{0,-{\frac {1}{2}}\lambda _{i}^{\min }\}}$, where ${\displaystyle \lambda _{i}^{\min }}$ is a valid lower bound on the ${\displaystyle i}$-th eigenvalue of the Hessian matrix of ${\displaystyle {f({\boldsymbol {x}})}}$, the ${\displaystyle 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 ${\displaystyle H(X)}$ be the interval Hessian matrix of ${\displaystyle {f(X)}}$ over the interval ${\displaystyle X}$. Then, ${\displaystyle \forall d_{i}>0}$ a valid lower bound on eigenvalue ${\displaystyle \lambda _{i}}$ may be derived from the ${\displaystyle i}$-th row of ${\displaystyle H(X)}$ as follows:

${\displaystyle \lambda _{i}^{\min }={\underline {h_{ii}}}-\sum _{i\neq j}(\max(|{\underline {h_{ij}}}|,|{\overline {h_{ij}}}|{\frac {d_{j}}{d_{i}}})}$

References

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