On the von Neumann and Frank--Wolfe Algorithms with Away Steps

DOI10.1137/15M1009937zbMath1382.90071arXiv1507.04073MaRDI QIDQ2789610

Daniel J. Rodríguez, Negar Soheili, Javier F. Peña

Publication date: 2 March 2016

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

linear convergencevon Neumanncoordinate descentFrank-Wolfeaway steps

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Quadratic programming (90C20) Methods of reduced gradient type (90C52)

Related Items (8)

Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning ⋮ Solving conic systems via projection and rescaling ⋮ An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion ⋮ The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes ⋮ Rescaling Algorithms for Linear Conic Feasibility ⋮ The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential ⋮ Polytope Conditioning and Linear Convergence of the Frank–Wolfe Algorithm ⋮ First-order methods for the convex hull membership problem

Cites Work

• Unnamed Item
• Unnamed Item
• On strata of degenerate polyhedral cones. I: Condition and distance to strata
• A randomized Kaczmarz algorithm with exponential convergence
• Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
• Linear programming, complexity theory and elementary functional analysis
• Linearly convergent away-step conditional gradient for non-strongly convex functions
• Condition
• A Primal–Dual Smooth Perceptron–von Neumann Algorithm
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• The Perceptron: A Model for Brain Functioning. I
• A family of linear programming algorithms based on an algorithm by von Neumann
• Some comments on Wolfe's ‘away step’
• The Relaxation Method for Solving Systems of Linear Inequalities
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• The Duality Between the Perceptron Algorithm and the von Neumann Algorithm
• Coresets for polytope distance
• An Iterative Procedure for Computing the Minimum of a Quadratic Form on a Convex Set
• A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
• A new condition number for linear programming

This page was built for publication: On the von Neumann and Frank--Wolfe Algorithms with Away Steps