Scalable Projection-Free Optimization Methods via MultiRadial Duality Theory

2024/03/20 by Thabo Samakhoana, Benjamin Grimmer, Samakhoana, Thabo +1 · 2 citations
Computer Science · #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2403.13688

openalex publication_date 2024/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recent works have developed new projection-free first-order methods based on utilizing linesearches and normal vector computations to maintain feasibility. These oracles can be cheaper than orthogonal projection or linear optimization subroutines but have the drawback of requiring a known strictly feasible point to do these linesearches with respect to. In this work, we develop new theory and algorithms which can operate using these cheaper linesearches while only requiring knowledge of points strictly satisfying each constraint separately. Convergence theory for several resulting ``multiradial'' gradient methods is established. We also provide preliminary numerics showing performance is essentially independent of how one selects the reference points for synthetic quadratically constrained quadratic programs.

Cited by

• Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets
• The Optimal Smoothings of Sublinear Functions and Convex Cones

Related

• Radial Duality Part II: Applications and Algorithms
• Projected Gradient Methods with Momentum
• Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems
• First-Order Projected Algorithms With the Same Linear Convergence Rate Bounds as Their Unconstrained Counterparts
• A Primal-Dual Type Algorithm with the O(1/t) Convergence Rate for Large Scale Constrained Convex Programs