convex-concave saddle point problems

Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems

Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely on smoothing, our methods are purely subgradient-based and handle nonsmoothness directly. This design makes … Read more

A Primal-Dual Frank-Wolfe Algorithm for Linear Programming

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

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

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