Curiosities and counterexamples in smooth convex optimization

Jerome Bolte (1) , Edouard Pauwels (2)

1 TSE-R - Toulouse School of Economics
2 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage

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.

Domaines: Optimisation et contrôle [math.OC]

Jerome Bolte, Edouard Pauwels. Curiosities and counterexamples in smooth convex optimization. Mathematical Programming, 2021, ⟨10.1007/s10107-021-01707-1⟩. ⟨hal-02447733v2⟩