  


An oraclebased projection and rescaling algorithm for linear semiinfinite feasibility problems and its application to SDP and SOCP
Masakazu Muramatsu(MasakazuMuramatsuuec.ac.jp) Abstract: We point out that Chubanov’s oraclebased algorithm for linear programming [5] can be applied almost as it is to linear semiinfinite programming (LSIP). In this note, we describe the details and prove the polynomial complexity of the algorithm based on the real computation model proposed by Blum, Shub and Smale (the BSS model) which is more suitable for floating point computation in modern computers. The adoption of the BBS model makes our description and analysis much simpler than the original one by Chubanov [5]. Then we reformulate semidefinite programming (SDP) and secondorder cone programming (SOCP) into LSIP, and apply our algorithm to obtain new complexity results for computing interior feasible solutions of homogeneous SDP and SOCP. Keywords: Linear semiinfinite programming, Projection and rescaling algorithm, Oraclebased algo rithm, Semidefinite programming. Category 1: Linear, Cone and Semidefinite Programming Category 2: Infinite Dimensional Optimization (Semiinfinite Programming ) Citation: Department of Computer and Network Engineering, The University of ElectroCommunications. Download: [PDF] Entry Submitted: 09/26/2018 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  