An oracle-based projection and rescaling algorithm for linear semi-infinite feasibility problems and its application to SDP and SOCP

2018/09/27 by Masakazu Muramatsu, Muramatsu, Masakazu, Tomonari Kitahara +7
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.1809.10340

openalex publication_date 2018/09/27 · openalex created_date 2018/10/05 · openalex updated_date 2026/07/28

Abstract

We point out that Chubanov's oracle-based algorithm for linear programming [5] can be applied almost as it is to linear semi-infinite 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 second-order cone programming (SOCP) into LSIP, and apply our algorithm to obtain new complexity results for computing interior feasible solutions of homogeneous SDP and SOCP.

Related

• Post-Processing with Projection and Rescaling Algorithms for Semidefinite Programming
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
• A Globally Convergent LP and SOCP-based algorithm for Semidefinite Programming
• A Fast Polynomial-time Primal-Dual Projection Algorithm for Linear Programming
• Semidefinite programming relaxations for linear semi-infinite polynomial programming