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

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

Deterministic global optimization