Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems

References

• [1] Belloni A, Freund R, Vempala S (2009) An efficient rescaled perceptron algorithm for conic systems. Math. Oper. Res. 34(3):621–641.Link, Google Scholar
• [2] Betke U (2004) Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput. Geometry 32:317–338.Crossref, Google Scholar
• [3] Bürgisser P, Cucker F (2013) Condition.] (Springer, Berlin).Crossref, Google Scholar
• [4] Cheung D, Cucker F (2001) A new condition number for linear programming. Math. Programming 91(2):163–174.Crossref, Google Scholar
• [5] Chubanov S (2012) A strongly polynomial algorithm for linear systems having a binary solution. Math. Programming 134(2):533–570.Crossref, Google Scholar
• [6] Chubanov S (2015) A polynomial projection algorithm for linear feasibility problems. Math. Programming 153(2):687–713.Crossref, Google Scholar
• [7] Dadush D, Végh LA, Zambelli G (2016) Rescaled coordinate descent methods for linear programming. Internat. Conf. Integer Programming Combin. Optim. (Springer), 26–37.Google Scholar
• [8] Dadush D, Végh LA, Zambelli G (2020) Rescaling algorithms for linear conic feasibility. Math. Oper. Res. 45(2):732–754.Link, Google Scholar
• [9] Dunagan J, Vempala S (2006) A simple polynomial-time rescaling algorithm for solving linear programs. Math. Programming 114(1):101–114.Crossref, Google Scholar
• [10] Epelman M, Freund RM (2000) Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system. Math. Programming 88(3):451–485.Crossref, Google Scholar
• [11] Freund R, Roundy R, Todd M (1985) Identifying the set of always-active constraints in a system of linear inequalities by a single linear program. Working paper, Massachusetts Institute of Technology, Cambridge.Google Scholar
• [12] Goffin J (1980) The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5(3):388–414.Link, Google Scholar
• [13] Gutman D, Peña J (2022) Perturbed Fenchel duality and first-order methods. Math. Programming Forthcoming.Google Scholar
• [14] Hoberg R, Rothvoss T (2017) An improved deterministic rescaling for linear programming algorithms. Internat. Conf. Integer Programming Combin. Optim. (Springer), 267–278.Google Scholar
• [15] Kitahara T, Tsuchiya T (2018) An extension of Chubanov’s polynomial-time linear programming algorithm to second-order cone programming. Optim. Methods Software 33(1):1–25.Crossref, Google Scholar
• [16] Lourenço B, Kitahara T, Muramatsu M, Tsuchiya T (2016) An extension of Chubanov’s algorithm to symmetric cones. Math. Programming 173(1–2):117–149.Crossref, Google Scholar
• [17] Peña J, Soheili N (2016) A deterministic rescaled perceptron algorithm. Math. Programming 155(1–2):497–510.Crossref, Google Scholar
• [18] Peña J, Soheili N (2017) Solving conic systems via projection and rescaling. Math. Programming 166(1–2):87–111.Crossref, Google Scholar
• [19] Peña J, Soheili N (2019) Computational performance of a projection and rescaling algorithm. Optim. Methods Software, ePub ahead of print May 1, https://doi.org/10.1080/10556788.2019.1615910.Google Scholar
• [20] Peña J, Roshchina V, Soheili N (2014) Some preconditioners for systems of linear inequalities. Optim. Lett. 8(7):2145–2152.Crossref, Google Scholar
• [21] Roos C (2018) An improved version of Chubanov’s method for solving a homogeneous feasibility problem. Optim. Methods Software 33(1):26–44.Crossref, Google Scholar
• [22] Soheili N, Peña J (2012) A smooth perceptron algorithm. SIAM J. Optim. 22(2):728–737.Crossref, Google Scholar
• [23] Ye Y (1994) Toward probabilistic analysis of interior-point algorithms for linear programming. Math. Oper. Res. 19(1):38–52.Link, Google Scholar