A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming
arXiv:1507.07624
Abstract
In this paper, we consider large-scale linearly constrained composite convex optimization problem, whose objective is a sum of a smooth function and a possibly nonsmooth function. We propose a scalable \textbf{F}rank-\textbf{W}olfe based \textbf{A}ugmented \textbf{L}agrangian (FW-AL) method for solving this problem. At each iteration, the proposed FW-AL method employs the FW method (or its variants) to approximately solve the AL subproblem {(with fixed Lagrange multiplier)} within a preselected tolerance and then updates the Lagrange multiplier. The proposed FW-AL method is well suitable for solving large-scale problems, because its computational cost per step scales (essentially) linearly with the size of the input. We analyze the non-ergodic convergence rate of the proposed FW-AL method.
This paper has been withdrawn by the author due to some errors in numerical results
References in corpus (7)
- On the Linear Convergence of the Alternating Direction Method of Multipliers
- On the Global Linear Convergence of the ADMM with Multi-Block Variables
- Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
- Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions
- The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
- A Primal-Dual Algorithmic Framework for Constrained Convex Minimization
- On the von Neumann and Frank-Wolfe Algorithms with Away Steps