×

zbMATH — the first resource for mathematics

An improved version of Chubanov’s method for solving a homogeneous feasibility problem. (English) Zbl 1398.90173
Summary: We deal with a recently proposed method of S. Chubanov [Math. Program. 153, No. 2 (A), 687–713 (2015; Zbl 1327.90102)] for solving linear homogeneous systems with positive variables. Some improvements of Chubanov’s method and its analysis are presented. We propose a new and simple cut criterion and show that the cuts defined by the new criterion are at least as sharp as in [Chubanov, loc. cit.]. The new cut criterion reduces the iteration bound for his Basic Procedure by a factor 5, without changing the order of its strongly polynomial complexity. Our Modified Main Algorithm is in essence the same as Chubanov’s Main Algorithm, except that it uses our Modified Basic Procedure as a subroutine. It is shown that it has \(O(n^4L)\) time complexity, just as in [Chubanov, loc. cit.]. Some promising computational results are presented, in comparison with the optimization package Gurobi.

MSC:
90C30 Nonlinear programming
Software:
Gurobi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chubanov, S., A polynomial projection algorithm for linear feasibility problems, Math. Program., 153, 687-713, (2015) · Zbl 1327.90102
[2] An ε-precise feasible solution to a linear program with a convexity constraint in\(##?##\)iterations, independent of problem size, Technical Report SOL 92-5, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, USA, October 1992
[3] Edmonds, J., systems of distinct representatives and linear algebra, J. Res. Natl. Bur. Stand. Sect. B, 71B, 241-245, (1967) · Zbl 0178.03002
[4] Epelman, M.; Freund, R.M., condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system, Math. Program., 88, 3, 451-485, (2000) · Zbl 0989.65061
[5] Golub, G.H.; Van Loan, C.F., Matrix Computations, (1989), Johns Hopkins University Press, Baltimore · Zbl 0733.65016
[6] Khachiyan, L.G., A polynomial algorithm in linear programming, Doklady Akademiia Nauk SSSR, 244, 1093-1096, (1979) · Zbl 0414.90086
[7] An extension of Chubanov polynomial-time linear programming algorithm to second-order cone programming, 2016. Manuscript
[8] The duality between the perception algorithm and the Von Neumann algorithm, in Modelling and Optimization: Theory and Applications, L. Zukuaga and T. Terlaky, eds., Springer Science+Business, New York, 2013, pp. 113-136
[9] A polynomial column-wise rescaling von Neumann algorithm,. Technical report 15T-010, Lehigh University, Bethlehem, USA, July 2015
[10] An extension of Chubanov’s algorithm to symmetric cones, 2017. Manuscript
[11] Solving conic systems via projection and rescaling, 2016. Manuscript
[12] Renegar, J., A polynomial-time algorithm, based on Newton’s method, for linear programming, Math. Program., 40, 59-93, (1988) · Zbl 0654.90050
[13] On Chubanov’s method for solving a homogeneous inequality system, in Numerical Analysis and Optimization. NAO-III, Muscat, Oman, January 2014, M. Al-Baali, L. Grandinetti, and A. Purnama, eds., 2015, Proceedings in Mathematics & Statistics. ISBN 978-3-319-17688-8, Springer, Switzerland, pp. 319-338 · Zbl 1330.65090
[14] Schrijver, A., Theory of Linear and Integer Programming, (1986), John Wiley & Sons, New York · Zbl 0665.90063
[15] Stiemke, E., über positive Lösungen homogener linearer gleichungen, Math. Ann., 76, 340-342, (1915) · JFM 45.0168.04
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.