Information-based complexity of linear operator equations

DOI10.1016/0885-064X(92)90013-2MaRDI QIDQ1194382zbMATH OpenOpenAlexFDO

Authors Arkadi Nemirovski

Publication date 27 September 1992

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

Full work available at URL https://doi.org/10.1016/0885-064x(92)90013-2

zbMATH Keywords

optimalitycomplexityHilbert spacesconjugate gradient methodsbounded operatorscomplexity boundsChebyshev methodslinear operator equationssuboptimal methods

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Equations and inequalities involving linear operators, with vector unknowns (47A50) Numerical solutions to equations with linear operators (65J10)

Recommendations

• On information complexity of certain classes of operator equations
• Information complexity of equations of the second kind with compact operators in Hilbert space
• Information complexity of weakly singular integral equations
• scientific article; zbMATH DE number 7650250
• scientific article; zbMATH DE number 3922389
• On optimality of Krylov's information when solving linear operator equations
• scientific article; zbMATH DE number 50734
• scientific article; zbMATH DE number 1524404
• Information complexity of functional optimization problems and their approximation schemes
• scientific article; zbMATH DE number 3508265

Cites work

• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• On optimality of Krylov's information when solving linear operator equations
• On the Convergence of the Conjugate Gradient Method for Singular Linear Operator Equations
• On the optimality of Krylov information

Cited in

(43)

• Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
• Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
• Efficient algorithms for distributionally robust stochastic optimization with discrete scenario support
• Dual extrapolation and its applications to solving variational inequalities and related problems
• On the oracle complexity of smooth strongly convex minimization
• Faster algorithm and sharper analysis for constrained Markov decision process
• Computational complexity of solving operator equation (I-T)x=y
• Generalizing the optimized gradient method for smooth convex minimization
• Optimal linear randomized methods for linear operators in Hilbert spaces
• Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
• Complexity of differential and integral equations
• Simple and optimal methods for stochastic variational inequalities. II: Markovian noise and policy evaluation in reinforcement learning
• What is the complexity of solution-restricted operator equations?
• Some worst-case datasets of deterministic first-order methods for solving binary logistic regression
• Nearly optimal first-order methods for convex optimization under gradient norm measure: an adaptive regularization approach
• Primal-dual accelerated gradient methods with small-dimensional relaxation oracle
• PEPIT: computer-assisted worst-case analyses of first-order optimization methods in python
• An information complexity approach to extended formulations
• Efficient first-order methods for convex minimization: a constructive approach
• On lower iteration complexity bounds for the convex concave saddle point problems
• Convergence of a Constrained Vector Extrapolation Scheme
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• On lower complexity bounds for large-scale smooth convex optimization
• Golden ratio algorithms for variational inequalities
• On information complexity of certain classes of operator equations
• Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods
• Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation
• scientific article; zbMATH DE number 1524404 (Why is no real title available?)
• Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
• Complementary composite minimization, small gradients in general norms, and applications
• Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
• Information complexity of equations of the second kind with compact operators in Hilbert space
• On polynomial rings in information dynamics of linear CA
• On Polynomial Rings in Information Dynamics of Linear CA
• scientific article; zbMATH DE number 50734 (Why is no real title available?)
• Complexity for some classes of well-posed problems
• Accelerated schemes for a class of variational inequalities
• Distributed and consensus optimization for non-smooth image reconstruction
• An optimal gradient method for smooth strongly convex minimization
• Minimal residual algorithm and matrix-vector information
• The exact information-based complexity of smooth convex minimization
• Fully polynomial time (,)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
• Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods

This page was built for publication: Information-based complexity of linear operator equations

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