duality gap

New Penalized Stochastic Gradient Methods for Linearly Constrained Strongly Convex Optimization

  • Meng Li
  • Paul Grigas
  • Alper Atamturk
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , ,

    For minimizing a strongly convex objective function subject to linear inequality constraints, we consider a penalty approach that allows one to utilize stochastic methods for problems with a large number of constraints and/or objective function terms. We provide upper bounds on the distance between the solutions to the original constrained problem and the penalty reformulations, … Read more

    A simplified treatment of Ramana’s exact dual for semidefinite programming

  • Bruno F. Lourenço
  • Gabor Pataki
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    In semidefinite programming the dual may fail to attain its optimal value and there could be a duality gap, i.e., the primal and dual optimal values may differ. In a striking paper, Ramana proposed a polynomial size extended dual that does not have these deficiencies and yields a number of fundamental results in complexity theory. … Read more