Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

References

• Gondzio J, González-Brevis P, Munari P. New developments in the primal--dual column generation technique. Eur J Oper Res. 2013;224:41–51.
   Web of Science ®Google Scholar
• Mitchell JE. Polynomial interior point cutting plane methods. Optim Methods Softw. 2003;18:507–534.
   Web of Science ®Google Scholar
• Mitchell JE. Cutting plane methods and subgradient methods. In: Oskoorouchi M, editor. Tutorials in operations research, Chapter 2. Catonsville (MD): INFORMS; 2009. p. 34–61.
   Google Scholar
• Evtushenko YG, Golikov AI, Mollaverdy N. Augmented Lagrangian method for large-scale linear programming problems. Optim Methods Softw. 2005;20:515–524.
   Web of Science ®Google Scholar
• Güler O. Augmented Lagrangian algorithms for linear programming. J Optim Theory Appl. 1992;75:445–470.
   Web of Science ®Google Scholar
• Helmberg C, Rendl F. A spectral bundle method for semidefinite programming. SIAM J Optim. 2000;10:673–696.
   Web of Science ®Google Scholar
• Engau A. Recent progress in interior-point methods: cutting plane methods and warm starts. In: Anjos MF, Lasserre JB, editors. Handbook of semidefinite, conic, and polynomial optimization. Vol. 166, International series in operations research & management science, Chapter 17. New York (NY): Springer; 2012. p. 471–498.
   Google Scholar
• Engau A, Anjos MF, Vannelli A. On handling cutting-planes in interior-point methods for solving semidefinite relaxations of binary quadratic optimization problems. Optim Methods Softw. 2012;27:539–559.
   Web of Science ®Google Scholar
• Gruber G, Rendl F. Computational experience with stable set relaxations. SIAM J Optim. 2003;13:1014–1028.
   Web of Science ®Google Scholar
• Helmberg C, Rendl F. Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math Program Ser A. 1998;82:291–315.
   Web of Science ®Google Scholar
• Mitchell JE. Computational experience with an interior point cutting plane algorithm. SIAM J Optim. 2000;10:1212–1227.
   Web of Science ®Google Scholar
• El-Bakry AS, Tapia RA, Zhang Y. A study of indicators for identifying zero variables in interior-point methods. SIAM Rev. 1994;36:45–72.
   Web of Science ®Google Scholar
• Facchinei F, Fischer A, Kanzow C. On the identification of zero variables in an interior-point framework. SIAM J Optim. 2000;10:1058–1078.
   Web of Science ®Google Scholar
• Oberlin C, Wright SJ. Active set identification in nonlinear programming. SIAM J Optim. 2006;17:577–605.
   Web of Science ®Google Scholar
• Atkinson DS, Vaidya PM. A cutting plane algorithm for convex programming that uses analytic centers. Math Program Ser B. 1995;69:1–43.
   Web of Science ®Google Scholar
• Goffin J-L, Luo Z-Q, Ye Y. Complexity analysis of an interior cutting plane method for convex feasibility problems. SIAM J Optim. 1996;6:638–652.
   Web of Science ®Google Scholar
• Goffin J-L, Vial J-P. Multiple cuts in the analytic center cutting plane method. SIAM J Optim. 2000;11:266–288.
   Web of Science ®Google Scholar
• Luo Z-Q, Roos C, Terlaky T. Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming. Appl Numer Math. 1999;29:379–394.
   Web of Science ®Google Scholar
• He MY, Tits AL. Infeasible constraint-reduced interior-point methods for linear optimization. Optim Methods Softw. 2012;27:801–825.
   Web of Science ®Google Scholar
• Jung J, O’Leary D, Tits A. Adaptive constraint reduction for convex quadratic programming. Comput Optim Appl. 2012;51:125–157.
   Web of Science ®Google Scholar
• Tits AL, Absil P-A, Woessner WP. Constraint reduction for linear programs with many inequality constraints. SIAM J Optim. 2006;17:119–146.
   Web of Science ®Google Scholar
• Winternitz LB, Nicholls SO, Tits AL, et al. A constraint-reduced variant of Mehrotra’s predictor--corrector algorithm. Comput Optim Appl. 2012;51:1001–1036.
   Web of Science ®Google Scholar
