Method and apparatus for solving an inequality constrained global optimization problem

• US 20030131033A1
• Filed: 01/08/2002
• Published: 07/10/2003
• Est. Priority Date: 01/08/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Hansen, Eldon R., Walster, G. William
• Granted Patent: US 7,062,524 B2
• Time in Patent Office: Days
• US Class Current: 708/446
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 7/49989 Interval arithmetic
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

One embodiment of the present invention provides a system that solves a global inequality constrained optimization problem specified by a function ƒ and a set of inequality constraints p_i(x)≦0 (i=1, . . . , m), wherein ƒ and p_i are scalar functions of a vector x=(x₁, x₂, x₃, . . . x_n). During operation, the system receives a representation of the function ƒ and the set of inequality constraints, and stores the representation in a memory within the computer system. Next, the system performs an interval inequality constrained global optimization process to compute guaranteed bounds on a globally minimum value of the function ƒ(x) subject to the set of inequality constraints. During this process, the system applies term consistency to a set of relations associated with the global inequality constrained optimization problem over a subbox X, and excludes any portion of the subbox X that violates the set of relations. The system also applies box consistency to the set of relations, and excludes any portion of the subbox X that violates the set of relations. The system also performs an interval Newton step on the subbox X to produce a resulting subbox Y. The system integrates the sub-parts of the process with branch tests designed to increase the overall speed of the process.

Claims

1. A method for using a computer system to solve a global inequality constrained optimization problem specified by a function ƒ

and a set of inequality constraints p_i(x)≦

0 (i=1, . . . , m), wherein ƒ and

p_i are scalar functions of a vector x=(x₁, x₂, x₃, . . . x_n), the method comprising;

receiving a representation of the function ƒ and

the set of inequality constraints at the computer system;

storing the representation in a memory within the computer system;

performing an interval inequality constrained global optimization process to compute guaranteed bounds on a globally minimum value of the function ƒ

(x) subject to the set of inequality constraints;

wherein performing the interval inequality constrained global optimization process involves,

applying term consistency to a set of relations associated with the global inequality constrained optimization problem over a subbox X, and excluding any portion of the subbox X that violates any of these relations,

applying box consistency to the set of relations associated with the global inequality constrained optimization problem over the subbox X, and excluding any portion of the subbox X that violates any of these relations, and

performing an interval Newton step for the global inequality constrained optimization problem over the subbox X to produce a resulting subbox Y, wherein the point of expansion of the interval Newton step is a point x.

2. The method of claim 1, wherein applying term consistency to the set of relations involves applying term consistency to the set of inequality constraints p_i(x)≦

0 (i=1, . . . , m) over the subbox X.

3. The method of claim 1, wherein applying box consistency to the set of relations involves applying box consistency to the set of inequality constraints p_i(x)≦

0 (i=1, . . . , m) over the subbox X.

4. The method of claim 1,

wherein performing the interval inequality constrained global optimization process involves,

keeping track of a smallest upper bound ƒ

_bar of the function ƒ

(x) at a feasible point x,

removing from consideration any subbox X for which ƒ

(X)>

ƒ

_bar;

wherein applying term consistency to the set of relations involves applying term consistency to the ƒ

_bar inequality ƒ

(x)≦

ƒ

_bar over the subbox X.

5. The method of claim 4, wherein applying box consistency to the set of relations involves applying box consistency to the ƒ

_bar inequality ƒ

(x)≦

ƒ

_bar over the subbox X.

6. The method of claim 1, wherein if the subbox X is strictly feasible (p_i(X)<

0 for all i=1, . . . , n), performing the interval inequality constrained 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 an extremum of ƒ

(x); and

wherein applying term consistency to the set of relations involves applying term consistency to each component g_i(x)=0 (i=1, . . . , n) of g(x)=0 over the subbox X.

7. The method of claim 6, wherein applying box consistency to the set of relations involves applying box consistency to each component g_i(x)=0 (i=1, . . . , n) of g(x)=0 over the subbox X.

8. The method of claim 1, wherein if the subbox X is strictly feasible (p_i(X)<

0 for all i=1, . . . , n), performing the interval inequality constrained 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 H_ii(X) of the Hessian over the subbox X is always negative, indicating that the function f is not convex over the subbox X and consequently does not contain a global minimum within the subbox X; and

wherein applying term consistency to the set of relations involves applying term consistency to each inequality H_ii(x)≧

0 (i=1, . . . , n) over the subbox X.

9. The method of claim 8, wherein applying box consistency to the set of relations involves applying box consistency to each inequality H_ii(x)≧

0 (i=1, . . . , n) over the subbox X.

