Simon P. Schurr

Preprocessing and Reduction for Degenerate Semidefinite Programs

  • Yuen-Lam Cheung
  • Simon P. Schurr
  • Henry Wolkowicz
    • Categories Optimization Software and Modeling Systems, Semi-definite Programming Tags , , ,

    This paper presents a backward stable preprocessing technique for (nearly) ill-posed semidefinite programming, SDP, problems, i.e.,~programs for which Slater’s constraint qualification, existence of strictly feasible points, (nearly) fails. Current popular algorithms for semidefinite programming rely on \emph{primal-dual interior-point, p-d i-p} methods. These algorithms require Slater’s constraint qualification for both the primal and dual problems. This … Read more

    A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations

  • Dianne P. O'Leary
  • Simon P. Schurr
  • AndrĂ© L. Tits
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this work we develop a primal-dual short-step interior point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the barrier function is either impossible or too expensive. As our main contribution, we show that if approximate gradients and Hessians can be computed, and the relative errors in … Read more

    Universal Duality in Conic Convex Optimization

  • Dianne P. O'Leary
  • Simon P. Schurr
  • AndrĂ© L. Tits
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +infinity and -infinity. In contrast, for optimization problems over nonpolyhedral convex cones, … Read more