Sun Microsystems, Inc.

Eldon R Hansen

G William Walster

One embodiment of the present invention provides a system that solves an overdetermined system of interval linear equations. During operation, the system receives a representation of the overdetermined system of interval linear equations Ax=b, wherein A is a matrix with m rows corresponding to m equations, and n columns corresponding to n variables, and wherein x includes n variable components, b includes m scalar components, and m&#x3e;n. Next, the system performs a Gaussian Elimination operation to transform Ax=b into the form wherein T is a square upper triangular matrix of order n, u is a vector with n components, v is a vector with m&#x2212;n components, and W is a matrix with m&#x2212;n rows and n columns, wherein W is zero except in the last column, which is represented as a column vector z with m&#x2212;n components. Next, the system performs an interval intersection operation based on the equations zx=v(i=1, . . . , m&#x2212;n) and Tx=uto solve for x. If xis not the empty interval, the system performs a back substitution operation using xand Tx=u to solve for the remaining components (x, . . . , x) of x.

Method and apparatus for solving overdetermined systems of interval linear equations

One embodiment of the present invention provides a system that facilitates performing exception-free arithmetic operations within a computer system. During execution of a computer program, the system receives an instruction to perform an arithmetic operation that involves manipulating floating-point values. If the arithmetic operation manipulates a floating-point value representing {+0}, the arithmetic operation is performed in a manner consistent with {+0} representing a set containing a single value '&#x2212;0', wherein '&#x2212;0' is the limit of a sequence of values that approaches zero only from above. Similarly, if the arithmetic operation manipulates a floating-point value representing {&#x2212;0}, the arithmetic operation is performed in a manner consistent with {&#x2212;0} representing a set containing a single value &#x201c;+0&#x201d;, wherein &#x201c;+0&#x201d; is the limit of a sequence of values that approaches zero only from below.

Method and apparatus for facilitating exception-free arithmetic in a computer system

One embodiment of the present invention provides a system that computes interval parameter bounds from fallible measurements. During operation, the system receives a set of measurements z, . . . , z, wherein an observation model describes each zas a function of a p-element vector parameter x=(x, . . . , x). Next, the system forms a system of nonlinear equations z&#x2212;h(x)=0 (i=1, . . . , n) based on the observation model. Finally, the system solves the system of nonlinear equations to determine interval parameter bounds on x.

Computing interval parameter bounds from fallible measurements using systems of nonlinear equations

One embodiment of the present invention provides a system that solves a global optimization problem specified by a function &#x192; and a set of equality constraints q(x)=0 (i=1, . . . , r), wherein &#x192; is a scalar function of a vector x=(x, x, x, . . . x). During operation, the system receives a representation of the function &#x192; and the set of equality constraints and stores the representation in a memory within a computer system. Next, the system and performs an interval global optimization process to compute guaranteed bounds on a globally minimum value of the function &#x192;(x) subject to the set of equality constraints. Performing this interval global optimization process involves, applying term consistency to the set of equality constraints over a subbox X, and excluding portions of the subbox X that violate the set of equality constraints.

Applying term consistency to an equality constrained interval global optimization problem

A system that solves a global inequality constrained optimization problem specified by a function &#x192; and a set of inequality constraints p(x)&#x2266;0(i=1, . . . , m), wherein &#x192; and pare scalar functions of a vector x=(x, x, x, . . . x). The system performs an interval inequality constrained global optimization process to compute guaranteed bounds on a globally minimum value of the function &#x192;(x) subject to the set of inequality constraints. The system applies term consistency and box 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 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.

Method and apparatus for solving an inequality constrained global optimization problem

One embodiment of the present invention provides a system that solves a global optimization problem specified by a function &#x192; and a set of inequality constraints p(x)&#x2266;0 (i=1, . . . , m), wherein &#x192; and pare scalar functions of a vector x=(x, x, x, . . . x). The system operates by receiving a representation of the function &#x192; and the set of inequality constraints, and then storing 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 the minimum value of the function &#x192;(x) subject to the set of inequality constraints. While performing the interval global optimization process, the system applies term consistency at various places in the process over a subbox X, and excludes any portion of the subbox X that violates term consistency.

Applying term consistency to an inequality constrained interval global optimization problem

One embodiment of the present invention provides a system that solves an unconstrained interval global optimization problem specified by a function &#x192;, wherein &#x192; is a scalar function of a vector x=(x, x, x, . . . x). The system operates by receiving a representation of the function &#x192;, and then performing an interval global optimization process to compute guaranteed bounds on a globally minimum value &#x192;* of the function &#x192;(x) and the location or locations x* of the global minimum. While performing the interval global optimization process, the system deletes all of part of a subbox X for which &#x192;(x)&#x3e;&#x192;_bar, wherein &#x192;_bar is the least upper bound on &#x192;* that has been so far found. This is called the '&#x192;_bar test'. The system applies term consistency to the &#x192;_bar test over the subbox X to increase that portion of the subbox X that can be proved to violate the &#x192;_bar test.

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

One embodiment of the present invention provides a system that bounds the solution set of a system of nonlinear equations specified by the set of linear equations Ax=b, wherein A is an interval matrix and b is an interval vector. During operation, the system preconditions the set of linear equations Ax=b by multiplying through by a matrix B to produce a preconditioned set of linear equations Mx=r, wherein M=BA and r=Bb. Next, the system widens the matrix Mto produce a widened matrix, M, wherein the midpoints of the elements of M form the identity matrix. Finally, the system uses M and r to compute the hull h of the system Mx=r, which bounds the solution set of the system Mx=r.

Method and apparatus for bounding the solution set of a system of linear equations

One embodiment of the present invention provides a system that solves a problem involving an interval parameter p through an interval solution process. During operation, the system receives a representation of the problem, wherein the problem includes a number of variables x, x, x, . . . xand at least one interval parameter p. The system stores the representation in a computer memory, and then performs the interval solution process on the problem. During this interval solution process, the system splits the problem into sub-problems by splitting the interval parameter p into subintervals, and creating separate sub-problems for each subinterval. The system then performs the interval solution process on the sub-problems. By splitting the interval parameter p, the system can achieve a tighter bound on the solution set of the problem. The decision to split on any parameter p is made in exactly the same way it would be made if p were a variable of the problem. Otherwise, parameters are kept separate from problem variables.

Method and apparatus solving problems having interval parameters

One embodiment of the present invention provides a system that solves a global optimization problem specified by a function &#x192; and a set of equality constraints q(x)=0 (i=1, . . . , r), wherein &#x192; is a scalar function of a vector x=(x, x, x, . . . x). During operation, the system receives a representation of the function &#x192; and the set of equality constraints and stores the representation in a memory. Next, the system performs an interval equality constrained global optimization process to compute guaranteed bounds on a globally minimum value of the function &#x192;(x) subject to the set of equality constraints. During this process, the system applies term consistency to a set of relations associated with the interval equality constrained global optimization problem over a subbox X, and excludes any portion of the subbox X that violates the set of relations. It also applies box consistency to the set of relations, and excludes any portion of the subbox X that violates the set of relations. Finally, the system performs an interval Newton step for the interval equality constrained global optimization problem over the subbox X. The system integrates the sub-parts of the process with branch tests designed to increase the overall speed of the process.

Method and apparatus for solving an equality constrained global optimization problem

One embodiment of the present invention provides a system that performs a procedure to solve a system of linear inequalities. During operation, the system receives a representation of the system of linear inequalities Ax&#x2266;b, wherein Ax&#x2266;b can be a linearized form of a system of nonlinear equations. Within this representation, A is an interval matrix with m rows corresponding to m inequalities, and with n columns corresponding to n variables, the vector x includes n variable components, and the vector b includes m scalar interval components. The system solves the system of linear inequalities Ax&#x2266;b by performing a Gaussian elimination process using only positive multipliers so as not to change the sense of any inequality. For a given column j in A, performing the Gaussian elimination process involves attempting to select a primary pivot row r including a primary pivot element, a, which does not contain zero, and attempting to select a secondary pivot row s including a secondary pivot element, a, which does not contain zero and is opposite in sign to a. If r and s are successfully selected, the system uses the secondary pivot element ato zero elements opposite in sign to it in the same column of A, except for the primary pivot element a. The system also adds a copy s' of the secondary pivot row s to the matrix A, thereby increasing the number of rows in the matrix A. Next, the system uses the primary pivot element are to zero elements opposite in sign to it in the same column of A, except for the copy of the secondary pivot element ain row s&#x2032;.

Method and apparatus for solving systems of linear inequalities

One embodiment of the present invention provides a system that receives a representation of the function &#x192; 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 &#x192;(x) over a subbox X. This interval global optimization process applies term consistency to a set of relations associated with the function &#x192; 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 &#x192; 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 &#x192;(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.

Method and apparatus for solving an unconstrained global optimization problem

One embodiment of the present invention provides a system for finding the roots of a system of nonlinear equations within an interval vector X=(X, . . . , X), wherein the system of non-linear equations is specified by a vector function &#x192;=(&#x192;, . . . , &#x192;). The system operates by receiving a representation of the interval vector X (which is also called a box), wherein for each dimension, i, the representation of Xincludes a first floating-point number, &#x3b1;, representing the left endpoint of X, and a second floating-point number, b, representing the right endpoint of X. Next, the system performs an interval Newton step on X to produce a resulting interval vector, X', wherein the point of expansion of the interval Newton step is a point, x, within the interval X, and wherein performing the interval Newton step involves evaluating &#x192;(x) to produce an interval result &#x192;(x). The system then evaluates a first termination condition, wherein the first termination condition is TRUE if: zero is contained within &#x192;(x), J(x,X) is regular (wherein J(x,X) is the Jacobian of the function &#x192;evaluated with respect to x over the box X); and X is contained within X&#x2032;. If the first termination condition is TRUE, the system terminates the interval Newton method and records X&#x2032; as a final bound.

Termination criteria for the interval version of Newton's method for solving systems of non-linear equations

One embodiment of the present invention provides a computer-based system for solving a system of nonlinear equations specified by a vector function, f, wherein f(x)=0 represents &#x192;(x)=0, &#x192;(x)=0, &#x192;(x)=0 . . . , &#x192;(x)=0, wherein x is a vector (x, X, X, . . . x). The system operates by receiving a representation of a subbox X=(X, X, . . . , X), wherein for each dimension, i, the representation of X, includes a first floating-point number, a, representing the left endpoint of X, and a second floating-point number, b, representing the right endpoint of X. The system stores the representation in a computer memory. Next, the system applies term consistency to the set of nonlinear equations, &#x192;(x)=0, &#x192;(x)=0, &#x192;(x)=0, . . . , &#x192;,(x)=0, over X, and excludes portions of X that violate the set of nonlinear equations. The system also applies box consistency to the set of nonlinear equations over X, and excludes portions of X that violate the set of nonlinear equations. Finally, the system performs an interval Newton step on X to produce a resulting subbox Y, wherein the point of expansion of the interval Newton step is a point x within X, and wherein performing the interval Newton step involves evaluating f(x) using interval arithmetic to produce an interval result f(x). The system integrates the sub-parts of the process with branch tests designed to increase the overall speed of the process.

Method and apparatus for solving systems of nonlinear equations using interval arithmetic

One embodiment of the present invention provides a system for finding zeros of a function, &#x192;, within an interval, X, using the interval version of Newton's method. The system operates by receiving a representation of the interval X. This representation including a first floating-point number, a, representing the left endpoint of X, and a second floating-point number, b, representing the right endpoint of X. Next, the system performs an interval Newton step on X, wherein the point of expansion is the midpoint, x, of the interval X. Note that performing the interval Newton step involves evaluating &#x192;(x) to produce an interval result &#x192;(x). If &#x192;(x) contains zero, the system evaluates &#x192;(a) to produce an interval result &#x192;(a). It also evaluates &#x192;(b) to produce an interval result &#x192;(b). The system then evaluates a termination condition for the processing of the current interval X, wherein the termination condition is TRUE if a number of sub-conditions are satisfied, including if &#x192;(a) contains zero and if &#x192;(b) contains zero. If the termination condition is TRUE, the system terminates the processing of the current interval X, and records X as a final bound.

Growing community of inventors

Los Altos, CA, United States of America

Eldon R Hansen