Certified Adaptive Triangulation Sampling for Deterministic Pareto-Surface Reconstruction

Many deterministic multi-objective optimization methods generate Pareto outcomes by repeatedly solving scalarized subproblems for different preference or reference vectors. When the number of objectives is m≥3, the resulting samples lie on an (m−1)-dimensional Pareto surface in objective space. For tasks such as visualization, trade-off exploration, interactive decision making, and sensitivity analysis, a finite cloud of non-dominated points may be insufficient; one often needs a continuous surrogate of the Pareto surface together with a quantitative control of its reconstruction error. This paper studies the corresponding outer-loop reconstruction problem: how should new reference vectors be selected so as to reconstruct the Pareto surface to a prescribed uniform accuracy while using as few scalarized solves as possible? We propose Certified Adaptive Triangulation Sampling (CATS), a curvature-aware adaptive triangulation method for reconstructing a Pareto surface from an oracle u↦z(u), u∈Δd, where d=m−1. CATS builds a simplicial mesh over the reference simplex and refines the cell with the largest local interpolation quantity η(τ)=12maxkMτ,kdiam(τ)2, where Mτ,k is an upper bound on the Hessian norm of the kth component of the oracle-induced map over τ. This quantity matches the natural error scale of affine interpolation for C2 maps. The rigorous certified interpretation of CATS applies when the preference-to-Pareto map is single-valued, C2, and equipped with reliable local Hessian-norm upper bounds. If such bounds are replaced by numerical curvature estimates, the same rule can still be used as an adaptive refinement indicator, but the resulting stopping test is not a formal certificate unless those estimates are themselves validated. Under the certified assumptions, we prove that the stopping condition maxτη(τ)≤ε guarantees supu∈Δd∥z(u)−z^(u)∥∞≤ε, and that the oracle complexity of certified simplicial piecewise-affine reconstruction is Θ(ε−d/2). On the rigorously certified core tests, CATS uses 2.7×–3.8× fewer oracle calls than uniform reference-direction sampling and 1.2×–1.6× fewer than an AWS-inspired patch-area refinement rule. Additional benchmark studies, evaluated with the same interpolation quantity as a practical stopping indicator, show the same qualitative advantage, especially on anisotropic and localized surface geometries.