subgradient method

Approximate Primal Solutions and Rate Analysis in Dual Subgradient Methods

  • Angelia Nedich
  • Asuman Ozdaglar
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We study primal solutions obtained as a by-product of subgradient methods when solving the Lagrangian dual of a primal convex constrained optimization problem (possibly nonsmooth). The existing literature on the use of subgradient methods for generating primal optimal solutions is limited to the methods producing such solutions only asymptotically (i.e., in the limit as the … Read more

    A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations

  • Christoph Helmberg
    • Categories Cutting Plane Approaches, Nonsmooth Optimization, Semi-definite Programming Tags , , , , , ,

    The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges … Read more