Gradient Projection and Conditional Gradient Methods for Constrained Nonconvex Minimization. (18th May 2020)

• Record Type: Journal Article
• Authors: Balashov, M. V.; Polyak, B. T.; Tremba, A. A.
• Is Part Of: Numerical functional analysis and optimization. Volume 41:Number 7(2020)
• Page Start: 822
• Page End: 849
• Publication Date: 2020-05-18
• Subjects: Minimization on a sphere -- smooth functions -- proximally smooth set -- strongly convex set -- gradient projection method -- Ležanski-Polyak-Lojasiewicz condition -- Frank-Wolfe method -- nonconvex optimization; 49J53 -- 90C26 -- 90C52. Secondary: 46N10 -- 65K10; Functional analysis -- Periodicals; Numerical analysis -- Periodicals; Mathematical optimization -- Periodicals; Numerical Analysis, Computer-Assisted; 515.705
• DOI: 10.1080/01630563.2019.1704780
• Languages: English
• ISSNs: 0163-0563

Abstract

Abstract: Minimization of a smooth function on a sphere or, more generally, on a smooth manifold, is the simplest non-convex optimization problem. It has a lot of applications. Our goal is to propose a version of the gradient projection algorithm for its solution and to obtain results that guarantee convergence of the algorithm under some minimal natural assumptions. We use the Ležanski-Polyak-Lojasiewicz condition on a manifold to prove the global linear convergence of the algorithm. Another method well fitted for the problem is the conditional gradient (Frank-Wolfe) algorithm. We examine some conditions which guarantee global convergence of full-step version of the method with linear rate.