Complexity of linear minimization and projection on some sets

DOI10.1016/J.ORL.2021.06.005OpenAlexW3170668484MaRDI QIDQ2060605

Sebastian Pokutta, Cyrille W. Combettes

Publication date: 13 December 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.10040

zbMATH Keywords

computational complexityconstrained optimizationprojectionFrank-Wolfe algorithmlinear minimization

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Related Items (5)

FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank–Wolfe Algorithms and Conditional Gradients ⋮ Riemannian optimization via Frank-Wolfe methods ⋮ The Frank-Wolfe algorithm: a short introduction ⋮ Some computable quasiconvex multiwell models in linear subspaces without rank-one matrices ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast projection onto the simplex and the \(l_1\) ball
• The gap function of a convex program
• Conditional gradient algorithms with open loop step size rules
• Lectures on Modern Convex Optimization
• Conditional Gradient Sliding for Convex Optimization
• A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion
• Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) in Hypre and PETSc
• Some comments on Wolfe's ‘away step’
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• ARPACK Users' Guide
• On Projection Algorithms for Solving Convex Feasibility Problems
• Strong Convergence of Block-Iterative Outer Approximation Methods for Convex Optimization
• Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions
• Sparse Approximate Solutions to Semidefinite Programs
• A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm
• Convex analysis and monotone operator theory in Hilbert spaces

This page was built for publication: Complexity of linear minimization and projection on some sets