Patent ID: 7062524
Filing Date: 2006-06-13
Classification: G06F,G06N

Abstract:
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 f and p i are scalar functions of a vector x=(x 1 , x 2 , x 3 . . . 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 f(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 aiXy 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: and recording the guaranteed bounds in the computer system memory; 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 ) is analytically inverted to produce an inverse function g −1 (y), substituting the subbox X into the modified equation to produce the equation g(X′ j )=h(X), solving for X′ j =g −1 (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.