Back to Search
Start Over
Efficiency of minimizing compositions of convex functions and smooth maps
- Source :
- Mathematical Programming. 178:503-558
- Publication Year :
- 2018
- Publisher :
- Springer Science and Business Media LLC, 2018.
-
Abstract
- We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rely on is the prox-linear method, which in each iteration solves a regularized subproblem formed by linearizing the smooth map. When the subproblems are solved exactly, the method has efficiency $$\mathcal {O}(\varepsilon ^{-2})$$ , akin to gradient descent for smooth minimization. We show that when the subproblems can only be solved by first-order methods, a simple combination of smoothing, the prox-linear method, and a fast-gradient scheme yields an algorithm with complexity $$\widetilde{\mathcal {O}}(\varepsilon ^{-3})$$ . We round off the paper with an inertial prox-linear method that automatically accelerates in presence of convexity.
- Subjects :
- 021103 operations research
General Mathematics
Numerical analysis
0211 other engineering and technologies
97N60, 90C25, 90C06, 90C30
010103 numerical & computational mathematics
02 engineering and technology
Composition (combinatorics)
Lipschitz continuity
01 natural sciences
Convexity
Combinatorics
Optimization and Control (math.OC)
FOS: Mathematics
Minification
0101 mathematics
Gradient descent
Convex function
Mathematics - Optimization and Control
Software
Smoothing
Mathematics
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 178
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....6698de8796df941e1ef8c625061a46d7