Method and apparatus for solving an unconstrained global optimization problem

Abstract

One embodiment of the present invention provides a system that receives a representation of the function ƒ and stores the representation in a memory. Next, the system performs an interval global optimization process to compute guaranteed bounds on a globally minimum value of the function ƒ(x) over a subbox X. This interval global optimization process applies term consistency to a set of relations associated with the function ƒ over the subbox X, and excludes any portion of the subbox X that violates any member of the set of relations. It also applies box consistency to the set of relations associated with the function ƒ over the subbox X, and excludes any portion of the subbox X that violates the set of relations. The interval global optimization process also performs an interval Newton step on the subbox X to produce a resulting subbox Y, wherein the point of expansion of the interval Newton step is a point x within the subbox X, and wherein performing the interval Newton step involves evaluating the gradient g(x) of the function ƒ(x) using interval arithmetic. The system integrates the sub-parts of the process with branch tests designed to increase the overall speed of the process.