  


Solving SDP Completely with an Interior Point Oracle
Bruno F. Lourenco (flourenco.b.aam.titech.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 (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 06/30/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  