Frank-Wolfe algorithm

Voronoi Conditional Gradient Method for Constrained Nonconvex Optimization

  • Abbas Khademi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    The Conditional Gradient method offers a computationally efficient, projection-free framework for constrained problems; however, in nonconvex settings it may converge to stationary points of low quality. We propose the Voronoi Conditional Gradient (VCG) method, a geometric heuristic that systematically explores the feasible region by constructing adaptive Voronoi partitions from previously discovered stationary points. VCG incrementally … Read more

    The Proximal Bundle Algorithm Under a Frank-Wolfe Perspective: an Improved Complexity Analysis

  • David Fersztand
  • Xu Andy Sun
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    The proximal bundle algorithm (PBA) is a fundamental and computationally effective algorithm for solving optimization problems with nonsmooth components. We investigate its convergence rate, focusing on composite settings where one function is smooth and the other is piecewise linear. We interpret a sequence of null steps of the PBA as a Frank-Wolfe algorithm on the … Read more

    Projection onto hyperbolicity cones and beyond: a dual Frank-Wolfe approach

  • Takayuki Nagano
  • Bruno F. Lourenço
  • Akiko Takeda
    • Categories Cone Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We discuss the problem of projecting a point onto an arbitrary hyperbolicity cone from both theoretical and numerical perspectives. While hyperbolicity cones are furnished with a generalization of the notion of eigenvalues, obtaining closed form expressions for the projection operator as in the case of semidefinite matrices is an elusive endeavour. To address that we … Read more

    A Unified Approach for Maximizing Continuous $\gamma$-weakly DR-submodular Functions

  • Mohammad Pedramfar
  • Christopher Quinn
  • Vaneet Aggarwal
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , ,

    This paper presents a unified approach for maximizing continuous \(\gamma\)-weakly DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the convex feasible region. We consider settings where the oracle provides access to either the … Read more

    A Primal-Dual Frank-Wolfe Algorithm for Linear Programming

  • Matthew Hough
  • Stephen A. Vavasis
    • Categories Linear Programming Tags , , ,

    We present two first-order primal-dual algorithms for solving saddle point formulations of linear programs, namely FWLP (Frank-Wolfe Linear Programming) and FWLP-P. The former iteratively applies the Frank-Wolfe algorithm to both the primal and dual of the saddle point formulation of a standard-form LP. The latter is a modification of FWLP in which regularizing perturbations are … Read more

    A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach

  • Renato D.C. Monteiro
  • Arnesh Sujanani
  • Diego Cifuentes
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , , ,

    This paper introduces HALLaR, a new first-order method for solving large-scale semidefinite programs (SDPs) with bounded domain. HALLaR is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a novel hybrid low-rank (HLR) method. The recipe behind HLR is based on two key ingredients: 1) an adaptive inexact proximal point method … Read more

    Nonlinear Distributionally Robust Optimization

  • Rayyan
  • Peyman Mohajerin Esfahani
    • Categories Infinite Dimensional Optimization, Optimization in Data Science, Robust Optimization Tags , ,

    This article focuses on a class of distributionally robust optimization (DRO) problems where, unlike the growing body of the literature, the objective function is potentially non-linear in the distribution. Existing methods to optimize nonlinear functions in probability space use the Frechet derivatives, which present both theoretical and computational challenges. Motivated by this, we propose an … Read more

    On a Frank-Wolfe Approach for Abs-smooth Functions

  • Timo Kreimeier
  • Sebastian Pokutta
  • Andrea Walther
  • Zev Woodstock
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Other Topics Tags , , , ,

    We propose an algorithm which appears to be the first bridge between the fields of conditional gradient methods and abs-smooth optimization. Our problem setting is motivated by various applications that lead to nonsmoothness, such as $\ell_1$ regularization, phase retrieval problems, or ReLU activation in machine learning. To handle the nonsmoothness in our problem, we propose … Read more