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 (Formula presented.), the resulting samples lie on an (Formula presented.) -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 (Formula presented.), (Formula presented.), where (Formula presented.). CATS builds a simplicial mesh over the reference simplex and refines the cell with the largest local interpolation quantity (Formula presented.), where (Formula presented.) is an upper bound on the Hessian norm of the kth component of the oracle-induced map over (Formula presented.). This quantity matches the natural error scale of affine interpolation for (Formula presented.) maps. The rigorous certified interpretation of CATS applies when the preference-to-Pareto map is single-valued, (Formula presented.), 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 (Formula presented.) guarantees (Formula presented.), and that the oracle complexity of certified simplicial piecewise-affine reconstruction is (Formula presented.). On the rigorously certified core tests, CATS uses (Formula presented.) – (Formula presented.) fewer oracle calls than uniform reference-direction sampling and (Formula presented.) – (Formula presented.) 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.