facial reduction

Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach

  • Erling D. Andersen
  • Henrik A. Friberg
  • Frank Permenter
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We establish connections between the facial reduction algorithm of Borwein and Wolkowicz and the self-dual homogeneous model of Goldman and Tucker when applied to conic optimization problems. Specifically, we show the self-dual homogeneous model returns facial reduction certificates when it fails to return a primal-dual optimal solution or a certificate of infeasibility. Using this observation, … Read more

    Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier

  • Dmitriy Drusvyatskiy
  • Nathan Krislock
  • Henry Wolkowicz
  • Y.-L. Voronin
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    We present two algorithms for large-scale low-rank Euclidean distance matrix completion problems, based on semidefinite optimization. Our first method works by relating cliques in the graph of the known distances to faces of the positive semidefinite cone, yielding a combinatorial procedure that is provably robust and parallelizable. Our second algorithm is a first order method … Read more

    Solving SDP Completely with an Interior Point Oracle

  • Bruno F. Lourenço
  • Masakazu Muramatsu
  • Takashi Tsuchiya
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    We suppose the existence of an oracle which solves any semidefinite programming (SDP) problem satisfying Slater’s condition simultaneously at its primal and dual sides. We note that such an oracle might not be able to directly solve general SDPs even after certain regularization schemes are applied. In this work we fill this gap and show … Read more

    Coordinate shadows of semi-definite and Euclidean distance matrices

  • Dmitriy Drusvyatskiy
  • Gabor Pataki
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider the projected semi-definite and Euclidean distance cones onto a subset of the matrix entries. These two sets are precisely the input data defining feasible semi-definite and Euclidean distance completion problems. We characterize when these sets are closed, and use the boundary structure of these two sets to elucidate the Krislock-Wolkowicz facial reduction algorithm. … Read more

    Facial reduction algorithms for conic optimization problems

  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Convex Optimization, Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags ,

    To obtain a primal-dual pair of conic programming problems having zero duality gap, two methods have been proposed: the facial reduction algorithm due to Borwein and Wolkowicz [1,2] and the conic expansion method due to Luo, Sturm, and Zhang [5]. We establish a clear relationship between them. Our results show that although the two methods … Read more