A geometric integration approach to smooth optimisation: Foundations of the discrete gradient method

• DOI: 10.48550/arxiv.1805.06444
• Publication Date: 2018-01-01
• Authors: Matthias J. Ehrhardt; Erlend S. Riis; Torbjørn Ringholm; Carola‐Bibiane Sc...
• Keywords: math.OC; 49M37, 49Q15, 65K05, 65K10, 74S60, 90C15, 90C26, 90C30; Optimization and Control (math.OC); FOS: Mathematics; 0101 mathematics; Mathematics - Optimization and Control; 01 natural sciences

Discrete gradient methods are geometric integration techniques that can preserve the dissipative structure of flows. Due to monotonic decay function values, they well suited for general convex and nonconvex optimization problems. Both zero- first-order algorithms be derived from discrete method by selecting different gradients. In this paper, we present a comprehensive analysis optimisation which provides solid theoretical foundation. We show is well-posed proving existence uniqueness iterates any positive time step, propose an efficient solving associated equation. Moreover, establish $O(1/k)$ convergence rate objectives prove linear if instead Polyak-Lojasiewicz inequality satisfied. The carried out three gradients - Gonzalez gradient, mean value Itoh-Abe as randomised method. Our results illustrated with variety numerical experiments, furthermore demonstrate robust respect stiffness.