Adaptive Metrics for Norm-Minimization-Based Outer Approximation in Convex Vector Optimization

Technical Summary: Adaptive Metrics for Norm-Minimization-Based Outer Approximation in Convex Vector Optimization

Problem Statement
The paper addresses the approximation of the upper image $P := \Gamma(X) + C$ in bounded convex vector optimization problems (CVOPs), where $X$ is a compact convex set, $\Gamma$ is a continuous $C$-convex mapping, and $C$ is a closed, solid, pointed polyhedral cone. The goal is to construct a polyhedral outer approximation of $P$ with a guaranteed error bound in the Hausdorff distance. While outer approximation algorithms driven by norm-minimizing scalarizations have been established to possess finite termination and convergence rates, a gap remained regarding the dependence of these rates on the choice of the scalarization norm. Specifically, previous work by Ararat et al. [4] demonstrated an improved convergence rate of $O(k^{2/(1-q)})$ for the standard Euclidean ($\ell_2$) norm, whereas the generic rate for arbitrary norms was $O(k^{1/(1-q)})$. It was unclear whether this improvement was an artifact of the Euclidean structure or a property of more general Hilbertian geometries, and whether adapting the metric dynamically could further enhance performance.

Methodology
The paper develops a theoretical framework and an adaptive algorithm to address these questions through three primary mechanisms:

1. Linear Isometry and Invariance: The authors establish that any inner-product norm $\|y\|_M = \sqrt{y^\top M y}$ (where $M \succ 0$) is isometric to the Euclidean norm via the linear transformation $T = M^{1/2}$. They prove that the norm-minimization-based outer approximation algorithm is invariant under this transformation. Consequently, the algorithm's behavior in an arbitrary inner-product space is equivalent to its behavior in the Euclidean space under a transformed problem. This allows the transfer of convergence analysis from the Euclidean case to any inner-product norm.

2. Adaptive-Metric Framework: The authors propose an algorithm where the scalarization norm varies at each iteration $k$ based on the history of cut normals. Specifically, the metric $M_k$ is constructed as a regularized average of the outer products of normalized cut normals: $M_k = \varepsilon_0 I + \frac{1}{k} \sum_{i=1}^k u_i u_i^\top$. While the scalarization uses this adaptive metric $M_k$, the approximation error is measured and the stopping criterion is enforced using a fixed Euclidean norm.

3. Dispersion Theorem: To ensure the adaptive metrics remain well-conditioned (i.e., the condition number does not explode), the paper introduces a "dispersion" condition. This condition requires that the sequence of cut normals spreads sufficiently across all directions in the objective space. The authors prove that if the efficient frontier of the upper image slice is a strictly convex hypersurface with bounded curvature (Assumption 3), the cut normals naturally disperse. This geometric property guarantees that the minimum eigenvalue of the empirical covariance matrix of the normals remains bounded away from zero, ensuring the adaptive metric remains well-conditioned throughout the execution.

Key Contributions
The paper makes five distinct contributions:

• Extension of Convergence Rates: It proves that the improved convergence rate $O(k^{2/(1-q)})$, previously known only for the Euclidean norm, extends to all inner-product norms. This is achieved by leveraging the linear isometry between the inner-product space and Euclidean space, showing the rate depends on Hilbertian geometry rather than the specific Euclidean structure.
• Explicit Convergence Bounds: The authors derive explicit convergence bounds in the original coordinates, quantifying how the spectral properties of the inner product matrix $M$ influence the constants in the error estimates.
• Adaptive-Metric Convergence: They establish the correctness and Euclidean convergence of the adaptive-metric variant. Under uniform spectral bounds on the adaptive metrics, they provide explicit bounds showing that improved metric conditioning (better dispersion) leads to sharper convergence constants.
• Dispersion Theorem: A central theoretical result (Theorem 15) provides sufficient geometric conditions (strict convexity with bounded curvature of the efficient frontier) under which the adaptive metrics remain well-conditioned. This bridges the gap between fixed-norm theory and the practical observation that adapting to problem geometry accelerates convergence.
• Numerical Validation: The paper presents numerical experiments on three test problems (including ball and ellipsoidal feasible sets) validating the theoretical rates and demonstrating the practical efficacy of the adaptive approach.

Results

• Theoretical Rates: The experiments confirm the theoretical rate $O(k^{2/(1-q)})$ for fixed inner-product norms. For the adaptive metric, while the theoretical guarantee is the generic $O(k^{1/(1-q)})$ rate (Theorem 18), the empirical results show consistent performance improvements.
• Iteration Savings: On problems with curved Pareto fronts (Examples 1 and 2), the adaptive metric approach reduced the number of iterations required to reach a specific tolerance by 31–33% compared to the fixed Euclidean norm.
• Metric Conditioning: The experiments verified the dispersion condition empirically. The minimum eigenvalue of the empirical covariance matrix $\Sigma_k$ remained bounded away from zero (e.g., $\approx 0.15$), and the metric quality parameter $\theta_k$ stabilized in the range $[0.41, 0.54]$, confirming the metrics remained well-conditioned.
• High-Dimensional Strategies: For dimensions $q \ge 4$, where full vertex enumeration is computationally prohibitive, the paper evaluated "LP probe" and "hybrid" strategies. The adaptive metric combined with an LP probe strategy achieved the fastest convergence (fewest iterations) in the tested high-dimensional case ($q=4$).
• Limitations: In a problem with a parabolic Pareto front and very low iteration counts (Example 3), the adaptive metric offered no speedup, attributed to insufficient data accumulation for the adaptation mechanism to engage effectively.

Significance and Claims
The paper claims to provide a rigorous foundation for the use of geometry-aware and adaptive inner-product metrics in norm-minimization-based convex vector optimization. Its primary significance lies in:

1. Clarifying Geometric Origins: It demonstrates that the improved convergence exponent is a property of Hilbertian geometry (inner-product spaces) rather than the specific Euclidean norm, resolving a theoretical ambiguity.
2. Justifying Adaptivity: It offers the first rigorous justification for adaptive metric selection in this context, proving that under natural geometric conditions (strict convexity), the algorithm self-corrects to maintain well-conditioned metrics, thereby avoiding the degradation of convergence constants.
3. Practical Efficiency: The results suggest that for problems with curved Pareto fronts, adapting the scalarization metric to the history of cuts can significantly reduce computational effort (iteration count) without increasing the per-iteration cost significantly.

The authors remain modest regarding the convergence rate of the adaptive metric itself; while they observe iteration savings, they note that proving the improved $O(k^{2/(1-q)})$ rate for the adaptive case remains an open question, as the standard isometry argument fails when the metric changes at every iteration. They also note that the current theory relies on strict convexity and full vertex enumeration, limiting its immediate scope to non-smooth boundaries and approximate vertex-finding strategies.