Learn about MOOPs

Overview

A multiobjective optimization problem (MOOP) is an optimization problem involving multiple, potentially conflicting, objectives. MOOPs arise in many areas of science and engineering, for example, when designing a product or fitting a model according to multiple performance criteria.

The goal of a MOOP is to find numerous solutions that describe the tradeoffs between these (potentially conflicting) objectives. The solution to a MOOP is a set of achievable objective values (and corresponding design points), describing the inherent tradeoffs in the problem. This tradeoff curve is called the Pareto front. Real-world MOOPs may also involve some constraints—additional hard rules that every solution must adhere to.

In a multiobjective simulation-based optimization problem, the objectives are derived from the outputs of one or more expensive simulations.

Here, we use the term simulation in its broadest sense. In our terminology, a simulation could refer to any data-generating process of sufficient complexity, including

• numerical simulations run on a computer,

• physical experiments performed in a laboratory environment, and

• other nontrivial data-generating campaigns.

A simulation’s expense can be judged by any of several factors, including

• the amount of time that is required to complete the simulation;

• the simulation’s occupation of valuable scientific resources, such as computing nodes or laboratory equipment;

• the need for expert/human involvement to validate simulation outputs; and

• consumption of raw resources such as energy or laboratory materials.

ParMOO is designed to solve multiobjective simulation-based optimization problems by exploiting the simulation-based structure in such problems.

One of the key concepts in ParMOO is the distinction between simulations and objectives.

In ParMOO, a simulation is an expensive or time-consuming process: it may require significant computational resources and may have a nonnegligible execution time.

\[{\bf S} : {\cal X} \rightarrow {\cal S}, \qquad {\cal X} \subset \mathbb{R}^n, {\cal S} \subset \mathbb{R}^m.\]

A single MOOP may involve multiple simulations, with varying costs, which map from the design variables to an intermediate space

ParMOO provides a framework for solving these problems, while parallelizing simulation evaluations.

In ParMOO, both objectives and constraints are algebraic functions of the design variables and/or the simulation outputs. After evaluating the simulation(s), evaluating the objective is assumed to be computationally inexpensive and tends to present a smaller opportunity for parallelization.

Objectives are expressed as

\[{\bf F} :{\cal X} \times {\cal S} \rightarrow {\cal Y}, \qquad {\cal Y} \subset \mathbb{R}^o.\]

Constraints are expressed as

\[{\bf G} :{\cal X} \times {\cal S} \rightarrow \mathbb{R}^p.\]

ParMOO allows its users to separately specify simulations, objective functions, and constraint functions. ParMOO will then utilize simulations sparingly, but it may use many objective and constraint evaluations to solve problems of the form

\[\min_{{\bf x} \in {\cal X}} {\bf F}({\bf x}, {\bf S}({\bf x})) \quad {s.t.} \quad {\bf G}({\bf x}, {\bf S}({\bf x})) \leq {\bf 0}^* .\]

\(^*\) Here “\(\min\)” is understood in the Pareto sense.

ParMOO Algorithm

ParMOO uses response surface methodology to solve MOOPs. This means that ParMOO fits a computationally cheaper surrogate to each output simulation, then optimizes various scalarizations of your problem using these surrogates instead of running the expensive simulations.

The key difference between ParMOO and other response surface techniques is that ParMOO uses its surrogates to model the simulation response surfaces, not to directly model the objective values. This allows ParMOO to exploit additional information about your problem, in situations where it is available.

Common use cases include the following.

• One or more objectives does not depend on any simulation outputs and therefore can be evaluated directly without concern for computational expense.

• The MOOP involves multiple simulations, each with differing costs, and therefore one simulation can be evaluated far more times than the other.

• The objectives have some exploitable structure, for example, the sum-of-squared simulation outputs, which readily admits additional information about the shape of the objective response surfaces.

This process has several key components, which ParMOO allows users to interchange.

• Before fitting any surrogates or performing any scalarizations, ParMOO must search the design space using one of the GlobalSearch implementations from the parmoo.searches module.

• After some data has been generated, ParMOO fits and updates a surrogate for each simulation output using one of the SurrogateFunction implementations from the parmoo.surrogates module.

• After fitting surrogates, ParMOO must scalarize the objectives so that it can solve the surrogate problems and produce candidate design points using one of the AcquisitionFunction implementations from the parmoo.acquisitions module.

• ParMOO must solve the scalarized surrogate optimization problems using one of the SurrogateOptimizer implementations from the parmoo.optimizers module.

You may mix and match built-in techniques to generate your own unique MOOP solver, or you may implement your own techniques by employing one of the abstract base classes defined in parmoo.structs.

Glossary

