Applying term consistency to the solution of unconstrained interval global optimization problems

1. A method for using a computer system to solve an unconstrained interval global optimization problem specified by a function ƒ, wherein ƒ is a scalar function of a vector x=(x 1 , x 2 , x 3 , . . . x n ), the method comprising:

receiving a representation of the function ƒ at the computer system;

storing the representation in a memory within the computer system; and

performing an interval global optimization process using interval operations to compute guaranteed bounds on a globally minimum value of the function ƒ(x);

wherein performing the interval global optimization process involves,

applying term consistency over a subbox X, and

excluding any portion of the subbox X that violates term consistency.

2. The method of claim 1 , wherein applying term consistency involves:

symbolically manipulating an equation within the computer system to solve for a first term, g(x′), thereby producing a modified equation g(x′)=h(x), wherein the first term g(x′) can be analytically inverted to produce an inverse function g −1 (y);

substituting the subbox X into the modified equation to produce the equation g(X′)=h(X)

solving for X′=g −1 (h(X)); and

intersecting X′ with the subbox X to produce a new subbox X + ;

wherein the new subbox X + contains all solutions of the equation within the subbox X, and wherein the size of the new subbox X + is less than or equal to the size of the subbox X.

3. The method of claim 1 , wherein performing the interval global optimization process involves:

keeping track of a least upper bound ƒ_bar of the function ƒ(x);

removing from consideration any subbox for which ƒ(x)>ƒ_bar;

applying term consistency to the inequality ƒ(x)≦ƒ_bar over the subbox X; and

excluding any portion of the subbox X that violates the inequality.

4. The method of claim 1 , wherein performing the interval global optimization process involves:

determining a gradient g(x) of the function ƒ(x), wherein g(x) includes components g i (x) (i=1, . . . , n);

removing from consideration any subbox for which g(x) is bounded away from zero, thereby indicating that the subbox does not include a global minimum of ƒ(x); and

applying term consistency to each component g i (x)=0 (i=1, . . . , n) of g(x)=0 over the subbox X; and

excluding any portion of the subbox X that violates a component.

5. The method of claim 1 , wherein performing the interval global optimization process involves:

determining diagonal elements H ii (x) (i=1, . . . , n) of the Hessian of the function ƒ(x);

removing from consideration any subbox for which a diagonal element of the Hessian is always negative, which indicates that the ƒ is not convex and consequently does not contain a global minimum within the subbox;

applying term consistency to each inequality H ii (x)≧0 (i=1, . . . , n) over the subbox X; and

excluding any portion of the subbox X that violate these inequalities.

6. The method of claim 1 , wherein performing the interval global optimization process involves performing the Newton method, wherein performing the Newton method involves:

computing the Jacobian J(x,X) of the function ƒ evaluated as a function of a point x over the subbox X;

computing an approximate inverse B of the center of J(x,X); and

using the approximate inverse B to analytically determine the system Bg(x), wherein g(x) is the gradient of the function ƒ(x), and wherein g(x) includes components g i (x) (i=1, . . . , n).

7. The method of claim 1 , further comprising terminating attempts to further reduce the subbox X when:

the width of X is less than a first threshold value; and

the magnitude of ƒ(X) is less than a second threshold value.

8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for using a computer system to solve an unconstrained interval global optimization problem specified by a function ƒ, wherein ƒ is a scalar function of a vector x=(x 1 , x 2 , x 3 , . . . x n ), the method comprising:

receiving a representation of the function ƒ at the computer system;

storing the representation in a memory within the computer system; and

performing an interval global optimization process using interval operations to compute guaranteed bounds on a globally minimum value of the function ƒ(x);

wherein performing the interval global optimization process involves,

applying term consistency over a subbox X, and

excluding any portion of the subbox X that violates term consistency.

9. The computer-readable storage medium of claim 8 , wherein applying term consistency involves:

symbolically manipulating an equation within the computer system to solve for a first term, g(x′), thereby producing a modified equation g(x′)=h(x), wherein the first term g(x′) can be analytically inverted to produce an inverse function g −1 (y);

substituting the subbox X into the modified equation to produce the equation g(X′)=h(X);

solving for X′=g −1 (h(X)); and

intersecting X′ with the subbox X to produce a new subbox X + ;

wherein the new subbox X + contains all solutions of the equation within the subbox X, and wherein the size of the new subbox X + is less than or equal to the size of the subbox X.

10. The computer-readable storage medium of claim 8 , wherein performing the interval global optimization process involves:

keeping track of a least upper bound ƒ_bar of the function ƒ(x);

removing from consideration any subbox for which ƒ(x)>ƒ_bar;

applying term consistency to the inequality ƒ(x)≦ƒ_bar over the subbox X; and

excluding any portion of the subbox X that violates the inequality.

11. The computer-readable storage medium of claim 8 , wherein performing the interval global optimization process involves:

determining a gradient g(x) of the function ƒ(x), wherein g(x) includes components g i (x) (i=1, . . . , n);

