Method and apparatus for using interval techniques to solve a multi-objective optimization problem

1. A method for using interval techniques within a computer system to solve a multi-objective optimization problem, comprising:

receiving a representation of multiple objective functions (ƒ 1 , . . . ,ƒ n ) at the computer system, wherein (ƒ 1 , . . . , ƒ n ) are scalar functions of a vector x=(x 1 , . . . , x n );

receiving a representation of a domain of interest for the multiple objective functions;

storing the representations in a memory within the computer system; and

performing an interval optimization process to compute guaranteed bounds on a Pareto front for the objective functions (ƒ 1 , . . . , ƒ n ), wherein for each point on the Pareto front, an improvement in one objective function cannot be made without adversely affecting at least one other objective function;

wherein performing the interval optimization process involves applying a direct-comparison technique between subdomains of the domain of interest to eliminate subdomains that are certainly dominated by other subdomains,

wherein performing the interval optimization process involves applying a gradient technique to eliminate subdomains that do not contain a local Pareto optimum,

wherein a subdomain [x] i is eliminated by the gradient technique if an intersection of certainly negative gradient regions C j for each objective function ƒ j is non-empty,

⋂

j

=

1

n

⁢

C

j

⁡

(

[

x

]

j

)

≠

∅

,

and

wherein the certainly negative gradient region C j for objective function ƒ j is the intersection of N j ([x] i ) (the negative gradient region associated with the minimum angle θ j of the gradient of ƒ j over the subdomain [x] i ) and N j ([x] i ) (the negative gradient region associated with the maximum angle θ j of the gradient of ƒ j over the subdomain [x] i ).

2. The method of claim 1 , wherein the method further comprises iteratively:

bisecting remaining subdomains that have not been eliminated by the gradient technique; and

applying the gradient technique to eliminate bisected subdomains that do not contain a local Pareto optimum.

3. The method of claim 2 , wherein bisecting a subdomain involves bisecting the subdomain in the direction that has the largest width of partial derivatives of all objective functions (ƒ 1 , . . . , ƒ n ) over the subdomain.

4. The method of claim 2 , wherein the direct-comparison technique is applied once for every n iterations of the gradient technique.

5. The method of claim 4 , wherein the iterations continue until either a predetermined maximum number of iterations are performed, or the largest area of any subdomain is below a predetermined value.

6. The method of claim 1 ,

wherein a subdomain U certainly dominates a subdomain V if every point uεU dominates every point vεV; and

wherein a point u dominates a point v under minimization if,

u i #v i , i=1, . . . , n, and

u i <v i for some iε{1, . . . , n}.

7. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for using interval techniques within a computer system to solve a multi-objective optimization problem, wherein the computer-readable storage medium can be any device that can store code and/or data for use by a computer system, the method comprising:

receiving a representation of multiple objective functions (ƒ 1 , . . . , ƒ n ) at the computer system, wherein (ƒ 1 , . . . , ƒ n ) are scalar functions of a vector X=(x 1 , . . . , x n );

receiving a representation of a domain of interest for the multiple objective functions;

storing the representations in a memory within the computer system; and

performing an interval optimization process to compute guaranteed bounds on a Pareto front for the objective functions (ƒ 1 , . . . , ƒ n ), wherein for each point on the Pareto front, an improvement in one objective function cannot be made without adversely affecting at least one other objective function;

wherein performing the interval optimization process involves applying a direct-comparison technique between subdomains of the domain of interest to eliminate subdomains that are certainly dominated by other subdomains,

wherein performing the interval optimization process involves applying a gradient technique to eliminate subdomains that do not contain a local Pareto optimum,

wherein a subdomain [x] i is eliminated by the gradient technique if an intersection of certainly negative gradient regions C j for each objective function ƒ j is non-empty,

⋂

j

=

1

n

⁢

C

j

⁡

(

[

x

]

j

)

≠

∅

,

and

