Optimization Online


Solving SDP Completely with an Interior Point Oracle

Bruno F. Lourenco (bruno***at***ism.ac.jp)
Masakazu Muramatsu (muramatu***at***cs.uec.ac.jp)
Takashi Tsuchiya (tsuchiya***at***grips.ac.jp)

Abstract: 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 how to use such an oracle to "completely solve" an arbitrary SDP. Completely solving an SDP, includes, for example, distinguishing between weak/strong feasibility/infeasibility and detecting when the optimal value is attained or not. We will employ several tools, including a variant of facial reduction where all auxiliary problems are ensured to satisfy Slater's condition at all sides. Our main technical innovation, however, is an analysis of double facial reduction, which is the process of applying facial reduction twice: first to the original problem and then once more to the dual of the regularized problem obtained during the first run. Although our discussion is focused on semidefinite programming, the majority of the results are proved for general convex cones

Keywords: double facial reduction, facial reduction, semidefinite programming, feasibility problem

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 06/30/2015
Entry Accepted: 06/30/2015
Entry Last Modified: 11/11/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society