A Conditional Gradient-Based Augmented Lagrangian Framework

2019/01/13 by Alp Yurtsever, Yurtsever, Alp, Olivier Fercoq +3 · 4 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1901.04013

openalex publication_date 2019/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper considers a generic convex minimization template with affine constraints over a compact domain, which covers key semidefinite programming applications. The existing conditional gradient methods either do not apply to our template or are too slow in practice. To this end, we propose a new conditional gradient method, based on a unified treatment of smoothing and augmented Lagrangian frameworks. The proposed method maintains favorable properties of the classical conditional gradient method, such as cheap linear minimization oracle calls and sparse representation of the decision variable. We prove O(1/√(k)) convergence rate of our method in the objective residual and the feasibility gap. This rate is essentially the same as the state of the art CG-type methods for our problem template, but the proposed method is significantly superior to existing methods in various semidefinite programming applications.

Citations

• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Smooth minimization of non-smooth functions

Cited by

• Locally Linear Convergence for Nonsmooth Convex Optimization via Coupled Smoothing and Momentum
• Quantum-enhanced Computer Vision: Going Beyond Classical Algorithms
• An Inexact Tensor-Train Primal-Dual Interior-Point Method for Semidefinite Programs
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics

Related

• A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming
• Blended Conditional Gradients: the unconditioning of conditional gradients
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
• Conditional Gradient Methods
• The Augmented Lagrangian Methods: Overview and Recent Advances