• Acquisition function: An acquisition function is our language for a family of scalarizing functions, which can be used to specify targets on the Pareto front. Acquisition functions may use objective scores, gradient values, and/or uncertainty information in order to guide ParMOO’s search for an approximation to the Pareto front.

  • Ex.– common acquisition functions from the literature include weighted sums (averages) of objective values, the epsilon constraint method, and expected hypervolume improvement.

• Design variable: A design variable is an input to your simulations, which can be controlled within some reasonable bounds.

  • Ex.- when designing an air foil using a fluid dynamics simulation, one design variable might be the angle of attack.

  • ParMOO currently supports continuous and categorical design variables.

• Design space: The design space is the underlying vector space where you could represent all possible design variable combinations.

  • Ex.- if you have \(n\) continuous design variables, then your design space would be all of \(\mathbb{R}^n\).

• Constraint: A constraint is a requirement that every solution point must satisfy.

  • Ex.- if your simulation code fails whenever \(x_1 > x_2\), then you might impose the constraint: \(x_2 - x_1 \leq 0\).

• Hard constraint: A hard constraint cannot be violated by the MOOP solver. ParMOO will never attempt to evaluate a point that violates a hard constraint.

  • Ex.- your simulation code does not need to be defined for points that are outside the upper/lower bounds on the design variables.

• Soft constraint: A soft constraint must be satisfied for a point to be considered a solution, but ParMOO may violate it during the course of the optimization process.

  • Ex.- all nonlinear constraints are soft constraints for ParMOO, and ParMOO will evaluate design points that violate these constraints, especially early in the optimization process.

• Bound constraint: A bound constraint is a simple upper/lower bound on the range of design values. In ParMOO, these are treated as hard constraints, while all other constraints are considered to be soft.

• Feasible design space: The feasible design space is the subset of the design space where all constraints (both hard and soft) are satisfied. In other words, this is the set of all “legal” designs.

  • Ex.- if you have n continuous design variables, constrained to the unit cube, then your entire design space is still \(R^n\), but your feasible design space is the cube \([0, 1]^n\).

• Simulation: A simulation can refer to any complex process for generating scientific or engineering data. This includes both numerical simulations and laboratory experiments. The data that is gathered from your simulation might used to compute your objectives, constraints, or both.

  • Ex.- if you are designing a material, your simulation may be a molecular dynamics code or a process for synthesizing new materials in the laboratory.

  • Each simulation may have a single output or many outputs, which will be passed on as inputs to your objectives and/or constraints.

• Objective: An objective is one of possibly many criteria that you will use to rank the “goodness” of a particular design configuration. By convention, we assume that your goal is to minimize all objectives.

  • Ex.- if you are designing materials, you may want to minimize the production of unwanted byproducts.

  • If your goal is actually to maximize an objective \(f_{max}\), you may supply the negated value of that objective \(-f_{max}\) to ParMOO.

• Feasible objective space: The feasible objective space is the image of the feasible design space – i.e., the set of all objective values that can be obtained, by evaluating every objective at configurations from the feasible design space.

  • In practice, you will not know your feasible objective space a priori.

• Nondominated: A point \({\bf y}^*\) in a set \({\cal V} \subset \mathbb{R}^p\) is nondominated if for all \({\bf y} \in {\cal V}\), either \({\bf y} = {\bf y}^*\) or \({\bf y}^*\) is less than \({\bf y}\) in at least one of its \(p\) components.

  • Objective values that are feasible and nondominated in the set of all observations make up the solution set returned by ParMOO.

• Pareto optimal: A point in the feasible objective space is Pareto optimal for a given MOOP if it is nondominated in the feasible objective space.

  • This is a member of the true solution set for a MOOP.

  • In practice, we cannot typically guarantee that any point in a multiobjective simulation optimization problem is Pareto optimal, so we return solutions that are nondominated among all other objective values that we have observed.

• Pareto front: The Pareto front is the set of all Pareto optimal objective points.

  • This is the true solution to a multiobjective optimization problem.

• Efficient set: The efficient set is the set of all corresponding design configurations that produce points on the Pareto front.

  • These are the solutions in the feasible design space, which are the pre-image of the Pareto front.

• Surrogate: A surrogate is a computational model that approximates another underlying function.

  • Ex.- a trained artificial neural network, Gaussian process, RBF model, or spline interpolant.

• Scalarization: A scalarization technique reduces a MOOP into a single-objective optimization problem. Typically, solving the scalarized problem should produce a solution that is efficient/Pareto optimal.

  • Ex.- minimize the weighted sum of all objectives in a MOOP to obtain a single efficient point/Pareto optimal value.

• Design of experiments/experimental design: An experimental design is a set of design points that are in some sense space filling and could be evaluated to gain some initial data for a particular simulation.

  • Ex.- generate 100 uniform random samples within the feasible design space.