Optimization Online


Solving SDP Completely with an Interior Point Oracle

Bruno F. Lourenco (flourenco.b.aa***at***m.titech.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 is able to solve any semidefinite programming (SDP) problem having interior feasible points at both 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 such as facial reduction or Ramana's dual are applied. The main objective of this work is to fill this gap and to show in detail how one can use such an oracle to 'completely solve' an arbitrary SDP. Here, we use the term completely solve an SDP to mean a scheme which works in the following way; given an SDP, the scheme checks whether it is feasible or not, and whenever feasible, computes its optimal value, and if the optimal value is attained, obtains a maximal rank optimal solution. If the optimal value is not attained, computes a feasible solution whose objective value is arbitrarily close to the optimal value. Moreover, if the original SDP is infeasible, it distinguishes between strong and weak infeasibility, and in the case of weak infeasibility, can compute a point in the corresponding affine space whose distance to the positive semidefinite cone is less than an arbitrary small given positive number.

Keywords: Conic linear programming; semidefinite programming; interior point oracle

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/16/2015

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