Introduction
Multi-objective optimization (MOO) is increasingly important in modern artificial intelligence (AI), including multimodal learning {(citep}(Wei & Hu, 2024; Saha et al., 2025)}, large language model (LLM) alignment {(citep}(Shi et al., 2024)}, and agentic AI systems {(citep}(Zhang et al., 2026)}. Let x x x be a decision variable in the feasible domain X ⊆ R n \mathcal{X} \subseteq\mathbb{R}^{n} X ⊆ R n . MOO minimizes a vector of objective functions f m : X → R f_m : \mathcal{X} \to\mathbb{R} f m : X → R :
min x ∈ X f ( x ) : = [ f 1 ( x ) , f 2 ( x ) , … , f M ( x ) ] T . (1) \min_{x \in\mathcal{X}} \mathbf{f}(x) := [f_1(x), f_2(x), \ldots, f_M(x)]^{\mathsf{T}} . \tag*{(1)} x ∈ X min f ( x ) := [ f 1 ( x ) , f 2 ( x ) , … , f M ( x ) ] T . (1)
In MOO, there is generally no single solution that minimizes all objectives simultaneously. Instead, the goal of (1) is to find a Pareto-optimal solution x ⋆ ∈ X x^{\star} \in\mathcal{X} x ⋆ ∈ X , for which no x ∈ X x \in\mathcal{X} x ∈ X satisfies f m ( x ) ≤ f m ( x ⋆ ) f_m(x) \le f_m(x^{\star}) f m ( x ) ≤ f m ( x ⋆ ) for all m m m , with strict inequality for at least one m m m . The collection of such solutions is called the Pareto set X P F \mathcal{X}_{\mathrm{PF}} X PF . Its image F P F : = f ( X P F ) \mathcal{F}_{\mathrm{PF}} := f(\mathcal{X}_{\mathrm{PF}}) F PF := f ( X PF ) forms the Pareto front (PF) {(citep}(Miettinen, 1999)}.
Preference information is essential in MOO because Pareto optimality alone does not determine which tradeoffs matter most to a decision maker {(citep}(Pajasmaa et al., 2025)}. Under standard regularity conditions, the PF forms an ( M − 1 ) (M-1) ( M − 1 ) -dimensional manifold of tradeoff solutions {(citep}(Hillermeier, 2001)}. This motivates two classical paradigms. A priori methods incorporate preferences before optimization to target preferred Pareto solutions {(citep}(Chen et al., 2024, 2025)}, but require preferences to be specified in advance. A posteriori methods instead construct a representative PF approximation for later selection {(citep}(Zhang et al., 2024; Boehmer & Wittmann, 2026)}, but must represent a continuous PF with finitely many solutions. This raises a fundamental question of how to allocate these solutions across the PF so that the resulting approximation reflects the desired preference distribution:
(Q1) How to generate Pareto solutions whose distribution matches a desired preference on the PF?
To specify the desired distribution of Pareto solutions, we prescribe a positive (unnormalized) preference profile ϑ : f ( X ) → ( 0 , ∞ ) \vartheta: f(\mathcal{X}) \to(0, \infty) ϑ : f ( X ) → ( 0 , ∞ ) over attainable objective values {(citep}(Wang et al., 2017; Chen et al., 2024). On the PF F P F ⊆ f ( X ) \mathcal{F}_{\mathrm{PF}} \subseteq f(\mathcal{X}) F PF ⊆ f ( X ) , larger values of ϑ \vartheta ϑ indicate regions where more Pareto solutions are desired, with ϑ ≡ 1 \vartheta\equiv1 ϑ ≡ 1 corresponding to uniform surface-area coverage. Existing methods seek Pareto stationarity, specified tradeoffs, or well-spread representations, but offer limited control over aligning a finite Pareto representation with ϑ \vartheta ϑ [22 , 36 , 48 , 72 ] . To address this challenge, we build on scalarization, which generates Pareto solutions by solving single-objective problems parameterized by weights w \mathbf{w} w in the ( M − 1 ) (M-1) ( M − 1 ) -dimensional simplex Δ M \Delta_M Δ M [25 , 40 ] . For example, weighted-sum scalarization yields x ⋆ ( w ) ∈ a r g m i n x ∈ X ∑ m = 1 M w m f m ( x ) \mathbf{x}^{\star}(\mathbf{w}) \in\mathop{\mathrm{argmin}}_{\mathbf{x}\in\mathcal{X}} \sum_{m=1}^{M} w_m f_m(\mathbf{x}) x ⋆ ( w ) ∈ argmin x ∈ X ∑ m = 1 M w m f m ( x ) . Weighted Tchebycheff scalarization (TS) [58 ] can further recover Pareto solutions on nonconvex fronts [24 , 38 ] , as detailed in § 2 . Under suitable regularity, varying w \mathbf{w} w induces the weight-to-PF map [43 , 24 ] (Hillermeier 2001):
w ↦ x ⋆ ( w ) ↦ f P F ( w ) : = f ( x ⋆ ( w ) ) ∈ F P F , w ∈ Δ M . (2) \mathbf{w} \mapsto\mathbf{x}^{\star}(\mathbf{w}) \mapsto\mathbf{f}_{\mathrm{PF}}(\mathbf{w}) := f(\mathbf{x}^{\star}(\mathbf{w})) \in\mathcal{F}_{\mathrm{PF}}, \quad\mathbf{w} \in\Delta_M . \tag*{(2)} w ↦ x ⋆ ( w ) ↦ f PF ( w ) := f ( x ⋆ ( w )) ∈ F PF , w ∈ Δ M . (2)
Although the weight simplex and the PF are both ( M − 1 ) (M-1) ( M − 1 ) -dimensional, equally sized regions in weight space can correspond to regions of different surface areas on the PF [34 ] . We characterize this local area scaling under (2) by the factor J ( w ) J(\mathbf{w}) J ( w ) . As illustrated in Figure 1 , the change-of-variables formula combines J ( w ) J(\mathbf{w}) J ( w ) with the prescribed preference ϑ \vartheta ϑ to yield the target weight density :
Figure 1. Preference ϑ ( f P F ( w ) ) \vartheta(\mathbf{f}_{\mathrm{PF}}(\mathbf{w})) ϑ ( f PF ( w )) and the factor J ( w ) J(\mathbf{w}) J ( w ) measuring PF area scaling jointly determine the target weight density ρ ϑ ( w ) \rho_{\vartheta}(\mathbf{w}) ρ ϑ ( w ) .
ρ ϑ ( w ) ⏟ target weight density ∝ ϑ ( f P F ( w ) ) ⏟ PF preference det ( D f P F ( w ) ⊤ D f P F ( w ) ) ⏟ generalized PF traversal speed ∝ J ( w ) . (3) \underbrace{\rho_{\vartheta}(\mathbf{w})}_{\text{target weight density}} \propto\underbrace{\vartheta(\mathbf{f}_{\mathrm{PF}}(\mathbf{w}))}_{\text{PF preference}} \underbrace{\sqrt{\det\left(D\mathbf{f}_{\mathrm{PF}}(\mathbf{w})^{\top}D\mathbf{f}_{\mathrm{PF}}(\mathbf{w})\right)}}_{\text{generalized PF traversal speed} \propto J(\mathbf{w})}. \tag*{(3)} target weight density ρ ϑ ( w ) ∝ PF preference ϑ ( f PF ( w )) generalized PF traversal speed ∝ J ( w ) det ( D f PF ( w ) ⊤ D f PF ( w ) ) . (3)
Here D f P F ( w ) D\mathbf{f}_{\mathrm{PF}}(\mathbf{w}) D f PF ( w ) denotes the Jacobian of the weight-to-PF map (2). The square-root determinant generalizes the PF traversal speed in SURF [34 ] . § 2 provides the formal change-of-variables derivation and exact definitions of J ( w ) J(\mathbf{w}) J ( w ) and the normalized ρ ϑ ( w ) \rho_{\vartheta}(\mathbf{w}) ρ ϑ ( w ) . Realizing this distribution with finitely many scalarization solves motivates our second question:
(Q2) How can we use finitely many scalarization weights to approximate the desired PF distribution under a limited computational budget?
We answer this question with SURFACE (Scalarization Updates for Redistributing Finite Approximations with Chart Estimation ), a geometry-aware framework for matching finite Pareto representations to a desired preference distribution. As illustrated in Figure 2 , SURFACE estimates the weight-to-PF geometry from a finite grid of scalarization weights and adaptively redistributes them toward the target weight density ρ ϑ \rho_{\vartheta} ρ ϑ in (3).
Figure 2. An overview of SURFACE. Cooler regions indicate lower target density, while warmer regions indicate higher density and a denser allocation of Pareto solutions. SURFACE estimates the weight-to-PF geometry and updates the scalarization weights to match this target distribution.
Specifically, it estimates the PF distribution induced by the weights by measuring the area of the PF patch corresponding to each cell of the weight grid. It then updates the weights so that the resulting Pareto solutions move toward the desired preference distribution.
In summary, our main contributions are:
C1) In § 2 , we show how a desired preference distribution over the PF maps to a distribution of scalarization weights via the weight-to-PF geometry, and give sufficient conditions for Tchebycheff scalarization to yield a smooth, nondegenerate PF parameterization.
C2) In § 3 , we introduce SURFACE, which adaptively updates scalarization weights to approximate a target preference distribution with a fixed number of Pareto solutions. It supports off-the-shelf optimizers, warm-started inexact solves, and parallel subproblem solves.
C3) In § 4 , we provide a rigorous convergence analysis, showing that the weight updates contract the preference mismatch linearly down to a finite-resolution floor of O ( N − 2 / ( M − 1 ) ) \mathcal{O}(N^{-2/(M-1)}) O ( N − 2/ ( M − 1 ) ) .
C4) In Section 5, we empirically corroborate the effectiveness of SURFACE and verify our theoretical claims: across 9 baselines and benchmarks including ZDT/DTLZ and MO-Gymnasium, SURFACE consistently achieves strong, steady performance.
Related work. Existing approaches to finite PF representation mainly target well-spread solutions through different design criteria. Adaptive scalarization adjusts parameters toward more even objective-space spacing [26 , 71 , 52 ] , but may require local sensitivity information [26 ] or sequential parameter updates [71 , 52 ] . Geometric methods construct additional objective-space directions or constraints [18 , 42 , 27 ] , while continuation methods trace the PF sequentially using local derivative or sensitivity information [48 , 8 ] (Hillermeier 2001). Evolutionary methods adapt weights or reference points according to sparsity and diversity [69 , 49 , 19 , 16 ] , and finite-design methods use covering, packing, subset-selection, or repulsion objectives [6 , 72 , 55 ] (Borghi 2023). Preference-conditioned models instead learn mappings from preferences to Pareto solutions [44 , 37 , 65 ] . SURF [34 ] achieves uniform spacing on bi-objective PFs by inverting a cumulative distribution function (CDF) that measures the fraction of PF arc length reached as the weight increases, with density proportional to PF traversal speed. SURFACE extends this idea to higher-dimensional PFs and user-specified preferences by estimating PF geometry from parallel scalarized solves and adjusting weights accordingly. Appendix § 10 .§ 1 provides detailed comparisons with existing methods.
Notation. Let Δ M : = { w ∈ R M : w m ≥ 0 , ∑ m = 1 M w m = 1 } \Delta_M := \{ \mathbf{w} \in\mathbb{R}^{M} : w_m \ge0, \sum_{m=1}^{M} w_m = 1 \} Δ M := { w ∈ R M : w m ≥ 0 , ∑ m = 1 M w m = 1 } denote the weight simplex. We write D D D for the Jacobian with respect to the displayed parameter coordinates, ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ for the Euclidean norm, and ∥ ⋅ ∥ ∞ \lVert\cdot\rVert_{\infty} ∥ ⋅ ∥ ∞ for the uniform norm. For k ≥ 0 k \ge0 k ≥ 0 , C k , 1 C^{k,1} C k , 1 denotes functions with k k k continuous derivatives and Lipschitz k k k th derivative, with ∥ ⋅ ∥ C k \lVert\cdot\rVert_{C^k} ∥ ⋅ ∥ C k the supremum norm through order k k k . We use Vol M − 1 \operatorname{Vol}_{M-1} Vol M − 1 for intrinsic weight-space volume. Recurring symbols are collected in Appendix § 10 .§ 2 .
Pareto-Front Geometry from Scalarization
Under suitable regularity, the weight-to-PF map (2) parameterizes the corresponding PF region [43 , 24 ] (Hillermeier 2001). Sufficient conditions are established for TS in § 2.1 and weighted-sum in Appendix § 11 .§ 4 . This allows us to answer (Q1) by finding a distribution of scalarization weights whose induced Pareto outcomes f P F ( w ) f_{\mathrm{PF}}(\mathbf{w}) f PF ( w ) follow the target PF preference ϑ \vartheta ϑ . The key is to characterize how variations in w \mathbf{w} w translate into changes on the PF.
To characterize how changes in w \mathbf{w} w affect the PF, we use the surface-area change-of-variables formula. Following SURF [34 Appendix C.3] , we define the PF-area factor that measures this local geometric scaling:
J ( w ) : = 1 M ⏟ PF-area det ( D P F ( w ) T D P F ( w ) ) ⏟ generalized PF traversal speed . (4) J(\mathbf{w}) := \underbrace{\frac{1}{\sqrt{M}}}_{\text{PF-area}} \underbrace{\sqrt{\det\left(D_{\mathrm{PF}}(\mathbf{w})^{\mathsf{T}}D_{\mathrm{PF}}(\mathbf{w})\right)}}_{\text{generalized PF traversal speed}} . \tag*{(4)} J ( w ) := PF-area M 1 generalized PF traversal speed det ( D PF ( w ) T D PF ( w ) ) . (4)
Here D P F D_{\mathrm{PF}} D PF is the Jacobian in M − 1 M-1 M − 1 independent simplex coordinates, det \det det denotes intrinsic ( M − 1 ) (M-1) ( M − 1 ) -dimensional simplex volume, and 1 / M 1/\sqrt{M} 1/ M accounts for the corresponding volume conversion. A weight-space volume element d w \mathrm{d}\mathbf{w} d w thus corresponds to PF surface area J ( w ) d w J(\mathbf{w})\,\mathrm{d}\mathbf{w} J ( w ) d w , so a simplex cell τ ⊆ Δ M \tau\subseteq\Delta_M τ ⊆ Δ M represents area ∫ τ J ( w ) d w \int_{\tau} J(\mathbf{w})\,\mathrm{d}\mathbf{w} ∫ τ J ( w ) d w , as illustrated in Figure 3 . For M = 2 M=2 M = 2 , this recovers the PF traversal-speed measure used in SURF. To realize the target preference ϑ \vartheta ϑ , the probability assigned to each weight-space region τ \tau τ must be proportional to the preference-weighted PF area ∫ τ ϑ ( f P F ( w ) ) J ( w ) d w \int_{\tau}\vartheta(f_{\mathrm{PF}}(\mathbf{w}))J(\mathbf{w})\,\mathrm{d}\mathbf{w} ∫ τ ϑ ( f PF ( w )) J ( w ) d w . Normalization yields the target weight density
Figure 3. Weight-to-PF geometry. A simplex cell τ \tau τ maps to a PF region f P F ( τ ) f_{\mathrm{PF}}(\tau) f PF ( τ ) . The factor J ( w ) J(\mathbf{w}) J ( w ) generalizes PF traversal speed to local surface-area scaling, with ∫ τ J ( w ) d w \int_{\tau} J(\mathbf{w})\,\mathrm{d}\mathbf{w} ∫ τ J ( w ) d w giving the area of the corresponding PF region.
ρ ϑ ( w ) : = ϑ ( f P F ( w ) ) J ( w ) ∫ Δ M ϑ ( f P F ( v ) ) J ( v ) d v . (5) \rho_{\vartheta}(\mathbf{w}) := \frac{\vartheta(f_{\mathrm{PF}}(\mathbf{w}))J(\mathbf{w})}{\int_{\Delta_M}\vartheta(f_{\mathrm{PF}}(\mathbf{v}))J(\mathbf{v})\,\mathrm{d}\mathbf{v}} . \tag*{(5)} ρ ϑ ( w ) := ∫ Δ M ϑ ( f PF ( v )) J ( v ) d v ϑ ( f PF ( w )) J ( w ) . (5)
Thus, sampling weights from ρ ϑ \rho_{\vartheta} ρ ϑ induces the prescribed PF distribution. In particular, ϑ ≡ 1 \vartheta\equiv1 ϑ ≡ 1 yields ρ 1 ∝ J \rho_1 \propto J ρ 1 ∝ J , recovering uniform PF surface-area coverage. To prepare for (Q2), since evaluating J J J may require costly sensitivity information, we use finitely many sampled weight–PF pairs { ( w n , f P F ( w n ) ) } n = 1 N \{(\mathbf{w}_n,f_{\mathrm{PF}}(\mathbf{w}_n))\}_{n=1}^{N} {( w n , f PF ( w n )) } n = 1 N to estimate the represented PF areas. The following lemma characterizes preference matching across their associated weight-space cells.
Lemma 1 (Preference Matching). Suppose f P F f_{\mathrm{PF}} f PF is injective and has full tangent rank. Let C ( W ) \mathcal{C}(W) C ( W ) be a finite measurable partition of Δ M \Delta_M Δ M associated with the weights W = { w n } n = 1 N ⊆ Δ M W=\{\mathbf{w}_n\}_{n=1}^{N}\subseteq\Delta_M W = { w n } n = 1 N ⊆ Δ M , with cells of positive volume. For each τ ∈ C ( W ) \tau\in\mathcal{C}(W) τ ∈ C ( W ) , let a τ : = f P F ( τ ) a_\tau:=f_{\mathrm{PF}}(\tau) a τ := f PF ( τ ) denote the corresponding PF patch, and define R ^ ϑ ( W ) : = max τ ∈ C ( W ) ∣ ∣ C ( W ) ∣ ∫ ρ ϑ ( w ) d w − 1 ) \widehat{R}_{\vartheta}(W):=\max_{\tau\in\mathcal{C}(W)}\left|\lvert\mathcal{C}(W)\rvert\int_{\rho_\vartheta(w)}\mathrm{d}w-1\right) R ϑ ( W ) := max τ ∈ C ( W ) ∣ C ( W )∣ ∫ ρ ϑ ( w ) d w − 1 ) . Then R ^ ϑ ( W ) = 0 \widehat{R}_{\vartheta}(W)=0 R ϑ ( W ) = 0 if and only if all PF patches { a τ } τ ∈ C ( W ) \{a_\tau\}_{\tau\in\mathcal{C}(W)} { a τ } τ ∈ C ( W ) carry equal preference-weighted area.
Appendix B.1 provides the proof of Lemma 1. The residual measures preference-mass imbalance across C ( W ) \mathcal{C}(W) C ( W ) . The separate weight mesh used to reconstruct the PF is introduced in Section 3. For ϑ ≡ 1 \vartheta\equiv1 ϑ ≡ 1 , this residual measures PF surface-area imbalance.
Regular PF Charts from TS
In this section, we specialize the weight-to-PF map to TS and establish its PF coverage and regular chart properties. Appendix B.4 provides an alternative analysis for weighted-sum scalarization.
TS is especially useful for PF construction because it can recover Pareto solutions on nonconvex fronts that some other scalarizations may miss [24 , 38 ] . The conventional weighted TS takes the form min x ∈ X max m λ m ( f m ( x ) − z m ) \min_{\mathbf{x}\in\mathcal{X}}\max_{m}\lambda_m(f_m(\mathbf{x})-z_m) min x ∈ X max m λ m ( f m ( x ) − z m ) , where λ ∈ relint ( Δ M ) \boldsymbol{\lambda}\in\operatorname{relint}(\Delta_M) λ ∈ relint ( Δ M ) and z m z_m z m is a reference point chosen strictly below the minimum value of each objective. Equivalently, under the reciprocal reparameterization λ m = w m − 1 ∑ j = 1 M w j − 1 \lambda_m=\frac{w_m^{-1}}{\sum_{j=1}^{M}w_j^{-1}} λ m = ∑ j = 1 M w j − 1 w m − 1 [37 ] , TS can be written as
x T S ⋆ ( w ) ∈ arg min x ∈ X max m = 1 , … , M f m ( x ) − z m w m , z m < min x ∈ X f m ( x ) , w ∈ relint ( Δ M ) . (6) \mathbf{x}_{\mathrm{TS}}^\star(\mathbf{w})\in\underset{\mathbf{x}\in\mathcal{X}}{\arg\min}\ \underset{m=1,\ldots,M}{\max}\ \frac{f_m(\mathbf{x})-z_m}{w_m},\qquad z_m<\min_{\mathbf{x}\in\mathcal{X}}f_m(\mathbf{x}),\quad\mathbf{w}\in\operatorname{relint}(\Delta_M). \tag*{(6)} x TS ⋆ ( w ) ∈ x ∈ X arg min m = 1 , … , M max w m f m ( x ) − z m , z m < x ∈ X min f m ( x ) , w ∈ relint ( Δ M ) . (6)
We adopt this formulation because w \mathbf{w} w directly parameterizes reference directions in objective space, facilitating the geometric analysis of the weight-to-PF map. For w ∈ relint ( Δ M ) \mathbf{w}\in\operatorname{relint}(\Delta_M) w ∈ relint ( Δ M ) , TS in (6) admits the equivalent epigraph formulation (7), which lets us state the conditions for a smooth solution path.
Assumption 1 (Regular full-ray TS regime). Fix any interior weight margin 0 < δ < 1 / M 0<\delta<1/M 0 < δ < 1/ M and define Δ M δ : = { w ∈ Δ M : w m ≥ δ , m = 1 , … , M } \Delta_M^\delta:=\{\mathbf{w}\in\Delta_M:w_m\ge\delta,\ m=1,\ldots,M\} Δ M δ := { w ∈ Δ M : w m ≥ δ , m = 1 , … , M } . Suppose X \mathcal{X} X is compact and z \mathbf{z} z is utopian, i.e., z m < min x ∈ X f m ( x ) z_m<\min_{\mathbf{x}\in\mathcal{X}}f_m(\mathbf{x}) z m < min x ∈ X f m ( x ) for every m m m . For every w ∈ Δ M δ \mathbf{w}\in\Delta_M^\delta w ∈ Δ M δ , the problem
min x ∈ X , s ∈ R s s.t. f m ( x ) − z m ≤ s w m , m = 1 , … , M , (7) \underset{\mathbf{x}\in\mathcal{X},\,s\in\mathbb{R}}{\min}\quad s\qquad\text{s.t.}\quad f_m(\mathbf{x})-z_m\le sw_m,\quad m=1,\ldots,M, \tag*{(7)} x ∈ X , s ∈ R min s s.t. f m ( x ) − z m ≤ s w m , m = 1 , … , M , (7) has a unique solution ( x T S ⋆ ( w ) , s ⋆ ( w ) ) (\mathbf{x}_{\mathrm{TS}}^\star(\mathbf{w}),s^\star(\mathbf{w})) ( x TS ⋆ ( w ) , s ⋆ ( w )) . At this solution, all M M M ray inequalities are active, the linear independence constraint qualification (LICQ) holds, every active inequality has a positive multiplier, and the second-order sufficient condition (SOSC) holds on the critical cone.
Compactness and a utopian z \mathbf{z} z are standard in TS [24 ] . Full activity, LICQ, positive multipliers, and SOSC are checkable from the ray residuals, active-constraint Jacobian, multiplier signs, and reduced Hessian [30 , 9 ] . Appendix B.3 gives concrete sufficient regimes for uniqueness and these regularity conditions. When the standard Tchebycheff formulation is nonsmooth, smooth Tchebycheff scalarizations provide a related alternative [38 ] . These conditions ensure a smooth, nonfolding TS parameterization over Δ M δ \Delta_M^\delta Δ M δ .
Proposition 1 (PF coverage and injectivity of TS). Under Assumption 1, TS maps Δ M δ \Delta_M^\delta Δ M δ injectively onto the corresponding PF patch f P F ( Δ M δ ) f_{\mathrm{PF}}(\Delta_M^\delta) f PF ( Δ M δ ) . Moreover, every Pareto point whose normalized positive-gap ray lies in Δ M δ \Delta_M^\delta Δ M δ is represented.
Injectivity follows from full ray activity in Assumption 1, which gives f P F ( w ) = z + s ⋆ ( w ) w f_{\mathrm{PF}}(\mathbf{w})=\mathbf{z}+s^\star(\mathbf{w})\mathbf{w} f PF ( w ) = z + s ⋆ ( w ) w with s ⋆ ( w ) > 0 s^\star(\mathbf{w})>0 s ⋆ ( w ) > 0 , so each represented PF point uniquely determines its weight. Coverage follows from classical TS completeness [43 , 24 ] , which applies to the represented positive-gap rays without requiring PF convexity. The following standard condition [30 , 9 ] further ensures the smoothness and regularity of this parameterization.
Assumption 2 (Feasibility and Smoothness). The feasible set X = { x : c 1 ( x ) ≤ 0 , c 2 ( x ) = 0 } \mathcal{X}=\{\mathbf{x}:c_1(\mathbf{x})\le0,\ c_2(\mathbf{x})=0\} X = { x : c 1 ( x ) ≤ 0 , c 2 ( x ) = 0 } is nonempty and closed. Every f m f_m f m and every component of c 1 c_1 c 1 is C 3 , 1 C^{3,1} C 3 , 1 on a common open convex neighborhood of X \mathcal{X} X , each component of c 1 c_1 c 1 is convex there, and c 2 c_2 c 2 is affine.
Together, these assumptions yield the following regularity properties of the TS-induced PF chart.
Algorithm 1 SURFACE
Require: Preference ϑ \vartheta ϑ , number of adaptive weights N N N , chosen weight domain (e.g. Δ M δ \Delta^\delta_M Δ M δ ) and its M M M (fixed) corner samples { ( w m δ , f ~ m ) } m = 1 M \{(\mathbf{w}^{\delta}_m,\tilde{f}_m)\}_{m=1}^{M} {( w m δ , f ~ m ) } m = 1 M , initial solver states { x ~ n ( − 1 ) } n = 1 N \{\tilde{x}^{(-1)}_n\}_{n=1}^{N} { x ~ n ( − 1 ) } n = 1 N , inner-step budget K K K , damping α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] , and outer rounds T T T
for t = 0 , … , T − 1 t = 0,\ldots,T-1 t = 0 , … , T − 1 do
{ w n ( t ) } n = 1 N ← MEQ N ( ρ t ) \{\mathbf{w}^{(t)}_n\}_{n=1}^{N} \leftarrow\operatorname{MEQ}_N(\rho_t) { w n ( t ) } n = 1 N ← MEQ N ( ρ t ) via Appendix C.2 ▹ \triangleright ▹ Initialize ρ 0 \rho_0 ρ 0 uniformly on Δ M δ \Delta^\delta_M Δ M δ
x ~ n ( t ) ← InnerSolver K ( w n ( t ) , x i n i t = x ~ n ( t − 1 ) ) \tilde{x}^{(t)}_n \leftarrow\operatorname{InnerSolver}_K\left(\mathbf{w}^{(t)}_n, x_{\mathrm{init}}=\tilde{x}^{(t-1)}_n\right) x ~ n ( t ) ← InnerSolver K ( w n ( t ) , x init = x ~ n ( t − 1 ) ) in parallel for n ∈ [ N ] n \in[N] n ∈ [ N ]
Optional: refine f ~ m \tilde{f}_m f ~ m towards f ( x ⋆ T S ( w m δ ) ) f\left(x^{\mathrm{TS}}_{\star}(\mathbf{w}^{\delta}_m)\right) f ( x ⋆ TS ( w m δ ) ) in parallel for m ∈ [ M ] m \in[M] m ∈ [ M ]
Interpolate P t P_t P t from { ( w n ( t ) , f ( x ~ n ( t ) ) ) } n = 1 N ∪ { ( w m δ , f ~ m ) } m = 1 M \{(\mathbf{w}^{(t)}_n,f(\tilde{x}^{(t)}_n))\}_{n=1}^{N} \cup\{(\mathbf{w}^{\delta}_m,\tilde{f}_m)\}_{m=1}^{M} {( w n ( t ) , f ( x ~ n ( t ) )) } n = 1 N ∪ {( w m δ , f ~ m ) } m = 1 M via Appendix C.1
Update ρ t + 1 \rho_{t+1} ρ t + 1 by (10)
end for
Ensure: { ( w n ( T − 1 ) , f ( x ~ n ( T − 1 ) ) ) } n = 1 N \{(\mathbf{w}^{(T-1)}_n,f(\tilde{x}^{(T-1)}_n))\}_{n=1}^{N} {( w n ( T − 1 ) , f ( x ~ n ( T − 1 ) )) } n = 1 N and corner samples { ( w m δ , f ~ m ) } m = 1 M \{(\mathbf{w}^{\delta}_m,\tilde{f}_m)\}_{m=1}^{M} {( w m δ , f ~ m ) } m = 1 M
Proposition 2 (Regular PF chart from TS). Suppose Assumptions 1 and 2 hold. Then the TS-induced PF chart has the following properties. (i) Smoothness. x ⋆ T S x^{\mathrm{TS}}_{\star} x ⋆ TS is uniformly Lipschitz and face-wise C 2 , 1 C^{2,1} C 2 , 1 on Δ M δ \Delta^\delta_M Δ M δ , with compatible one-sided extensions, and f P F = f ∘ x ⋆ T S f_{\mathrm{PF}}=f\circ x^{\mathrm{TS}}_{\star} f PF = f ∘ x ⋆ TS is face-wise C 2 , 1 C^{2,1} C 2 , 1 . (ii) Nonfolding. f P F f_{\mathrm{PF}} f PF is injective, has full tangent rank, and there exist 0 < c P ≤ C P < ∞ 0<c_P\le C_P<\infty 0 < c P ≤ C P < ∞ such that
c P ∥ w − v ∥ ≤ ∥ f P F ( w ) − f P F ( v ) ∥ ≤ C P ∥ w − v ∥ , w , v ∈ Δ M δ . (8) c_P\lVert\mathbf{w}-\mathbf{v}\rVert\le\lVert f_{\mathrm{PF}}(\mathbf{w})-f_{\mathrm{PF}}(\mathbf{v})\rVert\le C_P\lVert\mathbf{w}-\mathbf{v}\rVert,\qquad\mathbf{w},\mathbf{v}\in\Delta^\delta_M. \tag*{(8)} c P ∥ w − v ∥ ≤ ∥ f PF ( w ) − f PF ( v )∥ ≤ C P ∥ w − v ∥ , w , v ∈ Δ M δ . (8) (iii) Nondegenerate area. J J J is face-wise C 1 , 1 C^{1,1} C 1 , 1 with compatible one-sided traces and satisfies J ‾ ≤ J ( w ) ≤ J ‾ \underline{J}\le J(\mathbf{w})\le\overline{J} J ≤ J ( w ) ≤ J for some 0 < J ‾ ≤ J ‾ < ∞ 0<\underline{J}\le\overline{J}<\infty 0 < J ≤ J < ∞ and all w ∈ Δ M δ \mathbf{w}\in\Delta^\delta_M w ∈ Δ M δ .
The proof of Proposition 2 is given in Appendix B.2. Thus TS induces a smooth, nonfolding PF chart with uniformly nondegenerate area distortion on each Δ M δ \Delta^\delta_M Δ M δ . These properties extend to relint ( Δ M ) \operatorname{relint}(\Delta_M) relint ( Δ M ) when the full-ray regularity conditions hold throughout the interior, allowing an ideal reference point. For example, DTLZ2 [21 ] with z = 0 \mathbf{z}=0 z = 0 admits f P F ( w ) = w / ∥ w ∥ 2 f_{\mathrm{PF}}(\mathbf{w})=\mathbf{w}/\lVert\mathbf{w}\rVert_2 f PF ( w ) = w / ∥ w ∥ 2 , whose geometric regularity bounds remain uniform as δ ↓ 0 \delta\downarrow0 δ ↓ 0 . Combined with Lemma 1, these properties yield ρ ϑ ( w ) ∝ ϑ ( f P F ( w ) ) J ( w ) \rho_{\vartheta}(\mathbf{w})\propto\vartheta(f_{\mathrm{PF}}(\mathbf{w}))J(\mathbf{w}) ρ ϑ ( w ) ∝ ϑ ( f PF ( w )) J ( w ) , with ρ 1 ( w ) ∝ J ( w ) \rho_1(\mathbf{w})\propto J(\mathbf{w}) ρ 1 ( w ) ∝ J ( w ) recovering uniform PF surface-area coverage.
The SURFACE Algorithm
Building on the target weight density ρ ϑ ∝ ( ϑ ∘ f P F ) J \rho_{\vartheta}\propto(\vartheta\circ f_{\mathrm{PF}})J ρ ϑ ∝ ( ϑ ∘ f PF ) J from Section 2, we propose SURFACE, a general framework for adaptive weight selection under different scalarizations. SURFACE combines parallel scalarized solves, PF reconstruction, and mass equidistribution (MEQ) to match the prescribed preference. In this section, we use TS on Δ M δ \Delta^\delta_M Δ M δ as the running specialization, with fixed corners w m δ : = δ 1 + ( 1 − M δ ) e m \mathbf{w}^{\delta}_m:=\delta\mathbf{1}+(1-M\delta)\mathbf{e}_m w m δ := δ 1 + ( 1 − M δ ) e m . When the PF chart extends to the full simplex Δ M \Delta_M Δ M , the fixed corners become the vertices { e m } m = 1 M \{\mathbf{e}_m\}_{m=1}^{M} { e m } m = 1 M , as illustrated by DTLZ2 [21 ] with an ideal reference point (cf. Appendix B.3). Appendix B.4 gives the weighted-sum specialization on Δ M \Delta_M Δ M .
SURFACE retains M M M fixed TS chart-corner samples f ~ m ≈ f P F ( w m δ ) \tilde{f}_m\approx f_{\mathrm{PF}}(\mathbf{w}^{\delta}_m) f ~ m ≈ f PF ( w m δ ) alongside the N N N adaptive samples { w n ( t ) } n = 1 N \{\mathbf{w}^{(t)}_n\}_{n=1}^{N} { w n ( t ) } n = 1 N . When f P F f_{\mathrm{PF}} f PF extends continuously to Δ M \Delta_M Δ M , the chart corners approach f P F ( e m ) f_{\mathrm{PF}}(\mathbf{e}_m) f PF ( e m ) as δ ↓ 0 \delta\downarrow0 δ ↓ 0 . At outer round t t t , SURFACE applies finite K K K -step InnerSolver in parallel on the scalarized objectives to obtain
x ~ n ( t ) = InnerSolver K ( w n ( t ) , x i n i t = x ~ n ( t − 1 ) ) ≈ x ⋆ T S ( w n ( t ) ) , n = 1 , … , N . (9) \tilde{x}^{(t)}_n=\operatorname{InnerSolver}_K\left(\mathbf{w}^{(t)}_n,x_{\mathrm{init}}=\tilde{x}^{(t-1)}_n\right)\approx x^{\mathrm{TS}}_{\star}\left(\mathbf{w}^{(t)}_n\right),\qquad n=1,\ldots,N. \tag*{(9)} x ~ n ( t ) = InnerSolver K ( w n ( t ) , x init = x ~ n ( t − 1 ) ) ≈ x ⋆ TS ( w n ( t ) ) , n = 1 , … , N . (9)
For differentiable objectives, scalarization can be applied to the losses, and InnerSolver may use Adam [35 ] . For reinforcement learning, scalarization is applied to the rewards, and InnerSolver may use Proximal Policy Optimization (PPO) [53 ] or Group Relative Policy Optimization (GRPO) [56 ] . Warm-starting from the preceding round with x i n i t = x ~ n ( t − 1 ) x_{\mathrm{init}}=\tilde{x}^{(t-1)}_n x init = x ~ n ( t − 1 ) helps InnerSolver track the updated scalarized solutions with inexact solves, as detailed in the next section. The corner references { f ~ m } m = 1 M \{\tilde{f}_m\}_{m=1}^{M} { f ~ m } m = 1 M may be held fixed when accurate estimates are available or refined similarly in parallel.
Using the N N N weight-objective pairs { ( w n ( t ) , f ( x ~ n ( t ) ) ) } n = 1 N \{(\mathbf{w}_n^{(t)}, f(\tilde{\mathbf{x}}_n^{(t)}))\}_{n=1}^{N} {( w n ( t ) , f ( x ~ n ( t ) )) } n = 1 N and the M M M corner pairs { ( w m δ , f ~ m ) } m = 1 M \{(\mathbf{w}_m^\delta,\tilde{\mathbf{f}}_m)\}_{m=1}^{M} {( w m δ , f ~ m ) } m = 1 M , SURFACE constructs a smooth PF approximation P t ≈ f P F P_t \approx\mathbf{f}_{\mathrm{PF}} P t ≈ f PF through interpolation. One practical choice fits local radial basis function (RBF) models with quadratic terms and blends them smoothly Wendland, [63 ] . Appendix § 12 .§ 1 gives the interpolation details. For problems such as DTLZ2 Deb et al., [21 ] with z = 0 \mathbf{z} = \mathbf{0} z = 0 , this reconstruction also extends to Δ M \Delta_M Δ M as δ ↓ 0 \delta\downarrow0 δ ↓ 0 , with the simplex vertices as fixed corners. Replacing f P F \mathbf{f}_{\mathrm{PF}} f PF by P t P_t P t in (4) gives the estimated area factor J P t ( w ) : = 1 M det ( D P t ( w ) ⊤ D P t ( w ) ) J_{P_t}(\mathbf{w}) := \frac{1}{\sqrt{M}}\sqrt{\det(DP_t(\mathbf{w})^\top DP_t(\mathbf{w}))} J P t ( w ) := M 1 det ( D P t ( w ) ⊤ D P t ( w )) . SURFACE updates the weight density using this geometry and the prescribed PF preference, with damping factor α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] :
ρ t + 1 ( w ) : = ( 1 − α ) ρ t ( w ) + α ϑ ( P t ( w ) ) J P t ( w ) ∫ Δ M δ ϑ ( P t ( v ) ) J P t ( v ) d v , w ∈ Δ M δ . (10) \rho_{t+1}(\mathbf{w}) := (1-\alpha)\rho_t(\mathbf{w})+\alpha\frac{\vartheta(P_t(\mathbf{w}))J_{P_t}(\mathbf{w})}{\int_{\Delta_M^\delta}\vartheta(P_t(\mathbf{v}))J_{P_t}(\mathbf{v})\,\mathrm{d}\mathbf{v}}, \qquad\mathbf{w}\in\Delta_M^\delta. \tag*{(10)} ρ t + 1 ( w ) := ( 1 − α ) ρ t ( w ) + α ∫ Δ M δ ϑ ( P t ( v )) J P t ( v ) d v ϑ ( P t ( w )) J P t ( w ) , w ∈ Δ M δ . (10)
For ϑ = 1 \vartheta=1 ϑ = 1 , it targets uniform surface-area coverage of the corresponding PF patch.
Finally, SURFACE converts ρ t + 1 \rho_{t+1} ρ t + 1 into N N N adaptive weights for the next round through MEQ Budd & Williams, [13 ] . By Lemma 1, MEQ seeks weights whose associated cells carry equal ρ t + 1 \rho_{t+1} ρ t + 1 -mass. Let W = { w n } n = 1 N ∪ { w m δ } m = 1 M W=\{\mathbf{w}_n\}_{n=1}^{N}\cup\{\mathbf{w}_m^\delta\}_{m=1}^{M} W = { w n } n = 1 N ∪ { w m δ } m = 1 M include the adaptive weights and fixed corners, and let C ( W ) \mathcal{C}(W) C ( W ) be an associated cell partition of Δ M δ \Delta_M^\delta Δ M δ . MEQ redistributes the weights as follows:
{ w n ( t + 1 ) } n = 1 N = MEQ N ( ρ t + 1 ) ≈ arg min { w n } n = 1 N max τ ∈ C ( W ) ∣ ∣ C ( W ) ∣ ∫ τ ρ t + 1 ( w ) d w − 1 ∣ . (11) \{\mathbf{w}_n^{(t+1)}\}_{n=1}^{N}=\operatorname{MEQ}_N(\rho_{t+1})\approx\underset{\{\mathbf{w}_n\}_{n=1}^{N}}{\arg\min}\ \max_{\tau\in\mathcal{C}(W)}\left|\frac{|\mathcal{C}(W)|}{\int_{\tau}\rho_{t+1}(\mathbf{w})\,\mathrm{d}\mathbf{w}}-1\right|. \tag*{(11)} { w n ( t + 1 ) } n = 1 N = MEQ N ( ρ t + 1 ) ≈ { w n } n = 1 N arg min τ ∈ C ( W ) max ∫ τ ρ t + 1 ( w ) d w ∣ C ( W ) ∣ − 1 . (11)
SURFACE realizes this objective by transporting an initially equal-volume tessellation, producing smaller cells in regions of higher density. For M = 2 M=2 M = 2 , MEQ can be implemented by inverse cumulative-distribution transport Jiang et al., [34 ] . For M ≥ 3 M\geq3 M ≥ 3 , Appendix § 12 .§ 2 establishes two realizations: Moser transport Bruveris et al., [12 ] and equal-capacity minimization, where equal capacity means equal probability mass per cell.
Algorithm 1 summarizes the iteration, which requires O ( T N ) O(TN) O ( T N ) scalarized solves. The dominant cost is typically InnerSolver, since reconstruction and MEQ operate only in the ( M − 1 ) (M-1) ( M − 1 ) -dimensional weight space and require no additional scalarized solves.
Convergence Analysis
This section establishes the convergence of SURFACE by tracking the three approximations in Section 3: finite PF reconstruction via interpolation, numerical MEQ, and inexact inner scalarized solves. We use TS on a fixed Δ M δ \Delta_M^\delta Δ M δ from Proposition 2 and normalize (5) over this domain, targeting the represented PF patch f P F ( Δ M δ ) \mathbf{f}_{\mathrm{PF}}(\Delta_M^\delta) f PF ( Δ M δ ) . We impose the following condition on the preference density.
Assumption 3 (Regular preference). The preference density ϑ : F P F → R + \vartheta:\mathcal{F}_{\mathrm{PF}}\to\mathbb{R}_+ ϑ : F PF → R + extends to a C 2 , 1 C^{2,1} C 2 , 1 function on an open neighborhood containing f P F \mathbf{f}_{\mathrm{PF}} f PF and P t ( Δ M δ ) P_t(\Delta_M^\delta) P t ( Δ M δ ) for all t t t , with 0 ≤ ϑ ‾ ≤ ϑ ( y ) ≤ ϑ ‾ < ∞ 0\leq\underline{\vartheta}\leq\vartheta(\mathbf{y})\leq\overline{\vartheta}<\infty 0 ≤ ϑ ≤ ϑ ( y ) ≤ ϑ < ∞ and ∥ ϑ ∥ C 2 , 1 ≤ B ϑ \|\vartheta\|_{C^{2,1}}\leq B_\vartheta ∥ ϑ ∥ C 2 , 1 ≤ B ϑ for some constants ϑ ‾ , ϑ ‾ , B ϑ \underline{\vartheta},\overline{\vartheta},B_\vartheta ϑ , ϑ , B ϑ .
To characterize the target distortion, define the preference-weighted condition number κ ϑ : = ϑ ‾ J ϑ ‾ ( J ‾ / J ) \kappa_\vartheta:=\frac{\overline{\vartheta}J}{\underline{\vartheta}(\underline{J}/J)} κ ϑ := ϑ ( J / J ) ϑ J . For finite PF reconstruction, RBF interpolation Wendland, [63 ] gives second-order C 1 C^1 C 1 accuracy, while inexact scalarized solves introduce an additional reconstruction-error term.
Lemma 2 (Reconstruction and density accuracy). Suppose Assumptions 1–3 hold. Then there exists an augmented RBF interpolation P t P_t P t (cf. Appendix § 12 .§ 1 ) such that
∥ ϑ ( P t ) J P t ∫ ϑ ( P t ) J P t − ρ ϑ ∥ ∞ ≤ C C t N − 2 M − 1 + C N 1 M − 1 max n ∈ [ N ] ∥ x ~ n ( t ) − x ⋆ T ( w n ( t ) ) ∥ , (12) \left\|\frac{\vartheta(P_t)J_{P_t}}{\int\vartheta(P_t)J_{P_t}}-\rho_\vartheta\right\|_\infty\leq CC_tN^{-\frac{2}{M-1}}+CN^{\frac{1}{M-1}}\max_{n\in[N]}\|\tilde{\mathbf{x}}_n^{(t)}-\mathbf{x}_\star^{\mathrm{T}}(\mathbf{w}_n^{(t)})\|, \tag*{(12)} ∫ ϑ ( P t ) J P t ϑ ( P t ) J P t − ρ ϑ ∞ ≤ C C t N − M − 1 2 + C N M − 1 1 n ∈ [ N ] max ∥ x ~ n ( t ) − x ⋆ T ( w n ( t ) ) ∥ , (12) where C C C and the round-dependent coefficient C t C_t C t are bounded uniformly over the rounds.
The interpolation details and its proof are provided in Appendix § 12 .§ 1 . With exact scalarized solves, Lemma 2 gives a density error of order C C t N − 2 M − 1 CC_tN^{-\frac{2}{M-1}} C C t N − M − 1 2 , where C C C is independent of κ ϑ \kappa_\vartheta κ ϑ under uniform regularity conditions. The coefficient C t C_t C t captures the round-dependent reconstruction geometry and may be large when κ ϑ \kappa_\vartheta κ ϑ is large. As MEQ redistributes weights toward the target preference, it can improve the reconstruction geometry and reduce C t C_t C t . For inexact solves, the second term captures the amplification of inner optimization error by the inverse mesh scale. We next analyze numerical MEQ error, where both realizations balance the ρ t + 1 \rho_{t+1} ρ t + 1 -mass of their complete represented cells.
Proposition 3 (Finite MEQ stability). Suppose Assumptions 1–3 hold. Then there exist numerical MEQ realizations (cf. Appendix § 12 .§ 2 ) that achieve O ( N − 2 / ( M − 1 ) ) \mathcal{O}(N^{-2/(M-1)}) O ( N − 2/ ( M − 1 ) ) cell-mass error on complete represented cells while preserving mesh regularity for stable reconstruction in the next round.
Thus numerical MEQ has the same O ( N − 2 / ( M − 1 ) ) \mathcal{O}(N^{-2/(M-1)}) O ( N − 2/ ( M − 1 ) ) resolution as PF reconstruction while preserving the mesh regularity needed by Lemma 2. Appendix § 12 .§ 2 gives the construction and proof.
Finally, we quantify the effect of solving each scalarized problem for K K K inner steps. Following local convergence and sensitivity theory [9 ] and the finite-step analysis of SURF [34 ] , let η K \eta_K η K denote a K K K -step contraction factor such that ∥ x K − x T S ⋆ ( w ) ∥ ≤ η K ∥ x 0 − x T S ⋆ ( w ) ∥ \lVert x_K - x_{\mathrm{TS}}^{\star}(\mathbf{w})\rVert\le\eta_K\lVert x_0 - x_{\mathrm{TS}}^{\star}(\mathbf{w})\rVert ∥ x K − x TS ⋆ ( w )∥ ≤ η K ∥ x 0 − x TS ⋆ ( w )∥ . For linearly convergent methods, η K \eta_K η K decreases geometrically in K K K ; a sublinear rate η K = O ( K − p ) \eta_K = \mathcal{O}(K^{-p}) η K = O ( K − p ) applies when the solver satisfies the corresponding relative decision-error contraction. Since damping limits the motion of successive weights, α \alpha α trades outer progress against the required inner accuracy. We therefore define the coupled density-solver error
E t : = ∥ ρ t − ρ ϑ ∥ ∞ + C 0 ( 1 + α N 1 / ( M − 1 ) ) max n ∈ [ N ] ∥ x ~ n ( t ) − x T S ⋆ ( w n ( t ) ) ∥ . (13) \mathcal{E}_t := \lVert\rho_t - \rho_{\vartheta}\rVert_{\infty} + C_0\left(1+\alpha N^{1/(M-1)}\right)\max_{n\in[N]}\left\lVert\widetilde{x}_n^{(t)} - x_{\mathrm{TS}}^{\star}(\mathbf{w}_n^{(t)})\right\rVert. \tag*{(13)} E t := ∥ ρ t − ρ ϑ ∥ ∞ + C 0 ( 1 + α N 1/ ( M − 1 ) ) n ∈ [ N ] max x n ( t ) − x TS ⋆ ( w n ( t ) ) . (13)
The following theorem establishes SURFACE’s joint convergence and preference-mass guarantees.
Theorem 1 (SURFACE convergence). Suppose Assumptions 1–3 hold. Choose N = Ω ( κ ϑ 3 ( M − 1 ) / 2 ) N = \Omega(\kappa_{\vartheta}^{3(M-1)/2}) N = Ω ( κ ϑ 3 ( M − 1 ) /2 ) sufficiently large, 0 < α ≤ α ˉ < 1 0 < \alpha\le\bar{\alpha} < 1 0 < α ≤ α ˉ < 1 with α ˉ = Ω ( N − 3 / ( 2 ( M − 1 ) ) ) \bar{\alpha} = \Omega(N^{-3/(2(M-1))}) α ˉ = Ω ( N − 3/ ( 2 ( M − 1 )) ) , and K K K for the inner solver with η K \eta_K η K satisfying α ˉ 2 η K = O ( N − 3 / ( M − 1 ) ) \bar{\alpha}^{2}\eta_K = \mathcal{O}(N^{-3/(M-1)}) α ˉ 2 η K = O ( N − 3/ ( M − 1 ) ) . Initialize the inner solves to accuracy O ( N − 3 / ( M − 1 ) ) \mathcal{O}(N^{-3/(M-1)}) O ( N − 3/ ( M − 1 ) ) . Then there exist an interpolation (cf. Appendix § 12 .§ 1 ) and a moving-weight Moser MEQ realization (cf. Appendix § 12 .§ 2 ) of Algorithm 1 such that, for t = 0 , … , T − 1 t = 0,\ldots,T-1 t = 0 , … , T − 1 ,
E t ≤ ( 1 − α / 4 ) t E 0 + O ( N − 2 / ( M − 1 ) ) , R ^ ϑ ( W ( t ) ) ≤ C E t + O ( N − 2 / ( M − 1 ) ) . (14) \mathcal{E}_t \le(1-\alpha/4)^t\mathcal{E}_0 + \mathcal{O}\left(N^{-2/(M-1)}\right), \qquad\widehat{\mathcal{R}}_{\vartheta}(W^{(t)}) \le C\mathcal{E}_t + \mathcal{O}\left(N^{-2/(M-1)}\right). \tag*{(14)} E t ≤ ( 1 − α /4 ) t E 0 + O ( N − 2/ ( M − 1 ) ) , R ϑ ( W ( t ) ) ≤ C E t + O ( N − 2/ ( M − 1 ) ) . (14) Here, W ( t ) : = { w n ( t ) } n = 1 N ∪ { w m δ } m = 1 M W^{(t)} := \{\mathbf{w}_n^{(t)}\}_{n=1}^{N} \cup\{\mathbf{w}_m^{\delta}\}_{m=1}^{M} W ( t ) := { w n ( t ) } n = 1 N ∪ { w m δ } m = 1 M is the weight mesh at round t t t , and R ^ ϑ ( W ( t ) ) \widehat{\mathcal{R}}_{\vartheta}(W^{(t)}) R ϑ ( W ( t ) ) is the target-mass residual in Lemma 1 evaluated on complete represented cells of the selected MEQ realization.
The convergence proof is given in Appendix § 13 . With N = Ω ( κ ϑ 3 ( M − 1 ) / 2 ) N = \Omega(\kappa_{\vartheta}^{3(M-1)/2}) N = Ω ( κ ϑ 3 ( M − 1 ) /2 ) sufficiently large for the regularity thresholds, MEQ keeps C t = O ( 1 ) C_t = \mathcal{O}(1) C t = O ( 1 ) across rounds and yields an O ( N − 2 / ( M − 1 ) ) \mathcal{O}(N^{-2/(M-1)}) O ( N − 2/ ( M − 1 ) ) error floor for each fixed regular problem. Additionally, Table 1 summarizes the inner–outer trade-off: larger α ˉ \bar{\alpha} α ˉ requires more accurate inner solves but fewer outer rounds, whereas smaller α ˉ \bar{\alpha} α ˉ permits cheaper inner solves at the cost of more outer rounds. For sublinear inner convergence η K = O ( K − p ) \eta_K = \mathcal{O}(K^{-p}) η K = O ( K − p ) , the cases p > 2 p > 2 p > 2 , p = 2 p = 2 p = 2 , and p < 2 p < 2 p < 2 require inner cost K T = O ~ ( ϵ − 3 / ( 2 p ) ) KT = \widetilde{\mathcal{O}}(\epsilon^{-3/(2p)}) K T = O ( ϵ − 3/ ( 2 p ) ) , O ~ ( ϵ − 1 / 2 − 1 / ( 2 p ) ) \widetilde{\mathcal{O}}(\epsilon^{-1/2-1/(2p)}) O ( ϵ − 1/2 − 1/ ( 2 p ) ) , and O ~ ( ϵ − 3 / 4 ) \widetilde{\mathcal{O}}(\epsilon^{-3/4}) O ( ϵ − 3/4 ) , respectively. Thus, for repeated inner work, larger damping steps are preferable for p > 2 p > 2 p > 2 and smaller steps for p < 2 p < 2 p < 2 . The initial states { x ~ n ( − 1 ) } n = 1 N \{\widetilde{x}_n^{(-1)}\}_{n=1}^{N} { x n ( − 1 ) } n = 1 N can be obtained through a one-time I n n e r S o l v e r K 0 \mathrm{InnerSolverK}_0 InnerSolverK 0 warmup to meet the stated initialization accuracy.
Table 1. Outer–inner iteration trade-offs under α ˉ 2 η K = O ( N − 3 / ( M − 1 ) ) \bar{\alpha}^{2}\eta_K = \mathcal{O}(N^{-3/(M-1)}) α ˉ 2 η K = O ( N − 3/ ( M − 1 ) ) . The K K K and T T T columns assume linear inner convergence and α = Θ ( α ˉ ) \alpha= \Theta(\bar{\alpha}) α = Θ ( α ˉ ) , respectively. The “When to Use” column identifies preferred damping regimes for sublinear inner solvers with η K = O ( K − p ) \eta_K = \mathcal{O}(K^{-p}) η K = O ( K − p ) .
Experiments
We empirically evaluate SURFACE against fixed Uniform weighting and adaptive/stochastic baselines with matched returned-solution counts, comparing computational budgets through matched solver work or wall-clock evaluations. We adopt R ^ ϑ ( ↓ ) \widehat{\mathcal{R}}_{\vartheta}(\downarrow) R ϑ ( ↓ ) from Lemma 1 as our primary metric of preference distribution matching, using a consistent evaluation partitioning rule for cross-method comparisons. We also report hypervolume ( H V , ↑ ) (\mathrm{HV}, \uparrow) ( HV , ↑ ) and its normalized gap ( Δ H V , ↓ ) (\Delta\mathrm{HV}, \downarrow) ( Δ HV , ↓ ) for objective-space quality. We emphasize uniform PF coverage ( ϑ ≡ 1 ) (\vartheta\equiv1) ( ϑ ≡ 1 ) , an important a posteriori MOO task,
Vector (PDF)
caption: Finite-resolution errors versus N N N for M = 3 M=3 M = 3 (left) and M = 6 M=6 M = 6 (right). The decay is consistent with the predicted O ( N − 1 ) O(N^{-1}) O ( N − 1 ) and O ( N − 2 / 5 ) O(N^{-2/5}) O ( N − 2/5 ) rates.
evaluating PF-area uniformity through the target-mass residual and average and worst-case coverage through inverted generational distance (IGD, ↓ \downarrow ↓ ) and fill distance (↓ \downarrow ↓ ), respectively [33 , 72 ] . Section 5.1 examines our theoretical guarantees, Section 5.2 benchmarks PF coverage under TS on ZDT/DTLZ [73 , 21 ] problems, and Section 5.3 demonstrates applicability beyond TS using weighted-sum scalarization in multi-objective reinforcement learning. Further experimental protocols, metric definitions, implementation details, and additional experiments are in Appendix E.
Controlled Geometry and Preference Matching
This section considers an analytic three-objective problem:
min x ∈ Δ 3 f ( x ) = exp ( κ ∥ x − 1 3 1 ∥ 2 2 ) x , 0 ≤ κ ≤ 3. (15) \begin{aligned}
\min_{\mathbf{x}\in\Delta_3}\ \mathbf{f}(\mathbf{x}) &= \exp\left(\kappa\left\lVert\mathbf{x}-\frac{1}{3}\mathbf{1}\right\rVert_2^2\right)\mathbf{x}, \qquad0\leq\kappa\leq3. \tag*{(15)}
\end{aligned} x ∈ Δ 3 min f ( x ) = exp ( κ x − 3 1 1 2 2 ) x , 0 ≤ κ ≤ 3. (15)
TS with z = 0 \mathbf{z}=\mathbf{0} z = 0 yields f P F ( w ) = exp ( κ ∥ w − 1 3 1 ∥ 2 2 ) w \mathbf{f}_{\mathrm{PF}}(\mathbf{w})=\exp\left(\kappa\left\lVert\mathbf{w}-\frac{1}{3}\mathbf{1}\right\rVert_2^2\right)\mathbf{w} f PF ( w ) = exp ( κ w − 3 1 1 2 2 ) w . Its exact area-distortion ratio over Δ 3 \Delta_3 Δ 3 is J ‾ / J ‾ = e 4 κ / 3 1 + 8 κ / 3 + 8 κ 2 / 3 \overline{J}/\underline{J}=e^{4\kappa/3}\sqrt{1+8\kappa/3+8\kappa^2/3} J / J = e 4 κ /3 1 + 8 κ /3 + 8 κ 2 /3 , which increases with κ \kappa κ . Setting κ = 1 \kappa=1 κ = 1 , we first illustrate how SURFACE controls where finite PF resolution is allocated through ϑ \vartheta ϑ . We consider the uniform preference ϑ = 1 \vartheta=1 ϑ = 1 and a focused preference ϑ = ϑ f o c u s ( y ) = exp ( − ∥ y − f P F ( [ 0.55 , 0.30 , 0.15 ] ⊤ ) ∥ 2 2 2 σ 2 ) \vartheta=\vartheta_{\mathrm{focus}}(\mathbf{y})=\exp\left(-\frac{\left\lVert\mathbf{y}-\mathbf{f}_{\mathrm{PF}}([0.55,0.30,0.15]^\top)\right\rVert_2^2}{2\sigma^2}\right) ϑ = ϑ focus ( y ) = exp ( − 2 σ 2 ∥ y − f PF ([ 0.55 , 0.30 , 0.15 ] ⊤ ) ∥ 2 2 ) , where σ \sigma σ is 15% of the PF diameter. As shown in Figure 4 , using N = 63 N=63 N = 63 , α = 1 \alpha=1 α = 1 , and T = 5 T=5 T = 5 on (15) with κ = 1 \kappa=1 κ = 1 , SURFACE under the focused preference concentrates Pareto solutions around the target region, while SURFACE with ϑ = 1 \vartheta=1 ϑ = 1 redistributes samples toward uniform PF surface-area coverage. In contrast, fixed Uniform weighting inherits the uncontrolled weight-to-PF distortion and concentrates toward the PF center.
Figure 4. Uniform weighting versus SURFACE with ϑ = 1 \vartheta=1 ϑ = 1 , ϑ f o c u s \vartheta_{\mathrm{focus}} ϑ focus . Warmer colors indicate higher ϑ f o c u s \vartheta_{\mathrm{focus}} ϑ focus .
We fix ϑ = 1 \vartheta=1 ϑ = 1 and vary κ ∈ { 0 , 0.5 , 1 , 1.5 , 2 , 2.5 , 3 } \kappa\in\{0,0.5,1,1.5,2,2.5,3\} κ ∈ { 0 , 0.5 , 1 , 1.5 , 2 , 2.5 , 3 } to examine increasingly distorted PFs. As shown in Figure 5 , with N = 63 N=63 N = 63 , α = 0.2 \alpha=0.2 α = 0.2 , and T = 5 T=5 T = 5 rounds, the measured distortion ratio J ‾ / J ‾ \overline{J}/\underline{J} J / J increases from 1 to 299.53. At κ = 3 \kappa=3 κ = 3 , Uniform weighting has measured residual R ϑ = 8.901 \mathcal{R}_{\vartheta}=8.901 R ϑ = 8.901 , whereas SURFACE remains below 0.785 throughout the sweep. For reference, SURFACE (Exact J J J ) replaces the reconstructed area density with the analytic J J J while keeping the same transport procedure and has residual 0.0337 at κ = 3 \kappa=3 κ = 3 , providing an analytic-density reference. Figure 6 further shows that the finite-resolution errors decrease with N N N at rates consistent with the theoretical O ( N − 1 ) O(N^{-1}) O ( N − 1 ) for M = 3 M=3 M = 3 and O ( N − 2 / 5 ) O(N^{-2/5}) O ( N − 2/5 ) for M = 6 M=6 M = 6 in Theorem 1.
Figure 5. Residual R ϑ ( W T ) \mathcal{R}_{\vartheta}(W_T) R ϑ ( W T ) versus PF distortion. SURFACE (Exact J J J ) uses the analytic density.
Uniform Pareto-Front Coverage on ZDT and DTLZ Benchmarks
We further evaluate SURFACE on ZDT1/2/4 and DTLZ2/3/4 [73 , 21 ] with the uniform PF coverage preference ϑ = 1 \vartheta=1 ϑ = 1 . We compare SURFACE with Uniform weighting (Zhang & Li, [69 ] ), UMOD (Zhang et al., [72 ] ), LMPFE (Tian et al., [60 ] ), DEA-GNG (Liu et al., [39 ] ), Subset selection (Shang et al., [55 ] ), NSGA-III (Deb & Jain, [19 ] ), SMS-EMOA (Beume et al., [5 ] ), MOEA/D (Zhang & Li, [69 ] ), and MOEA/D-AWA (Qi et al., [49 ] ), with the same number of returned solutions. SURFACE and Uniform use the same scalarized optimization procedure and differ only in their scalarization weights, allowing us to isolate the effect of adaptive weight redistribution. We evaluate the remaining baselines end-to-end, including their optimization and solution-selection procedures. We use target-mass residuals as the primary distribution-matching metrics, together with area-weighted IGD (Ishibuchi et al., [33 ] ), fill distance (Zhang et al., [72 ] ), and hypervolume (Beume et al., [5 ] ; Shang et al., [54 ] ).
Table 2 reports a preview of the results, while complete results for all ten methods are provided in Appendix § 14 .§ 3 . Across the 11 settings, SURFACE achieves the best mean rank, as visualized in Figure 7 , where the coverage metric averages the first three PF-representation metrics. Compared with Uniform, SURFACE improves all four metrics in every primary comparison, with median reductions of 35.7% in PF-area imbalance, 3.64% in IGD, 14.2% in fill distance, and 7.21% in normalized hypervolume gap. These results show that adapting the scalarization weights to the PF geometry produces a more uniform finite representation while maintaining competitive objective-space quality. We further examine how SURFACE allocates solutions under uniform and focused preferences on connected and disconnected PFs. As shown in Figure 8 , SURFACE with ϑ = 1 \vartheta= 1 ϑ = 1 distributes solutions across the PF, while ϑ f o c u s \vartheta_{\mathrm{focus}} ϑ focus concentrates them in preferred regions. On DTLZ2, the focused preference emphasizes balanced tradeoffs, while on disconnected DTLZ7 (M = 2 , 3 M = 2, 3 M = 2 , 3 ) and DTLZ3 fronts, it increases resolution in preferred regions while retaining broad PF coverage. These disconnected-front results extend the empirical evaluation beyond the smooth, connected PF charts covered by our theoretical guarantees.
Figure 7. Mean ranks on PF coverage and HV over eleven ZDT/DTLZ tasks. Error bars show standard deviations. Complete results are in Appendix E.3.
Table 2. Benchmark results for representative baselines. Entries for stochastic baselines are mean ± standard deviation over five seeds. SURFACE and Uniform are deterministic. Complete results for all ten methods are reported in Appendix § 14 .§ 3 .
Figure 8. SURFACE with ϑ = 1 \vartheta= 1 ϑ = 1 , ϑ f o c u s \vartheta_{\mathrm{focus}} ϑ focus . From left to right: DTLZ2 (M = 3 M = 3 M = 3 , N = 66 N = 66 N = 66 ), DTLZ7 (M = 3 M = 3 M = 3 , N = 153 N = 153 N = 153 ), DTLZ7 (M = 2 M = 2 M = 2 , N = 20 N = 20 N = 20 ), and ZDT3 (M = 2 M = 2 M = 2 , N = 25 N = 25 N = 25 ). Warmer PF colors indicate higher ϑ f o c u s \vartheta_{\mathrm{focus}} ϑ focus on a shared 0–1 scale.
Multi-Objective Policy Optimization
We additionally evaluate SURFACE’s compatibility beyond TS by implementing it with weighted-sum scalarization on Deep Sea Treasure, Resource Gathering, and Fruit Tree from MO-Gymnasium (Felten et al., [29 ] ). Deep Sea Treasure (M = 2 M = 2 M = 2 ) is a navigation task balancing treasure value and travel time, while Resource Gathering (M = 3 M = 3 M = 3 ) balances gold and gem collection against enemy risk. Fruit Tree (M = 6 M = 6 M = 6 ) is a tree-navigation task in which different fruits provide different nutritional rewards. We optimize weighted sums of expected rewards with KL regularization ([50 , 34 ] ), with theoretical details in Appendix § 11 .§ 4 . With the uniform PF target ϑ ≡ 1 \vartheta\equiv1 ϑ ≡ 1 , we compare SURFACE with Uniform using the same inner solver. We match the solver budget between the two methods. The remaining baselines use their standard evolutionary policy optimizers. As shown in Table 3 , SURFACE consistently improves both PF-area residuals and area-weighted IGD over Uniform on all three environments while maintaining comparable hypervolume. Experimental settings, additional resolution studies, and policy diagnostics are provided in Appendix § 14 .§ 4 .
Table 3. MO-Gym policy results. Stochastic entries are mean ± sample standard deviation over five seeds. Uniform and SURFACE are deterministic. Bold marks the best mean in each row.
Conclusion
This paper introduced SURFACE, a geometry-aware framework for matching a prescribed preference distribution on the PF. The framework estimates the weight-to-PF chart from finitely many scalarized solutions and redistributes scalarization weights via mass equidistribution. Theoretically, we showed that Tchebycheff scalarization induces a smooth, nonfolding, and nondegenerate PF chart under the stated regularity conditions. We also proved that SURFACE contracts the coupled density–solver error geometrically to an O ( N − 2 / ( M − 1 ) ) O(N^{-2/(M-1)}) O ( N − 2/ ( M − 1 ) ) finite-resolution floor. The same rate holds for the target-mass imbalance across complete represented PF regions. Experiments across ZDT/DTLZ benchmarks and MO-Gymnasium policy tasks against nine baselines confirm consistent gains in preference matching and Pareto representation quality. SURFACE is compatible with off-the-shelf solvers and inexact warm-started optimization. A natural future direction is to mitigate the rapid growth of the required number of adaptive weights N N N with the number of objectives M M M . This could be achieved through adaptive sparse weight placement or hierarchical mesh refinement.
AI Use Statement
We used generative AI tools to help polish the writing and to double-check parts of the mathematical proofs. All final arguments and proofs were reviewed and verified by the authors.
Reproducibility Statement
Implementation details for SURFACE and the experimental settings are provided in Appendix § 14 . The code is provided in the supplementary material.
Acknowledgements
This work is partially supported by the Center of Excellence (CoE) in Data Science and Artificial Intelligence at the University of Rochester. We also acknowledge the Center for Integrated Research Computing (CIRC) at the University of Rochester and Empire AI for providing computational resources and support.
Related Work and Notation
This section gives further comparisons with related methods and collects the notation used in the analysis.
Detailed Related Work
Preference specification and Pareto-set learning. Preference information in MOO is commonly incorporated either a priori , before optimization, or a posteriori , after constructing a Pareto representation [46 ] . A priori methods use specified preferences to target preferred Pareto solutions or regions [14 , 15 ] . Preference-conditioned learning extends this paradigm by learning a map from preferences to Pareto solutions. Pareto HyperNetworks [44 ] generate models conditioned on preference vectors, while Pareto Set Learning [37 ] learns a continuous preference-to-solution map for expensive MOO. Evolutionary Preference Sampling [66 ] adapts the preference distribution used for training, and shape-agnostic Pareto Set Learning [65 ] formulates Pareto-set learning as distribution transformation with a hypervolume objective. A posteriori methods instead construct a finite PF approximation for subsequent selection [72 , 7 ] . SURFACE connects these two paradigms: it specifies the desired allocation a priori through a probability distribution over the PF and returns an a posteriori finite representation whose resolution follows that distribution.
Scalarization and geometry-based PF coverage. Scalarization generates Pareto solutions by varying preference parameters. Weighted-sum scalarization [40 ] covers the full PF under suitable convexity conditions but can miss Pareto solutions on nonconvex fronts [43 , 24 ] . Tchebycheff scalarization [43 , 24 ] , achievement scalarization [24 ] , and Pascoletti–Serafini scalarization [26 ] provide alternative parameterizations under their respective conditions. Standard scalarization determines which Pareto solution corresponds to a parameter but does not control the distribution of a finite parameter set over the PF. In particular, uniformly spaced parameters can produce nonuniformly spaced Pareto points [18 , 71 , 34 ] . We therefore use uniform scalarization weights as a baseline for isolating the effect of SURFACE’s redistribution.
Several methods adapt scalarization parameters or objective-space constructions to improve PF coverage. Eichfelder [26 ] uses local sensitivity information to adapt Pascoletti–Serafini parameters toward nearly equidistant objective-space points. Zhang & Gao [71 ] adjusts min–max weights to generate more uniformly spaced Pareto points, while Saini et al. [52 ] removes directions in densely represented regions and adds directions in sparse regions. Normal-boundary intersection [18 ] generates solutions along normal directions from reference points on the convex hull of the individual minima. The normalized normal-constraint method [42 ] normalizes the objectives and generates solutions through moving objective-space constraints. Directed Search Domain methods [27 ] sequentially restrict objective-space regions to place new solutions in sparsely represented areas, with a higher-dimensional extension given by Yu & Utyuzhnikov [67 ] . These methods primarily target uniform or well-spread representations. Their updates use local sensitivity information [26 ] , sequential parameter selection [71 , 52 , 27 ] , or additional objective-space directions and constraints [18 , 42 ] . SURFACE uses the weight–objective pairs from a parallel batch of scalarized solves to estimate the PF geometry. It then adjusts the weights for a prescribed PF distribution while retaining the chosen scalarization and inner solver.
Finite Pareto representations: tracing, diversity, and design. Continuation methods construct finite PF representations by following local Pareto geometry. Hillermeier (2001) models Pareto candidates as a differentiable manifold and uses generalized homotopy to discretize it evenly. Pereyra [47 ] ; Pereyra et al. [48 ] incorporate spacing conditions into continuation procedures, including objective-space arc-length spacing for constrained bi-objective problems. Martin et al. [41 ] follows bi-objective branches with interval validation, Bolten et al. [8 ] traces locally Pareto-optimal solutions through numerical integration of sensitivity information, and Beltrán et al. [3 ] extends Pareto tracing to inequality-constrained problems. These methods advance sequentially from previously computed solutions using local derivative, tangent, or sensitivity information [48 , 8 ] (Hillermeier 2001). SURFACE also uses local PF geometry to place solutions, but reconstructs this geometry from parallel scalarized solves. Evolutionary decomposition and reference-vector methods construct finite representations by controlling search directions or reference points. MOEA/D [69 ] decomposes MOO into scalar subproblems associated with a fixed set of weights. MOEA/D-AWA [49 ] removes weights associated with crowded or duplicate solutions and adds weights in sparse PF regions. DEA-GNG [39 ] adapts preference vectors using a growing neural gas representation of the evolving PF. NSGA-III [19 ] maintains diversity through reference-point association, while RVEA [16 ] combines angle-penalized distance with adaptive reference vectors. These methods allocate solutions using sparsity, occupancy, learned PF structure, or angular diversity.
Other methods define representativeness through an explicit finite-set objective. LMPFE [60 ] approximates the PF using multiple local models, while fixed-cardinality subset selection [55 ] selects a representative subset from a larger candidate set. UMOD [72 ] measures representativeness by fill distance and optimizes a max-packing surrogate with a constant-factor fill-distance guarantee. Borghi (2023) uses binary repulsive potentials for bi- and tri-objective PFs, while Borghi et al. (2023) combines gradient-free search with energy-based parameter dynamics. Riesz energy has been used to generate arbitrary-cardinality reference sets on the unit simplex [6 ] and to optimize point configurations directly on nonlinear PFs [45 ] . These methods define the desired representation through approximation, covering, packing, subset selection, or repulsion.
Set-quality indicators provide another, implicit specification of the desired finite representation. Classical indicators combine convergence and spread in different ways [73 ] . Crowding distance [20 ] favors locally isolated solutions. IGD [33 ] measures distances to a chosen reference set, while IGD+ [33 ] modifies this distance to satisfy weak Pareto compliance. Hypervolume [5 ] measures dominated objective-space volume relative to a reference point, and its optimal fixed-cardinality distribution depends on the PF geometry and reference point [54 ] . SMS-EMOA [5 ] selects solutions by hypervolume contribution, while indicator-based subset selection (Shang et al.,
retains the finite set preferred by the selected criterion. These indicators induce an allocation through a reference set, reference point, or diversity criterion. These approaches specify a finite representation through search directions, geometric spacing, or a set-quality objective. SURFACE takes a target PF distribution as input and balances its probability mass across the represented cells. A constant preference density gives uniform PF surface-area allocation.
Mesh redistribution for distribution matching. Moving-mesh and geometric-transport methods motivate SURFACE’s redistribution step. Adaptive moving meshes [32 , 13 , 64 ] distribute a prescribed monitor density equally among cells while controlling mesh quality. The monitor density determines where mesh points concentrate. Prescribed-Jacobian transport [17 ] controls the local volume change of a map to transform one density into another. Moser-type transport on domains with corners [12 ] constructs smooth maps between positive densities. Centroidal Voronoi methods [23 ] and capacity-constrained sampling [70 ] provide related ways to distribute a finite set of points, called sites. In SURFACE, these sites are scalarization weights. The prescribed PF preference and the weight-to-PF geometry determine the density to redistribute. For two objectives and a constant preference profile, the construction reduces to SURF’s chord-length fraction and inverse-CDF update [34 ] . SURF addresses uniform allocation along a one-dimensional PF, while SURFACE supports nonconstant PF distributions and higher-dimensional PFs through face-preserving transport. For two objectives, a nonconstant profile gives the corresponding preference-weighted arc-length construction.
Notation
We use ∥ u ∥ C k , 1 : = ∥ u ∥ C k + Lip ( D k u ) \lVert u\rVert_{C^{k,1}} := \lVert u\rVert_{C^k} + \operatorname{Lip}(D^k u) ∥ u ∥ C k , 1 := ∥ u ∥ C k + Lip ( D k u ) , interpreted face-wise where needed. Table 4 collects symbols that recur across sections. The last column points to each symbol’s main definition or explanation. Each proof introduces its local notation.
Table 4. Recurring notation guide.
Practical Implementation of SURFACE
We describe how to implement one outer round of Algorithm 1. SURFACE requires only a scalarized inner solver, returned objective vectors, and a prescribed preference density. Reconstruction and redistribution operate in the ( M − 1 ) (M-1) ( M − 1 ) -dimensional weight domain, without differentiating through the inner optimization.
Initialization. Choose a scalarization, a positive preference profile ϑ \vartheta ϑ , the number N N N of adaptive weights, the damping α \alpha α , and the number T T T of outer rounds. For the regular TS construction, use the weight domain Δ M δ \Delta_{M}^{\delta} Δ M δ with its M M M fixed chart corners { w m δ } m = 1 M \{w_{m}^{\delta}\}_{m=1}^{M} { w m δ } m = 1 M . Construct a shape-regular reference triangulation with N N N adaptive vertices and fixed corners, retaining its connectivity across rounds. Initialize ρ 0 \rho_{0} ρ 0 as the uniform density on this domain and assign an initial state to each scalarized solver. Obtain objective values at the fixed chart corners once, or refine those solutions as needed. These M M M corner samples are separate from the N N N adaptive solutions and are included in the inner-solve accounting if not supplied.
Scalarized solves and PF reconstruction. At round t t t , use MEQN ( ρ t ) \operatorname{MEQN}(\rho_{t}) MEQN ( ρ t ) to obtain the current adaptive weights { w n ( t ) } n = 1 N \{w_{n}^{(t)}\}_{n=1}^{N} { w n ( t ) } n = 1 N . Solve the associated scalarized problems independently, warm-starting the n n n th solve from x ~ n ( t − 1 ) \tilde{x}_{n}^{(t-1)} x ~ n ( t − 1 ) as in (9) . These solves may be run in parallel. Collect the weight–objective pairs { ( w n ( t ) , f ( x ~ n ( t ) ) ) } n = 1 N \{(w_{n}^{(t)}, f(\tilde{x}_{n}^{(t)}))\}_{n=1}^{N} {( w n ( t ) , f ( x ~ n ( t ) )) } n = 1 N together with the fixed chart-corner pairs. To construct P t P_{t} P t , fit a quadratically augmented, compactly supported Wendland RBF model to each local patch, separately for each objective coordinate. In a patch, the fitted function has the form
P t , l o c ( w ) = q ( w ) + ∑ j c j ϕ ( ∥ w − w j ∥ r ) , (16) P_{t,\mathrm{loc}}(\mathbf{w})=q(\mathbf{w})+\sum_{j}c_{j}\phi\left(\frac{\lVert\mathbf{w}-\mathbf{w}_{j}\rVert}{r}\right), \tag*{(16)} P t , loc ( w ) = q ( w ) + j ∑ c j ϕ ( r ∥ w − w j ∥ ) , (16)
where q q q is quadratic, ϕ \phi ϕ is the Wendland kernel, and r r r is a local support radius. The coefficients are determined by interpolation at the neighboring samples with the usual polynomial side constraints. Smooth partition-of-unity weights blend these overlapping fits into P t P_{t} P t . This gives a differentiable chart between sampled weights and permits computing D P t DP_{t} D P t without differentiating the inner solver. Appendix C.1 specifies the patch and stability conditions.
Density estimation. Evaluate P t P_{t} P t and its derivatives at quadrature nodes in the weight domain. Using the same M − 1 M-1 M − 1 independent weight coordinates as in Eq. (4) , compute
J P t ( w ) = 1 M det ( D P t ( w ) T D P t ( w ) ) . (17) J_{P_{t}}(\mathbf{w})=\frac{1}{\sqrt{M}}\sqrt{\det\left(DP_{t}(\mathbf{w})^{\mathsf{T}}DP_{t}(\mathbf{w})\right)}. \tag*{(17)} J P t ( w ) = M 1 det ( D P t ( w ) T D P t ( w ) ) . (17)
Evaluate the prescribed preference on the reconstructed objective vectors, ϑ ( P t ( w ) ) \vartheta(P_{t}(\mathbf{w})) ϑ ( P t ( w )) , and normalize the product ϑ ( P t ) J P t \vartheta(P_{t})J_{P_{t}} ϑ ( P t ) J P t by numerical integration over Δ M δ \Delta_{M}^{\delta} Δ M δ . Blend this normalized density with ρ t \rho_{t} ρ t using Eq. (10) to obtain ρ t + 1 \rho_{t+1} ρ t + 1 . The preference is evaluated through its extension to a neighborhood of the PF, as in Assumption 3.
Mass equidistribution. Use ρ t + 1 \rho_{t+1} ρ t + 1 to generate the next adaptive weights. The goal is to make the associated complete cells carry equal probability mass, as in Eq. (11) . For M = 2 M=2 M = 2 , apply inverse-CDF transport to the reference sites. For M ≥ 3 M\geq3 M ≥ 3 , Appendix C.2 gives two realizations. The Moser realization integrates a face-preserving flow that transports the equal-volume reference partition toward the target density. The equal-capacity realization first selects density-dependent sites, then balances their power-cell masses by optimizing the dual offsets in Eq. (42) ; optional site refinement is restricted as in Eq. (40) . In both cases, the straight simplicial mesh T ( W ) \mathcal{T}(W) T ( W ) , constructed from the resulting sites and retained connectivity, is used for reconstruction, whereas the complete cells C ( W ) \mathcal{C}(W) C ( W ) are used to assess mass balance. The M M M chart corners remain fixed. Repeat the scalarized solves at the updated weights in the next round.
Inner-solver interface and reproducibility. The inner solver takes a weight, an initialization, and a computational budget or stopping tolerance, and returns an updated decision state and its objective vector. For differentiable models it can perform K K K steps of a standard optimizer on the scalarized loss; for a finite MDP it can use a convergent policy solver. Warm starts follow the persistent vertex labels of the mesh. For reproducibility, report the weight domain and corner samples, N N N , T T T , α \alpha α , the inner-solver stopping rule, the reconstruction stencil and kernel, quadrature accuracy, the MEQ realization and tolerances, and measured runtime. Theoretical guarantees for inexact solves require the solver-accuracy conditions of Appendix D.2; the implementation interface itself is agnostic to the chosen optimizer.
Proofs for Pareto-Front Geometry
The geometric analysis has two parts. The area formula relates probability mass in weight space to preference-weighted PF area. The scalarization results establish the smoothness and injectivity needed to use this relation for TS and weighted sums.
Proof of Lemma 1
We measure PF surface area using the ( M − 1 ) (M-1) ( M − 1 ) -dimensional Hausdorff measure H M − 1 \mathcal{H}^{M-1} H M − 1 . For every measurable τ ⊆ Δ M \tau\subseteq\Delta_M τ ⊆ Δ M , the area formula gives
H M − 1 ( f P F ( τ ) ) = ∫ τ J ( w ) d Vol M − 1 ( w ) . (18) \mathcal{H}^{M-1}\left(f_{\mathrm{PF}}(\tau)\right) = \int_{\tau} J(\mathbf{w})\,\mathrm{d}\operatorname{Vol}_{M-1}(\mathbf{w}). \tag*{(18)} H M − 1 ( f PF ( τ ) ) = ∫ τ J ( w ) d Vol M − 1 ( w ) . (18)
Accordingly, d H M − 1 ( y ) \mathrm{d}\mathcal{H}^{M-1}(\mathbf{y}) d H M − 1 ( y ) denotes the PF surface-area element at y \mathbf{y} y .
Proof. For any measurable A ⊆ Δ M A \subseteq\Delta_M A ⊆ Δ M , injectivity and full rank of f P F f_{\mathrm{PF}} f PF give the area formula
∫ A ϑ ( f P F ( w ) ) J ( w ) d w = ∫ f P F ( A ) ϑ ( y ) d H M − 1 ( y ) . (19) \int_A \vartheta(f_{\mathrm{PF}}(\mathbf{w}))J(\mathbf{w})\mathrm{d}\mathbf{w} = \int_{f_{\mathrm{PF}}(A)} \vartheta(\mathbf{y})\mathrm{d}\mathcal{H}^{M-1}(\mathbf{y}). \tag*{(19)} ∫ A ϑ ( f PF ( w )) J ( w ) d w = ∫ f PF ( A ) ϑ ( y ) d H M − 1 ( y ) . (19)
Using (5) , we have
∫ A ρ ϑ ( w ) d w = ∫ f P F ( A ) ϑ ( y ) d H M − 1 ( y ) ∫ f P F ( Δ M ) ϑ ( y ) d H M − 1 ( y ) . (20) \int_A \rho_{\vartheta}(\mathbf{w})\mathrm{d}\mathbf{w} =
\frac{\int_{f_{\mathrm{PF}}(A)} \vartheta(\mathbf{y})\mathrm{d}\mathcal{H}^{M-1}(\mathbf{y})}{\int_{f_{\mathrm{PF}}(\Delta_M)} \vartheta(\mathbf{y})\mathrm{d}\mathcal{H}^{M-1}(\mathbf{y})}. \tag*{(20)} ∫ A ρ ϑ ( w ) d w = ∫ f PF ( Δ M ) ϑ ( y ) d H M − 1 ( y ) ∫ f PF ( A ) ϑ ( y ) d H M − 1 ( y ) . (20)
Applying (20) to each τ ∈ C ( W ) \tau\in\mathcal{C}(\mathcal{W}) τ ∈ C ( W ) shows that R ^ ϑ ( W ) = 0 \widehat{R}_{\vartheta}(\mathcal{W}) = 0 R ϑ ( W ) = 0 if and only if ∫ τ ρ ϑ ( w ) d w = 1 / ∣ C ( W ) ∣ \int_{\tau} \rho_{\vartheta}(\mathbf{w})\mathrm{d}\mathbf{w} = 1/|\mathcal{C}(\mathcal{W})| ∫ τ ρ ϑ ( w ) d w = 1/∣ C ( W ) ∣ for every τ ∈ C ( W ) \tau\in\mathcal{C}(\mathcal{W}) τ ∈ C ( W ) , equivalently, all PF patches f P F ( τ ) f_{\mathrm{PF}}(\tau) f PF ( τ ) carry equal preference-weighted area.
The same identity describes the distribution of a PF point generated by sampling w \mathbf{w} w from ρ ϑ \rho_{\vartheta} ρ ϑ . For any measurable B ⊆ f P F ( Δ M ) B \subseteq f_{\mathrm{PF}}(\Delta_M) B ⊆ f PF ( Δ M ) ,
Pr ( f P F ( w ) ∈ B ) = ∫ f P F − 1 ( B ) ρ ϑ ( w ) d w = ∫ B ϑ ( y ) d H M − 1 ( y ) ∫ f P F ( Δ M ) ϑ ( y ) d H M − 1 ( y ) . (21) \Pr\left(f_{\mathrm{PF}}(\mathbf{w}) \in B\right) = \int_{f_{\mathrm{PF}}^{-1}(B)} \rho_{\vartheta}(\mathbf{w})\mathrm{d}\mathbf{w} = \frac{\int_B \vartheta(\mathbf{y})\mathrm{d}\mathcal{H}^{M-1}(\mathbf{y})}{\int_{f_{\mathrm{PF}}(\Delta_M)} \vartheta(\mathbf{y})\mathrm{d}\mathcal{H}^{M-1}(\mathbf{y})}. \tag*{(21)} Pr ( f PF ( w ) ∈ B ) = ∫ f PF − 1 ( B ) ρ ϑ ( w ) d w = ∫ f PF ( Δ M ) ϑ ( y ) d H M − 1 ( y ) ∫ B ϑ ( y ) d H M − 1 ( y ) . (21)
Thus sampling weights from ρ ϑ \rho_{\vartheta} ρ ϑ produces PF points with density proportional to ϑ \vartheta ϑ with respect to surface area.
We also use this formula for reconstructed surfaces. For a C 1 C^1 C 1 map P P P , let J P J_P J P denote the area factor obtained by replacing f P F f_{\mathrm{PF}} f PF with P P P in (4) . If P P P is injective on a measurable region A A A , then H M − 1 ( P ( A ) ) = ∫ A J P ( w ) d w \mathcal{H}^{M-1}(P(A)) = \int_A J_P(\mathbf{w})\mathrm{d}\mathbf{w} H M − 1 ( P ( A )) = ∫ A J P ( w ) d w . Thus J P ( w ) d w J_P(\mathbf{w})\mathrm{d}\mathbf{w} J P ( w ) d w measures the surface area represented by an infinitesimal weight-space region.
Proof of Proposition 2
Proof. Fix 0 < δ < 1 / M 0 < \delta< 1/M 0 < δ < 1/ M . We first show that the TS solution varies smoothly with its weight. On Δ M \Delta_M Δ M , the objective max m = 1 , … , M ( f m ( x ) − z m ) / w m \max_{m=1,\ldots,M}(f_m(\mathbf{x}) - z_m)/w_m max m = 1 , … , M ( f m ( x ) − z m ) / w m is jointly continuous in ( x , w ) (\mathbf{x}, \mathbf{w}) ( x , w ) . Compactness of X \mathcal{X} X and uniqueness in Assumption 1 therefore imply, by Berge’s maximum theorem, Berge [4 ] , that x T S ∗ ( w ) \mathbf{x}_{\mathrm{TS}}^*(\mathbf{w}) x TS ∗ ( w ) and s ∗ ( w ) s^*(\mathbf{w}) s ∗ ( w ) are continuous. The utopian reference point and active ray constraints give s ∗ ( w ) > 0 s^*(\mathbf{w}) > 0 s ∗ ( w ) > 0 . Compactness then gives a uniform positive lower bound.
At each w ∈ Δ M δ \mathbf{w} \in\Delta_M^\delta w ∈ Δ M δ , LICQ, strict complementarity, and SOSC make the active Karush–Kuhn–Tucker (KKT) system of (7) strongly regular (Bonnans & Shapiro [9 ] ). The C 3 , 1 C^{3,1} C 3 , 1 problem data give a C 2 , 1 C^{2,1} C 2 , 1 KKT residual. The implicit-function theorem therefore gives a locally unique C 2 , 1 C^{2,1} C 2 , 1 mapping from weights to the solution and its multipliers ([9 ] . Strict complementarity keeps the active set unchanged locally, and continuity and uniqueness identify this local solution with the global TS solution.
Because Δ M δ \Delta_{M}^{\delta} Δ M δ is a compact subset of relint ( Δ M ) \operatorname{relint}(\Delta_M) relint ( Δ M ) , finitely many such neighborhoods cover it. This gives uniform C 2 , 1 C^{2,1} C 2 , 1 bounds on a neighborhood of Δ M δ \Delta_{M}^{\delta} Δ M δ in the affine hyperplane 1 ⊤ w = 1 \mathbf{1}^{\top}\mathbf{w}=1 1 ⊤ w = 1 . Hence x T S ⋆ \mathbf{x}_{\mathrm{TS}}^{\star} x TS ⋆ and s ⋆ s^{\star} s ⋆ are uniformly Lipschitz, and f P F = f ∘ x T S ⋆ f_{\mathrm{PF}}=f\circ\mathbf{x}_{\mathrm{TS}}^{\star} f PF = f ∘ x TS ⋆ is C 2 , 1 C^{2,1} C 2 , 1 on this neighborhood.
We next use the radial identity f P F ( w ) = z + s ⋆ ( w ) w f_{\mathrm{PF}}(\mathbf{w})=\mathbf{z}+s^{\star}(\mathbf{w})\mathbf{w} f PF ( w ) = z + s ⋆ ( w ) w to show that changes in the weights produce nonzero changes on the PF. For any tangent direction v \mathbf{v} v satisfying 1 ⊤ v = 0 \mathbf{1}^{\top}\mathbf{v}=0 1 ⊤ v = 0 ,
D f P F ( w ) [ v ] = s ⋆ ( w ) v + D s ⋆ ( w ) [ v ] w . (22) D f_{\mathrm{PF}}(\mathbf{w})[\mathbf{v}]=s^{\star}(\mathbf{w})\mathbf{v}+D s^{\star}(\mathbf{w})[\mathbf{v}]\mathbf{w}. \tag*{(22)} D f PF ( w ) [ v ] = s ⋆ ( w ) v + D s ⋆ ( w ) [ v ] w . (22)
If D f P F ( w ) [ v ] = 0 D f_{\mathrm{PF}}(\mathbf{w})[\mathbf{v}]=0 D f PF ( w ) [ v ] = 0 , summing the coordinates in (22) gives D s ⋆ ( w ) [ v ] = 0 D s^{\star}(\mathbf{w})[\mathbf{v}]=0 D s ⋆ ( w ) [ v ] = 0 . Since s ⋆ ( w ) > 0 s^{\star}(\mathbf{w})>0 s ⋆ ( w ) > 0 , it follows that v = 0 \mathbf{v}=0 v = 0 , so f P F f_{\mathrm{PF}} f PF has full tangent rank. Injectivity follows from Proposition 1.
The uniform C 1 C^1 C 1 bound gives ∣ f P F ( w ) − f P F ( v ) ∣ ≤ C P ∣ w − v ∣ \lvert f_{\mathrm{PF}}(\mathbf{w})-f_{\mathrm{PF}}(\mathbf{v})\rvert\le C_P\lvert\mathbf{w}-\mathbf{v}\rvert ∣ f PF ( w ) − f PF ( v )∣ ≤ C P ∣ w − v ∣ . For nearby weights, full tangent rank, continuity of D f P F D f_{\mathrm{PF}} D f PF , and compactness give a uniform lower bound on the ratio of PF distance to weight distance. For weights separated by a fixed positive distance, compactness and injectivity imply that ∣ f P F ( w ) − f P F ( v ) ∣ / ∣ w − v ∣ \lvert f_{\mathrm{PF}}(\mathbf{w})-f_{\mathrm{PF}}(\mathbf{v})\rvert/\lvert\mathbf{w}-\mathbf{v}\rvert ∣ f PF ( w ) − f PF ( v )∣ / ∣ w − v ∣ attains a positive minimum. Together, these bounds give (8).
Finally, since f P F f_{\mathrm{PF}} f PF is C 2 , 1 C^{2,1} C 2 , 1 on a neighborhood of Δ M δ \Delta_{M}^{\delta} Δ M δ , its derivative is C 1 , 1 C^{1,1} C 1 , 1 . Full tangent rank and compactness imply that the singular values of the tangent derivative are uniformly bounded above and bounded away from zero. The Gram-determinant map in (4) is continuous on full-rank matrices, so J J J is continuous on Δ M δ \Delta_{M}^{\delta} Δ M δ . Compactness therefore gives constants 0 < J ≤ J ‾ < ∞ 0<J\leq\overline{J}<\infty 0 < J ≤ J < ∞ such that J ≤ J ( w ) ≤ J ‾ J\leq J(\mathbf{w})\leq\overline{J} J ≤ J ( w ) ≤ J for all w ∈ Δ M δ \mathbf{w}\in\Delta_{M}^{\delta} w ∈ Δ M δ . This proves the claim.
Sufficient Regular Regimes
Proposition 4 (Full-ray TS optimality). Suppose Assumption 2 holds, X \mathcal{X} X is compact, and z \mathbf{z} z is utopian. Fix any 0 < δ < 1 / M 0<\delta<1/M 0 < δ < 1/ M and assume that, for every w ∈ Δ M δ \mathbf{w}\in\Delta_{M}^{\delta} w ∈ Δ M δ , the following conditions hold.
(i) There exists a unique Pareto-optimal x ∈ X \mathbf{x}\in\mathcal{X} x ∈ X satisfying f 1 ( x ) − z 1 w 1 = ⋯ = f M ( x ) − z M w M \frac{f_1(\mathbf{x})-z_1}{w_1}=\cdots=\frac{f_M(\mathbf{x})-z_M}{w_M} w 1 f 1 ( x ) − z 1 = ⋯ = w M f M ( x ) − z M .
(ii) At this point, the gradients ∇ ( f m ( x ) − z m w m − f M ( x ) − z M w M ) \nabla\left(\frac{f_m(\mathbf{x})-z_m}{w_m}-\frac{f_M(\mathbf{x})-z_M}{w_M}\right) ∇ ( w m f m ( x ) − z m − w M f M ( x ) − z M ) for m = 1 , … , M − 1 m=1,\ldots,M-1 m = 1 , … , M − 1 , together with the gradients of the active feasibility constraints, are linearly independent.
(iii) The constrained first-order stationarity condition for (6) admits strictly positive coefficients on all M M M normalized objectives.
(iv) For the same first-order multipliers, the corresponding Lagrangian has positive second variation along every nonzero feasible first-order direction for which all M M M normalized objectives have the same directional derivative.
Then (7) has a unique fully active solution satisfying LICQ, positive ray multipliers, and SOSC. Strict complementarity of active feasibility inequalities remains the condition stated in Assumption 1. In particular, when no feasibility inequality is active, all conditions of that assumption hold and Proposition 2 applies.
Proof. Fix w ∈ Δ M δ \mathbf{w}\in\Delta_{M}^{\delta} w ∈ Δ M δ and let x \mathbf{x} x be the unique point in (i). Let s s s be the common value of the normalized objective gaps. Then
f m ( x ) − z m = s w m , m = 1 , … , M , (23) f_m(\mathbf{x})-z_m=s w_m,\qquad m=1,\ldots,M, \tag*{(23)} f m ( x ) − z m = s w m , m = 1 , … , M , (23)
so ( x , s ) (\mathbf{x},s) ( x , s ) is feasible for (7) and all ray inequalities are active.
We first show global optimality and uniqueness. If another feasible pair had an epigraph value smaller than s s s , then
f m ( x ′ ) − z m < f m ( x ) − z m , m = 1 , … , M , (24) f_m(\mathbf{x}')-z_m<f_m(\mathbf{x})-z_m,\qquad m=1,\ldots,M, \tag*{(24)} f m ( x ′ ) − z m < f m ( x ) − z m , m = 1 , … , M , (24)
which would strictly improve every objective and contradict Pareto optimality of x \mathbf{x} x . Hence ( x , s ) (\mathbf{x},s) ( x , s ) is globally optimal. If another global solution had the same epigraph value, its objective values would be no larger than those of x x x . Pareto optimality forces equality in every objective. The normalized objective gaps are then equal at that solution as well, and uniqueness in (i) gives the same decision point. Thus (7) has a unique solution.
We next verify LICQ. Consider any linear dependence among the gradients of the M M M active ray constraints and the active feasibility constraints in the variables ( x , s ) (x,s) ( x , s ) . The s s s component implies that the coefficients of the ray gradients have weighted sum zero. Eliminating the coefficient of the M M M th ray constraint reduces the x x x component to a linear dependence among the M − 1 M-1 M − 1 normalized-gap gradients in part (ii) and the active feasibility-constraint gradients. Part (ii) forces all coefficients to vanish. Hence LICQ holds for (7).
Part (iii) gives strictly positive coefficients on the gradients ∇ f m ( x ) / w m \nabla f_m(x)/w_m ∇ f m ( x ) / w m in the max-form stationarity condition. Dividing the coefficient associated with objective m m m by w m > 0 w_m>0 w m > 0 gives a strictly positive multiplier for the corresponding ray inequality. Since the max-form coefficients sum to one, these ray multipliers satisfy the stationarity condition with respect to s s s . The stationarity condition with respect to x x x is unchanged. Hence every active ray inequality has a positive multiplier.
Finally, full activity and positive multipliers imply that every critical direction of (7) satisfies the linearized equalities of all M M M ray constraints. Eliminating the epigraph component leaves a feasible decision direction along which all normalized objectives have the same directional derivative. If this decision component is zero, the linearized ray equalities also force the epigraph component to be zero. Part (iv) therefore gives strictly positive second variation along every nonzero critical direction, proving SOSC. When the feasibility inequalities are inactive, the positive ray multipliers also establish strict complementarity for the full problem.
Proposition 5 (DTLZ2 with \delta \downarrow 0). Consider standard DTLZ2 ([21 ] ) *with M \ge 2objectives. For every 0 < δ < 1 M \text{objectives. For every } 0 < \delta< \frac{1}{M} objectives. For every 0 < δ < M 1 , choosing a strictly utopian reference z = − ϵ 1 \mathbf{z}=-\epsilon\mathbf{1} z = − ϵ 1 with 0 < ϵ ≤ δ / 2 0 < \epsilon\le\delta/2 0 < ϵ ≤ δ /2 ensures that the TS problem satisfies the regular full-ray conditions of Proposition 4 uniformly on Δ M δ \Delta_M^\delta Δ M δ . In particular, δ \delta δ can be made arbitrarily small, provided ϵ = O ( δ ) \epsilon=O(\delta) ϵ = O ( δ ) , allowing the represented PF to approach the entire DTLZ2 PF with approximation error O ( δ ) O(\delta) O ( δ ) .*
Proof. The DTLZ2 PF is the nonnegative unit sphere, characterized by ∥ f ( x ) ∥ 2 = 1 \lVert f(x)\rVert_2=1 ∥ f ( x ) ∥ 2 = 1 , with all tail variables equal to 1 / 2 1/2 1/2 . For any w ∈ Δ M δ \mathbf{w}\in\Delta_M^\delta w ∈ Δ M δ , the ray from z = − ϵ 1 \mathbf{z}=-\epsilon\mathbf{1} z = − ϵ 1 in direction w \mathbf{w} w intersects this sphere uniquely. Indeed, ∥ w − ϵ 1 ∥ 2 < 1 \lVert\mathbf{w}-\epsilon\mathbf{1}\rVert_2<1 ∥ w − ϵ 1 ∥ 2 < 1 , and the norm increases strictly along the ray thereafter. Since ϵ ≤ δ / 2 \epsilon\le\delta/2 ϵ ≤ δ /2 , every coordinate of the intersection is at least δ / 2 > 0 \delta/2>0 δ /2 > 0 . Thus, the intersection corresponds to a unique decision point with interior angular coordinates and tail variables equal to 1 / 2 1/2 1/2 . No smaller TS objective value is feasible, since it would require an objective vector strictly dominated by this PF point. This establishes part (i).
The DTLZ2 objective map has full tangent rank on the strictly positive PF, and f P F ( w ) T w > 0 \mathbf{f}_{\mathrm{PF}}(\mathbf{w})^{\mathsf{T}}\mathbf{w}>0 f PF ( w ) T w > 0 ensures that the ray is transverse to the sphere, verifying part (ii). The stationarity multipliers are strictly positive and proportional to w m f m ( x T S ∗ ( w ) ) w_m f_m(\mathbf{x}_{\mathrm{TS}}^*(\mathbf{w})) w m f m ( x TS ∗ ( w )) , establishing part (iii). For part (iv), the linearized active constraints eliminate all nonzero angular critical directions, while the remaining tail directions have strictly positive quadratic curvature. These conditions hold uniformly on each fixed Δ M δ \Delta_M^\delta Δ M δ by smoothness and compactness.
Finally, the ray intersection satisfies ∥ f P F ( w ) − w ∥ w ∥ 2 ∥ 2 ≤ 2 M ϵ \left\lVert\mathbf{f}_{\mathrm{PF}}(\mathbf{w})-\frac{\mathbf{w}}{\lVert\mathbf{w}\rVert_2}\right\rVert_2\le2\sqrt{M}\epsilon f PF ( w ) − ∥ w ∥ 2 w 2 ≤ 2 M ϵ . As δ ↓ 0 \delta\downarrow0 δ ↓ 0 , Δ M δ \Delta_M^\delta Δ M δ approaches the full simplex, and the normalization map w ↦ w / ∥ w ∥ 2 \mathbf{w}\mapsto\mathbf{w}/\lVert\mathbf{w}\rVert_2 w ↦ w / ∥ w ∥ 2 is Lipschitz on the simplex. Consequently, every point on the DTLZ2 PF can be approximated by the represented PF with error O ( δ + ϵ ) = O ( δ ) O(\delta+\epsilon)=O(\delta) O ( δ + ϵ ) = O ( δ ) . Hence, δ \delta δ can be made arbitrarily small while preserving the full-ray conditions on each Δ M δ \Delta_M^\delta Δ M δ .
Weighted-Sum Specialization
Weighted-sum scalarization gives another regular PF chart when the objectives become strongly convex after a smooth change of variables. We consider
x L S ∗ ( w ) ∈ arg min x ∈ X ∑ m = 1 M w m f m ( x ) , w ∈ Δ M . (25) \mathbf{x}_{\mathrm{LS}}^*(\mathbf{w})\in\underset{\mathbf{x}\in\mathcal{X}}{\arg\min}\ \sum_{m=1}^{M}w_m f_m(\mathbf{x}),\qquad\mathbf{w}\in\Delta_M. \tag*{(25)} x LS ∗ ( w ) ∈ x ∈ X arg min m = 1 ∑ M w m f m ( x ) , w ∈ Δ M . (25)
Although optimization problems may be nonconvex in their original parameterization, some admit an equivalent convex representation through a change of variables, as studied in hidden-convex optimization [28 ] . Building on this perspective, we impose hidden strong convexity and additional regularity conditions to establish a smooth, nondegenerate PF chart for weighted-sum scalarization.
Assumption 4 (Hidden strong convexity). There exist a compact convex set Y \mathcal{Y} Y and a C 3 , 1 C^{3,1} C 3 , 1 diffeomorphism Ψ \Psi Ψ between neighborhoods of Y \mathcal{Y} Y and X \mathcal{X} X , with Ψ ( Y ) = X \Psi(\mathcal{Y}) = \mathcal{X} Ψ ( Y ) = X , such that each transformed objective f m ∘ Ψ f_m \circ\Psi f m ∘ Ψ is μ \mu μ -strongly convex on Y \mathcal{Y} Y for a common μ > 0 \mu> 0 μ > 0 . The set Y \mathcal{Y} Y is defined by C 3 , 1 C^{3,1} C 3 , 1 , convex inequalities and affine equalities. For every w ∈ Δ M \mathbf{w} \in\Delta_M w ∈ Δ M , the transformed weighted-sum problem satisfies LICQ and strict complementarity at its minimizer, and the objective gradients projected onto the tangent space of the active constraints have rank M − 1 M-1 M − 1 .
Proposition 6 (Regular PF chart from weighted sums). Suppose Assumptions 2 and 4 hold. Then (25) has a unique solution for every w ∈ Δ M \mathbf{w} \in\Delta_M w ∈ Δ M , weighted-sum scalarization covers the PF, and f P F ( w ) : = f ( x L S ( w ) ) f_{\mathrm{PF}}(\mathbf{w}) := f(\mathbf{x}_{\mathrm{LS}}(\mathbf{w})) f PF ( w ) := f ( x LS ( w )) is injective with full tangent rank. Moreover, f P F f_{\mathrm{PF}} f PF admits a C 2 , 1 C^{2,1} C 2 , 1 extension to a neighborhood of Δ M \Delta_M Δ M in the affine hyperplane 1 T w = 1 \mathbf{1}^{\mathsf T}\mathbf{w} = 1 1 T w = 1 . There exist constants 0 < c P ≤ C P < ∞ 0 < c_P \le C_P < \infty 0 < c P ≤ C P < ∞ , s.t. c P ∥ w − v ∥ ≤ ∥ f P F ( w ) − f P F ( v ) ∥ ≤ C P ∥ w − v ∥ c_P \lVert\mathbf{w} - \mathbf{v} \rVert\le\lVert f_{\mathrm{PF}}(\mathbf{w}) - f_{\mathrm{PF}}(\mathbf{v}) \rVert\le C_P \lVert\mathbf{w} - \mathbf{v} \rVert c P ∥ w − v ∥ ≤ ∥ f PF ( w ) − f PF ( v )∥ ≤ C P ∥ w − v ∥ , w , v ∈ Δ M \mathbf{w}, \mathbf{v} \in\Delta_M w , v ∈ Δ M .
c P ∥ w − v ∥ ≤ ∥ f P F ( w ) − f P F ( v ) ∥ ≤ C P ∥ w − v ∥ , w , v ∈ Δ M (26) c_P \lVert\mathbf{w} - \mathbf{v} \rVert\le\lVert f_{\mathrm{PF}}(\mathbf{w}) - f_{\mathrm{PF}}(\mathbf{v}) \rVert\le C_P \lVert\mathbf{w} - \mathbf{v} \rVert,\qquad\mathbf{w},\mathbf{v}\in\Delta_M \tag*{(26)} c P ∥ w − v ∥ ≤ ∥ f PF ( w ) − f PF ( v )∥ ≤ C P ∥ w − v ∥ , w , v ∈ Δ M (26) The area factor J J J is C 1 , 1 C^{1,1} C 1 , 1 on Δ M \Delta_M Δ M and satisfies 0 < J ‾ ≤ J ( w ) ≤ J ‾ < ∞ 0 < \underline{J} \le J(\mathbf{w}) \le\overline{J} < \infty 0 < J ≤ J ( w ) ≤ J < ∞ .
For regularized policy objectives, the proposition applies when a smooth invertible policy parameterization satisfies Assumption 4, including the condition that weight changes produce nonzero first-order changes on the PF.
Proof. Under x = Ψ ( y ) \mathbf{x} = \Psi(\mathbf{y}) x = Ψ ( y ) , problem (25) minimizes ∑ m = 1 M w m ( f m ∘ Ψ ) ( y ) \sum_{m=1}^{M} w_m(f_m \circ\Psi)(\mathbf{y}) ∑ m = 1 M w m ( f m ∘ Ψ ) ( y ) over Y \mathcal{Y} Y . Since the transformed objectives are μ \mu μ -strongly convex and w ∈ Δ M \mathbf{w} \in\Delta_M w ∈ Δ M , each weighted-sum problem has a unique minimizer. Convexity also ensures that weighted-sum scalarization covers the entire PF [24 ] . Conversely, every weighted-sum minimizer is Pareto optimal: any dominating point would either improve the weighted objective or contradict uniqueness. The bijection Ψ \Psi Ψ preserves these properties in the original variables.
We next establish smoothness. Strong convexity and convexity of the constraints imply SOSC. Together with LICQ and strict complementarity, these conditions ensure nonsingularity of the KKT system [9 ] . Since the problem data are C 3 , 1 C^{3,1} C 3 , 1 , the implicit-function theorem yields a locally unique C 2 , 1 C^{2,1} C 2 , 1 solution mapping. Strict complementarity preserves the active set locally, while uniqueness makes these local mappings consistent. They therefore extend to a neighborhood of the compact simplex Δ M \Delta_M Δ M , giving a C 2 , 1 C^{2,1} C 2 , 1 extension of x L S ∗ \mathbf{x}_{\mathrm{LS}}^* x LS ∗ and f P F f_{\mathrm{PF}} f PF .
To prove full tangent rank, fix w ∈ Δ M \mathbf{w} \in\Delta_M w ∈ Δ M and a nonzero v \mathbf{v} v with 1 T v = 0 \mathbf{1}^{\mathsf T}\mathbf{v} = 0 1 T v = 0 . Let y ˙ \dot{\mathbf{y}} y ˙ denote the derivative of the transformed minimizer in direction v \mathbf{v} v . Suppose D f P F ( w ) [ v ] = 0 D f_{\mathrm{PF}}(\mathbf{w})[\mathbf{v}] = 0 D f PF ( w ) [ v ] = 0 , so ∇ ( f m ∘ Ψ ) T y ˙ = 0 \nabla(f_m \circ\Psi)^{\mathsf T}\dot{\mathbf{y}} = 0 ∇ ( f m ∘ Ψ ) T y ˙ = 0 for every m m m . Differentiating the KKT conditions and taking the inner product with y ˙ \dot{\mathbf{y}} y ˙ gives
y ˙ T H y ˙ = − y ˙ T ∑ m = 1 M v m ∇ ( f m ∘ Ψ ) = 0 (27) \dot{\mathbf{y}}^{\mathsf T} H \dot{\mathbf{y}} = -\dot{\mathbf{y}}^{\mathsf T}\sum_{m=1}^{M} v_m \nabla(f_m \circ\Psi) = 0 \tag*{(27)} y ˙ T H y ˙ = − y ˙ T m = 1 ∑ M v m ∇ ( f m ∘ Ψ ) = 0 (27)
where H H H is the Lagrangian Hessian. Since y ˙ \dot{\mathbf{y}} y ˙ lies in the active-constraint tangent space, SOSC implies y ˙ = 0 \dot{\mathbf{y}} = 0 y ˙ = 0 . The differentiated stationarity condition then shows that v \mathbf{v} v lies in the nullspace of the projected objective-gradient matrix. By KKT stationarity and the rank-M − 1 M-1 M − 1 assumption, this nullspace is spanned by w \mathbf{w} w . Since 1 T v = 0 \mathbf{1}^{\mathsf T}\mathbf{v} = 0 1 T v = 0 , we obtain v = 0 \mathbf{v} = 0 v = 0 , a contradiction. Hence f P F f_{\mathrm{PF}} f PF has full tangent rank.
For injectivity, suppose f P F ( w ) = f P F ( v ) f_{\mathrm{PF}}(\mathbf{w}) = f_{\mathrm{PF}}(\mathbf{v}) f PF ( w ) = f PF ( v ) . The corresponding minimizers attain the same objective vector and therefore minimize both weighted-sum problems. Uniqueness gives the same decision point. Subtracting their KKT stationarity conditions shows that w − v \mathbf{w} - \mathbf{v} w − v lies in the nullspace of the projected objective-gradient matrix. The rank condition and 1 T ( w − v ) = 0 \mathbf{1}^{\mathsf T}(\mathbf{w} - \mathbf{v}) = 0 1 T ( w − v ) = 0 imply w = v \mathbf{w} = \mathbf{v} w = v .
Finally, the C 2 , 1 C^{2,1} C 2 , 1 regularity, full tangent rank, injectivity, and compactness of Δ M \Delta_M Δ M yield the bi-Lipschitz bounds in (26). The Gram-determinant expression (4) then implies that J J J is C 1 , 1 C^{1,1} C 1 , 1 and satisfies 0 < J ‾ ≤ J ( w ) ≤ J ‾ < ∞ 0 < \underline{J} \le J(\mathbf{w}) \le\overline{J} < \infty 0 < J ≤ J ( w ) ≤ J < ∞ uniformly on Δ M \Delta_M Δ M .
Details for the SURFACE Algorithm
We analyze PF reconstruction and weight redistribution on the fixed domain Δ M δ \Delta_M^\delta Δ M δ from Proposition 2. Throughout, C C C denotes constants independent of N N N , T T T , t t t , and α \alpha α ; unless specified otherwise, they may depend on fixed regularity parameters, including κ ϑ \kappa_{\vartheta} κ ϑ . The round-dependent coefficient C t C_t C t captures the largest PF-patch diameter on the current reconstruction mesh. For PF reconstruction, let T ( W ) \mathcal{T}(W) T ( W ) denote the straight simplicial mesh through the returned vertices. To obtain exactly N N N adaptive vertices, we map the finest standard edgewise grid with at most N N N noncorner vertices onto Δ M δ \Delta^\delta_M Δ M δ , keeping its M M M corners fixed. Any remaining vertices are inserted at the barycenters of distinct cells, each subdivided into M M M simplices. Since consecutive edgewise grids differ by O ( N ( M − 2 ) / ( M − 1 ) ) O(N^{(M-2)/(M-1)}) O ( N ( M − 2 ) / ( M − 1 ) ) vertices and contain Θ ( N ) \Theta(N) Θ ( N ) cells, these insertions suffice for all sufficiently large N N N . In the Moser realization, complete transported reference cells define C ( W ) \mathcal{C}(W) C ( W ) . In the capacity realization, complete power cells define C ( W ) \mathcal{C}(W) C ( W ) . The retained reference connectivity defines T ( W ) \mathcal{T}(W) T ( W ) in either case. The straight reconstruction mesh T ( W ) \mathcal{T}(W) T ( W ) has Θ ( N ) \Theta(N) Θ ( N ) uniformly shape-regular simplices of diameter comparable to N − 1 / ( M − 1 ) N^{-1/(M-1)} N − 1/ ( M − 1 ) , with corresponding mesh bounds on each face. Quasi-uniformity means that cell sizes remain comparable across the domain. Shape regularity means that the simplices avoid becoming arbitrarily thin relative to their diameter. These geometric conditions apply to the reconstruction mesh. The power cells are used to measure mass and need not satisfy them. The two realizations retain the same reconstruction connectivity and vertex labels across rounds. For M = 2 M=2 M = 2 , no additional insertions are needed.
Reconstruction also uses fixed TS chart-corner samples at w m δ w^\delta_m w m δ . Their initial solver states satisfy
max m ∈ [ M ] ∥ x ~ m , δ ( 0 ) − x T S ⋆ ( w m δ ) ∥ ≤ c x N − 3 / ( M − 1 ) , (28) \max_{m\in[M]} \left\lVert\tilde{x}^{(0)}_{m,\delta}-x^\star_{\mathrm{TS}}(w^\delta_m)\right\rVert\le c_x N^{-3/(M-1)}, \tag*{(28)} m ∈ [ M ] max x ~ m , δ ( 0 ) − x TS ⋆ ( w m δ ) ≤ c x N − 3/ ( M − 1 ) , (28)
for some O ( 1 ) O(1) O ( 1 ) constant c x > 0 c_x>0 c x > 0 . These states are retained or refined without increasing their error, providing corner interpolation data of the same accuracy in objective space at every round. If not supplied, the corner samples require M M M additional initial solves. Subsequent refinements are counted in the inner-solver cost.
Reconstructing the PF Between Sampled Weights
We use the quadratically augmented local RBF interpolation from Section 3, with strictly positive-definite C 4 C^4 C 4 Wendland kernels and a smooth partition of unity [63 ] . Each local model combines an RBF fit with quadratic terms, and the partition of unity blends the overlapping models smoothly. Each local fit uses all mesh vertices within its partition-weight support.
The overlapping patches have diameter Θ ( N − 1 / ( M − 1 ) ) \Theta(N^{-1/(M-1)}) Θ ( N − 1/ ( M − 1 ) ) , bounded overlap, and kernel support radii proportional to their diameters. They are enlarged sufficiently to ensure uniform quadratic unisolvency, including at the boundary of Δ M δ \Delta^\delta_M Δ M δ . This means that the sample locations distinguish quadratic polynomials uniquely and with uniform stability after each patch is rescaled to unit size. The partition weights have derivatives of order j ≤ 3 j\leq3 j ≤ 3 bounded by C N j / ( M − 1 ) CN^{j/(M-1)} C N j / ( M − 1 ) . For κ ϑ \kappa_{\vartheta} κ ϑ -independent reconstruction constants, we additionally require the following bounds to be uniform across the considered preference profiles: after rescaling ϑ \vartheta ϑ so that ∫ Δ M δ ϑ ( P F J ) = 1 \int_{\Delta^\delta_M}\vartheta(\mathrm{PF}_J)=1 ∫ Δ M δ ϑ ( PF J ) = 1 , its C 2 , 1 C^{2,1} C 2 , 1 norm; the chart’s C 2 , 1 C^{2,1} C 2 , 1 norm and positive tangent-rank margin; and the stability of the rescaled local interpolation systems. These conditions hold for a fixed regular reference mesh and a fixed chart with uniformly bounded normalized preference smoothness, but require separate verification for a density-adapted mesh. They do not require a uniform positive lower bound on ϑ \vartheta ϑ .
Under the C 2 , 1 C^{2,1} C 2 , 1 chart regularity of Proposition 2, we define the round-dependent reconstruction factor
C t : = 1 + N 2 / ( M − 1 ) max τ ∈ T ( W ( t ) ) diam ( f P F ( τ ) ) 2 . (29) C_t := 1+N^{2/(M-1)}\max_{\tau\in\mathcal{T}(W(t))}\operatorname{diam}\left(\mathbf{f}_{\mathrm{PF}}(\tau)\right)^2. \tag*{(29)} C t := 1 + N 2/ ( M − 1 ) τ ∈ T ( W ( t )) max diam ( f PF ( τ ) ) 2 . (29)
This factor captures the largest PF-patch diameter relative to the nominal mesh spacing N − 1 / ( M − 1 ) N^{-1/(M-1)} N − 1/ ( M − 1 ) . The mesh and chart regularity bounds ensure that C t C_t C t remains bounded across rounds for each fixed preference, with a bound that may depend on κ ϑ \kappa_{\vartheta} κ ϑ . For capacity MEQ, the density-selected sites and their admissible refinements preserve a regular reconstruction mesh, so C t = O ( 1 ) C_t=O(1) C t = O ( 1 ) across rounds for each fixed regular problem. For adaptive Moser MEQ, a κ ϑ \kappa_{\vartheta} κ ϑ -independent bound after some round follows if max τ ∈ T ( W ( t ) ) diam ( f P F ( τ ) ) ≤ D N − 1 / ( M − 1 ) \max_{\tau\in\mathcal{T}(W(t))}\operatorname{diam}(\mathbf{f}_{\mathrm{PF}}(\tau))\leq D N^{-1/(M-1)} max τ ∈ T ( W ( t )) diam ( f PF ( τ )) ≤ D N − 1/ ( M − 1 ) holds from that round onward with D D D independent of κ ϑ \kappa_{\vartheta} κ ϑ ; then C t ≤ 1 + D 2 C_t\leq1+D^2 C t ≤ 1 + D 2 . This extra PF-diameter bound is not implied by equal cell mass alone. For example, when M = 2 M=2 M = 2 and ϑ ≡ 1 \vartheta\equiv1 ϑ ≡ 1 , exact inverse-CDF MEQ gives equal PF arc length to the transported intervals, so the bound follows from a uniform bound on total PF arc length. For strongly nonuniform preferences, low-preference regions may instead contain large PF intervals.
Lemma 3 (PF reconstruction accuracy). Suppose Assumptions 1 and 2 hold, and the pinned-corner data satisfy the initialization and retention rule in (28). Suppose the current weight mesh is quasi-uniform and shape regular on Δ M δ \Delta_M^\delta Δ M δ and on each relative face, with mesh spacing comparable to N − 1 / ( M − 1 ) N^{-1/(M-1)} N − 1/ ( M − 1 ) . If the adaptive scalarized solutions used to construct P t P_t P t are exact, then, for all sufficiently large N N N , the restriction of P t P_t P t to Δ M δ \Delta_M^\delta Δ M δ satisfies
∥ P t − f P F ∥ C 1 ≤ C C t N − 2 / ( M − 1 ) , ∥ P t − f P F ∥ C 2 ≤ C C t 1 / 2 N − 1 / ( M − 1 ) , ∥ P t ∥ C 2 , 1 ≤ C . (30) \|P_t-f_{\mathrm{PF}}\|_{C^1}\le CC_tN^{-2/(M-1)},\qquad\|P_t-f_{\mathrm{PF}}\|_{C^2}\le CC_t^{1/2}N^{-1/(M-1)},\qquad\|P_t\|_{C^{2,1}}\le C. \tag*{(30)} ∥ P t − f PF ∥ C 1 ≤ C C t N − 2/ ( M − 1 ) , ∥ P t − f PF ∥ C 2 ≤ C C t 1/2 N − 1/ ( M − 1 ) , ∥ P t ∥ C 2 , 1 ≤ C . (30) If the scalarized solutions are inexact, then
∥ P t − f P F ∥ C 1 ≤ C C t N − 2 / ( M − 1 ) + C N 1 / ( M − 1 ) max n ∈ [ N ] ∥ x ~ n ( t ) − x T S ⋆ ( w n ( t ) ) ∥ . (31) \|P_t-f_{\mathrm{PF}}\|_{C^1}\le CC_tN^{-2/(M-1)}+CN^{1/(M-1)}\max_{n\in[N]}\left\|\tilde{x}_n^{(t)}-x_{\mathrm{TS}}^\star(w_n^{(t)})\right\|. \tag*{(31)} ∥ P t − f PF ∥ C 1 ≤ C C t N − 2/ ( M − 1 ) + C N 1/ ( M − 1 ) n ∈ [ N ] max x ~ n ( t ) − x TS ⋆ ( w n ( t ) ) . (31) ∥ P t − f P F ∥ C 2 ≤ C C t 1 / 2 N − 1 / ( M − 1 ) + C N 2 / ( M − 1 ) max n ∈ [ N ] ∥ x ~ n ( t ) − x T S ⋆ ( w n ( t ) ) ∥ . (32) \|P_t-f_{\mathrm{PF}}\|_{C^2}\le CC_t^{1/2}N^{-1/(M-1)}+CN^{2/(M-1)}\max_{n\in[N]}\left\|\tilde{x}_n^{(t)}-x_{\mathrm{TS}}^\star(w_n^{(t)})\right\|. \tag*{(32)} ∥ P t − f PF ∥ C 2 ≤ C C t 1/2 N − 1/ ( M − 1 ) + C N 2/ ( M − 1 ) n ∈ [ N ] max x ~ n ( t ) − x TS ⋆ ( w n ( t ) ) . (32) Moreover, if the maximum decision error is O ( N − 3 / ( M − 1 ) ) O(N^{-3/(M-1)}) O ( N − 3/ ( M − 1 ) ) , then P t P_t P t has a uniform C 2 , 1 C^{2,1} C 2 , 1 bound on Δ M δ \Delta_M^\delta Δ M δ . The fixed chart-corner samples are included in the reconstruction mesh and satisfy (28).
Proof. We first establish uniform interpolation stability. After rescaling, quasi-uniformity gives bounded vertex counts and positive separation, while patch construction ensures quadratic unisolvency, including at the boundary. Strict positive definiteness of the Wendland kernel then yields uniformly bounded inverses, with stability preserved by the partition of unity. Under the stated additional uniformity conditions, these constants are independent of κ ϑ \kappa_\vartheta κ ϑ .
Let h = N − 1 / ( M − 1 ) h=N^{-1/(M-1)} h = N − 1/ ( M − 1 ) . By the bi-Lipschitz property of Proposition 2 and (29), the local interpolation scales are bounded by C C t 1 / 2 h CC_t^{1/2}h C C t 1/2 h . Since f P F f_{\mathrm{PF}} f PF is C 2 , 1 C^{2,1} C 2 , 1 , its quadratic Taylor remainder is cubic in the local patch diameter. Quadratic reproduction and interpolation stability therefore give errors of order C C t h 2 CC_th^2 C C t h 2 in C 1 C^1 C 1 and C C t 1 / 2 h CC_t^{1/2}h C C t 1/2 h in C 2 C^2 C 2 . The cubic remainder also controls the Lipschitz second derivative, yielding a uniform C 2 , 1 C^{2,1} C 2 , 1 bound. The partition of unity preserves these estimates, including on boundary patches by the one-sided chart regularity.
For inexact data, linearity of the interpolation operator implies that nodal perturbations are amplified by at most C h − j Ch^{-j} C h − j in derivatives of order j ≤ 3 j\le3 j ≤ 3 . Since f f f is uniformly Lipschitz near the TS solution path, objective-value errors are bounded by the corresponding decision errors. Adding these perturbations to the exact-data estimates proves (31)–(32). If the maximum adaptive decision error is O ( h 3 ) O(h^3) O ( h 3 ) , the third-order amplification remains bounded, preserving the C 2 , 1 C^{2,1} C 2 , 1 estimate.
Finally, the corner errors in (28) contribute O ( h 2 ) O(h^2) O ( h 2 ) in C 1 C^1 C 1 , O ( h ) O(h) O ( h ) in C 2 C^2 C 2 , and O ( 1 ) O(1) O ( 1 ) in C 2 , 1 C^{2,1} C 2 , 1 , all absorbed into the stated bounds.
The next result transfers chart error to the density used in (10).
Lemma 4 (Preference-density stability). Suppose Assumptions 1–3 hold. If P t P_t P t is sufficiently close to f P F f_{\mathrm{PF}} f PF in C 1 C^1 C 1 , then P t P_t P t has full tangent rank and
∥ ϑ ( P t ) J P t ∫ Δ M δ ϑ ( P t ) J P t − ρ ϑ ∥ ∞ ≤ C ∥ P t − f P F ∥ C 1 , ∥ ϑ ( P t ) J P t ∫ Δ M δ ϑ ( P t ) J P t − ρ ϑ ∥ C 1 ≤ C ∥ P t − f P F ∥ C 2 . (33) \left\|\frac{\vartheta(P_t)J_{P_t}}{\int_{\Delta_M^\delta}\vartheta(P_t)J_{P_t}}-\rho_\vartheta\right\|_\infty\le C\|P_t-f_{\mathrm{PF}}\|_{C^1},\qquad
\left\|\frac{\vartheta(P_t)J_{P_t}}{\int_{\Delta_M^\delta}\vartheta(P_t)J_{P_t}}-\rho_\vartheta\right\|_{C^1}\le C\|P_t-f_{\mathrm{PF}}\|_{C^2}. \tag*{(33)} ∫ Δ M δ ϑ ( P t ) J P t ϑ ( P t ) J P t − ρ ϑ ∞ ≤ C ∥ P t − f PF ∥ C 1 , ∫ Δ M δ ϑ ( P t ) J P t ϑ ( P t ) J P t − ρ ϑ C 1 ≤ C ∥ P t − f PF ∥ C 2 . (33) If P t P_t P t has a uniform C 2 , 1 C^{2,1} C 2 , 1 bound, then the normalized density on the left is strictly positive and has a uniform C 1 , 1 C^{1,1} C 1 , 1 bound.
Proof. Proposition 2 gives a uniform positive lower bound on the tangent singular values of D f P F D f_{\mathrm{PF}} D f PF . A sufficiently small C 1 C^1 C 1 perturbation preserves this bound for D P t D P_t D P t . The Gram-determinant expression in (4) is smooth on the resulting compact full-rank set. Hence
∥ J P t − J ∥ ∞ ≤ C ∥ P t − f P F ∥ C 1 , and ∥ J P t − J ∥ C 1 ≤ C ∥ P t − f P F ∥ C 2 . (34) \|J_{P_t}-J\|_\infty\le C\|P_t-f_{\mathrm{PF}}\|_{C^1},\qquad\text{and}\qquad\|J_{P_t}-J\|_{C^1}\le C\|P_t-f_{\mathrm{PF}}\|_{C^2}. \tag*{(34)} ∥ J P t − J ∥ ∞ ≤ C ∥ P t − f PF ∥ C 1 , and ∥ J P t − J ∥ C 1 ≤ C ∥ P t − f PF ∥ C 2 . (34) Assumption 3 and the chain rule give the corresponding estimates for ϑ ( P t ) − ϑ ( f P F ) \vartheta(P_t)-\vartheta(f_{\mathrm{PF}}) ϑ ( P t ) − ϑ ( f PF ) . The product rule gives the same orders for ϑ ( P t ) J P t − ϑ ( f P F ) J \vartheta(P_t)J_{P_t}-\vartheta(f_{\mathrm{PF}})J ϑ ( P t ) J P t − ϑ ( f PF ) J . For the κ ϑ \kappa_\vartheta κ ϑ -uniform variant, normalize ϑ \vartheta ϑ so that the exact integral equals one. The uniform upper smoothness bounds then make the integrand
perturbation at most C ∥ P t − f P F ∥ C 1 C\lVert P_t-f_{\mathrm{PF}}\rVert_{C^1} C ∥ P t − f PF ∥ C 1 with C C C independent of κ ϑ \kappa_\vartheta κ ϑ . For sufficiently small error, the reconstructed normalizer is at least 1 / 2 1/2 1/2 , so the L ∞ L^\infty L ∞ density-stability constant is also independent of κ ϑ \kappa_\vartheta κ ϑ . For the L ∞ L^\infty L ∞ estimate, the area factor is the norm of an exterior product of chart derivatives and is Lipschitz on bounded sets without a positive lower bound on J J J . For the C 1 C^1 C 1 estimate, a uniform tangent-rank margin additionally controls derivatives of this norm. The final regularity claim follows from the uniform C 2 , 1 C^{2,1} C 2 , 1 bounds. Without the additional uniformity conditions, the original estimates hold with constants depending on the fixed preference and chart bounds.
Combining Lemmas 3 and 4 gives
∥ ϑ ( P t ) J P t Δ M s ϑ ( P t ) J P t − ρ ϑ ∥ ∞ ≤ C C t N − 2 / ( M − 1 ) + C N 1 / ( M − 1 ) max n ∈ [ N ] ∥ x ~ n ( t ) − x T S ∗ ( w n ( t ) ) ∥ . (35) \left\lVert\frac{\vartheta(P_t)J_{P_t}}{\Delta_M^s\vartheta(P_t)J_{P_t}}-\rho_\vartheta\right\rVert_\infty\le CC_tN^{-2/(M-1)}+CN^{1/(M-1)}\max_{n\in[N]}\left\lVert\widetilde{x}_n^{(t)}-x_{\mathrm{TS}}^*(w_n^{(t)})\right\rVert. \tag*{(35)} Δ M s ϑ ( P t ) J P t ϑ ( P t ) J P t − ρ ϑ ∞ ≤ C C t N − 2/ ( M − 1 ) + C N 1/ ( M − 1 ) n ∈ [ N ] max x n ( t ) − x TS ∗ ( w n ( t ) ) . (35)
This is the reconstruction bound stated in Lemma 2. Under the additional uniformity conditions above, the constants C C C in this reconstruction bound are independent of κ ϑ \kappa_\vartheta κ ϑ , while C t C_t C t retains its dependence on the current PF-patch geometry. Decision errors of order N − 3 / ( M − 1 ) N^{-3/(M-1)} N − 3/ ( M − 1 ) contribute at the same N − 2 / ( M − 1 ) N^{-2/(M-1)} N − 2/ ( M − 1 ) scale after differentiation.
Finite MEQ: Mass Accuracy and Mesh Stability
Finite MEQ redistributes the weights for the normalized density ρ \rho ρ in (10). The complete represented cells C ( W ) \mathcal{C}(W) C ( W ) measure target mass, whereas the straight simplicial mesh T ( W ) \mathcal{T}(W) T ( W ) through the returned weights and fixed corners is used for PF reconstruction. We give two finite realizations with the same cell-mass accuracy and reconstruction-mesh guarantees.
Face-Preserving Moser Transport
On the regular reference mesh, locally average ρ \rho ρ over overlapping patches of diameter Θ ( N − 1 / ( 2 ( M − 1 ) ) ) \Theta(N^{-1/(2(M-1))}) Θ ( N − 1/ ( 2 ( M − 1 )) ) . Following Bruveris et al. [12 ] , construct two face-tangent divergence fields: the first transports the uniform density ρ 0 \rho_0 ρ 0 to the local average, and the second transports that average to ρ \rho ρ . For each stage, linearly blend the source and destination densities over time. Dividing the corresponding divergence field by this positive density gives a velocity field. Integrating that velocity moves the weights from the source distribution to the destination distribution. The composition Φ \Phi Φ preserves relative faces and corners and satisfies
ρ ( Φ ( w ) ) det D Φ ( w ) = ρ 0 ( w ) . (36) \rho(\Phi(\mathbf{w}))\det D\Phi(\mathbf{w})=\rho_0(\mathbf{w}). \tag*{(36)} ρ ( Φ ( w )) det D Φ ( w ) = ρ 0 ( w ) . (36)
For M = 2 M=2 M = 2 , this is implemented by inverse-CDF sampling [34 ] .
Proposition 7 (Finite face-preserving Moser realization). Let ρ \rho ρ be a positive normalized C 1 , 1 C^{1,1} C 1 , 1 density with common positive bounds. Suppose it admits a regular component g g g with a common C 1 , 1 C^{1,1} C 1 , 1 bound such that
∥ ρ − g ∥ ∞ + N − 1 / ( M − 1 ) ∥ ρ − g ∥ C 1 + N − 2 / ( M − 1 ) ∥ ρ − g ∥ C 1 , 1 ≤ c N − 1 / ( 2 ( M − 1 ) ) , (37) \lVert\rho-g\rVert_\infty+N^{-1/(M-1)}\lVert\rho-g\rVert_{C^1}+N^{-2/(M-1)}\lVert\rho-g\rVert_{C^{1,1}}\le cN^{-1/(2(M-1))}, \tag*{(37)} ∥ ρ − g ∥ ∞ + N − 1/ ( M − 1 ) ∥ ρ − g ∥ C 1 + N − 2/ ( M − 1 ) ∥ ρ − g ∥ C 1 , 1 ≤ c N − 1/ ( 2 ( M − 1 )) , (37) for sufficiently small c c c . Then the selected Φ \Phi Φ is uniformly bi-Lipschitz, face preserving, and satisfies
N − 1 / ( M − 1 ) Lip ( D Φ ) ≤ C ( N − 1 / ( 2 ( M − 1 ) ) + c ) . (38) N^{-1/(M-1)}\operatorname{Lip}(D\Phi)\le C\left(N^{-1/(2(M-1))}+c\right). \tag*{(38)} N − 1/ ( M − 1 ) Lip ( D Φ ) ≤ C ( N − 1/ ( 2 ( M − 1 )) + c ) . (38) Using the same reference and divergence operators for every input, the selected transport is Lipschitz in the density in the uniform norm, with a constant independent of N N N . A finite realization attains
max τ ∈ C ( W ) ∣ ∫ τ ρ ( w ) d w − 1 ∣ ≤ C N − 2 / ( M − 1 ) . (39) \max_{\tau\in\mathcal{C}(W)}\left|\int_{\tau}\rho(\mathbf{w})\,\mathrm{d}\mathbf{w}-1\right|\le CN^{-2/(M-1)}. \tag*{(39)} τ ∈ C ( W ) max ∫ τ ρ ( w ) d w − 1 ≤ C N − 2/ ( M − 1 ) . (39)
Proof. Cover the simplex by overlapping interior, face, and corner patches of diameter Θ ( N − 1 / ( 2 ( M − 1 ) ) ) \Theta(N^{-1/(2(M-1))}) Θ ( N − 1/ ( 2 ( M − 1 )) ) , with bounded overlap and smooth partition weights. Subtracting patch averages before differentiation shows that local averaging preserves positive bounds and normalization, has bounded C 1 C^1 C 1 norm, and has C 1 , 1 C^{1,1} C 1 , 1 norm O ( N 1 / ( 2 ( M − 1 ) ) ) O(N^{1/(2(M-1))}) O ( N 1/ ( 2 ( M − 1 )) ) under (37). Apply a fixed face-tangent divergence operator ([12 ] ) to the difference between ρ 0 \rho_0 ρ 0 and the local average. Its coordinate integrals and cutoffs give bounded C 1 C^1 C 1 velocity after division by the positive interpolated density. The velocity’s C 1 , 1 C^{1,1} C 1 , 1 norm is O ( N 1 / ( 2 ( M − 1 ) ) ) O(N^{1/(2(M-1))}) O ( N 1/ ( 2 ( M − 1 )) ) . The second flow corrects the averaging difference. This difference decomposes into patch-supported zero-integral terms. Rescaling the same divergence formulas and extending by zero gives a globally face-tangent correction field. The rescaled estimates and (37) bound its first derivative and mesh-scaled derivative variation by C ( N − 1 / ( 2 ( M − 1 ) ) + c ) C(N^{-1/(2(M-1))}+c) C ( N − 1/ ( 2 ( M − 1 )) + c ) . The denominators in both flows remain positive. The variational equations and Gronwall’s inequality yield uniform bi-Lipschitz bounds and (38) . Face tangency preserves relative faces and corners, and mass conservation proves (36) . For two input densities, local averaging is nonexpansive in the uniform norm, and the local divergence correction has uniform operator norm O ( N − 1 / ( 2 ( M − 1 ) ) ) O(N^{-1/(2(M-1))}) O ( N − 1/ ( 2 ( M − 1 )) ) in that norm. The two Moser velocities consequently differ by at most C C C times the uniform density difference. Their common spatial Lipschitz bounds and Gronwall’s inequality give the claimed stability of the selected transports.
Approximate the fixed local divergence fields and integrate both flows with face-preserving quadrature and time steps. Refine until the map-value error is O ( α N − 2 / ( M − 1 ) ) O(\alpha N^{-2/(M-1)}) O ( α N − 2/ ( M − 1 ) ) , the derivative error is O ( N − 2 / ( M − 1 ) ) O(N^{-2/(M-1)}) O ( N − 2/ ( M − 1 ) ) , and the defect in (36) is O ( N − 2 / ( M − 1 ) ) O(N^{-2/(M-1)}) O ( N − 2/ ( M − 1 ) ) . These tolerances are attainable by convergence of the numerical fields and flows for each fixed N N N . Integrating over each equal-volume reference cell, of volume Θ ( N − 1 ) \Theta(N^{-1}) Θ ( N − 1 ) , gives (39) . Independent cell quadrature to absolute accuracy O ( N − 1 − 2 / ( M − 1 ) ) O(N^{-1-2/(M-1)}) O ( N − 1 − 2/ ( M − 1 ) ) certifies the estimate.
Lemma 5 (Moser mesh stability). Under Proposition 7, the straight mesh T ( W ) \mathcal{T}(W) T ( W ) is quasi-uniform and shape regular at scale N − 1 / ( M − 1 ) N^{-1/(M-1)} N − 1/ ( M − 1 ) on Δ M δ \Delta^\delta_M Δ M δ and every relative face, uniformly over the rounds.
Proof. The piecewise-affine interpolation of Φ \Phi Φ has derivative error at most C N − 1 / ( M − 1 ) Lip ( D Φ ) CN^{-1/(M-1)}\operatorname{Lip}(D\Phi) C N − 1/ ( M − 1 ) Lip ( D Φ ) , while finite nodal errors add O ( α N − 1 / ( M − 1 ) ) O(\alpha N^{-1/(M-1)}) O ( α N − 1/ ( M − 1 ) ) . The bi-Lipschitz bound for the exact transport gives a positive lower bound on the ratio of transported distance to original distance. By (38) , choose c c c sufficiently small and then N N N sufficiently large so that the total interpolation error is smaller than half this lower bound. The required resolution depends on the density and transport bounds. The interpolant is thus globally bi-Lipschitz. Face preservation and degree one ensure full coverage without overlapping straight simplices. The resulting singular-value bounds prove shape regularity and quasi-uniformity, including on relative faces. Their constants may depend on the transport’s density bounds, and hence on κ ϑ \kappa_\vartheta κ ϑ .
Equal-Capacity Minimization
Alternatively, equal-capacity MEQ directly partitions Δ M δ \Delta^\delta_M Δ M δ into cells of equal ρ \rho ρ -mass, using the density in (10) . Here the sites are the scalarization weights. A positive smooth selection density determines where they are placed. Select their coordinates successively by inverting the conditional CDF of each coordinate given the preceding coordinates. Retain the reference mesh connectivity and fixed corners. For exact solves, the input density itself has the required regularity. For inexact solves, apply a fixed, positive, smooth averaging rule to obtain the site-selection density. Evaluate the cell capacities against the original ρ \rho ρ . Both choices give uniformly bi-Lipschitz, face-preserving sites, and the fixed averaging rule is Lipschitz in the input density in the uniform norm. Identify Δ M δ \Delta^\delta_M Δ M δ affinely with the standard simplex and use barycentric stick-breaking coordinates z i = w i / ( 1 − ∑ j < i w j ) z_i=w_i/(1-\sum_{j<i}w_j) z i = w i / ( 1 − ∑ j < i w j ) . The uniform measure has beta-type conditional densities, which are C 1 C^1 C 1 -regular but have derivatives bounded by bounded positive factors. Successive conditional-CDF matching fixes z i = 0 , 1 z_i=0,1 z i = 0 , 1 , preserving each face and corner. The conditional-quantile identities and common density bounds control the derivatives of the map and its inverse, including face limits, and its stability under uniform density perturbations. Standard piecewise-affine interpolation then preserves the regularity of the selected mesh for sufficiently large N N N . The density-selected sites may be refined by minimizing the equal-capacity transport cost over W W W alone:
min W ∑ n = 1 N ∫ τ n ( W ) ∥ w − w n ∥ 2 ρ ( w ) d w (40) \min_W \sum_{n=1}^{N}\int_{\tau_n(W)} \lVert w-w_n\rVert^2 \rho(w)\,\mathrm{d}w \tag*{(40)} W min n = 1 ∑ N ∫ τ n ( W ) ∥ w − w n ∥ 2 ρ ( w ) d w (40)
subject to each site remaining on its original relative face and within an O ( α N − 2 / ( M − 1 ) ) O(\alpha N^{-2/(M-1)}) O ( α N − 2/ ( M − 1 ) ) perturbation of its selected position. For every admissible collection of distinct sites W W W , the cells τ n ( W ) \tau_n(W) τ n ( W ) are the capacity-balanced power cells
τ n ( W ) = { w ∈ Δ M δ : ∥ w − w n ∥ 2 − λ n ≤ ∥ w − w j ∥ 2 − λ j , ∀ j } , (41) \tau_n(W)=\left\{w\in\Delta_M^\delta:\lVert w-w_n\rVert^2-\lambda_n\le\lVert w-w_j\rVert^2-\lambda_j,\ \forall j\right\}, \tag*{(41)} τ n ( W ) = { w ∈ Δ M δ : ∥ w − w n ∥ 2 − λ n ≤ ∥ w − w j ∥ 2 − λ j , ∀ j } , (41)
whose offsets maximize
1 N ∑ n = 1 N λ n + ∫ Δ M δ min n { ∥ w − w n ∥ 2 − λ n } ρ ( w ) d w . (42) \frac{1}{N}\sum_{n=1}^{N}\lambda_n+\int_{\Delta_M^\delta}\min_n\left\{\lVert w-w_n\rVert^2-\lambda_n\right\}\rho(w)\,\mathrm{d}w. \tag*{(42)} N 1 n = 1 ∑ N λ n + ∫ Δ M δ n min { ∥ w − w n ∥ 2 − λ n } ρ ( w ) d w . (42)
The maximizing offsets in (42) enforce ∫ τ n ( W ) ρ ( w ) d w = 1 / N \int_{\tau_n(W)}\rho(w)\,\mathrm{d}w=1/N ∫ τ n ( W ) ρ ( w ) d w = 1/ N . Thus, the cells are determined by W W W and ρ \rho ρ , and the objective in (40) optimizes the returned scalarization sites. Here C ( W ) C(W) C ( W ) comprises these complete power cells, while T ( W ) T(W) T ( W ) retains the reference connectivity through the returned sites and pinned corners.
Proposition 8 (Finite equal-capacity realization). For the positive normalized densities generated under Assumptions 1–3, select the density-dependent sites above and optimize the offsets in (42) . This gives a finite capacity-balanced realization satisfying (39) . The selected sites, as well as any minimizer of (40) within the prescribed displacement bounds, define a quasi-uniform, shape-regular reconstruction mesh T ( W ) T(W) T ( W ) for sufficiently large N N N , including on relative faces.
Proof. Fix the density-selected noncorner sites and the pinned corners. The smooth, uniformly bi-Lipschitz selection map and sufficiently fine reference triangulation give a quasi-uniform, shape-regular straight mesh, including on relative faces, with distinct sites. For these fixed sites, the concave dual (42) attains its maximum modulo a common offset: positivity of ρ \rho ρ and the prescribed positive masses prevent an optimizing sequence of normalized offsets from diverging. Its derivative with respect to λ n \lambda_n λ n is 1 / N − ∫ τ n ( W ) ρ 1/N-\int_{\tau_n(W)}\rho 1/ N − ∫ τ n ( W ) ρ , because power-cell interfaces have zero volume. Hence all complete power cells have mass 1 / N 1/N 1/ N at a maximizer. Finite dual optimization and quadrature to absolute mass accuracy O ( N − 1 − 2 / ( M − 1 ) ) O(N^{-1-2/(M-1)}) O ( N − 1 − 2/ ( M − 1 ) ) per cell yield (39) . The selected sites themselves satisfy the displacement constraints in (40) . The admissible site set is compact and preserves separation for sufficiently large N N N , so the continuous reduced objective attains a minimum. The allowed O ( α N − 2 / ( M − 1 ) ) O(\alpha N^{-2/(M-1)}) O ( α N − 2/ ( M − 1 ) ) nodal perturbations change the affine element derivatives by O ( α N − 1 / ( M − 1 ) ) O(\alpha N^{-1/(M-1)}) O ( α N − 1/ ( M − 1 ) ) , preserving the selected mesh regularity. Site positions vary with the selection density, while dual offsets enforce capacities for each selected or refined W W W . □
For each selected or refined W W W , optimizing the power-cell offsets balances cell masses without moving the sites; redistribution of W W W comes from density-dependent selection and optional constrained site refinement.
Lemma 6 (Round-to-round admissibility). Under Assumptions 1–3, both MEQ realizations preserve a regular reconstruction mesh and positive, uniformly C 1 , 1 C^{1,1} C 1 , 1 densities at every exact-solve round.
Proof. The uniform initial density and regular reference mesh start a joint induction. Fix the positive density and mesh regularity bounds, with slack around the convex segment joining ρ 0 \rho_0 ρ 0 and ρ ϑ \rho_\vartheta ρ ϑ , before choosing the reconstruction accuracy and N N N . For a regular current mesh, Lemmas 3 and 4 give full tangent rank, a uniformly C 2 , 1 C^{2,1} C 2 , 1 reconstructed chart, and a positive normalized reconstructed density with uniform C 1 , 1 C^{1,1} C 1 , 1 bounds for exact solves. Damping in (10) preserves these bounds. Proposition 7 with q = ρ t + 1 q=\rho_{t+1} q = ρ t + 1 and Lemma 5 give the next Moser mesh. For the capacity realization, the density-selected sites and their admissible refinements provide the next regular reconstruction mesh. The fresh-density C 1 C^1 C 1 error is O ( N − 1 / ( M − 1 ) ) O(N^{-1/(M-1)}) O ( N − 1/ ( M − 1 ) ) by Lemmas 3 and 4. Unrolling the damped update keeps ρ t + 1 \rho_{t+1} ρ t + 1 within the fixed density class, while the preceding mesh bounds keep the next mesh in its fixed regularity class. This closes the exact-solve induction. For the capacity realization, the selected-site mesh remains regular under the stated displacement restriction, so N N N must exceed the interpolation, site-selection mesh, and tangent-rank thresholds. These thresholds depend on the chart and reference regularity. Theorem 1 requires N N N to exceed these fixed-problem thresholds, including the Moser mesh-stability threshold in Lemma 5. For inexact solves, the joint density–mesh–solver induction is proved in Lemma 7. The capacity realization uses the regularity of the site-selection map and the positive density bounds for its power-cell dual, whereas the Moser step uses its scale-dependent condition. □
Proof of Proposition 3. Lemma 6 supplies the admissible densities and meshes at each round. Proposition 7 and Lemma 5 establish the finite Moser realization. Proposition 8 establishes the capacity realization with the same mass accuracy and mesh guarantees.
Proposition 9 (Target-mass error after MEQ). For either realization, let ρ \rho ρ be the normalized density passed to MEQ and W W W its returned weights and fixed corners. Then
R ^ ϑ ( W ) ≤ C ∥ ρ − ρ ϑ ∥ ∞ + C N − 2 / ( M − 1 ) . (43) \widehat{R}_{\vartheta}(W) \le C\lVert\rho-\rho_{\vartheta}\rVert_{\infty}+CN^{-2/(M-1)}. \tag*{(43)} R ϑ ( W ) ≤ C ∥ ρ − ρ ϑ ∥ ∞ + C N − 2/ ( M − 1 ) . (43)
Proof. By (39), each represented cell τ \tau τ has ρ \rho ρ -mass at most [ 1 + C N − 2 / ( M − 1 ) ] / ∣ C ( W ) ∣ [1+CN^{-2/(M-1)}]/|\mathcal{C}(W)| [ 1 + C N − 2/ ( M − 1 ) ] /∣ C ( W ) ∣ . The positive lower bound on ρ \rho ρ therefore gives ∣ C ( W ) ∣ Vol M − 1 ( τ ) ≤ C |\mathcal{C}(W)|\operatorname{Vol}_{M-1}(\tau)\le C ∣ C ( W ) ∣ Vol M − 1 ( τ ) ≤ C . Consequently,
∣ C ( W ) ∣ ∣ ∫ τ ( ρ ϑ ( w ) − ρ ( w ) ) d w ∣ ≤ C ∥ ρ − ρ ϑ ∥ ∞ . (44) |\mathcal{C}(W)|\left|\int_{\tau}(\rho_{\vartheta}(\mathbf{w})-\rho(\mathbf{w}))\,\mathrm{d}\mathbf{w}\right|\le C\lVert\rho-\rho_{\vartheta}\rVert_{\infty}. \tag*{(44)} ∣ C ( W ) ∣ ∫ τ ( ρ ϑ ( w ) − ρ ( w )) d w ≤ C ∥ ρ − ρ ϑ ∥ ∞ . (44)
Adding the finite cell-mass error proves (43). The mass-residual constant may depend on the positive lower bound on ρ \rho ρ .
For moving-weight Moser MEQ, the complete transported cells and the corresponding straight reconstruction simplices have comparable diameters by Lemma 5. The definition of R ^ ϑ \widehat{R}_{\vartheta} R ϑ bounds the preference-weighted PF area of each cell by ( 1 + R ^ ϑ ) / ∣ C ( W ( t ) ) ∣ (1+\widehat{R}_{\vartheta})/|\mathcal{C}(W(t))| ( 1 + R ϑ ) /∣ C ( W ( t )) ∣ times the total preference mass. Positivity of ϑ \vartheta ϑ and the transported-cell shape regularity convert this area bound into a PF-diameter bound. Since ∣ C ( W ( t ) ) ∣ = Θ ( N ) |\mathcal{C}(W(t))|=\Theta(N) ∣ C ( W ( t )) ∣ = Θ ( N ) , (29) yields
C t = O ( 1 + ( 1 + R ^ ϑ ( W ( t ) ) ) 2 / ( M − 1 ) ) . (45) C_t=O\left(1+\left(1+\widehat{R}_{\vartheta}(W^{(t)})\right)^{2/(M-1)}\right). \tag*{(45)} C t = O ( 1 + ( 1 + R ϑ ( W ( t ) ) ) 2/ ( M − 1 ) ) . (45)
For capacity MEQ, the density-selected mesh likewise gives a round-uniform bound on C t C_t C t .
Proofs for the Convergence Analysis
The reconstruction and MEQ bounds now give the convergence results in Section 4. With exact scalarized solves, the density update contracts toward the target up to reconstruction error. With inexact solves, we track solver error together with density error and show that the required density and mesh bounds hold at every round. Throughout, N N N is taken large enough to meet the reconstruction and mesh-stability thresholds above, which may depend on the fixed regularity parameters, e.g., κ ϑ \kappa_{\vartheta} κ ϑ .
Exact Scalarized Solves
Theorem 2 (Exact-solve convergence of SURFACE). Suppose Assumptions 1–3 hold, take N N N sufficiently large for the reconstruction and MEQ stability conditions in Appendix C.2, and suppose all scalarized solutions used to construct P t P_t P t are exact. Use the finite MEQ construction and numerical accuracy targets in Appendix C.2. Then, at every outer round from initialization through the last returned round of Algorithm 1,
∥ ρ t − ρ ϑ ∥ ∞ ≤ ( 1 − α ) t ∥ ρ 0 − ρ ϑ ∥ ∞ + C α N − 2 / ( M − 1 ) ∑ j = 0 t − 1 ( 1 − α ) t − 1 − j C j \lVert\rho_t-\rho_{\vartheta}\rVert_{\infty}\le(1-\alpha)^t\lVert\rho_0-\rho_{\vartheta}\rVert_{\infty}+C\alpha N^{-2/(M-1)}\sum_{j=0}^{t-1}(1-\alpha)^{t-1-j}C_j ∥ ρ t − ρ ϑ ∥ ∞ ≤ ( 1 − α ) t ∥ ρ 0 − ρ ϑ ∥ ∞ + C α N − 2/ ( M − 1 ) j = 0 ∑ t − 1 ( 1 − α ) t − 1 − j C j ≤ ( 1 − α ) t ∥ ρ 0 − ρ ϑ ∥ ∞ + C N − 2 / ( M − 1 ) . (46) \le(1-\alpha)^t\lVert\rho_0-\rho_{\vartheta}\rVert_{\infty}+CN^{-2/(M-1)}. \tag*{(46)} ≤ ( 1 − α ) t ∥ ρ 0 − ρ ϑ ∥ ∞ + C N − 2/ ( M − 1 ) . (46) Moreover, there is
R ^ ϑ ( W ( t ) ) ≤ C ( 1 − α ) t ∥ ρ 0 − ρ ϑ ∥ ∞ + C N − 2 / ( M − 1 ) , (47) \widehat{R}_{\vartheta}(W^{(t)})\le C(1-\alpha)^t\lVert\rho_0-\rho_{\vartheta}\rVert_{\infty}+CN^{-2/(M-1)}, \tag*{(47)} R ϑ ( W ( t ) ) ≤ C ( 1 − α ) t ∥ ρ 0 − ρ ϑ ∥ ∞ + C N − 2/ ( M − 1 ) , (47) ∥ P t − f P F ∥ C 1 ≤ C C t N − 2 / ( M − 1 ) . (48) \lVert P_t-f_{\mathrm{PF}}\rVert_{C^1}\le CC_tN^{-2/(M-1)}. \tag*{(48)} ∥ P t − f PF ∥ C 1 ≤ C C t N − 2/ ( M − 1 ) . (48)
Proof. Lemma 6 shows that all exact rounds remain in the regular reconstruction and MEQ regime.
Lemmas 3 and 4 give
∥ ϑ ( P t ) J P t ∣ Δ M δ ϑ ( P t ) J P t ∣ − ρ ϑ ∥ ∞ ≤ C C t N − 2 / ( M − 1 ) . \left\lVert\frac{\vartheta(P_t)J_{P_t}}{\left|\Delta_M^{\delta}\vartheta(P_t)J_{P_t}\right|}-\rho_{\vartheta}\right\rVert_{\infty}\le CC_tN^{-2/(M-1)}. Δ M δ ϑ ( P t ) J P t ϑ ( P t ) J P t − ρ ϑ ∞ ≤ C C t N − 2/ ( M − 1 ) .
Using (10),
∥ ρ t + 1 − ρ ϑ ∥ ∞ ≤ ( 1 − α ) ∥ ρ t − ρ ϑ ∥ ∞ + C α C t N − 2 / ( M − 1 ) . (49) \lVert\rho_{t+1}-\rho_{\vartheta}\rVert_{\infty}\le(1-\alpha)\lVert\rho_t-\rho_{\vartheta}\rVert_{\infty}+C\alpha C_tN^{-2/(M-1)}. \tag*{(49)} ∥ ρ t + 1 − ρ ϑ ∥ ∞ ≤ ( 1 − α ) ∥ ρ t − ρ ϑ ∥ ∞ + C α C t N − 2/ ( M − 1 ) . (49)
Iterating this recursion gives the first inequality in (46) . Lemma 6 gives C j ≤ C C_j \le C C j ≤ C , so the geometrically weighted sum is uniformly bounded and yields the second inequality.
The sum in (46) shows how early reconstruction errors affect later rounds. An initially large C j C_j C j receives a geometrically decreasing weight, while (45) bounds subsequent coefficients for each fixed preference. Under the additional PF-diameter condition following (29) , later C j C_j C j have a κ ϑ \kappa_\vartheta κ ϑ -independent bound; otherwise a dependence through the mesh may remain. Equation (48) follows from Lemma 3, and Proposition 9 combined with (46) gives (47) .
Inexact Scalarized Solves
Following the finite-step inner-solver analysis of SURF [34 ] , we characterize the work of InnerSolverK _K K by its contraction factor η K \eta_K η K . When the solve at round t + 1 t+1 t + 1 is warm-started from the returned state at round t t t , we assume
∥ x ~ n ( t + 1 ) − x T S ∗ ( w n ( t + 1 ) ) ∥ ≤ η K ∥ x ~ n ( t ) − x T S ∗ ( w n ( t + 1 ) ) ∥ , n ∈ [ N ] . (50) \left\lVert\widetilde{x}_n^{(t+1)}-x_{\mathrm{TS}}^*\left(w_n^{(t+1)}\right)\right\rVert\le\eta_K\left\lVert\widetilde{x}_n^{(t)}-x_{\mathrm{TS}}^*\left(w_n^{(t+1)}\right)\right\rVert,\qquad n\in[N]. \tag*{(50)} x n ( t + 1 ) − x TS ∗ ( w n ( t + 1 ) ) ≤ η K x n ( t ) − x TS ∗ ( w n ( t + 1 ) ) , n ∈ [ N ] . (50)
The factor η K \eta_K η K measures how much K K K inner steps reduce decision error at a fixed weight. We require (50) at every warm start encountered by SURFACE. For linearly convergent methods, η K \eta_K η K decreases geometrically with K K K . Sublinear methods fit this analysis when their guarantee yields the same multiplicative decision-error bound. Projected gradient provides one example in the hidden strongly convex weighted-sum setting [34 ] . For TS, the local strong regularity and quadratic growth in Assumption 1 support locally contractive methods when the initialization lies in their convergence neighborhood [9 ] .
Damping limits how far the weights move between rounds and therefore how much the exact scalarized solutions change. Reconstruction then converts errors in the returned solutions into errors in the estimated density. By Lemma 3, one, two, and three inverse powers of mesh spacing amplify sample error in C 1 C^1 C 1 , C 2 C^2 C 2 , and C 2 , 1 C^{2,1} C 2 , 1 , respectively. We choose the solver accuracy to keep the C 1 C^1 C 1 error small enough to preserve tangent rank and the accumulated density error small enough for the two-stage transport. The initial solves satisfy
max n ∈ [ N ] ∥ x ~ n ( 0 ) − x T S ∗ ( w n ( 0 ) ) ∥ ≤ C x N − 3 / ( M − 1 ) , (51) \max_{n\in[N]}\left\lVert\widetilde{x}_n^{(0)}-x_{\mathrm{TS}}^*\left(w_n^{(0)}\right)\right\rVert\le C_xN^{-3/(M-1)}, \tag*{(51)} n ∈ [ N ] max x n ( 0 ) − x TS ∗ ( w n ( 0 ) ) ≤ C x N − 3/ ( M − 1 ) , (51)
and we choose the inner budget so that
η K = O ( min { ( 1 + α N 1 / ( M − 1 ) ) − 1 , α − 2 N − 3 / ( M − 1 ) } ) . (52) \eta_K=O\left(\min\left\{\left(1+\alpha N^{1/(M-1)}\right)^{-1},\ \alpha^{-2}N^{-3/(M-1)}\right\}\right). \tag*{(52)} η K = O ( min { ( 1 + α N 1/ ( M − 1 ) ) − 1 , α − 2 N − 3/ ( M − 1 ) } ) . (52)
Here C x > 0 C_x>0 C x > 0 is any fixed constant, independent of N N N , T T T , and α \alpha α . Choose K K K to meet the fixed transport and contraction bounds below. In particular, α ˉ 2 η K = O ( N − 3 / ( M − 1 ) ) \bar{\alpha}^{2}\eta_K=O(N^{-3/(M-1)}) α ˉ 2 η K = O ( N − 3/ ( M − 1 ) ) with an admissible constant implies (52) when α ˉ = Ω ( N − 3 / ( 2 ( M − 1 ) ) ) \bar{\alpha}=\Omega(N^{-3/(2(M-1))}) α ˉ = Ω ( N − 3/ ( 2 ( M − 1 )) ) . Exact solves correspond to η K = 0 \eta_K=0 η K = 0 .
The next lemma shows that this initialization and inner budget keep the solver error, density bounds, and mesh regularity under control at every round.
Lemma 7 (Invariant inexact trajectory). Suppose Assumptions 1–3 hold, 0 < α ≤ α ˉ ≤ 1 0<\alpha\le\bar{\alpha}\le1 0 < α ≤ α ˉ ≤ 1 with α ˉ = Ω ( N − 3 / ( 2 ( M − 1 ) ) ) \bar{\alpha}=\Omega(N^{-3/(2(M-1))}) α ˉ = Ω ( N − 3/ ( 2 ( M − 1 )) ) , and (51) –(52) hold. Initialize and retain or refine the pinned-corner data as in (28) . Use the moving-weight Moser realization and numerical targets in Appendix § 12 .§ 2 . For every fixed C x C_x C x , choose the constants in the inner-solver and numerical MEQ accuracy bounds independently of N N N , T T T , and α \alpha α . Then, for all sufficiently large N N N and every outer round of Algorithm 1,
max n ∈ [ N ] ∥ x ~ n ( t ) − x T S ∗ ( w n ( t ) ) ∥ ≤ C ∗ min { N − 1 / ( M − 1 ) , α − 1 N − 3 / ( M − 1 ) } , C t ≤ C . (53) \max_{n\in[N]}\left\lVert\widetilde{x}_n^{(t)}-x_{\mathrm{TS}}^*\left(w_n^{(t)}\right)\right\rVert\le C_*\min\left\{N^{-1/(M-1)},\ \alpha^{-1}N^{-3/(M-1)}\right\},\qquad C_t\le C. \tag*{(53)} n ∈ [ N ] max x n ( t ) − x TS ∗ ( w n ( t ) ) ≤ C ∗ min { N − 1/ ( M − 1 ) , α − 1 N − 3/ ( M − 1 ) } , C t ≤ C . (53) Moreover, P t P_t P t has full tangent rank, ρ t \rho_t ρ t has common positive lower and upper bounds and satisfies the scale-dependent condition in Proposition 7, and W ( t ) W^{(t)} W ( t ) satisfies Lemma 5.
Proof. Write h = N − 1 / ( M − 1 ) h=N^{-1/(M-1)} h = N − 1/ ( M − 1 ) and let e t e_t e t denote the maximum adaptive decision error at round t t t . Fix the density and mesh bounds as in Lemma 6. Take N N N sufficiently large for the fixed initialization constant C x C_x C x and choose K K K and numerical MEQ tolerances to meet the transport and contraction estimates. At each round, compare the actual chart with the reconstruction from exact objective values at the same adaptive weights, retaining the current pinned-corner data. Starting at ρ 0 = ρ 0 \rho_0=\rho_0 ρ 0 = ρ 0 , apply the damped update to these comparison charts to define g t g_t g t . Lemmas 3 and 4 give the fresh comparison densities a common C 1 , 1 C^{1,1} C 1 , 1 bound and O ( h ) O(h) O ( h ) proximity to ρ ϑ \rho_\vartheta ρ ϑ in C 1 C^1 C 1 . Hence g t g_t g t remains in the fixed regular class.
We jointly maintain the stated decision-error invariant and e t ≤ q t e 0 + C η K α e_t \le q^t e_0 + C\eta_K\alpha e t ≤ q t e 0 + C η K α for a fixed q < 1 / 2 q < 1/2 q < 1/2 . Both hold initially, with ρ 0 = g 0 \rho_0 = g_0 ρ 0 = g 0 and the regular reference mesh. Suppose they hold through round t t t . Reconstruction gives
∥ P t − f P F ∥ C 1 ≤ C h 2 + C e t / h , and , ∥ P t ∥ C 2 , 1 ≤ C ( 1 + e t / h 3 ) . (54) \lVert P_t-f_{\mathrm{PF}}\rVert_{C^1} \le Ch^2+Ce_t/h,\qquad\text{and},\qquad\lVert P_t\rVert_{C^{2,1}} \le C(1+e_t/h^3). \tag*{(54)} ∥ P t − f PF ∥ C 1 ≤ C h 2 + C e t / h , and , ∥ P t ∥ C 2 , 1 ≤ C ( 1 + e t / h 3 ) . (54)
Since e t ≤ 2 − t C x h 3 + C η K α e_t \le2^{-t}C_xh^3+C\eta_K\alpha e t ≤ 2 − t C x h 3 + C η K α and (52) gives η K α / h ≤ C min { α / h , h 2 / α } ≤ C h 1 / 2 \eta_K\alpha/h \le C\min\{\alpha/h,h^2/\alpha\}\le Ch^{1/2} η K α / h ≤ C min { α / h , h 2 / α } ≤ C h 1/2 , we have e t / h = O ( h 1 / 2 ) e_t/h=O(h^{1/2}) e t / h = O ( h 1/2 ) . Thus, the reconstructed density retains full tangent rank and positive bounds for all sufficiently large N N N , for any fixed C x C_x C x .
The scaled interpolation estimates and the chain and product rules bound the difference between actual and comparison densities by C e t / h Ce_t/h C e t / h , C e t / h 2 Ce_t/h^2 C e t / h 2 , and C e t / h 3 Ce_t/h^3 C e t / h 3 in C 0 C^0 C 0 , C 1 C^1 C 1 , and C 1 , 1 C^{1,1} C 1 , 1 , respectively. The quadratic second-derivative term is absorbed using e t 2 / h 4 ≤ C ∗ e t / h 3 e_t^2/h^4\le C_*e_t/h^3 e t 2 / h 4 ≤ C ∗ e t / h 3 . Unrolling gives
∥ ρ t + 1 − g t + 1 ∥ ∞ + h ∥ ρ t + 1 − g t + 1 ∥ C 1 + h 2 ∥ ρ t + 1 − g t + 1 ∥ C 1 , 1 ≤ C α h ∑ s = 0 t ( 1 − α ) t − s e s ≤ C h ( α e 0 + η K α ) = O ( h ) . (55) \lVert\rho_{t+1}-g_{t+1}\rVert_\infty+h\lVert\rho_{t+1}-g_{t+1}\rVert_{C^1}+h^2\lVert\rho_{t+1}-g_{t+1}\rVert_{C^{1,1}}
\le\frac{C\alpha}{h}\sum_{s=0}^{t}(1-\alpha)^{t-s}e_s\le\frac{C}{h}(\alpha e_0+\eta_K\alpha)=O(\sqrt{h}). \tag*{(55)} ∥ ρ t + 1 − g t + 1 ∥ ∞ + h ∥ ρ t + 1 − g t + 1 ∥ C 1 + h 2 ∥ ρ t + 1 − g t + 1 ∥ C 1 , 1 ≤ h C α s = 0 ∑ t ( 1 − α ) t − s e s ≤ h C ( α e 0 + η K α ) = O ( h ) . (55)
Here α e 0 ≤ C x h 3 \alpha e_0\le C_xh^3 α e 0 ≤ C x h 3 and η K α ≤ C h 3 / 2 \eta_K\alpha\le Ch^{3/2} η K α ≤ C h 3/2 follow from (51)–(52). The initialization contributes O ( C x h 2 ) O(C_xh^2) O ( C x h 2 ) to the scaled density error, which is o ( h 1 / 2 ) o(h^{1/2}) o ( h 1/2 ) . The fixed inner-solver accuracy is chosen to meet (37), with regular component g t + 1 g_{t+1} g t + 1 .
Proposition 7 and Lemma 5 therefore give the moving next mesh in the fixed mesh class, so C t + 1 ≤ C C_{t+1}\le C C t + 1 ≤ C . Damping preserves the positive lower and upper bounds of the reconstructed densities. Retain the same reference vertices, cover, and divergence operators at every round. The stability of the selected exact Moser map and the O ( α h 2 ) O(\alpha h^2) O ( α h 2 ) numerical map-value tolerance give
max n ∈ [ N ] ∥ w n ( t + 1 ) − w n ( t ) ∥ ≤ C ∥ ρ t + 1 − ρ t ∥ ∞ + C α h 2 . (56) \max_{n\in[N]}\lVert w_n^{(t+1)}-w_n^{(t)}\rVert\le C\lVert\rho_{t+1}-\rho_t\rVert_\infty+C\alpha h^2. \tag*{(56)} n ∈ [ N ] max ∥ w n ( t + 1 ) − w n ( t ) ∥ ≤ C ∥ ρ t + 1 − ρ t ∥ ∞ + C α h 2 . (56)
The density update and reconstruction bound give
∥ ρ t + 1 − ρ t ∥ ∞ ≤ C α ( ∥ ρ t − ρ ϑ ∥ ∞ + C t h 2 + e t / h ) . (57) \lVert\rho_{t+1}-\rho_t\rVert_\infty\le C\alpha\left(\lVert\rho_t-\rho_\vartheta\rVert_\infty+C_th^2+e_t/h\right). \tag*{(57)} ∥ ρ t + 1 − ρ t ∥ ∞ ≤ C α ( ∥ ρ t − ρ ϑ ∥ ∞ + C t h 2 + e t / h ) . (57)
By the uniform density bounds, Lipschitz sensitivity of x T S ∗ x_{\mathrm{TS}}^* x TS ∗ , and the warm-start contraction (50),
e t + 1 ≤ η K [ ( 1 + C α / h ) e t + C α + C α C t h 2 ] ≤ q e t + C η K α . (58) e_{t+1}\le\eta_K\left[(1+C\alpha/h)e_t+C\alpha+C\alpha C_th^2\right]\le qe_t+C\eta_K\alpha. \tag*{(58)} e t + 1 ≤ η K [ ( 1 + C α / h ) e t + C α + C α C t h 2 ] ≤ q e t + C η K α . (58)
Choose the fixed inner-solver accuracy in (52) so that q ≤ 1 / 2 q\le1/2 q ≤ 1/2 . Then e t ≤ 2 − t e 0 + C η K α e_t\le2^{-t}e_0+C\eta_K\alpha e t ≤ 2 − t e 0 + C η K α . If α ≤ h 2 \alpha\le h^2 α ≤ h 2 , then η K α = O ( h ) \eta_K\alpha=O(h) η K α = O ( h ) ; otherwise the second condition gives η K α = O ( h 3 / α ) \eta_K\alpha=O(h^3/\alpha) η K α = O ( h 3 / α ) . Therefore e t ≤ C ∗ min { h , α − 1 h 3 } e_t\le C_*\min\{h,\alpha^{-1}h^3\} e t ≤ C ∗ min { h , α − 1 h 3 } for a fixed C ∗ C_* C ∗ , closing the joint induction. □
Lemma 7 gives mesh regularity and the weight-motion bound along the moving Moser trajectory. The same bounds control the coupled recursion below.
Lemma 8 (One-step coupled contraction). Under the conditions of Lemma 7, there exist constants C 0 , C > 0 C_0,C>0 C 0 , C > 0 , independent of N N N , T T T , and α \alpha α , such that, for all sufficiently large N N N ,
E t + 1 ≤ ( 1 − α / 4 ) E t + C α C t N − 2 / ( M − 1 ) . (59) \mathcal{E}_{t+1}\le(1-\alpha/4)\mathcal{E}_t+C\alpha C_tN^{-2/(M-1)}. \tag*{(59)} E t + 1 ≤ ( 1 − α /4 ) E t + C α C t N − 2/ ( M − 1 ) . (59)
Proof. (35) and the density update give
∥ ρ t + 1 − ρ ϑ ∥ ∞ ≤ ( 1 − α ) ∥ ρ t − ρ ϑ ∥ ∞ + C α C t N − 2 / ( M − 1 ) \lVert\rho_{t+1}-\rho_\vartheta\rVert_\infty\le(1-\alpha)\lVert\rho_t-\rho_\vartheta\rVert_\infty+C\alpha C_tN^{-2/(M-1)} ∥ ρ t + 1 − ρ ϑ ∥ ∞ ≤ ( 1 − α ) ∥ ρ t − ρ ϑ ∥ ∞ + C α C t N − 2/ ( M − 1 )
+ C α N 1 / ( M − 1 ) max n ∈ [ N ] ∥ x ~ n ( t ) − x T S ∗ ( w n ( t ) ) ∥ . (60) \qquad+C\alpha N^{1/(M-1)}\max_{n\in[N]}\left\lVert\widetilde{x}_n^{(t)}-x_{\mathrm{TS}}^*(w_n^{(t)})\right\rVert. \tag*{(60)} + C α N 1/ ( M − 1 ) n ∈ [ N ] max x n ( t ) − x TS ∗ ( w n ( t ) ) . (60)
Equations (56)–(57), Lipschitz continuity of x T S ∗ x_{\mathrm{TS}}^* x TS ∗ , and (50) give the inner recursion below. The numerical motion C α N − 2 / ( M − 1 ) C\alpha N^{-2/(M-1)} C α N − 2/ ( M − 1 ) is absorbed into its last term because C t ≥ 1 C_t\ge1 C t ≥ 1 .
max n ∈ [ N ] ∥ x ~ n ( t + 1 ) − x T S ∗ ( w n ( t + 1 ) ) ∥ ≤ η K ( 1 + C α N 1 / ( M − 1 ) ) max n ∈ [ N ] ∥ x ~ n ( t ) − x T S ∗ ( w n ( t ) ) ∥ \max_{n\in[N]}\left\lVert\widetilde{x}_n^{(t+1)}-x_{\mathrm{TS}}^*(w_n^{(t+1)})\right\rVert
\le\eta_K\left(1+C\alpha N^{1/(M-1)}\right)\max_{n\in[N]}\left\lVert\widetilde{x}_n^{(t)}-x_{\mathrm{TS}}^*(w_n^{(t)})\right\rVert n ∈ [ N ] max x n ( t + 1 ) − x TS ∗ ( w n ( t + 1 ) ) ≤ η K ( 1 + C α N 1/ ( M − 1 ) ) n ∈ [ N ] max x n ( t ) − x TS ∗ ( w n ( t ) )
+ C α ∥ ρ t − ρ ϑ ∥ ∞ + C α C t N − 2 / ( M − 1 ) . (61) \qquad+C\alpha\lVert\rho_t-\rho_\vartheta\rVert_\infty+C\alpha C_tN^{-2/(M-1)}. \tag*{(61)} + C α ∥ ρ t − ρ ϑ ∥ ∞ + C α C t N − 2/ ( M − 1 ) . (61)
Multiply (61) by C 0 ( 1 + α N 1 / ( M − 1 ) ) C_0(1+\alpha N^{1/(M-1)}) C 0 ( 1 + α N 1/ ( M − 1 ) ) and add it to (60) . Choose C 0 C_0 C 0 to absorb the direct solver-error term and K K K to meet the coupled-contraction margin in (52) . The density component then has coefficient at most 1 − α / 2 1-\alpha/2 1 − α /2 , and the solver component has coefficient at most 1 − α ˉ / 4 ≤ 1 − α / 4 1-\bar{\alpha}/4\le1-\alpha/4 1 − α ˉ /4 ≤ 1 − α /4 . The remaining terms are bounded by C α C t N − 2 / ( M − 1 ) C\alpha C_tN^{-2/(M-1)} C α C t N − 2/ ( M − 1 ) , which proves (59) .
Proof of Theorem 1. Use the moving-weight Moser realization in Proposition 7. Lemma 7 gives C j ≤ C ‾ m e s h C_j\le\overline{C}_{\mathrm{mesh}} C j ≤ C mesh for all rounds, where C ‾ m e s h \overline{C}_{\mathrm{mesh}} C mesh is independent of j j j and N N N for each fixed regular problem. Take N = Ω ( κ ϑ 3 ( M − 1 ) / 2 ) N=\Omega(\kappa_{\vartheta}^{3(M-1)/2}) N = Ω ( κ ϑ 3 ( M − 1 ) /2 ) sufficiently large for the reconstruction and Moser mesh-stability thresholds in Appendix § 12 .§ 2 . Iterating (59) gives
E t ≤ ( 1 − α / 4 ) t E 0 + C α N − 2 / ( M − 1 ) ∑ j = 0 t − 1 ( 1 − α / 4 ) t − 1 − j C j ≤ ( 1 − α / 4 ) t E 0 + 4 C C ‾ m e s h N − 2 / ( M − 1 ) . (62) \begin{aligned}
\mathcal{E}_t\le(1-\alpha/4)^t\mathcal{E}_0+C\alpha N^{-2/(M-1)}\sum_{j=0}^{t-1}(1-\alpha/4)^{t-1-j}C_j \\
&\le(1-\alpha/4)^t\mathcal{E}_0+4C\overline{C}_{\mathrm{mesh}}N^{-2/(M-1)}. \tag*{(62)}
\end{aligned} E t ≤ ( 1 − α /4 ) t E 0 + C α N − 2/ ( M − 1 ) j = 0 ∑ t − 1 ( 1 − α /4 ) t − 1 − j C j ≤ ( 1 − α /4 ) t E 0 + 4 C C mesh N − 2/ ( M − 1 ) . (62)
This is the claimed bound on the coupled error. Proposition 9 then gives
R ^ ϑ ( W ( t ) ) ≤ C ∥ ρ t − ρ ϑ ∥ ∞ + C N − 2 / ( M − 1 ) ≤ C E t + C N − 2 / ( M − 1 ) , (63) \widehat{\mathcal{R}}_{\vartheta}(W^{(t)})\le C\|\rho_t-\rho_{\vartheta}\|_{\infty}+CN^{-2/(M-1)}\le C\mathcal{E}_t+CN^{-2/(M-1)}, \tag*{(63)} R ϑ ( W ( t ) ) ≤ C ∥ ρ t − ρ ϑ ∥ ∞ + C N − 2/ ( M − 1 ) ≤ C E t + C N − 2/ ( M − 1 ) , (63)
Combining this residual bound with (45) shows that the residual-dependent part of the upper bound on C t C_t C t contracts at the linear rate ( 1 − α / 4 ) t (1-\alpha/4)^t ( 1 − α /4 ) t . After t = O ( α − 1 log N ) t=O(\alpha^{-1}\log N) t = O ( α − 1 log N ) rounds, R ^ ϑ ( W ( t ) ) = O ( N − 2 / ( M − 1 ) ) \widehat{\mathcal{R}}_{\vartheta}(W^{(t)})=O(N^{-2/(M-1)}) R ϑ ( W ( t ) ) = O ( N − 2/ ( M − 1 ) ) and hence C t = O ( 1 + N − 2 / ( M − 1 ) ) = O ( 1 ) C_t=O(1+N^{-2/(M-1)})=O(1) C t = O ( 1 + N − 2/ ( M − 1 ) ) = O ( 1 ) uniformly over subsequent rounds. This proves the target-mass bound.
For fixed κ ϑ \kappa_{\vartheta} κ ϑ , choose N = Θ ( ϵ − ( M − 1 ) / 2 ) N=\Theta(\epsilon^{-(M-1)/2}) N = Θ ( ϵ − ( M − 1 ) /2 ) sufficiently large for the regularity thresholds. Under the initialization in (51) , Lemmas 7 and 8 give an O ( ϵ ) O(\epsilon) O ( ϵ ) error floor after T = O ( α − 1 log ϵ − 1 ) T=O(\alpha^{-1}\log\epsilon^{-1}) T = O ( α − 1 log ϵ − 1 ) outer rounds. For a linearly convergent InnerSolver K \operatorname{InnerSolver}_K InnerSolver K with η K ≤ q K \eta_K\le q^K η K ≤ q K , q ∈ ( 0 , 1 ) q\in(0,1) q ∈ ( 0 , 1 ) , the three damping regimes in Table 1 yield repeated work per adaptive weight of O ( log 2 ϵ − 1 ) O(\log^2\epsilon^{-1}) O ( log 2 ϵ − 1 ) , O ( ϵ − 1 / 2 log 2 ϵ − 1 ) O(\epsilon^{-1/2}\log^2\epsilon^{-1}) O ( ϵ − 1/2 log 2 ϵ − 1 ) , and O ( ϵ − 3 / 4 log ϵ − 1 ) O(\epsilon^{-3/4}\log\epsilon^{-1}) O ( ϵ − 3/4 log ϵ − 1 ) , respectively, favoring constant damping. For η K = O ( K − p ) \eta_K=O(K^{-p}) η K = O ( K − p ) , the corresponding repeated-work bounds are O ~ ( ϵ − 3 / ( 2 p ) ) \widetilde{O}(\epsilon^{-3/(2p)}) O ( ϵ − 3/ ( 2 p ) ) , O ~ ( ϵ − 1 / 2 − 1 / ( 2 p ) ) \widetilde{O}(\epsilon^{-1/2-1/(2p)}) O ( ϵ − 1/2 − 1/ ( 2 p ) ) , and O ~ ( ϵ − 3 / 4 ) \widetilde{O}(\epsilon^{-3/4}) O ( ϵ − 3/4 ) . The leading powers favor constant damping for p > 2 p>2 p > 2 and fixed inner work for p < 2 p<2 p < 2 , with a tie at p = 2 p=2 p = 2 . The theorem’s O ( ϵ 3 / 2 ) O(\epsilon^{3/2}) O ( ϵ 3/2 ) initialization requires O ( ϵ − 3 / ( 2 p ) ) O(\epsilon^{-3/(2p)}) O ( ϵ − 3/ ( 2 p ) ) one-time work per weight in every regime. Including warmup, the repeated-work advantage of smaller damping disappears in the leading exponent for p ≤ 2 p\le2 p ≤ 2 . These bounds apply to the N N N adaptive weights. The M M M fixed corners additionally require O ( M log ϵ − 1 ) O(M\log\epsilon^{-1}) O ( M log ϵ − 1 ) initial work for linear convergence or O ( M ϵ − 3 / ( 2 p ) ) O(M\epsilon^{-3/(2p)}) O ( M ϵ − 3/ ( 2 p ) ) for sublinear convergence if accurate states are not supplied, plus subsequent refinements. Aggregate adaptive inner work scales with N N N , while reconstruction, quadrature, and transport costs are counted separately.
Experiment Details
This section gives the additional experimental details for Section 5.
Experimental Protocol and Benchmark Scope
Baselines. Uniform weighting uses the same scalarized solver and returned cardinality as SUR-FACE, providing a direct comparison between fixed and geometry-adaptive scalarization weights. We further compare with several classes of finite-PF methods. M O E A / D MOEA/D M O E A / D [69 ] decomposes the MOO problem using a fixed set of weight vectors, while M O E A / D MOEA/D M O E A / D -A W A AWA A W A [49 ] adaptively removes weights in crowded regions and adds weights toward sparse PF regions. D E A DEA D E A -G N G GNG GN G [39 ] also adapts preference vectors, using a growing neural gas model to capture the evolving PF geometry. N S G A NSGA N S G A -I I I III I I I [19 ] maintains population diversity through reference-point association, whereas S M S SMS S M S -E M O A EMOA E M O A [5 ] uses hypervolume contribution for environmental selection. R V E A RVEA R V E A [60 ] approximates the PF through multiple local models, and S u b s e t Subset S u b se t s e l e c t i o n selection se l ec t i o n [55 ] selects a fixed-cardinality representation from a larger candidate set. Finally, U M O D UMOD U M O D [72 ] directly targets representativeness through a max-packing design, which serves as a surrogate for minimizing PF fill distance. All methods use matched returned cardinalities, with five seeds for stochastic baselines.
Benchmarks. We evaluate SURFACE on problems with M ∈ { 2 , 3 , 4 , 6 } M \in\{2, 3, 4, 6\} M ∈ { 2 , 3 , 4 , 6 } objectives. The synthetic suite includes ZDT1/2/4 [73 ] and DTLZ2/3/4 [21 ] . ZDT1/2/4 have smooth, connected bi-objective PFs on the represented interior branch. ZDT2 changes the PF curvature, while ZDT4 adds multiple local optima in decision space. DTLZ2/3/4 share the same smooth spherical PF of dimension M − 1 M-1 M − 1 . DTLZ3 adds multiple local optima, and DTLZ4 biases the map from decisions to PF points. Appendix § 11 .§ 3 verifies the regular full-ray TS conditions for DTLZ2. We also evaluate the engineering benchmark RE21 [59 ] using its empirical reference front, and the policy problems Deep Sea Treasure, Resource Gathering, Fruit Tree, and Minecart from MO-Gymnasium [29 ] . These tasks test the method on analytic fronts, empirical reference fronts, and optimized policies.
Metrics. We measure how evenly the returned solutions allocate target mass, how closely they cover the PF, and how much objective-space volume they dominate. The primary metric is the finite target-mass residual R ^ ϑ ( W ) \widehat{R}_{\vartheta}(W) R ϑ ( W ) (↓) from Lemma 1, evaluated on the selected cells associated with each returned set. We use connected mesh cells for transport diagnostics and PF-area-weighted Voronoi cells for cross-method comparisons. For ϑ = 1 \vartheta= 1 ϑ = 1 , it measures imbalance in PF surface-area allocation. IGD (↓) measures the average distance from the PF to the nearest returned objective vector. The fill distance (↓) measures the largest such distance [33 , 72 ] . We also report hypervolume HV (↑) [5 , 54 ] , the dominated objective-space volume relative to a fixed task-specific reference point. Its normalized hypervolume gap Δ H V : = 1 − H V / H V r e f \Delta\mathrm{HV} := 1-\mathrm{HV}/\mathrm{HV}_{\mathrm{ref}} Δ HV := 1 − HV / HV ref (↓) uses the reference PF hypervolume H V r e f \mathrm{HV}_{\mathrm{ref}} HV ref computed with the same task-specific reference point.
Inner solvers. Within each task, SURFACE and Uniform use the same inner solver and return the same number of solutions. The controlled DTLZ2 resolution studies use exact scalarized solutions. The quadratic experiment uses warm-started gradient descent to measure the effect of inner-solver error. For Deep Sea Treasure, Resource Gathering, and Fruit Tree, we use deterministic KL-regularized soft-value iteration with tolerance 10 − 11 10^{-11} 1 0 − 11 . For Minecart, both methods use a common frozen GPI-LS model and 2,016 evaluation episodes. We run each stochastic baseline with five seeds and the same returned-set size.
Computational budgets. All methods return the same number of Pareto solutions. SURFACE and Uniform use identical inner solvers with matched iteration budgets: SURFACE performs K K K inner steps per weight over T T T rounds, while Uniform performs K T KT K T steps per fixed weight, with auxiliary corner solves counted consistently. For analytic or high-accuracy inner solvers, we account for numerical solve costs and SURFACE’s reconstruction and transport overhead. For evolutionary and other stochastic baselines with different optimization procedures, we compare end-to-end runtime and evaluation costs, including wall-clock-budget comparisons on Resource Gathering.
Controlled Validation
Controlled PF distortion. We first use the three-objective radial problem in (15) to isolate the effect of scalarization-induced PF distortion. We vary κ ∈ { 0 , 0.5 , 1 , 1.5 , 2 , 2.5 , 3 } \kappa\in\{0, 0.5, 1, 1.5, 2, 2.5, 3\} κ ∈ { 0 , 0.5 , 1 , 1.5 , 2 , 2.5 , 3 } and normalize the analytic density using four independently scrambled Sobol rules with 18,192 points each. The mesh contains 66 returned vertices, including three pinned corners, and 100 cells. SURFACE uses T = 5 T = 5 T = 5 outer rounds and α = 0.2 \alpha= 0.2 α = 0.2 . Across the sweep, the measured distortion ratio J ‾ / J ‾ \overline{J}/\underline{J} J / J increases from 1 to 299.53. Uniform weighting reaches R ^ ϑ = 8.901 \widehat{R}_{\vartheta} = 8.901 R ϑ = 8.901 , whereas SURFACE remains below 0.785 throughout the sweep. Supplying the analytic PF-area density to the same transport solver gives R ^ ϑ = 0.0337 \widehat{R}_{\vartheta} = 0.0337 R ϑ = 0.0337 , providing an analytic-density reference.
Finite-resolution error. Figure 6 compares the measured errors with the predicted O ( N − 2 / ( M − 1 ) ) \mathcal{O}(N^{-2/(M-1)}) O ( N − 2/ ( M − 1 ) ) scale. In the figure, free probes are the N N N adaptive weights, and curved-mass residual measures target-mass imbalance on complete transported cells. For DTLZ2 with M = 3 M = 3 M = 3 , exact scalarized solves and one undamped update reduce the chart error ∥ p T − p P F ∥ C 1 \lVert p_T - p_{\mathrm{PF}}\rVert_{C^1} ∥ p T − p PF ∥ C 1 , density error E T \mathcal{E}_T E T , and residual R ^ ϑ ( W T ) \widehat{R}_{\vartheta}(W_T) R ϑ ( W T ) from ( 0.2368 , 0.3300 , 0.04909 ) (0.2368, 0.3300, 0.04909) ( 0.2368 , 0.3300 , 0.04909 ) at N = 12 N = 12 N = 12 to ( 0.02912 , 0.01934 , 0.00652 ) (0.02912, 0.01934, 0.00652) ( 0.02912 , 0.01934 , 0.00652 ) at N = 150 N = 150 N = 150 . This decrease is consistent with the O ( N − 1 ) \mathcal{O}(N^{-1}) O ( N − 1 ) scale in Lemma 2 and the exact-solve result, Theorem 2. For M = 6 M = 6 M = 6 , the errors also decrease with N N N , and the chart-error slope is close to the predicted O ( N − 2 / 5 ) \mathcal{O}(N^{-2/5}) O ( N − 2/5 ) scale. The analytic quadratic experiment separately measures the effect of inexact solves. Exact solutions give R ^ ϑ = 0.00253 \widehat{R}_{\vartheta}=0.00253 R ϑ = 0.00253 , compared with 0.320 for Uniform. With 16 warm-started gradient steps, the decision error falls to 1.24 × 10 − 9 1.24 \times10^{-9} 1.24 × 1 0 − 9 and R ^ ϑ < 0.00254 \widehat{R}_{\vartheta}<0.00254 R ϑ < 0.00254 , approaching the exact-solve result.
Finite MEQ validation. We check numerical MEQ by independently evaluating transported cell masses. For M = 3 M=3 M = 3 , the refined Bernstein–Moser configuration has worst cell-mass error 0.0395, compared with 0.0575 for the standard configuration. For M = 4 M=4 M = 4 , all tested transports at N ∈ { 6 , 16 , 31 , 52 , 80 } N \in\{6, 16, 31, 52, 80\} N ∈ { 6 , 16 , 31 , 52 , 80 } adaptive weights remain nondegenerate. At the finest resolution, the cell-mass error is 0.0354, the minimum orientation ratio is 0.535, and the maximum condition number is 7.07. The orientation ratio is the signed volume of a transported straight simplex divided by that of its reference simplex. A positive ratio indicates that the simplex has retained its orientation. The condition number is the ratio of the largest to smallest singular value of the affine map from the reference simplex to the transported simplex. The corresponding PF-area residuals on complete transported cells are 0.160, 0.155, 0.185, 0.207, and 0.207. These measurements check the mass accuracy and mesh geometry in Proposition 3. Appendix C.2.1 specifies the numerical tolerances.
Reconstruction accuracy. To examine how PF reconstruction affects density estimation, we reuse the saved samples at N ∈ { 16 , 31 , 52 } N \in\{16, 31, 52\} N ∈ { 16 , 31 , 52 } . We measure chart and density errors by root-mean-square (RMS) values over evaluation points. Radial reconstruction fits the scalar multiplier of each reference direction and combines it with that direction and the reference point to reconstruct the objective vector. At N = 31 N=31 N = 31 , radial reconstruction reduces the PF reconstruction error from 0.0646 to 0.0267 and the density error from 0.671 to 0.127. At N = 52 N=52 N = 52 , it reduces the density error from 0.377 to 0.0942 and the independently evaluated cell-mass error from 0.0479 to 0.0196. These results illustrate the reconstruction-to-density relation in Lemma 2. A fixed piecewise-linear density approximation adds interpolation error at finer resolutions, so we evaluate the reconstructed density directly.
Details of ZDT and DTLZ Benchmark Results
The ZDT1/2/4 and DTLZ2/3/4 comparison contains 11 tasks with M = 2 , 3 , 4 M=2, 3, 4 M = 2 , 3 , 4 . Every method returns N + M N+M N + M solutions. SURFACE and Uniform share the same scalarized solver, so their comparison isolates weight redistribution. The other baselines use their respective optimization procedures, with five seeds for each stochastic method. Table 5 gives the mean ranks, Table 6 gives the per-task results, and Figure 7 compares PF-coverage and hypervolume ranks.
Table 5. Mean ranks over 11 ZDT/DTLZ task-dimension groups. Coverage averages the first three PF-representation metrics and excludes hypervolume. Lower is better.
Table 6. Complete results for SURFACE and 9 baselines. Stochastic-method entries are mean ± sample standard deviation over five seeds. Uniform and SURFACE are deterministic and have no standard-deviation terms. Each Coverage row reports the mean rank over R ^ ϑ \widehat{R}_{\vartheta} R ϑ , IGD, and fill distance.
SURFACE has the best mean ranks in PF-area imbalance, IGD, fill distance, and aggregate PF coverage over the 11 tasks in Table 5 . These measures capture both the balance of allocated PF area and the distances from the PF to the returned solutions. Relative to Uniform, SURFACE improves PF-area imbalance, IGD, and hypervolume gap on all listed tasks. It also improves fill distance except on the two M = 4 M=4 M = 4 tasks, where Uniform gives 0.380 and SURFACE gives 0.381. The best individual method varies by task. On DTLZ2 with M = 4 M=4 M = 4 , LMPFE and DEA-GNG have lower PF-area imbalance than SURFACE, and DEA-GNG has lower IGD.
SURFACE also has the best mean Δ \Delta Δ HV rank over the 11 groups. Other methods achieve better hypervolume on individual tasks, as shown in Table 6 . Hypervolume rewards dominated objective-space volume, while uniform PF coverage rewards balanced representation of the surface. Figure 7 shows the resulting rank comparison, with SURFACE combining the lowest mean PF-coverage rank and the lowest mean hypervolume-gap rank.
Multi-Objective Policy Optimization
We evaluate SURFACE on Deep Sea Treasure, Resource Gathering, and Fruit Tree from MO-Gymnasium [29 ] . For each preference w w w , we optimize
F w ( π ) = − ∑ m = 1 M w m J m ( π ) + β R K L ( π ) . (64) F_w(\pi) = - \sum_{m=1}^{M} w_m J_m(\pi) + \beta R_{\mathrm{KL}}(\pi). \tag*{(64)} F w ( π ) = − m = 1 ∑ M w m J m ( π ) + β R KL ( π ) . (64)
Here J m ( π ) = E π [ ∑ t ≥ 0 γ t r m ( s t , a t ) ] J_m(\pi) = \mathbb{E}_{\pi}\left[\sum_{t \ge0} \gamma^t r_m(s_t,a_t)\right] J m ( π ) = E π [ ∑ t ≥ 0 γ t r m ( s t , a t ) ] is the unregularized discounted return, and
R K L ( π ) : = E π [ ∑ t ≥ 0 γ t KL ( π ( ⋅ ∣ s t ) ∥ π r e f ( ⋅ ∣ s t ) ) ] = 1 1 − γ ∑ s d π γ ( s ) KL ( π ( ⋅ ∣ s ) ∥ π r e f ( ⋅ ∣ s ) ) . R_{\mathrm{KL}}(\pi) := \mathbb{E}_{\pi}\left[\sum_{t \ge0} \gamma^t \operatorname{KL}(\pi(\cdot\mid s_t) \mathbin\Vert\pi_{\mathrm{ref}}(\cdot\mid s_t))\right] = \frac{1}{1-\gamma}\sum_s d^\gamma_\pi(s)\operatorname{KL}(\pi(\cdot\mid s) \mathbin\Vert\pi_{\mathrm{ref}}(\cdot\mid s)). R KL ( π ) := E π [ t ≥ 0 ∑ γ t KL ( π ( ⋅ ∣ s t ) ∥ π ref ( ⋅ ∣ s t )) ] = 1 − γ 1 s ∑ d π γ ( s ) KL ( π ( ⋅ ∣ s ) ∥ π ref ( ⋅ ∣ s )) .
Here d π γ ( s ) : = ( 1 − γ ) ∑ t ≥ 0 γ t Pr π ( s t = s ) d^\gamma_\pi(s) := (1-\gamma)\sum_{t \ge0}\gamma^t \Pr_\pi(s_t = s) d π γ ( s ) := ( 1 − γ ) ∑ t ≥ 0 γ t Pr π ( s t = s ) is the discounted state-occupancy distribution, starting from the environment’s initial-state distribution. The reference policy π r e f \pi_{\mathrm{ref}} π ref assigns positive probability to every available action. For the standard entropy-regularized soft-value solver, it is uniform over those actions. As ∑ m w m = 1 \sum_m w_m = 1 ∑ m w m = 1 , (64) is the weighted sum of f m β ( π ) = − J m ( π ) + β R K L ( π ) f^\beta_m(\pi) = -J_m(\pi) + \beta R_{\mathrm{KL}}(\pi) f m β ( π ) = − J m ( π ) + β R KL ( π ) . evaluate PF-area allocation, IGD, and HV using the unregularized return vectors ( J m ( π ) ) m = 1 M (J_m(\pi))_{m=1}^{M} ( J m ( π ) ) m = 1 M . We use discount factor 0.999, with β = 1.5 \beta= 1.5 β = 1.5 for Deep Sea Treasure and β = 0.5 \beta= 0.5 β = 0.5 for Resource Gathering and Fruit Tree. Soft value iteration stops at tolerance 10 − 11 10^{-11} 1 0 − 11 . SURFACE uses α = 0.3 \alpha= 0.3 α = 0.3 . Each adaptive weight retains its label across rounds and warm-starts from the preceding solution with that label. We reuse the fixed corner solutions and perform a final solve at the returned weights.
Deep Sea Treasure and Resource Gathering use 30 outer rounds, while Fruit Tree uses ten. They return 16, 21, and 56 policies, respectively. SURFACE and Uniform share the deterministic soft-value solver. The other baselines use an evolutionary optimizer over policy logits, run with five seeds. Table 3 reports the comparison.
We further study the effect of returned-set resolution on the M = 6 M = 6 M = 6 Fruit Tree task ([29 ] ). Policy sensitivities describe how the optimized policies change with the scalarization weights. We use these derivatives to evaluate the return-space geometry, and compare all resolutions using independently sampled, surface-area-weighted return-space Voronoi cells. Site selection uses nearest-site assignments on a separate fixed weighted oracle reference. SURFACE achieves decreasing target-mass residuals R ^ ϑ = 0.2523 , 0.1955 , 0.1694 \widehat{R}_{\vartheta} = 0.2523, 0.1955, 0.1694 R ϑ = 0.2523 , 0.1955 , 0.1694 as the returned cardinality increases from N = 126 N = 126 N = 126 to 252 and 462. On this six-objective task, increasing the number of returned policies reduces the measured target-mass imbalance.
Minecart tests SURFACE with a different policy-optimization backend. This continuous-state, discrete-action benchmark is provided by MO-Gymnasium ([29 ] ) and was introduced by Abels et al. [1 ] . Both methods use the same frozen GPI-LS policy set ([2 ] ), with 2,016 evaluation episodes per method at temperature 0.03. The selected weights condition GPI-LS action selection over this fixed policy set, without retraining its members. Relative to Uniform, SURFACE reduces the return-space coverage metric from 3.55 to 2.50 and IGD from 0.429 to 0.421, while increasing hypervolume from 507.7 to 516.0.