αΒΒ

Short description: Second-order deterministic global optimization algorithm

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

[math]\displaystyle{ L(\boldsymbol{x})=f(\boldsymbol{x})+\sum_{i=1}^{i=n}\alpha_i(x_i^L - x_i)(x_i^U - x_i) }[/math]

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

Calculation of [math]\displaystyle{ \boldsymbol{\alpha} }[/math]

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

[math]\displaystyle{ \lambda_i^{\min}=\underline{h_{ii}}-\sum_{i\neq j}(\max(|\underline{h_{ij}}|,|\overline{h_{ij}}|\frac{d_j}{d_i}) }[/math]