Search and poll method for solving multi-fidelity optimization problems

Patent metadata

Field	Value
Publication number	US-2017011143-A1
Application number	US-201514794792-A
Country	US
Kind code	A1
Filing date	Jul 8, 2015
Priority date	Jul 8, 2015
Publication date	Jan 12, 2017
Grant date	—

Abstract

A computer-implemented search and poll method can iteratively solve a multi-fidelity optimization problem including an objective function and any constraints. A search step of the method includes constructing and optimizing surrogates of the objective function and any constraints to identify a new set of trial points, and running lower fidelity simulations in ascending order to reduce a number of trial points in the new set. The search step further includes evaluating the reduced number of trial points with the objective function and any constraints using a high fidelity simulation.

First claim

1 . A computer-implemented search and poll method for iteratively solving a multi-fidelity optimization problem including an objective function and any constraints, wherein a search step of the method includes:
constructing and optimizing surrogates of the objective function and any constraints to identify a new set of trial points, running lower fidelity simulations in ascending order to reduce a number of trial points in the new set; and evaluating the reduced number of trial points with the objective function and any constraints using a high fidelity simulation.

2 . The method of claim 1 , wherein at least two lower fidelity simulations are run.

3 . The method of claim 1 , wherein those trial points predicted to perform poorly by the lower fidelity simulations are removed from the new set.

4 . The method of claim 1 , wherein the optimization problem includes the objective function and nonlinear constraints; wherein the surrogates of the objective function and the nonlinear constraints are optimized; and wherein the reduced number of trial points is evaluated with the objective function and the nonlinear constraints.

5 . The method of claim 1 , wherein the optimization problem has derivatives that are unavailable or unreliable, and the objective function and any constraints are non-smooth or discontinuous or fail when queried.

6 . The method of claim 1 , wherein the surrogates are constructed as functions of input variables and fidelity level, whereby the surrogates are constructed as mixed variable surrogate functions.

7 . The method of claim 1 , wherein kriging functions are used as the surrogates, each kriging function including a single regression function and at least one correlation matrix.

8 . The method of claim 7 , wherein the kriging functions are mixed variable such that each kriging function has a single regression function and a single correlation matrix that take as inputs both the fidelity level and variables of the optimization problem.

9 . The method of claim 1 , wherein running the lower fidelity simulations includes looping through fidelity levels m=1 to M−1 in ascending order, where level M is the highest fidelity level, wherein for each iteration,
the objective function and any constraints are evaluated at points x ∈ Sk at fidelity level m and the surrogate functions are updated;
the surrogates are evaluated at points x ∈ Sk at fidelity level M; and
the trial points from Sk are removed for which the surrogates do not predict a high likelihood of a successful iteration.

10 . The method of claim 9 , wherein each iteration further includes performing a poll step if the search step is unsuccessful.

11 . The method of claim 1 , wherein the objective function and any constraints model three-dimensional flow of air over an airfoil.

12 . A computer comprising a processor and memory encoded with data for causing the processor to perform a search and poll method to iteratively solve a multi-fidelity optimization problem including an objective function and any constraints, wherein a search step of the method includes:
constructing and optimizing surrogates of the objective function and any constraints to identify a new set of trial points, running lower fidelity simulations in ascending order to reduce a number of trial points in the new set; and evaluating the reduced number of trial points with the objective function and any constraints using a high fidelity simulation.

13 . The computer of claim 12 , wherein the optimization problem includes the objective function and nonlinear constraints.

14 . The computer of claim 13 , wherein the surrogates are mixed variable kriging functions.

15 . The computer of claim 12 , wherein at least two lower fidelity simulations are run per search step.

16 . The computer of claim 12 , wherein running the lower fidelity simulations includes looping through fidelity levels m=1 to M−1 in ascending order, where level M is the highest fidelity level, wherein for each iteration and S k is the new set of trial points,
the objective function and any constraints are evaluated at points x ∈ S k at fidelity level m and the surrogate functions are updated;
the surrogates are evaluated at points x ∈ Sk at fidelity level M; and
the trial points from S k are removed for which the surrogates do not predict a high likelihood of a successful iteration.

17 . An article comprising computer-readable memory encoded with data that, when executed, causes a computer to perform a search and poll method to iteratively solve a multi-fidelity optimization problem including an objective function and any constraints, wherein a search step of the method includes:
constructing and optimizing surrogates of the objective function and any constraints to identify a new set of trial points, running lower fidelity simulations in ascending order to reduce a number of trial points in the new set; and evaluating the reduced number of trial points with the objective function and any constraints using a high fidelity simulation.

18 . The article of claim 17 , wherein at least two lower fidelity simulations are run per search step.

19 . The article of claim 17 , wherein the surrogates are mixed variable kriging functions, each kriging function including a single regression function and a single correlation matrix that take as inputs both the fidelity level and variables of the optimization problem.

20 . The article of claim 17 , wherein running the lower fidelity simulations includes looping through fidelity levels m=1 to M−1 in ascending order, where level M is the highest fidelity level, wherein for each iteration and S k is the new set of trial points,
the objective function and any constraints are evaluated at points x ∈ S k at fidelity level m and the surrogate functions are updated;
the surrogates are evaluated at points x ∈ Sk at fidelity level M; and
the trial points from S k are removed for which the surrogates do not predict a high likelihood of a successful iteration.

Assignees

• Boeing Co

Inventors

• Abramson Mark A
• Booker Andrew J
• Cramer Evin J
• Simonis Joseph P

Classifications

• G06F30/20 Primary

  Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) · CPC title

• G06F30/15

  Vehicle, aircraft or watercraft design · CPC title

• G06F2111/04

  Constraint-based CAD · CPC title

• G06F17/5009 Primary

  Physics · mapped topic

• G06F2111/06

  Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA] · CPC title