10. The method of claim 1, wherein if the subbox X is strictly feasible (p_i(X)<

0 for all i=1, . . . , n), performing the interval Newton step involves;

computing the Jacobian J(x,X) of the gradient of the function ƒ

evaluated with respect to a point x over the subbox X; and

computing an approximate inverse B of the center of J(x,X), 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).

11. The method of claim 10, wherein applying term consistency to the set of relations involves applying term consistency to each component (Bg(x))_i=0 (i=1, . . . , n) to solve for the variable x_i over the subbox X.

12. The method of claim 10, wherein applying box consistency to the set of relations involves applying box consistency to each component (Bg(x))_i=0 (i=1, . . . , n) to solve for the variable x_i over the subbox X.

13. The method of claim 1, wherein performing the interval Newton step involves performing the Newton step on the John conditions.

14. The method of claim 1,

wherein performing the interval inequality constrained global optimization process involves,

linearizing the set of inequality constraints to produce a set of linear inequality constraints with interval coefficients that enclose the nonlinear inequality constraints, and

preconditioning the set of linear inequality constraints through additive linear combinations to produce a set of preconditioned linear inequality constraints;

and

wherein applying term consistency to the set of relations involves applying term consistency to the set of preconditioned linear inequality constraints over the subbox X.

15. The method of claim 14, wherein applying box consistency to the set of relations involves applying box consistency to the set of preconditioned linear inequality constraints over the subbox X.

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

symbolically manipulating an equation within the computer system to solve for a term, g(x′

_j), thereby producing a modified equation g(x′

_j)=h(x), wherein the term g(x′

_j) can be analytically inverted to produce an inverse function g<sup>−

1</sup>(y);

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

_j)=h(X);

solving for X′

_j=g<sup>−

1</sup>(h(X)); and

intersecting X′

_j with the j-th element of 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 method of claim 1, wherein performing the interval Newton step involves:

computing J(x,X), wherein J(x,X) is the Jacobian of the function f evaluated as a function of x over the subbox X; and

determining if J(x,X) is regular as a byproduct of solving for the subbox Y that contains values of y that satisfy M(x,X)(y−

x)=r(x), where M(x,X)=BJ(x,X), r(x)=−

Bf(x), and B is an approximate inverse of the center of J(x,X).

18. 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 a global inequality constrained optimization problem specified by a function ƒ

and a set of inequality constraints p_i(x)≦

0 (i=1, . . . , m), wherein ƒ and

p_i are scalar functions of a vector x=(x₁, x₂, x₃, . . . x_n), the method comprising;

receiving a representation of the function ƒ and

the set of inequality constraints at the computer system;

storing the representation in a memory within the computer system;

performing an interval inequality constrained global optimization process to compute guaranteed bounds on a globally minimum value of the function ƒ

(x) subject to the set of inequality constraints;

wherein performing the interval inequality constrained global optimization process involves,

applying term consistency to a set of relations associated with the global inequality constrained optimization problem over a subbox X, and excluding any portion of the subbox X that violates any of these relations,

applying box consistency to the set of relations associated with the global inequality constrained optimization problem over the subbox X, and excluding any portion of the subbox X that violates any of these relations, and

performing an interval Newton step for the global inequality constrained optimization problem over the subbox X to produce a resulting subbox Y, wherein the point of expansion of the interval Newton step is a point x.

19. The computer-readable storage medium of claim 18, wherein applying term consistency to the set of relations involves applying term consistency to the set of inequality constraints p_i(x)≦

0 (i=1, . . . , m) over the subbox X.

20. The computer-readable storage medium of claim 18, wherein applying box consistency to the set of relations involves applying box consistency to the set of inequality constraints p_i(x)≦

0 (i=1, . . . , m) over the subbox X.

21. The computer-readable storage medium of claim 18,

wherein performing the interval inequality constrained global optimization process involves,

keeping track of a smallest upper bound ƒ

_bar of the function ƒ

(x) at a feasible point x,

removing from consideration any subbox X for which ƒ

(X)>

ƒ

_bar;

wherein applying term consistency to the set of relations involves applying term consistency to the ƒ

_bar inequality ƒ

(x)≦

ƒ

_bar over the subbox X.

22. The computer-readable storage medium of claim 21, wherein applying box consistency to the set of relations involves applying box consistency to the ƒ

_bar inequality ƒ

(x)≦

ƒ

_bar over the subbox X.

23. The computer-readable storage medium of claim 22, wherein if the subbox X is strictly feasible (p_i(X)<

0 for all i=1, . . . , n), performing the interval inequality constrained 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 an extremum of ƒ

(x); and

wherein applying term consistency to the set of relations involves applying term consistency to each component g_i(x)=0 (i=1, . . . , n) of g(x)=0 over the subbox X.

