convex-concave saddle point problems

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 … Read more

    Solving large scale polynomial convex problems on \ell_1/nuclear norm balls by randomized first-order algorithms

  • Aharon Ben-Tal
  • Arkadi Nemirovski
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast First Order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when … Read more