Rescaling Algorithms for Linear Conic Feasibility

References

• [1] Agmon S (1954) The relaxation method for linear inequalities. Canadian J. Math. 6(3):382–392.Crossref, Google Scholar
• [2] Basu A, Loera JAD, Junod M (2013) On Chubanov’s method for linear programming. INFORMS J. Comput. 26(2):336–350.Link, Google Scholar
• [3] Belloni A, Freund RM, Vempala S (2009) An efficient rescaled perceptron algorithm for conic systems. Math. Oper. Res. 34(3):621–641.Link, Google Scholar
• [4] Betke U (2004) Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput. Geometry 32(3):317–338.Crossref, Google Scholar
• [5] Blum L, Shub M, Smale S (1989) On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. 21(1):1–46.Google Scholar
• [6] Chubanov S (2011) A polynomial relaxation-type algorithm for linear programming. Working paper, Bosch Center for Artificial Intelligence, Siegen, Germany.Google Scholar
• [7] Chubanov S (2012) A strongly polynomial algorithm for linear systems having a binary solution. Math. Programming 134(2):533–570.Crossref, Google Scholar
• [8] Chubanov S (2015) A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions. Working paper, Bosch Center for Artificial Intelligence, Siegen, Germany.Google Scholar
• [9] Chubanov S (2015) A polynomial projection algorithm for linear feasibility problems. Math. Programming 153(2):687–713.Crossref, Google Scholar
• [10] Chubanov S (2017) A polynomial algorithm for linear feasibility problems given by separation oracles. Working paper, Bosch Center for Artificial Intelligence, Siegen, Germany.Google Scholar
• [11] Dadush D, Végh LA, Zambelli G (2016) Rescaled coordinate descent methods for linear programming. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming Combin. Optim. (Springer-Verlag, Berlin), 26–37.Google Scholar
• [12] Dadush D, Végh LA, Zambelli G (2018) Geometric rescaling algorithms for submodular function minimization. Czumaj A, ed. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 832–848.Google Scholar
• [13] Dantzig GB (1991) Converting a converging algorithm into a polynomially bounded algorithm. Technical report, Stanford University, Stanford, CA.Google Scholar
• [14] Dantzig GB (1992) An ε-precise feasible solution to a linear program with a convexity constraint in 1/ε2 iterations independent of problem size. Technical Report 92-5, Stanford University, Stanford, CA.Google Scholar
• [15] Dunagan J, Vempala S (2008) A simple polynomial-time rescaling algorithm for solving linear programs. Math. Programming 114(1):101–114.Crossref, Google Scholar
• [16] 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
• [17] Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• [18] Goffin J (1980) The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5(3):388–414.Link, Google Scholar
• [19] Grötschel M, Lovász L, Schrijver A (2012) Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2 (Springer-Verlag, Berlin Heidelberg).Google Scholar
• [20] Hoberg R, Rothvoss T (2017) An improved deterministic rescaling for linear programming algorithms. Eisenbrand F, Koenemann J, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 10328 (Springer, Cham, Switzerland), 267–278.Google Scholar
• [21] Li D, Terlaky T (2013) The duality between the perceptron algorithm and the von Neumann algorithm. Zuluaga L, Terlaky T, eds. Modeling and Optimization: Theory and Applications, Springer Proceedings in Mathematics & Statistics, vol. 62 (Springer, New York), 113–136.Crossref, Google Scholar
• [22] Li D, Roos C, Terlaky T (2015) A polynomial column-wise rescaling von Neumann algorithm. Working paper, Capital One, Plano, TX.Google Scholar
• [23] Motzkin T, Schoenberg I (1954) The relaxation method for linear inequalities. Canadian J. Math. 6(3):393–404.Crossref, Google Scholar
• [24] Nemirovski A (2004) Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1):229–251.Crossref, Google Scholar
• [25] Nesterov Y (2005) Smooth minimization of non-smooth functions. Math. Programming 103(1):127–152.Crossref, Google Scholar
• [26] Novikoff AB (1962) On convergence proofs for perceptrons. Proc. Sympos. Math. Theory Automata (Polytechnic Institute of Brooklyn, New York), 615–622.Google Scholar
• [27] Peña J, Soheili N (2016) A deterministic rescaled perceptron algorithm. Math. Programming 155(1–2):497–510.Crossref, Google Scholar
• [28] Peña J, Soheili N (2017) Solving conic systems via projection and rescaling. Math. Programming 166(1–2):87–111.Crossref, Google Scholar
• [29] Peña J, Rodriguez D, Soheili N (2016) On the von Neumann and Frank–Wolfe algorithms with away steps. SIAM J. Optim. 26(1):499–512.Crossref, Google Scholar
• [30] Roos K (2015) On Chubanov’s method for solving a homogeneous inequality system. Al-Baali M, Grandinetti L, Purnama A, eds. Numerical Analysis and Optimization, Springer Proceedings in Mathematics & Statistics, vol. 134 (Springer, Cham, Switzerland), 319–338.Crossref, Google Scholar
• [31] Rosenblatt F (1958) The perceptron: A probabilistic model for information storage and organization in the brain. Psych. Rev. 65(6):386–408.Crossref, Google Scholar
• [32] Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• [33] Soheili N, Peña J (2012) A smooth perceptron algorithm. SIAM J. Optim. 22(2):728–737.Crossref, Google Scholar
• [34] Vavasis SA, Ye Y (1995) Condition numbers for polyhedra with real number data. Oper. Res. Lett. 17(5):209–214.Crossref, Google Scholar
• [35] Végh LA, Zambelli G (2014) A polynomial projection-type algorithm for linear programming. Oper. Res. Lett. 42(1):91–96.Crossref, Google Scholar
• [36] Wolfe P (1976) Finding the nearest point in a polytope. Math. Programming 11(1):128–149.Crossref, Google Scholar
• [37] Ye Y (1994) Toward probabilistic analysis of interior-point algorithms for linear programming. Math. Oper. Res. 19(1):38–52.Link, Google Scholar
• [38] Yu AW, Kılınç-Karzan F, Carbonell JG (2014) Saddle points and accelerated perceptron algorithms. Proc. Machine Learn. Res. 32(2):1827–1835.Google Scholar