Method and apparatus for initializing interval computations through subdomain sampling

1. A method for using a computer system to evaluate a function within a domain using an interval computing technique, the method comprising:

receiving the function and the domain over which the function is to be evaluated;

creating a set of sampling subdomains within the domain by generating a set of boxes of different sizes which are located at different positions across the domain;

performing evaluations on the set of sampling subdomains to generate evaluation results;

sorting the evaluation results based on box size;

selecting a box size from the different box sizes by identifying a largest box size which achieves tight bounds on the evaluation results;

discretizing the domain into subdomains of the selected box size; and

using the interval computing technique to evaluate the function on each of the subdomains wherein the interval computing technique recursively subdivides and evaluates the function on the subdomains.

2. The method of claim 1 , wherein the tight bound is obtained at a box size where subsequent reductions in box size decrease the percentage of boxes that contain a solution by less than a pre-specified amount.

3. The method of claim 1 , wherein the sampling subdomains include large sampling subdomains which do not generate tight bounds on the evaluation results.

4. The method of claim 1 , wherein identifying the largest box size which achieves tight bounds on the evaluation results involves identifying a transition from a sampling subdomain size which does not generate tight bounds on the evaluation results to a next-largest sampling subdomain size which generates tight bounds.

5. The method of claim 1 , wherein performing evaluations on the set of sampling subdomains involves:

evaluating the function on the set of sampling subdomains; and

evaluating derivatives of the function on the set of sampling subdomains.

6. The method of claim 1 , wherein performing evaluations on the set of sampling subdomains further involves using interval techniques, which can include:

box consistency;

Hull consistency;

term consistency;

monotonicity; and

Newton contraction.

7. The method of claim 6 , wherein the evaluation results indicate an initial box size on which a specific interval technique becomes effective for function evaluation.

8. A computer-readable storage medium storing instructions that when executed by a computer system cause the computer system to use a computer system to evaluate a function within a domain using an interval computing technique, the method comprising:

receiving the function and the domain over which the function is to be evaluated;

creating a set of sampling subdomains within the domain by generating a set of boxes of different sizes which are located at different positions across the domain;

performing evaluations on the set of sampling subdomains to generate evaluation results;

sorting the evaluation results based on box size;

selecting a box size from the different box sizes by identifying a largest box size which achieves tight bounds on the evaluation results;

discretizing the domain into subdomains of the selected box size; and

using the interval computing technique to evaluate the function on each of the subdomains wherein the interval computing technique recursively subdivides and evaluates the function on the subdomains.

9. The computer-readable storage medium of claim 8 , wherein the tight bound is obtained at a box size where subsequent reductions in box size decrease the percentage of boxes that contain a solution by less than a pre-specified amount.

10. The computer-readable storage medium of claim 8 , wherein the sampling subdomains include large sampling subdomains which do not generate tight bounds on the evaluation results.

11. The computer-readable storage medium of claim 8 , wherein identifying the largest box size which achieves tight bounds on the evaluation results involves identifying a transition from a sampling subdomain size which does not generate tight bounds on the evaluation results to a next-largest sampling subdomain size which generates tight bounds.

12. The computer-readable storage medium of claim 8 , wherein performing evaluations on the set of sampling subdomains involves:

evaluating the function on the set of sampling subdomains; and

evaluating derivatives of the function on the set of sampling subdomains.

13. The computer-readable storage medium of claim 8 , wherein performing evaluations on the set of sampling subdomains further involves using interval techniques, which can include:

box consistency;

Hull consistency;

term consistency;

monotonicity; and

Newton contraction.

14. The computer-readable storage medium of claim 13 , wherein the evaluation results indicate an initial box size on which a specific interval technique becomes effective for function evaluation.

15. An apparatus that uses a computer system to evaluate a function within a domain using an interval computing technique, the apparatus comprising:

a receiving mechanism configured to receive the function and the domain over which the function is to be evaluated;

a memory for storing the function and the domain;

a generation mechanism configured to create a set of sampling subdomains within the domain by generating a set of boxes of different sizes which are located at different positions across the domain;

an evaluation mechanism configured to perform evaluations on the set of sampling subdomains to generate evaluation results;

a sorting mechanism configured to sort the evaluation results based on box size;

a selection mechanism configured to select a box size from the different box sizes by identifying a largest box size which achieves tight bounds on the evaluation results;

a discretization mechanism configured to discretize the domain into subdomains of the selected box size; and

an evaluation mechanism configured to use the interval computing technique to evaluate the function on each of the subdomains by recursively subdividing and evaluating the function on the subdomains.

16. The apparatus of claim 15 , wherein the tight bound is obtained at a box size where subsequent reductions in box size decrease the percentage of boxes that contain a solution by less than a pre-specified amount.

17. The apparatus of claim 15 , wherein the sampling subdomains include large sampling subdomains which do not generate tight bounds on the evaluation results.

18. The apparatus of claim 15 , wherein identifying the largest box size which achieves tight bounds on the evaluation results involves identifying a transition from a sampling subdomain size which does not generate tight bounds on the evaluation results to a next-largest sampling subdomain size which generates tight bounds.

19. The apparatus of claim 15 , wherein performing evaluations on the set of sampling subdomains involves:

evaluating the function on the set of sampling subdomains; and

evaluating derivatives of the function on the set of sampling subdomains.

20. The apparatus of claim 15 , wherein performing evaluations on the set of sampling subdomains further involves using interval techniques, which can include:

box consistency;

Hull consistency;

term consistency;

monotonicity; and

Newton contraction.

21. The apparatus of claim 20 , wherein the evaluation results on the sampling subdomains indicate an initial box size on which a specific interval technique becomes effective for function evaluation.