On optimality of Krylov's information when solving linear operator equations

DOI10.1016/0885-064X(91)90001-EMaRDI QIDQ1179025zbMATH OpenOpenAlexFDO

Authors Arkadi Nemirovski

Publication date 26 June 1992

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(91)90001-e

zbMATH Keywords

Chebyshev-type methodsKrylov's informationlinear operator equationsworst-case efficiency estimate

Mathematics Subject Classification ID

Equations and inequalities involving linear operators, with vector unknowns (47A50)

Review text

The paper deals with the optimality of Krylov's information in solving linear operator equations for certain problem classes. Let \(B\) be the space of bounded linear operators on an \(n\)-dimensional Hilbert space \(H\). The pair \((A,b)\in B\times H\) is called a problem associated with the linear equation \(Ax=b\), \(A\in B\), \(b\in H\). Suppose that the only information available during the solution process consists of \(b\) being known a priori and the fact that at each step any vector from \(H\) can be multiplied on our choice of \(A\). For a class \(U\) of problems and each method \(P\) that solves the problems from \(U\), let \(x_ P(k,A,b)\) denote the \(k\)th approximate solution found by the method when applied to the problem \((A,b)\). Then the worst-case efficiency estimate for the method with respect to \(U\) can be obtained via the \(k\)th approximates. Inturn, the best possible efficiency estimate can be established by considering the worst-case efficiencies for a family of methods. The paper establishes that if the number of steps \(k\) is not greater than \((n-3)/2\), then the best possible efficiency estimate corresponds to Chebyshev-type methods for a certain variety of problem classes. In particular, the most powerful (adaptive) information for these classes is the Krylov's information. It may be noted that the earlier results of Nemirovskij and Yudin (1983) and Chou (1987) show this information to be ``almost optimal.

Recommendations

• On the optimality of Krylov information
• Information-based complexity of linear operator equations
• On the Optimal Solution of Large Linear Systems
• Minimal residual algorithm and matrix-vector information

Cites work

• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• On the optimality of Krylov information

Cited in

(17)

• Information-based complexity of linear operator equations
• Minimal residual algorithm and matrix-vector information
• Approximating fixed points of weakly contracting mappings
• Krylov solvability of unbounded inverse linear problems
• On the oracle complexity of smooth strongly convex minimization
• Randomized block Krylov methods for approximating extreme eigenvalues
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Excess information in parametric linear optimization
• Perspectives on information-based complexity
• On lower complexity bounds for large-scale smooth convex optimization
• Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
• On the optimality of Krylov information
• Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation
• Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods
• Complementary composite minimization, small gradients in general norms, and applications
• Computer-assisted design of accelerated composite optimization methods: OptISTA
• Existence and computation of short-run equilibria in economic geography

This page was built for publication: On optimality of Krylov's information when solving linear operator equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179025)