Efficient First-Order Methods for Linear Programming and Semidefinite Programming

Understand

We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations.

• The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable.
• We observe, moreover, that the objective function is naturally smoothed, thereby allowing most first-order methods to be applied.
• We develop complexity bounds in the unsmoothed case for a particular subgradient method, and in the smoothed case for Nesterov's original optimal first-order method for smooth functions.