Convergence Rates for ${\ell }_p$ Norm Minimization in Convex Vector Optimization

Abstract

We analyze convergence rates of norm-minimization-based outer approximation algorithms for convex vector optimization when the scalarization uses an ${\ell }_p$ norm with $p\in (1,\infty )$. While the Euclidean case ($p=2$) achieves the optimal rate $O(k^{2/(1-q)})$, the behavior under general ${\ell }_p$ norms has remained open. A direct approach via the modulus of smoothness yields only the weaker exponent $\min (p,2)$, which degrades for $1<p<2$. We prove that the Hausdorff approximation error satisfies $\hat{I}{´}_H(P_k,A)=O(k^{2/(1-q)})$ for \emph{every} $p\in (1,\infty )$, where $q$ is the number of objectives and $k$ is the iteration count. The proof introduces a Euclidean intermediary technique that exploits the ambient inner product structure of ${\mathbb{R}}^q$ to obtain a quadratic bound on the hyperplane distance, bypassing the ${\ell }_p$ smoothness limitation; norm equivalence then converts this to any ${\ell }_p$ metric at the cost of only a dimension-dependent constant, not a loss of exponent. Numerical experiments confirm the $p$-independent rate predicted by the theory.

Updated Ref. 6