Knowing when a Pareto front has stopped moving

The problem with multi-objective optimization

Anyone who has run a multi-objective design study knows the concern of not knowing when to stop. In a single-objective optimization study, convergence is easy to reason about: there’s one performance score, and you can watch the best-so-far value flatten out. Multi-objective Pareto studies aren’t so easy. Instead of chasing a single best solution, we are searching for trade-offs between conflicting objectives that are “equally good”, meaning that none of them dominates the others across all objectives. Consequently, we must track the performance of multiple solutions and come up with a procedure to quantify the convergence.

That raises three questions that are hard to answer just by eyeballing a Pareto plot:

• Is the optimization actually converging, or is it still exploring?
• Have any feasible solutions been found yet, or is everything still violating constraints?
• Does my study need more compute budget?

Simcenter HEEDS 2604 answers all three with a new run-time analytics feature: the Pareto Convergence plot.

What is a Pareto front?

In a multi-objective study, one design dominates another when it is no worse in any objective and better in at least one. A design that no other design dominates is called non-dominated, or Pareto-optimal: none of its objectives can be improved without making at least one other objective worse. The Pareto front is the set of these non-dominated designs, plotted in objective space. It does not point to one best design; it shows the trade-offs on offer, and the engineer chooses the compromise. With more than two objectives, the front becomes a surface, or a set of points in a higher-dimensional space.

Four related terms:

• Rank: Rank 1 is the current Pareto front, the designs that no other evaluated design dominates. Rank 2 is the next non-dominated layer once Rank 1 is set aside, and so on. Because ranks are relative to all the designs evaluated so far, a design that was non-dominated early can be pushed down to Rank 3 or 4 when better designs appear. That is why the drift below compares accumulated fronts. Pareto Plot Insights in Simcenter STAR-CCM+ Design Manager shows the ranks in a Pareto plot.
• Multi-objective optimisation: a search for the best trade-offs between two or more conflicting objectives instead of a single optimum, also called Pareto optimisation. In Simcenter HEEDS, the multi-objective SHERPA strategy (MO-SHERPA) treats the objectives independently of each other and returns a set of trade-off designs. A worked example: Multi-Objective Optimization with Simcenter HEEDS and Simcenter Amesim.
• Hypervolume: the size of the region in objective space that a set of designs dominates, measured up to a reference point. A larger hypervolume means a better front; Simcenter HEEDS 2510 uses hypervolume metrics in SHERPA (Simcenter HEEDS 2510: multi-objective SHERPA compared with 2504).
• Surrogate model: a fast predictive function, trained on simulation results, that estimates a response for new input values, so an optimiser can try a design in seconds instead of hours or days. Simcenter HEEDS builds polynomial, radial basis function and Kriging surrogates and compares them, and since 2510 it can also build neural network surrogates from study data; a surrogate can stand in for an analysis such as a Simcenter STAR-CCM+ run. Check the final front with full simulations: in Volupe’s heat sink test, the fully simulated front was still the best. More in HEEDS Smarter Tools for Better Surrogate Results and Surrogate Models.

What the Pareto Convergence plot actually shows

The core idea is to track how much the Pareto front (solutions which cannot improve one objective without making another one worse) is still moving, cycle over cycle, and turn that into a single number: the Pareto Drift.

Let’s take a closer look at how the curve is built. Let N be the latest cycle evaluated at the moment the plot is drawn, and let the reference set be the accumulated Pareto solutions (Rank 1) found from the start of the study through cycle N, i.e. the best-so-far front, as of right now. Now we sweep a second index, across every cycle from 1 up to N. For each T:

• Take the accumulated Pareto set found from the start of the study through cycle T (not just the solutions discovered in cycle T).
• Measure its average distance to the reference set (the accumulated front through N).

Plotting that distance against T, for every T from 1 to N, produces the drift curve. Two things fall out of this naturally:

• T = N always sits at (or near) zero drift, since at that point you’re comparing the accumulated front to itself.
• Early T values show the largest drift, since the front was still immature and far from where the study eventually settled.

So the curve isn’t built once and appended to: every time a new cycle finishes, N moves forward, the reference set updates, and the entire curve is recomputed against the new reference. Watching the curve flatten near zero as it approaches the right edge is the signal that the front has stabilized: like watching a residual converge in a CFD run, except here the whole history gets re-evaluated against the newest endpoint each time. The figure below shows two different states of the drift curve, after 600 designs (left) and after 800 designs (right). It noticeably changed magnitudes and the shape is slightly changed as well.

A bonus: feasibility detection for free

Because of how the drift value is normalized, it carries a second piece of information almost as a side effect: feasibility.

• Pareto Drift > 1 → at least one constraint is still violated; the current front includes infeasible solutions.
• Pareto Drift between 0 and 1 → feasible solutions are present.

This means the same plot that tells you whether the optimization has converged also tells you when the study first crossed into the feasible region. For heavily constrained problems this is enormously useful. Rather than scanning through hundreds of designs after the fact to find the first feasible candidate, you can see the exact cycle where the curve drops below the feasibility threshold. The figure above shows the drop of the drift value between the 11th and 12th cycle together with the corresponding Pareto plot of the feasible region. In cycle 12 we obtained the first 2 feasible designs in rank 1. Rank 2 remains infeasible.

Takeaway

The Pareto Convergence plot in Simcenter HEEDS 2604 turns “is my multi-objective study converging?” from a judgment call into something you can read off a chart, in real time, while the study is still running. For teams running expensive multi-objective studies it’s a small addition with a tremendous effect on how confidently you can manage the compute budget and communicate progress.

If the drift shows that a study needs more budget, size the next run before you spend it. Simcenter HEEDS 2510 suggests a minimum number of evaluations for single- and multi-objective SHERPA studies (Optimization Intelligence), and Volupe’s design of experiments (DOE) calculator shows how many runs your deadline allows and suggests a design for your goal, from factorial and Box–Behnken designs to Latin hypercube and Sobol sampling, with the points as CSV.