Convergence Rates for $\ell_p$ Norm Minimization in Convex Vector Optimization
Provides a unified optimal convergence guarantee for a class of algorithms in multi-objective optimization, solving a theoretical bottleneck for practitioners using non-Euclidean norms.
The paper proves that for convex vector optimization, $\ell_p$ norm minimization achieves the optimal convergence rate $O(k^{2/(1-q)})$ for all $p \in (1,\infty)$, resolving a gap where previous methods gave weaker rates for $p<2$. Numerical experiments confirm the rate.
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 $δ_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 $\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.