Method and apparatus for solving an equality constrained global optimization problem

摘要

One embodiment of the present invention provides a system that solves a global optimization problem specified by a function and a set of equality constraints q_i(x)0 (i1, . . . , r), wherein is a scalar function of a vector x(x₁, x₂, x₃, . . . x_n). During operation, the system receives a representation of the function 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 (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.