24. The computer-readable storage medium of claim 23, wherein applying box consistency to the set of relations involves applying box consistency to each component g_i(x)=0 (i=1, . . . , n) of g(x)=0 over the subbox X.

25. The computer-readable storage medium of claim 18, wherein if the subbox X is strictly feasible p_i(X)<

0 for all i=1, . . . , n), performing the interval inequality constrained 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 H_ii(X) of the Hessian over the subbox X is always negative, indicating that the function f is not convex over the subbox X and consequently does not contain a global minimum within the subbox X; and

wherein applying term consistency to the set of relations involves applying term consistency to each inequality H_ii(x)≧

0 (i=1, . . . , n) over the subbox X.

26. The computer-readable storage medium of claim 25, wherein applying box consistency to the set of relations involves applying box consistency to each inequality H_ii(x)>

0 (I=1, . . . , n) over the subbox X.

27. The computer-readable storage medium of claim 18, wherein if the subbox X is strictly feasible (p_i(X)<

0 for all i=1, . . . , n), performing the interval Newton step involves;

computing the Jacobian J(x,X) of the gradient of the function ƒ

evaluated with respect to a point x over the subbox X; and

computing an approximate inverse B of the center of J(x,X), 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).

28. The computer-readable storage medium of claim 27, wherein applying term consistency to the set of relations involves applying term consistency to each component (Bg(x))_i=0 (i=1, . . . , n) to solve for the variable x_i over the subbox X.

29. The computer-readable storage medium of claim 27, wherein applying box consistency to the set of relations involves applying box consistency to each component (Bg(x))_i=0 (i=1, . . . , n) to solve for the variable x_i over the subbox X.

30. The computer-readable storage medium of claim 18, wherein performing the interval Newton step involves performing the interval Newton step on the John conditions.

31. The computer-readable storage medium of claim 18,

wherein performing the interval inequality constrained global optimization process involves,

linearizing the set of inequality constraints to produce a set of linear inequality constraints with interval coefficients that enclose the nonlinear inequality constraints, and

preconditioning the set of linear inequality constraints through additive linear combinations to produce a set of preconditioned linear inequality constraints;

and

wherein applying term consistency to the set of relations involves applying term consistency to the set of preconditioned linear inequality constraints over the subbox X.

32. The computer-readable storage medium of claim 31, wherein applying box consistency to the set of relations involves applying box consistency to the set of preconditioned linear inequality constraints over the subbox X.

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

symbolically manipulating an equation within the computer system to solve for a term, g(x′

_j), thereby producing a modified equation g(x′

_j)=h(x), wherein the term g(x′

_j) can be analytically inverted to produce an inverse function g<sup>−

1</sup>(y);

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

_j)=h(X);

solving for X′

_j=g<sup>−

1</sup>(h(X)); and

intersecting X′

_j with the j-th element of 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.

34. The computer-readable storage medium of claim 18, wherein performing the interval Newton step involves:

computing J(x,X), wherein J(x,X) is the Jacobian of the function f evaluated as a function of x over the subbox X; and

determining if J(x,X) is regular as a byproduct of solving for the subbox Y that contains values of y that satisfy M(x,X)(y−

x)=r(x), where M(x,X)=BJ(x,X), r(x)=−

Bf(x), and B is an approximate inverse of the center of J(x,X).

35. An apparatus that solves a global inequality constrained optimization problem specified by a function ƒ

and a set of inequality constraints p_i(x)≦

0 (i=1, . . . , m), wherein ƒ and

p_i are scalar functions of a vector x=(x₁, x₂, x₃, . . . x_n), the apparatus comprising;

a receiving mechanism that is configured to receive a representation of the function ƒ and

the set of inequality constraints at the computer system;

a memory for storing the representation;

an interval global optimization mechanism that is configured to perform an interval inequality constrained global optimization process to compute guaranteed bounds on a globally minimum value of the function ƒ

(x) subject to the set of inequality constraints;

a term consistency mechanism within the interval global optimization mechanism that is configured to apply term consistency to a set of relations associated with the global inequality constrained optimization problem over a subbox X, and to exclude any portion of the subbox X that violates any of these relations,

a box consistency mechanism within the interval global optimization mechanism that is configured to apply box consistency to the set of relations associated with the global inequality constrained optimization problem over the subbox X, and to exclude any portion of the subbox X that violates any of these relations, and

an interval Newton mechanism within the interval global optimization mechanism that is configured to perform an interval Newton step for the global inequality constrained optimization problem over the subbox X to produce a resulting subbox Y, wherein the point of expansion of the interval Newton step is a point x.

