Randomized Methods for Linear Constraints: Convergence Rates and Conditioning

References

• Akaike H. On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Statist. Math. (1959) 11:1–16Crossref, Google Scholar
• Amaldi E., Belotti P., Hauser R., Jünger M., Kaibel V. Randomized relaxation methods for the maximum feasible subsystem problem. Integer Programming and Combinatorial Optimization (2005) 3509(Springer-Verlag, Berlin) 249–264Lecture Notes in Computer ScienceCrossref, Google Scholar
• Amemiya I., Ando T. Convergence of random products of contractions in Hilbert space. Acta. Sci. Math. (1965) 26:239–244Google Scholar
• Bauschke H. H. A norm convergence result on random products of relaxed projections in Hilbert space. Trans. Amer. Math. Soc. (1995) 347:1365–1373Crossref, Google Scholar
• Bauschke H. H., Butnariu D., Censor Y., Reich S. Projection algorithms: Results and open problems. Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications (2001) (Elsevier, Amsterdam) 11–22Crossref, Google Scholar
• Bauschke H. H., Borwein J. M. On the convergence of von Neumann's alternating projection algorithm for two sets. Set-Valued Anal. (1993) 1:185–212Crossref, Google Scholar
• Bauschke H. H., Borwein J. M. On projection algorithms for solving convex feasibility problems. SIAM Rev. (1996) 38:367–426Crossref, Google Scholar
• Billingsley P.Probability and Measure (1986) (John Wiley & Sons, New York) Google Scholar
• Bruck R. E. Random products of contractions in metric and Banach spaces. J. Math. Anal. Appl. (1982) 88:319–332Crossref, Google Scholar
• Demmel J. W. On condition numbers and the distance to the nearest ill-posed problem. Numerische Mathematik (1987) 51:251–289Crossref, Google Scholar
• Demmel J. W. The probability that a numerical analysis problem is difficult. Math. Comput. (1988) 50:449–480Crossref, Google Scholar
• Deutsch F.Best Approximation in Inner Product Spaces (2001) (Springer-Verlag, New York) Crossref, Google Scholar
• Dontchev A. L., Lewis A. S., Rockafellar R. T. The radius of metric regularity. Trans. Amer. Math. Soc. (2003) 355:493–517Crossref, Google Scholar
• Dye J., Khamsi M. A., Reich S. Random products of contractions in Banach spaces. Trans. Amer. Math. Soc. (1991) 325:87–99Crossref, Google Scholar
• Eckart C., Young G. The approximation of one matrix by another of low rank. Psychometrika (1936) 1:211–218Crossref, Google Scholar
• Golub G., van Loan C.Matrix Computations (1996) (Johns Hopkins University Press, Baltimore) Google Scholar
• Gubin L. G., Polyak B. T., Raik E. V. The method of projections for finding the common point of convex sets. U.S.S.R. Comput. Math. Math. Phys. (1967) 7:1–24Crossref, Google Scholar
• Güler O., Hoffman A. J., Rothblum U. Approximations to solutions to systems of linear inequalities. SIAM J. Matrix Anal. Appl. (1995) 16:688–696Crossref, Google Scholar
• Ho J. C. K., Tunçel L. Reconciliation of various complexity and condition measures for linear programming problems and a generalization of Tardos' theorem. Foundations Comput. Math.: Proc. Smalefest 2000 (2002) (World Scientific, Singapore) 93–148Crossref, Google Scholar
• Hoffman A. J. On approximate solutions of systems of linear inequalities. J. Res. National Bureau Standards (1952) 49:263–265Crossref, Google Scholar
• Horn R., Johnson C.Matrix Analysis (1999) (Cambridge University Press, Cambridge, UK) Google Scholar
• Leventhal D. Metric subregularity and the proximal point method. J. Math. Anal. Appl. (2009) 360:681–688Crossref, Google Scholar
• Lewis A. S., Luke D. R., Malick J. Local convergence for alternating and averaged nonconvex projections. Foundations Comput. Math. (2009) 9:485–513Crossref, Google Scholar
• Li W. The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program. Linear Algebra Appl. (1993) 187:15–40Crossref, Google Scholar
• Luo Z.-Q. On the convergence of the LMS algorithm with adaptive learning rate for linear feedback networks. Neural Comput. (1991) 3:226–245Crossref, Google Scholar
• Luo Z.-Q., Tseng P. On the convergence of the coordinate descent method for convex differentiable minimization. J. Optim. Theory Appl. (1992a) 72:7–35Crossref, Google Scholar
• Luo Z.-Q., Tseng P. On the linear convergence of descent methods for convex essentially smooth minimization. SIAM J. Control Optim. (1992b) 30:408–425Crossref, Google Scholar
• Luo Z.-Q., Tseng P. Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem. SIAM J. Optim. (1992c) 2:43–54Crossref, Google Scholar
• Luo Z.-Q., Tseng P. Error bound and reduced gradient projection algorithms for convex minimization over a polyhedral set. SIAM J. Optim. (1993a) 3:43–59Crossref, Google Scholar
• Luo Z.-Q., Tseng P. On the convergence rate of dual ascent methods for strictly convex minimization. Math. Oper. Res. (1993b) 18:846–867Link, Google Scholar
• Luo Z.-Q., Tseng P. Error bounds and convergence analysis of feasible descent methods: A general approach. Ann. Oper. Res. (1993c) 46:157–178Crossref, Google Scholar
• Luo Z.-Q., Tseng P. Analysis of an approximate gradient projection method with applications to the back propagation algorithm. Optim. Methods Software (1994) 4:85–101Crossref, Google Scholar
• Nesterov Y. Efficiency of coordinate descent methods on huge-scale optimization problems. (2010) . CORE Discussion Paper 2010/2, Université Catholique de Louvain, Center for Operations Research and Economics, Louvain-la-Neuve, BelgiumGoogle Scholar
• Ng K. F., Zheng X. Y. Hoffman's least error bounds for linear inequalities. J. Global Optim. (2004) 30:391–403Crossref, Google Scholar
• Pang J.-S. Error bounds in mathematical programming. Math. Programming (1997) 79:299–332Crossref, Google Scholar
• Pierra G. Decomposition through formalization in a product space. Math. Programming (1984) 28:96–115Crossref, Google Scholar
• Polyak B. T., Butnariu D., Censor Y., Reich S. Random algorithms for solving convex inequalities. Inherently Parallel Algorithms in Feasibility and Other Applications (2001) (Elsevier, Amsterdam) Crossref, Google Scholar
• Quarteroni A., Sacco R., Saleri F.Numerical Mathematics (2007) (Springer-Verlag, New York) Google Scholar
• Renegar J. Perturbation theory for linear programming. Math. Programming (1994) 65:73–91Crossref, Google Scholar
• Renegar J. Incorporating conditions measures into the complexity theory of linear programming. SIAM J. Optim. (1995a) 5:506–524Crossref, Google Scholar
• Renegar J. Linear programming, complexity theory and elementary functional analysis. Math. Programming (1995b) 70:279–351Crossref, Google Scholar
• Rockafellar R. T., Wets R. J.-B.Variational Analysis (1998) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Strohmer T., Vershynin R. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. (2009) 15:262–278Crossref, Google Scholar
• Tseng P. On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math. (1995) 60:237–252Crossref, Google Scholar
• Zhang S. Global error bounds for convex conic problems. SIAM J. Optim. (2000) 10:836–851Crossref, Google Scholar