🔢 mathematics

Convergence Rates for $\ell_p$ Norm Minimization in Convex Vector Optimization

This paper establishes that norm-minimization-based outer approximation algorithms for convex vector optimization achieve the optimal convergence rate of $O(k^{2/(1-q)})$ for any $\ell_p$ norm with $p \in (1,\infty)$ by introducing a Euclidean intermediary technique that bypasses the limitations of direct $\ell_p$ smoothness analysis.

Original authors: Mohammed Alshahrani

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammed Alshahrani

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to draw a perfect map of a mysterious, smooth, multi-dimensional island (the "optimal solution") using only a limited number of straight-edged fences. Your goal is to build a fence (a polytope) that hugs the island as closely as possible, leaving as little empty space as possible between the fence and the island's edge.

This paper is about a specific method for building that fence, called the Norm-Minimization Outer Approximation Algorithm. It asks a very specific question: Does the shape of the ruler you use to measure "closeness" change how fast you can build the perfect fence?

Here is the breakdown of the paper's discovery, using simple analogies.

1. The Problem: Measuring "Closeness"

In the world of optimization, you often have to choose a "ruler" (a mathematical norm) to measure the distance between your current fence and the true island.

The Euclidean Ruler ( $p=2$ ): This is the standard, familiar ruler we use in everyday life (like a tape measure). It measures distance as the crow flies. Previous research showed that if you use this ruler, your fence gets closer to the island very quickly. Specifically, the error shrinks at a "super-fast" rate.
The $\ell_p$ Rulers ( $p \neq 2$ ): These are alternative rulers.
- If $p < 2$ , the ruler is "rougher" or "sharper" (like a jagged saw).
- If $p > 2$ , the ruler is "smoother" or "flatter" (like a soft cushion).

The Big Question: If you switch from the standard Euclidean ruler to these "rough" or "smooth" $\ell_p$ rulers, does your fence-building speed slow down?

2. The Old Guess vs. The New Discovery

The Old Guess (The "Direct Approach"):
Mathematicians initially thought that if you used a "rough" ruler (where $1 < p < 2$ ), the algorithm would stumble. They guessed the speed would slow down, proportional to how rough the ruler was. It was like thinking, "If I try to walk on a jagged path, I can't run as fast as on a smooth path."

The New Discovery (The Paper's Main Result):
The author, Mohammed Alshahrani, proves that this guess is wrong.

No matter which $\ell_p$ ruler you pick (whether it's rough, smooth, or standard), the speed at which your fence hugs the island remains exactly the same. The "roughness" of the ruler does not slow you down. The convergence rate is universal.

3. How Did They Prove It? (The "Euclidean Intermediary" Trick)

This is the clever part of the paper.

Usually, when analyzing a "rough" ruler, you get stuck because the math gets messy and the speed seems to degrade. The author found a clever shortcut:

The Detour: Instead of measuring the distance directly with the "rough" $\ell_p$ ruler, the author temporarily switches to the standard Euclidean (square) ruler to do the heavy lifting.
The Secret: Even though the algorithm uses a weird $\ell_p$ ruler to decide where to cut the fence, the geometry of the space (the room the island is in) is still fundamentally Euclidean. The author uses this underlying Euclidean structure to prove that the "distance" between the fence and the island shrinks quadratically (very fast).
The Switch Back: Once the proof is done using the Euclidean ruler, the author simply converts the result back to the $\ell_p$ ruler. Because all rulers in this finite space are related, this conversion only changes the size of the error (a constant factor), but it does not change the speed (the exponent) at which the error disappears.

Analogy: Imagine you are trying to measure the speed of a car driving on a bumpy road (the $\ell_p$ norm). You might think the bumps slow the car down. But the author realized that if you look at the car's engine (the underlying Euclidean structure), it's running at full power regardless of the road. The bumps might make the ride jolty (changing the constant), but the car's top speed (the convergence rate) remains the same.

4. What the Numbers Say

The paper includes computer experiments to back this up. They tested the algorithm with many different "rulers" ( $p = 1.25, 1.5, 2, 3, 4, 8$ ) on different shapes.

Result: In every single case, the error dropped at the same theoretical speed.
Observation: While the speed was the same, the efficiency varied slightly. The standard Euclidean ruler ( $p=2$ ) was often the most efficient in terms of raw numbers, but the "rough" rulers didn't fail or slow down in the way people predicted.

5. Why This Matters

This result is a "universal law" for this type of algorithm. It tells us that we don't need to worry about picking the "perfect" ruler to get the best theoretical speed. The algorithm is robust. Whether you use a standard ruler, a jagged one, or a soft one, the math guarantees you will reach the solution at the same optimal pace.

In summary: The paper proves that the "shape" of your measuring tool doesn't change the speed limit of the algorithm. The speed is determined by the geometry of the space itself, not the ruler you hold in your hand.

Technical Summary: Convergence Rates for $\ell_p$ Norm Minimization in Convex Vector Optimization

Problem Statement
The paper addresses the convergence rates of outer approximation algorithms for Convex Vector Optimization Problems (CVOPs). Specifically, it investigates the performance of norm-minimization-based algorithms where the scalarization metric is an $\ell_p$ norm with $p \in (1, \infty)$ .

In these algorithms, a sequence of polyhedral outer approximations $\{P_k\}$ is iteratively refined to approximate the upper image $P$ of the CVOP. At each step, the algorithm selects a vertex $v$ of the current polytope, solves a closest-point problem to find the residual $z_v = y_v - v$ (where $y_v$ is the projection of $v$ onto the feasible set), and adds a supporting halfspace defined by the gradient of the norm at $z_v$ .

The central question is how the choice of $p$ affects the convergence rate of the Hausdorff approximation error $\delta_H(P_k, A)$ , where $A$ is a compact convex slice of the upper image. While the Euclidean case ( $p=2$ ) is known to achieve the optimal rate $O(k^{2/(1-q)})$ (where $q$ is the number of objectives), the behavior for general $\ell_p$ norms remained an open problem. A direct analysis using the modulus of smoothness suggested a weaker rate of $O(k^{s(p)/(1-q)})$ with $s(p) = \min(p, 2)$ , implying that "rougher" norms ( $1 < p < 2$ ) would suffer a degradation in convergence speed.

Methodology
The paper develops a theoretical framework to prove that the convergence rate exponent is actually independent of $p$ for all $p \in (1, \infty)$ . The methodology involves:

Geometric Lemmas: The authors adapt the geometric lemmas used in the Euclidean case (specifically those by Ararat et al. and Lotov et al.) to the $\ell_p$ setting. This includes establishing bounds on hyperplane distances, deviation vector separations, and packing numbers.
Euclidean Intermediary Technique: The core innovation is a proof technique (Lemma 7) that bypasses the limitations of the $\ell_p$ $ℓ_{p}$ modulus of smoothness. Instead of bounding the hyperplane distance directly using $\ell_p$ $ℓ_{p}$ smoothness properties (which yields the suboptimal exponent $\min(p, 2)$ $min (p, 2)$ ), the authors utilize the ambient Euclidean inner product structure of $\mathbb{R}^q$ $R^{q}$ .
- They expand the squared Euclidean norm of the difference between deviation vectors ( $\|\alpha - \alpha'\|_2^2$ ).
- They exploit the non-negativity of terms arising from the first-order optimality conditions of the projection problem.
- This yields a quadratic bound on the hyperplane distance in terms of the Euclidean norm.
Norm Equivalence: The quadratic bound derived in the Euclidean metric is then converted to the $\ell_p$ metric using standard norm equivalence inequalities. Crucially, this conversion introduces only a dimension-dependent constant factor ( $N_{2,p}$ ) but does not alter the quadratic exponent.
Convergence Framework: The proof integrates these estimates into the $H(r, A)$ -sequence convergence framework. By establishing that the deviation vectors are sufficiently separated and that the number of such vectors is bounded by packing estimates, the authors derive the asymptotic rate.

Key Contributions

Universal Convergence Rate: The paper proves that for every $p \in (1, \infty)$ , the norm-minimization algorithm achieves the convergence rate $\delta_H(P_k, A) = O(k^{2/(1-q)})$ . This establishes that the exponent $c(p) = 2$ is universal across all $\ell_p$ norms, refuting the conjecture that the rate depends on the smoothness power type $s(p) = \min(p, 2)$ .
Refutation of Prior Conjectures: The results disprove the hypothesis that the convergence rate is limited by the primal smoothness or dual convexity power types (e.g., $c(p) = \min(2, p, p/(p-1))$ ). The paper demonstrates that neither the primal smoothness nor the dual convexity determines the exponent.
Euclidean Intermediary Proof Technique: The authors introduce a novel proof strategy that leverages the Euclidean structure of the ambient space to obtain quadratic bounds, effectively decoupling the convergence rate from the specific geometry of the scalarization norm.
Geometric Extensions: The work extends the geometric lemmas of Ararat et al. (specifically regarding hyperplane distance bounds and deviation vector separation) to the general $\ell_p$ setting, providing the necessary tools for convergence analysis beyond inner-product norms.

Results

Theoretical: Theorem 11 formally states that the convergence rate exponent is $c(p) = 2$ for all $p \in (1, \infty)$ . The constant in the big-O notation depends on $p$ (via norm equivalence constants and packing constants), but the exponent remains invariant.
Numerical: The authors conducted numerical experiments on three test problems (including a spherical cap, a rotated ellipse, and a nonlinear objective with a polytope feasible set) for $q \in \{2, 3\}$ $q \in {2, 3}$ and $p \in \{1.25, 1.5, 2, 3, 4, 8\}$ $p \in {1.25, 1.5, 2, 3, 4, 8}$ .
- The empirical convergence rates $\hat{c}(p)$ were found to be consistent across different values of $p$ within each problem configuration.
- While the absolute values of the fitted exponents varied slightly from the theoretical $c=2$ (due to finite-sample effects, initial plateaus, or transient behavior), there was no systematic dependence on $p$ .
- The experiments confirmed that the Euclidean case ( $p=2$ ) does not offer a superior exponent compared to other $p$ values, though it may offer better multiplicative constants.

Significance and Claims
The paper claims to resolve a significant open question regarding the efficiency of norm-minimization algorithms in vector optimization. By proving that the optimal convergence rate $O(k^{2/(1-q)})$ holds for all $\ell_p$ norms, the work demonstrates that the choice of scalarization norm within the $\ell_p$ family does not compromise the asymptotic convergence speed.

The authors emphasize that the rate-limiting factor is not the smoothness of the scalarization norm itself, but rather the Euclidean curvature of the "deviation surface" formed by support points and cut normals. This suggests that the exponent $c=2$ is a robust feature of the algorithm's geometry in $\mathbb{R}^q$ , rather than an artifact specific to Euclidean metrics.

The paper concludes by noting that while the exponent is universal, the multiplicative constant in the convergence bound does depend on $p$ , with the Euclidean case ( $p=2$ ) generally yielding the most favorable constants. The work leaves open the question of whether this universality extends to all strictly convex and smooth norms, and how the algorithm behaves at the non-smooth endpoints ( $p=1$ and $p=\infty$ ).