36. The apparatus of claim 35, wherein the term consistency mechanism is configured to apply term consistency to the set of inequality constraints p_i(x)≦

0 (i=1, . . . , m) over the subbox X.

37. The apparatus of claim 35, wherein the box consistency mechanism is configured to apply box consistency to the set of inequality constraints p_i(x)≦

0 (i=1, . . . , m) over the subbox X.

38. The apparatus of claim 35,

wherein the interval global optimization mechanism is configured to,

keep track of a smallest upper bound ƒ

_bar of the function ƒ

(x) at a feasible point x, and to

remove from consideration any subbox X for which ƒ

(X)>

ƒ

_bar;

wherein the term consistency mechanism is configured to apply term consistency to the ƒ

_bar inequality ƒ

(x)≦

ƒ

_bar over the subbox X.

39. The apparatus of claim 38, wherein the box consistency mechanism is configured to apply box consistency to the ƒ

_bar inequality ƒ

(x)≦

ƒ

_bar over the subbox X.

40. The apparatus of claim 35, wherein if the subbox X is strictly feasible (p_i(X)<

0 for all i=1, . . . , n), 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);

remove from consideration any subbox for which g(x) is bounded away from zero, thereby indicating that the subbox does not include an extremum of ƒ

(x); and

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.

41. The apparatus of claim 40, wherein the box consistency mechanism is configured to apply box consistency to each component g_i(x)=0 (i=1, . . . , n) of g(x)=0 over the subbox X.

42. The apparatus of claim 35, wherein if the subbox X is strictly feasible (p_i(X)<

0 for all i=1, . . . , n), the interval global optimization mechanism is configured to;

determine diagonal elements H_ii(x) (i=1, . . . , n) of the Hessian of the function ƒ

(x);

remove from consideration any subbox for which a diagonal element H_ii(X) of the Hessian over the subbox X is always negative, indicating that the function f is not convex over the subbox X and consequently does not contain a global minimum within the subbox X; and

the term consistency mechanism is configured to apply term consistency to each inequality H_ii(x)≧

0 (i=1, . . . , n) over the subbox X.

43. The apparatus of claim 42, wherein the box consistency mechanism is configured to apply box consistency to each inequality H_ii(x)≧

0 (i=1, . . . , n) over the subbox X.

44. The apparatus of claim 35, wherein if the subbox X is strictly feasible (p_i(X)<

0 for all i=1, . . . , n), the interval global optimization mechanism is configured to perform the interval Newton step by;

computing the Jacobian J(x,X) of the gradient of the function ƒ

evaluated with respect to a point x over the subbox X; and

computing an approximate inverse B of the center of J(x,X), 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).

45. The apparatus of claim 44, the term consistency mechanism is configured to apply term consistency to each component (Bg(x))_i=0 (i=1, . . . , n) to solve for the variable x_i over the subbox X.

46. The apparatus of claim 44, the box consistency mechanism is configured to apply box consistency to each component (Bg(x))_i=0 (i=1, . . . , n) to solve for the variable x, over the subbox X.

47. The apparatus of claim 35, wherein the interval Newton mechanism is configured to perform the Newton step on the John conditions.

48. The apparatus of claim 35,

wherein the interval global optimization mechanism is configured to:

linearize the set of inequality constraints to produce a set of linear inequality constraints with interval coefficients that enclose the nonlinear inequality constraints, and to

precondition the set of linear inequality constraints through additive linear combinations to produce a set of preconditioned linear inequality constraints; and

wherein the term consistency mechanism is configured to apply term consistency to the set of preconditioned linear inequality constraints over the subbox X.

49. The apparatus of claim 48, wherein the box consistency mechanism is configured to apply box consistency to the set of preconditioned linear inequality constraints over the subbox X.

50. The apparatus of claim 35, wherein the term consistency mechanism is configured to:

symbolically manipulate an equation within the computer system to solve for a term, g(x′

_j), thereby producing a modified equation g(x′

_j)=h(x), wherein the term g(x′

_j) can be analytically inverted to produce an inverse function g<sup>−

1</sup>(y);

substitute the subbox X into the modified equation to produce the equation g(X′

_j)=h(X);

solve for X′

_j=g<sup>−

1</sup>(h(X)); and

intersect X′

_j with the j-th element of 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.

51. The apparatus of claim 35, wherein the interval Newton mechanism is configured to:

compute J(x,X), wherein J(x,X) is the Jacobian of the function f evaluated as a function of x over the subbox X; and

to

determine if J(x,X) is regular as a byproduct of solving for the subbox Y that contains values of y that satisfy M(x,X)(y−

x)=r(x), where M(x,X)=BJ(x,X), r(x)=−

Bf(x), and B is an approximate inverse of the center of J(x,X).