Curiosities and counterexamples in smooth convex optimization. (English) Zbl 1504.90092
Summary: 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-Łojasiewicz 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\ge 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.
MSC:
| 90C25 | Convex programming |
Keywords:
convex programming; smooth convex counterexamples; interpolation of decreasing convex sequences; Bregman methods; block-coordinate methods; exact line searchReferences:
| [1] | Alvarez, F.; Bolte, J.; Brahic, O., Hessian Riemannian gradient flows in convex programming, SIAM J. Control. Optim., 43, 2, 477-501 (2004) · Zbl 1077.34050 · doi:10.1137/S0363012902419977 |
| [2] | Alvarez, D.F., Pérez, C.J.M.: A dynamical system associated with Newton’s method for parametric approximations of convex minimization problems. Appl. Math. Optim. 38, 193-217 (1998) · Zbl 0905.34057 |
| [3] | Auslender, A., Optimisation Méthodes Numériques (1976), Paris: Masson, Paris · Zbl 0326.90057 |
| [4] | Auslender, A., Penalty and barrier methods: a unified framework, SIAM J. Optim., 10, 1, 211-230 (1999) · Zbl 0953.90045 · doi:10.1137/S1052623497324825 |
| [5] | Aubin, J-P; Cellina, A., Differential Inclusions: Set-Valued Maps and Viability Theory (1984), Berlin: Springer, Berlin · Zbl 0538.34007 · doi:10.1007/978-3-642-69512-4 |
| [6] | Bauschke, HH; Bolte, J.; Teboulle, M., A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications, Math. Oper. Res., 42, 2, 330-348 (2016) · Zbl 1364.90251 · doi:10.1287/moor.2016.0817 |
| [7] | Bauschke, HH; Combettes, PL, Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2011), New York: Springer, New York · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7 |
| [8] | Beck, A., First-Order Methods in Optimization (2017), Philadelphia: SIAM, Philadelphia · Zbl 1384.65033 · doi:10.1137/1.9781611974997 |
| [9] | Beck, A.; Teboulle, M., Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett., 31, 3, 167-175 (2003) · Zbl 1046.90057 · doi:10.1016/S0167-6377(02)00231-6 |
| [10] | Beck, A.; Tetruashvili, L., On the convergence of block coordinate descent type methods, SIAM J. Optim., 23, 4, 2037-2060 (2013) · Zbl 1297.90113 · doi:10.1137/120887679 |
| [11] | Bertsekas, DP; Scientific, A., Convex Optimization Algorithms (2015), Belmont: Athena Scientific, Belmont · Zbl 1347.90001 |
| [12] | Bolte, J.; Daniilidis, A.; Ley, O.; Mazet, L., Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity, Trans. Am. Math. Soc., 362, 6, 3319-3363 (2010) · Zbl 1202.26026 · doi:10.1090/S0002-9947-09-05048-X |
| [13] | Bolte, J.; Nguyen, TP; Peypouquet, J.; Suter, BW, From error bounds to the complexity of first-order descent methods for convex functions, Math. Program., 165, 2, 471-507 (2017) · Zbl 1373.90076 · doi:10.1007/s10107-016-1091-6 |
| [14] | Bolte, J.; Teboulle, M., Barrier operators and associated gradient-like dynamical systems for constrained minimization problems, SIAM J. Control Optim., 42, 4, 1266-1292 (2003) · Zbl 1051.49010 · doi:10.1137/S0363012902410861 |
| [15] | Borwein, JM; Li, G.; Yao, L., Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets, SIAM J. Optim., 24, 1, 498-527 (2014) · Zbl 1296.41011 · doi:10.1137/130919052 |
| [16] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [17] | Chen, C.; He, B.; Ye, Y.; Yuan, X., The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155, 1-2, 57-79 (2016) · Zbl 1332.90193 · doi:10.1007/s10107-014-0826-5 |
| [18] | Crouzeix, J-P, Conditions for convexity of quasiconvex functions, Math. Oper. Res., 5, 1, 120-125 (1980) · Zbl 0428.26007 · doi:10.1287/moor.5.1.120 |
| [19] | Daniilidis, A.; Ley, O.; Sabourau, S., Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions, Journal de matéhmatiques pures et appliquées, 94, 2, 183-199 (2010) · Zbl 1201.37023 · doi:10.1016/j.matpur.2010.03.007 |
| [20] | Dragomir, R.A., Taylor, A., d’Aspremont, A., Bolte, J.: Optimal complexity and certification of Bregman first-order methods (2019). arXiv preprint arXiv:1911.08510 |
| [21] | Fenchel, W., Convex Cones, Sets and Functions, Mimeographed Lecture Note (1951), Princeton: Princeton University, Princeton |
| [22] | de Finetti, B., Sulle stratificazioni convesse, Ann. Mat., 30, 1, 173-183 (1949) · Zbl 0039.05701 · doi:10.1007/BF02415006 |
| [23] | Gale, D.; Klee, V.; Rockafellar, RT, Convex functions on convex polytopes, Proc. Am. Math. Soc., 19, 4, 867-873 (1968) · Zbl 0246.26009 · doi:10.1090/S0002-9939-1968-0230219-6 |
| [24] | Golub, GH; Hansen, PC; O’Leary, DP, Tikhonov regularization and total least squares, SIAM J. Matrix Anal. Appl., 21, 1, 185-194 (1999) · Zbl 0945.65042 · doi:10.1137/S0895479897326432 |
| [25] | Kannai, Y., Concavifiability and constructions of concave utility functions, J. Math. Econ., 4, 1, 1-56 (1977) · Zbl 0361.90008 · doi:10.1016/0304-4068(77)90015-5 |
| [26] | Kurdyka, K.; Mostowski, T.; Parusinski, A., Proof of the gradient conjecture of R. Thom, Ann. Math., 152, 3, 763-792 (2000) · Zbl 1053.37008 · doi:10.2307/2661354 |
| [27] | Łojasiewicz, S.: Sur les trajectoires du gradient d’une fonction analytique. Seminari di Geometria, Bologna (1982/83). Universita’ degli Studi di Bologna, Bologna 1984, 115-117 (1984) · Zbl 0606.58045 |
| [28] | Lorentz, GG, Bernstein Polynomials (1954), Providence: American Mathematical Society, Providence · Zbl 0989.41504 |
| [29] | Ma, TW, Higher chain formula proved by combinatorics, Electron. J. Comb., 16, 1, N21 (2009) · Zbl 1226.05010 · doi:10.37236/259 |
| [30] | Manselli, P.; Pucci, C., Maximum length of steepest descent curves for quasi-convex functions, Geom. Dedicata, 38, 2, 211-227 (1991) · Zbl 0724.52006 · doi:10.1007/BF00181220 |
| [31] | Nemirovsky, AS; Yudin, DB, Problem Complexity and Method Efficiency in Optimization (1983), New York: Wiley-Interscience, New York · Zbl 0501.90062 |
| [32] | Nesterov, Y., Lectures on Convex Optimization (2003), Berlin: Springer, Berlin · Zbl 1427.90003 |
| [33] | Nesterov, Y.; Nemirovskii, A., Interior-Point Polynomial Algorithms in Convex Programming (1994), Philadelphia: SIAM, Philadelphia · Zbl 0824.90112 · doi:10.1137/1.9781611970791 |
| [34] | Powell, MJ, On search directions for minimization algorithms, Math. Program., 4, 1, 193-201 (1973) · Zbl 0258.90043 · doi:10.1007/BF01584660 |
| [35] | Schneider, R., Convex Bodies: The Brunn-Minkowski Theory (1993), Cambridge: Cambridge University Press, Cambridge · Zbl 0798.52001 · doi:10.1017/CBO9780511526282 |
| [36] | Torralba, D.: Convergence épigraphique et changements d’échelle en analyse variationnelle et optimisation. Ph.D. Thesis, Université Montpellier 2 (1996) |
| [37] | Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton · Zbl 0932.90001 · doi:10.1515/9781400873173 |
| [38] | Thom, R., Problèmes rencontrés dans mon parcours mathématique : un bilan, Publications mathématiques de l’IHES, 70, 199-214 (1989) · Zbl 0709.58001 · doi:10.1007/BF02698877 |
| [39] | Wright, SJ, Coordinate descent algorithms, Math. Program., 151, 1, 3-34 (2015) · Zbl 1317.49038 · doi:10.1007/s10107-015-0892-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
