αΒΒ

"Alpha BB" redirects here. For other uses, see ABB (disambiguation).

αΒΒ is a second-order deterministic global optimization algorithm for finding the optima of general, twice continuously differentiable functions. 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}})\in C^{2}}$ be a function of general non-linear non-convex structure, defined in a finite box $X=\{{\boldsymbol {x}}\in \mathbb {R} ^{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 $X$ by superposing a sum of univariate quadratics, each of sufficient magnitude to overcome the non-convexity of ${f({\boldsymbol {x}})}$ everywhere in $X$, as follows:

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

$L({\boldsymbol {x}})$ is called the $\alpha {\text{BB}}$ underestimator for general functional forms. If all $\alpha _{i}$ are sufficiently large, the new function $L({\boldsymbol {x}})$ is convex everywhere in $X$. 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,-{\frac {1}{2}}\lambda _{i}^{\min }\}$, where $\lambda _{i}^{\min }$ is a valid lower bound on the $i$-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 $X$. Then, $\forall d_{i}>0$ a valid lower bound on eigenvalue $\lambda _{i}$ may be derived from the $i$-th row of $H(X)$ as follows:

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