• Winternitz LB, Tits AL, Absil P-A. Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization. J Optim Theory Appl. 2014;160:127–157.
   Web of Science ®Google Scholar
• Park S. Matrix reduction in numerical optimization [PhD thesis]. College Park (MD): University of Maryland; 2011.
   Google Scholar
• Park S, O’Leary DP. A polynomial time constraint-reduced algorithm for semidefinite optimization problems. J Optim Theory Appl. 2015;166:558–571.
   Web of Science ®Google Scholar
• Potra FA, Sheng R. A superlinearly convergent primal--dual infeasible-interior-point algorithm for semidefinite programming. SIAM J Optim. 1998;8:1007–1028.
   Web of Science ®Google Scholar
• Dantzig GB, Ye Y. A build-up interior method for linear programming: affine scaling form. Technical report, Stanford University/University of Iowa, USA; 1991.
   Google Scholar
• Kaliski JA, Ye Y. A short-cut potential reduction algorithm for linear programming. Manage Sci. 1993;39:757–776.
   Web of Science ®Google Scholar
• Tone K. An active-set strategy in an interior point method for linear programming. Math Program Ser A. 1993;59:345–360.
   Web of Science ®Google Scholar
• Engau A. Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology. Asia-Pac J Oper Res. 2014;31:1450022 (18 pages).
   Web of Science ®Google Scholar
• Engau A, Anjos MF, Bomze I. Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem. Math Methods Oper Res. 2013;78:35–59.
   Web of Science ®Google Scholar
• den Hertog D, Roos C, Terlaky T. Adding and deleting constraints in the logarithmic barrier method for LP. In: Du D-Z, Sun J, editors. Advances in optimization and approximation. Vol. 1, Nonconvex optimization and its applications. Dordrecht: Kluwer Academic; 1994. p. 166–185.
   Google Scholar
• Engau A, Anjos MF, Vannelli A. On interior-point warmstarts for linear and combinatorial optimization. SIAM J Optim. 2010;20:1828–1861.
   Web of Science ®Google Scholar
• Gondzio J, Grothey A. Reoptimization with the primal--dual interior point method. SIAM J Optim. 2002;13:842–864.
   Web of Science ®Google Scholar
• Skajaa A, Andersen ED, Ye Y. Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems. Math Program Comput. 2013;5:1–25.
   Google Scholar
• Wright SJ. Primal--dual interior-point methods. Philadelphia (PA): Society for Industrial and Applied Mathematics (SIAM); 1997.
   Google Scholar
• Mizuno S, Todd MJ, Ye Y. On adaptive-step primal--dual interior-point algorithms for linear programming. Math Oper Res. 1993;18:964–981.
   Web of Science ®Google Scholar
• Mizuno S. Polynomiality of infeasible-interior-point algorithms for linear programming. Math Program Ser A. 1994;67:109–119.
   Web of Science ®Google Scholar
• Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica. 1984;4:373–395.
   Web of Science ®Google Scholar
• Khachiyan LG. A polynomial algorithm in linear programming. Dokl Akad Nauk SSSR. 1979;244:1093–1096.
   Google Scholar
• Kojima M, Megiddo N, Mizuno S. A primal--dual infeasible-interior-point algorithm for linear programming. Math Program Ser A. 1993;61:263–280.
   Web of Science ®Google Scholar
• Mizuno S. A new polynomial time method for a linear complementarity problem. Math Program Ser A. 1992;56:31–43.
   Web of Science ®Google Scholar
• Kojima M, Mizuno S, Yoshise A. A polynomial-time algorithm for a class of linear complementarity problems. Math Program Ser A. 1989;44:1–26.
   Web of Science ®Google Scholar
• Kojima M, Mizuno S, Yoshise A. A primal--dual interior point algorithm for linear programming. In: Meggido N, editor. Progress in mathematical programming: Interior point and related methods (Pacific Grove, CA, 1987). New York (NY): Springer; 1989. p. 29–47.
   Google Scholar
• Monteiro RDC, Adler I. Interior path following primal--dual algorithms. I. Linear programming. Math Program Ser A. 1989;44:27–41.
   Web of Science ®Google Scholar
• Monteiro RDC, Adler I. Interior path following primal--dual algorithms. II. Convex quadratic programming. Math Program Ser A. 1989;44:43–66.
   Web of Science ®Google Scholar