Curiosities and counterexamples in smooth convex optimization

• 成果类型: Article
• 署名作者: Bolte, Jerome; Pauwels, Edouard
• 署名单位: Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01707-1
• 发表日期: 2022
• 页码: 553-603
• 关键词: descent; CONVERGENCE; FLOWS

摘要

Counterexamples to some old-standing optimization problems in the smooth convex coercive setting are provided. We show that block-coordinate, steepest descent with exact search or Bregman descent methods do not generally converge. Other failures of various desirable features are established: directional convergence of Cauchy's gradient curves, convergence of Newton's flow, finite length of Tikhonov path, convergence of central paths, or smooth Kurdyka-Lojasiewicz inequality. All examples are planar. These examples are based on general smooth convex interpolation results. Given a decreasing sequence of positively curved C-k convex compact sets in the plane, we provide a level set interpolation of a C-k smooth convex function where k >= 2 is arbitrary. If the intersection is reduced to one point our interpolant has positive definite Hessian, otherwise it is positive definite out of the solution set. Furthermore, given a sequence of decreasing polygons we provide an interpolant agreeing with the vertices and whose gradients coincide with prescribed normals.