removing from consideration any subbox for which g(x) is bounded away from zero, thereby indicating that the subbox does not include a global minimum of ƒ(x); and

applying term consistency to each component g i (x)=0 (i=1, . . . , n) of g(x)=0 over the subbox X; and

excluding any portion of the subbox X that violates a component.

12. The computer-readable storage medium of claim 8 , wherein performing the interval global optimization process involves:

determining diagonal elements H ii (x) (i=1, . . . , n) of the Hessian of the function ƒ(x);

removing from consideration any subbox for which a diagonal element of the Hessian is always negative, which indicates that the ƒ is not convex and consequently does not contain a global minimum within the subbox;

applying term consistency to each inequality H ii (x)≧0(i=1, . . . , n) over the subbox X; and

excluding any portion of the subbox X that violate these inequalities.

13. The computer-readable storage medium of claim 8 , wherein performing the interval global optimization process involves performing the Newton method, wherein performing the Newton method involves:

computing the Jacobian J(x,X) of the function ƒ evaluated as a function of a point x over the subbox X;

computing an approximate inverse B of the center of J(x,X); and

using the approximate inverse B to analytically determine the system Bg(x), wherein g(x) is the gradient of the function ƒ(x), and wherein g(x) includes components g i (x) (i=1, . . . , n).

14. The computer-readable storage medium of claim 8 , wherein the method further comprises terminating attempts to further reduce the subbox X when:

the width of X is less than a first threshold value; and

the magnitude of ƒ(X) is less than a second threshold value.

15. An apparatus that solves an unconstrained interval global optimization problem specified by a function ƒ, wherein ƒ is a scalar function of a vector x=(x 1 , x 2 , X 3 , . . . x n ), the apparatus comprising:

a receiving mechanism that is configured to receive a representation of the functions ƒ;

a memory for storing the representation; and

an interval global optimization mechanism that is configured to perform an interval global optimization process using interval operations to compute guaranteed bounds on a globally minimum value of the function ƒ(x);

a term consistency mechanism within the interval global optimization mechanism that is configured to,

apply term consistency over a subbox X, and to

exclude any portion of the subbox X that violates term consistency.

16. The apparatus of claim 15 , wherein the term consistency mechanism includes:

a symbolic manipulation mechanism that is configured to symbolically manipulate an equation within the computer system to solve for a first term, g(x′), thereby producing a modified equation g(x′)=h(x), wherein the first term g(x′) can be analytically inverted to produce an inverse function g −1 (y);

a solving mechanism that is configured to,

substitute the subbox X into the modified equation to produce the equation g(X′)=h(X), and to

solve for X′=g 1 −1 (h(X)); and

an intersecting mechanism that is configured to intersect X′ with the subbox X to produce a new subbox X + ;

wherein the new subbox X + contains all solutions of the equation within the subbox X, and wherein the size of the new subbox X + is less than or equal to the size of the subbox X.

17. The apparatus of claim 15 ,

wherein the interval global optimization mechanism is configured to,

keep track of a least upper bound bar ƒ_of the function ƒ(x), and to

remove from consideration any subbox for which ƒ(x)>ƒ_bar;

wherein the term consistency mechanism is configured to,

apply term consistency to the inequality ƒ(x)≦ƒ_bar over the subbox X, and to

exclude any portion of the subbox X that violates the inequality.

18. The apparatus of claim 15 ,

wherein the interval global optimization mechanism is configured to,

determine a gradient g(x) of the function ƒ(x), wherein g(x) includes components g i (x) (i=1, . . . , n), and to

remove from consideration any subbox for which g(x) is bounded away from zero, thereby indicating that the subbox does not include a global minimum of ƒ(x); and

wherein the term consistency mechanism is configured to,

apply term consistency to each component g i (x)=0 (i=1, . . . , n) of g(x)=0 over the subbox X, and to

exclude any portion of the subbox X that violates a component.

19. The apparatus of claim 15 ,

wherein the interval global optimization mechanism is configured to,

determine diagonal elements H ii (x) (i=1, . . . , n) of the Hessian of the function ƒ(x), and to

remove from consideration any subbox for which a diagonal element of the Hessian is always negative, which indicates that the ƒ is not convex and consequently does not contain a global minimum within the subbox; and

wherein the term consistency mechanism is configured to,

apply term consistency to each inequality H ii (x)≧0 (i=1, . . . , n) over the subbox X, and to

exclude any portion of the subbox X that violate these inequalities.

20. The apparatus of claim 15 , further comprising a Newton mechanism within the interval global optimization mechanism that is configured to:

compute the Jacobian J(x,X) of the function evaluated as a function of a point x over the subbox X;

compute an approximate inverse B of the center of J(x,X); and to

using the approximate inverse B to analytically determine the system Bg(x), wherein g(x) is the gradient of the function ƒ(x), and wherein g(x) includes components g i (x) (i=1, . . . , n).

21. The apparatus of claim 15 , further comprising a termination mechanism that is configured to terminate attempts to further reduce the subbox X when:

the width of X is less than a first threshold value; and

the magnitude of ƒ(X) is less than a second threshold value.