NDLI: Steepest Descent Method with Random Step Lengths

Content Provider	Springer Nature Link
Author	Kalousek, Zdeněk
Copyright Year	2015
Abstract	The paper studies the steepest descent method applied to the minimization of a twice continuously differentiable function. Under certain conditions, the random choice of the step length parameter, independent of the actual iteration, generates a process that is almost surely R-convergent for quadratic functions. The convergence properties of this random procedure are characterized based on the mean value function related to the distribution of the step length parameter. The distribution of the random step length, which guarantees the maximum asymptotic convergence rate independent of the detailed properties of the Hessian matrix of the minimized function, is found, and its uniqueness is proved. The asymptotic convergence rate of this optimally created random procedure is equal to the convergence rate of the Chebyshev polynomials method. Under practical conditions, the efficiency of the suggested random steepest descent method is degraded by numeric noise, particularly for ill-conditioned problems; furthermore, the asymptotic convergence rate is not achieved due to the finiteness of the realized calculations. The suggested random procedure is also applied to the minimization of a general non-quadratic function. An algorithm needed to estimate relevant bounds for the Hessian matrix spectrum is created. In certain cases, the random procedure may surpass the conjugate gradient method. Interesting results are achieved when minimizing functions having a large number of local minima. Preliminary results of numerical experiments show that some modifications of the presented basic method may significantly improve its properties.
Ending Page	422
Page Count	64
Starting Page	359
File Format	PDF
ISSN	16153375
e-ISSN	16153383
Journal	Foundations of Computational Mathematics
Issue Number	2
Volume Number	17
Language	English
Publisher	Springer US
Publisher Date	2015-11-23
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Economics Gradient methods Other methods Computational experiments Linear and Multilinear Algebras, Matrix Theory Stochastic process Optimization Convergence Monte Carlo methods Algorithms Iterative methods for linear systems Numerical Analysis Computer Science Nonconvex programming, global optimization Applications of Mathematics Math Applications in Computer Science
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Analysis Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Convergence of the Stochastic Euler Scheme for Locally Lipschitz Coefficients

Online Gradient Descent Learning Algorithms

Asymptotic Analysis of Numerical Steepest Descent with Path Approximations

Transversality and Alternating Projections for Nonconvex Sets

Random Gradient-Free Minimization of Convex Functions

A Gradient-Descent Method for Curve Fitting on Riemannian Manifolds

Adaptive Restart for Accelerated Gradient Schemes

Fast First-Order Methods for Composite Convex Optimization with Backtracking

Local Linear Convergence for Alternating and Averaged Nonconvex Projections

Steepest Descent Method with Random Step Lengths

Similar Documents

Convergence of the Stochastic Euler Scheme for Locally Lipschitz Coefficients

Online Gradient Descent Learning Algorithms

Asymptotic Analysis of Numerical Steepest Descent with Path Approximations

Transversality and Alternating Projections for Nonconvex Sets

Random Gradient-Free Minimization of Convex Functions

A Gradient-Descent Method for Curve Fitting on Riemannian Manifolds

Adaptive Restart for Accelerated Gradient Schemes

Fast First-Order Methods for Composite Convex Optimization with Backtracking

Local Linear Convergence for Alternating and Averaged Nonconvex Projections

Steepest Descent Method with Random Step Lengths