An Extension of Chubanov's Polynomial-Time Linear Programming Algorithm to Second-Order Cone Programming

2016/11/07 by Tomonari Kitahara, Takashi Tsuchiya, Kitahara, Tomonari +1
Mathematics · Engineering · Computer Science · #Advanced Optimization Algorithms Research #Advanced Control Systems Optimization #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.1611.01898

Abstract

Recently, Chubanov proposed an interesting new polynomial-time algorithm for linear program. In this paper, we extend his algorithm to second-order cone programming.

Related

• On Chubanov's method for Linear Programming
• A polynomial projection-type algorithm for linear programming
• A Quadratically Convergent Sequential Programming Method for Second-Order Cone Programs Capable of Warm Starts
• An oracle-based projection and rescaling algorithm for linear semi-infinite feasibility problems and its application to SDP and SOCP
• An extension of Chubanov's algorithm to symmetric cones