An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming. (2nd January 2018)

• Record Type: Journal Article
• Authors: Kitahara, T.; Tsuchiya, T.
• Is Part Of: Optimization methods and software. Volume 33:Number 1(2018)
• Page Start: 1
• Page End: 25
• Publication Date: 2018-01-02
• Subjects: Chubanov's algorithm -- linear programming -- second-order cone programming; 65K05 -- 65K10; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1382495
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In this paper, we extend Chubanov's new polynomial-time algorithm for linear programming to second-order cone programming based on the idea of cutting plane method. The algorithm finds an -dimensional vector x which satisfies, where and is a direct product of n second-order cones and half lines. Like Chubanov's algorithm, one iteration of the proposed algorithm consists of two phases: execution of a basic procedure and scaling. Within calls of the basic procedure, the algorithm either (i) finds an interior feasible solution, (ii) finds a non-zero dual feasible solution, or (iii) verifies that there is no interior feasible solution whose minimum eigenvalue is greater than or equal to ϵ . Each basic procedure requires arithmetic operations, where is the dimension of each second-order cone. If the problem is interior feasible, then the algorithm finds an interior feasible solution in calls of the basic procedure, where is a condition number associated with the system.