wherein the certainly negative gradient region C j for objective function ƒ j is the intersection of N j ([x] i ) (the negative gradient region associated with the minimum angle θ j of the gradient of ƒ j over the subdomain [x] i ) and N j ([x] i )(the negative gradient region associated with the maximum angle θ j of the gradient of ƒ j over the subdomain [x] i ).

8. The computer-readable storage medium of claim 7 , wherein the method further comprises iteratively:

bisecting remaining subdomains that have not been eliminated by the gradient technique; and

applying the gradient technique to eliminate bisected subdomains that do not contain a local Pareto optimum.

9. The computer-readable storage medium of claim 8 , wherein bisecting a subdomain involves bisecting the subdomain in the direction that has the largest width of partial derivatives of all objective functions (ƒ i , . . . , ƒ n ) over the subdomain.

10. The computer-readable storage medium of claim 8 , wherein the direct-comparison technique is applied once for every n iterations of the gradient technique.

11. The computer-readable storage medium of claim 10 , wherein the iterations continue until either a predetermined maximum number of iterations are performed, or the largest area of any subdomain is below a predetermined value.

12. The computer-readable storage medium of claim 7 ,

wherein a subdomain U certainly dominates a subdomain V if every point uεU dominates every point vεV; and

wherein a point u dominates a point v under minimization if,

u 1 #v i i=1, . . . , n, and

u i <v i for some iε{1, . . . , n}.

13. An apparatus that uses interval techniques to solve a multi-objective optimization problem, comprising:

a receiving mechanism configured to receive a representation of multiple objective functions (ƒ 1 , . . . , ƒ n ), wherein (ƒ 1 , . . . , ƒ n ) are scalar functions of a vector x=(x 1 , . . . , x n );

wherein the receiving mechanism is configured to receive a representation of a domain of interest for the multiple objective functions;

a memory configured to store the representations; and

an interval optimizer configured to performing an interval optimization process to compute guaranteed bounds on a Pareto front for the objective functions (ƒ 1 , . . . , ƒ n ), wherein for each point on the Pareto front, an improvement in one objective function cannot be made without adversely affecting at least one other objective function;

wherein the interval optimizer is configured to apply a direct-comparison technique between subdomains of the domain of interest to eliminate subdomains that are certainly dominated by other subdomains,

wherein the interval optimizer is configured to apply a gradient technique to eliminate subdomains that do not contain a local Pareto optimum,

wherein a subdomain [x] i is eliminated by the gradient technique if an intersection of certainly negative gradient regions C j for each objective function ƒ j is non-empty,

⋂

j

=

1

n

⁢

C

j

⁡

(

[

x

]

j

)

≠

∅

,

and

wherein the certainly negative gradient region C j for objective function ƒ j is the intersection of N j ([x] i ) (the negative gradient region associated with the minimum angle θ j of the gradient of ƒ j over the subdomain [x] i ) and N j ([x] i ) (the negative gradient region associated with the maximum angle θ j of the gradient of over the subdomain [x] i ).

14. The apparatus of claim 13 , wherein the interval optimizer is configured to iteratively:

bisect remaining subdomains that have not been eliminated by the gradient technique; and to

apply the gradient technique to eliminate bisected subdomains that do not contain a local Pareto optimum.

15. The apparatus of claim 14 , wherein bisecting a subdomain involves bisecting the subdomain in the direction that has the largest width of partial derivatives of all objective functions (ƒ 1 , . . . , ƒ n ) over the subdomain.

16. The apparatus of claim 14 , wherein the direct-comparison technique is applied once for every n iterations of the gradient technique.

17. The apparatus of claim 16 , wherein the iterations continue until either a predetermined maximum number of iterations are performed, or the largest area of any subdomain is below a predetermined value.

18. The apparatus of claim 13 ,

wherein a subdomain U certainly dominates a subdomain V if every point uεU dominates every point vεV; and

wherein a point u dominates a point v under minimization if,

u i #v i , i=1, . . . , n, and

u i <v i for some iε{1, . . . ,n}.