Ellipsoid Separation in Data-Dependent Time via Infimal Displacement Vectors
math.OC
Submitted: 2026-10-24
Updated: 2026-10-24
License: http://creativecommons.org/licenses/by/4.0/
The gist: The infimal displacement vector of the nonexpansive operator underlying the primal-dual hybrid gradient algorithm (PDHG) is known to encode useful information for infeasible optimization problems.
Abstract
The infimal displacement vector of the nonexpansive operator underlying the primal-dual hybrid gradient algorithm (PDHG) is known to encode useful information for infeasible optimization problems. In particular, for the ellipsoid separation problem (ESP), where the goal is to find a separating hyperplane between two collections of ellipsoids, the infimal displacement vector corresponding to an infeasible second-order cone program (SOCP) encodes a separating hyperplane. We show FISTA computes a sequence of approximations to the dual component of the infimal displacement vector and establish that a solution to the ESP can be obtained in O(δ A-2) iterations. Here δ A denotes the distance between the convex hulls of the two ellipsoid collections.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise