Method and apparatus for solving an inequality constrained global optimization problem
First Claim
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 pi(x)≦
0 (i=1, . . . , m), wherein ƒ and
pi are scalar functions of a vector x=(x1, x2, x3, . . . xn), 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.
3 Assignments
0 Petitions
Accused Products
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 pi(x)≦0 (i=1, . . . , m), wherein ƒ and pi are scalar functions of a vector x=(x1, x2, x3, . . . xn). 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.
-
Citations
51 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 pi(x)≦
0 (i=1, . . . , m), wherein ƒ and
pi are scalar functions of a vector x=(x1, x2, x3, . . . xn), 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
- and a set of inequality constraints pi(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 pi(x)≦
0 (i=1, . . . , m), wherein ƒ and
pi are scalar functions of a vector x=(x1, x2, x3, . . . xn), 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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
- and a set of inequality constraints pi(x)≦
-
35. An apparatus that solves a global inequality constrained optimization problem specified by a function ƒ
- and a set of inequality constraints pi(x)≦
0 (i=1, . . . , m), wherein ƒ and
pi are scalar functions of a vector x=(x1, x2, x3, . . . xn), 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. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
- and a set of inequality constraints pi(x)≦
Specification