Accelerating Multi-Objective Optimization under High Evaluation Costs

54 concepts53 papers1 proposal

In single-objective optimization, the goal is straightforward: find the single point that minimizes or maximizes a target metric. In multi-objective optimization (MOO), however, the goal shifts from finding a single point to mapping an entire manifold known as the Pareto front. This front represents the optimal set of trade-offs where no single objective can be improved without degrading another.

As noted by Bandyopadhyay, discovering a diverse and comprehensive Pareto front is vastly more computationally intensive than traditional single-objective optimization. This challenge becomes acute when evaluating a single candidate solution is expensive—such as when it requires hours of hardware simulation (Joardar et al.), training deep neural networks from scratch (Dushatskiy et al.), or executing complex physical experiments (Li et al.). When individual function evaluations carry high costs, standard evolutionary algorithms that rely on thousands of iterations become completely intractable.

To overcome this bottleneck, recent research focuses on exploiting the underlying structure of the objective space to approximate, interpolate, or amortize the Pareto front with minimal evaluations.

The Inefficiency of Independent Scalarization

The traditional way to solve multi-objective problems is to convert them into a series of single-objective subproblems. This is typically done via scalarization—combining multiple objectives into a single metric using a weighted sum or a localized target. By systematically varying these weights, an optimization algorithm can trace out the Pareto front point by point.

However, treating these subproblems as independent tasks introduces massive computational redundancy. As Parisi et al. and Chen et al. point out, adjacent points on a Pareto front share deeply related features and structural properties. If an algorithm solves for a trade-off that equally balances two objectives, that solution contains substantial information about a neighboring trade-off that slightly favors one objective over the other. Independent optimization runs discard this shared structure, forcing expensive solvers to repeatedly rebuild value functions or search paths from scratch (Roijers et al.).

Furthermore, the mathematical overhead of managing multi-objective criteria adds to the computational burden. For instance, evaluating the "quality" of a discovered front often requires computing its hypervolume—a calculation that scales poorly as the number of objectives increases. To mitigate this specific overhead, Tsukamoto et al. demonstrate that replacing exact hypervolume calculations with fast approximations based on scalarizing functions can drastically accelerate optimization algorithms. Similarly, Wang shows that dynamically relaxing the strictness of Pareto dominance criteria during the search process can prevent algorithms from wasting evaluations on minor, inconsequential trade-offs.

Amortizing the Front via Hypernetworks

Rather than discovering points on the Pareto front sequentially, a powerful alternative paradigm seeks to learn the entire continuous front simultaneously using a single model. This is known as amortized optimization.

An elegant realization of this idea is found in Pareto Hypernetworks (PHNs), introduced by Navon et al.. Instead of training separate neural networks for every possible trade-off configuration, the authors train a single "hypernetwork." This hypernetwork takes a user's specific preference vector (e.g., "prioritize model accuracy over inference speed") as an input and directly generates the optimal weights for the target network.

Preference Vector (e.g., [0.8, 0.2]) ──> [ Hypernetwork ] ──> Target Network Weights ──> Instant Evaluation

Because the hypernetwork is a continuous function, it learns to map the entire topology of the Pareto front at once. It smooths over the trade-off space, allowing users to navigate the front instantly at runtime with zero additional training cost. To further reduce the sample complexity of setting up these models, Yu leverages meta-learning to "warm-start" optimization frameworks on new, expensive tasks by transferring structural knowledge from related, previously solved landscapes.

Geometric and Manifold Interpolation

When function evaluations are so limited that even training a hypernetwork is out of reach, researchers leverage the geometric property that Pareto fronts often form smooth, low-dimensional manifolds embedded within a higher-dimensional objective space.

Instead of evaluating thousands of points to find this manifold, we can optimize a tiny, sparse set of high-quality "anchor" points and mathematically fill in the gaps. Tanabe et al. formalize this in a two-phase framework called TPB. In the first phase, a surrogate-model-based algorithm identifies a small number of optimal trade-off solutions. In the second phase, the framework fits a Bézier simplex—a smooth, geometric surface patch—to interpolate the remainder of the Pareto front.

By shifting the burden of discovering new trade-offs from expensive physical or numerical simulations to cheap geometric interpolation, this approach maps complex fronts with a fraction of the evaluation budget. This geometric insight is mirrored by Li et al. through manifold interpolation techniques, and by Li et al., who utilize quadratic approximations to efficiently amortize the Pareto front when merging large-scale neural networks.

Active Information Gathering and Batching

When true evaluations are unavoidable, the challenge becomes purely informational: how do we select the next point to sample so that we learn the maximum amount of information about the Pareto front? This is the domain of multi-objective Bayesian Optimization (MOBO).

Instead of sampling blindly, MOBO uses probabilistic surrogate models (like Gaussian Processes) to predict both the expected performance and the uncertainty of unexplored designs. Gaudrie et al. design targeted acquisition criteria that allow practitioners to focus these expensive evaluations on specific, preferred regions of the front rather than wasting resources mapping parts of the trade-off space they do not intend to use.

To accelerate this process in modern parallel computing environments, Garrido-Merchán et al. developed parallel predictive entropy search. This method calculates the information gain a batch of points will provide about the entire optimal Pareto set. By evaluating how an entire group of points collectively reduces uncertainty, the algorithm can safely run multiple high-cost simulations in parallel without sampling redundant regions of the search space. Managing this selection process can itself be framed as a bi-objective optimization problem, balancing the immediate exploitation of known high-performing areas against the exploration of highly uncertain regions (Carciaghi et al.).

Key Foundational Work

A pareto-compliant surrogate approach for multiobjective optimization (2010) — contributed 2 concept elements to this direction.
A mono surrogate for multiobjective optimization (2010) — contributed 1 concept elements to this direction.
Dominance-Based Pareto-Surrogate for Multi-Objective Optimization (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_expensive_multi_objective_optimization_8985ce0e,
  title = {expensive multi-objective optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expensive-multi-objective-optimization/rdr_8985ce0ec3ef45dbafa2acae21db2567},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_expensive_multi_objective_optimization_8985ce0e_v1,
  title = {expensive multi-objective optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expensive-multi-objective-optimization/rdr_8985ce0ec3ef45dbafa2acae21db2567/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake