Alternating Linear Minimization: Revisiting von Neumann's alternating projections

Gábor Braun, Sebastian Pokutta, Robert WeismantelarXiv 2022 · DOI · arXiv

Abstract

In 1933 von Neumann proved a beautiful result that one can approximate a point in the intersection of two convex sets by alternating projections, i.e., successively projecting on one set and then the other. This algorithm assumes that one has access to projection operators for both sets. In this note, we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets.

Introduction

Finding a point in the intersection of two convex sets $P$ and $Q$ is a foundational problem in optimization and geometry. Traditionally, this has been solved using von Neumann's alternating projections method. However, calculating a projection—finding the point in a set closest to a given external point—can be computationally expensive, often requiring the solution of a secondary optimization problem. This paper explores whether we can achieve the same results using simpler, "cheaper" operations.

The Classic Baseline: Alternating Projections

The standard approach, known as Projections Onto Convex Sets (POCS), relies on the existence of efficient projection operators $\Pi_P$ and $\Pi_Q$. By iteratively projecting the current estimate onto each set, the sequence eventually converges to a point in the intersection $P \cap Q$.

Algorithm 1: The classic von Neumann alternating projections method (POCS).

While theoretically sound, the high cost of projections in high-dimensional spaces or complex sets limits the scalability of this approach. In many modern applications, solving a linear minimization over a set is significantly faster than calculating a projection.

The ALM Algorithm: Moving Beyond Projections

This paper introduces Alternating Linear Minimization (ALM). The core innovation is replacing the expensive projection step with a Linear Minimization Oracle (LMO). An LMO simply finds a point in the set that minimizes a linear objective—a task that is often much more efficient than computing a projection.

The ALM algorithm treats the intersection problem as the minimization of the distance function $f(x, y) = \|x - y\|^2$ over the product space $P \times Q$. By applying a block-coordinate version of the Frank-Wolfe (Conditional Gradient) method, the authors derive a projection-free iterative process.

Algorithm 3: The proposed Alternating Linear Minimization (ALM) algorithm.

Theoretical Guarantees and Convergence

A key contribution of this work is proving that ALM maintains the same $O(1/t)$ convergence rate as the classic alternating projections method. This is a significant result because LMOs provide "weaker" information than projections. The authors demonstrate that a "naive" simulation of projections using LMOs would result in a much slower $O(1/\sqrt{t})$ rate, whereas their integrated ALM approach preserves efficiency.

The convergence error is bounded by the diameters of the sets ($D_P, D_Q$), ensuring that the algorithm performs reliably across different geometric configurations.

Handling Polytopes and Disjointness

For sets defined as polytopes, the authors provide an adaptive variant that can achieve exact recovery of the intersection point. By tracking the extreme points (vertices) discovered by the LMOs, the algorithm can eventually solve a small linear feasibility problem to jump to the precise intersection. This provides a bridge between iterative approximation and exact discrete geometry.

Furthermore, if the sets $P$ and $Q$ do not intersect, ALM naturally generates a certifying hyperplane. This mathematical certificate provides definitive proof of disjointness, with the number of iterations required scaling inversely with the actual distance between the sets.

Conclusion

Alternating Linear Minimization offers a powerful alternative to traditional projection-based methods. By leveraging the efficiency of linear minimization oracles without sacrificing convergence speed, ALM provides a scalable framework for solving intersection problems in modern, high-dimensional applications where projections are computationally prohibitive.

Summary updated

Abstract

In 1933 von Neumann proved a beautiful result that one can approximate a point in the intersection of two convex sets by alternating projections, i.e., successively projecting on one set and then the other. This algorithm assumes that one has access to projection operators for both sets. In this note, we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets.
BibTeX
@misc{braun2022alternating,
  author = {Gábor Braun and Sebastian Pokutta and Robert Weismantel},
  title = {{Alternating Linear Minimization: Revisiting von Neumann's alternating projections}},
  year = {2022},
  eprint = {2212.02933},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2212.02933},
}
Figure