The condition number of a function relative to a set. (English) Zbl 1470.90077
Summary: The condition number of a differentiable convex function, namely the ratio of its smoothness to strong convexity constants, is closely tied to fundamental properties of the function. In particular, the condition number of a quadratic convex function is the square of the aspect ratio of a canonical ellipsoid associated to the function. Furthermore, the condition number of a function bounds the linear rate of convergence of the gradient descent algorithm for unconstrained convex minimization. We propose a condition number of a differentiable convex function relative to a reference convex set and distance function pair. This relative condition number is defined as the ratio of relative smoothness to relative strong convexity constants. We show that the relative condition number extends the main properties of the traditional condition number both in terms of its geometric insight and in terms of its role in characterizing the linear convergence of first-order methods for constrained convex minimization. When the reference set \(X\) is a convex cone or a polyhedron and the function \(f\) is of the form \(f = g\circ A\), we provide characterizations of and bounds on the condition number of \(f\) relative to \(X\) in terms of the usual condition number of \(g\) and a suitable condition number of the pair \((A, X)\).
MSC:
| 90C25 | Convex programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C52 | Methods of reduced gradient type |
References:
| [1] | Bauschke, H.; 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 |
| [2] | Beck, A.; Shtern, S., Linearly convergent away-step conditional gradient for non-strongly convex functions, Math. Program., 164, 1-27 (2017) · Zbl 1370.90010 · doi:10.1007/s10107-016-1069-4 |
| [3] | Beck, A.; Teboulle, M., A conditional gradient method with linear rate of convergence for solving convex linear systems, Math. Methods Oper. Res., 59, 2, 235-247 (2004) · Zbl 1138.90440 · doi:10.1007/s001860300327 |
| [4] | Bubeck, S., Lee, Y., Singh, M.: A geometric alternative to Nesterov’s accelerated gradient descent. arXiv preprint arXiv:1506.08187 (2015) |
| [5] | Chen, G.; Teboulle, M., Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM J. Optim., 3, 3, 538-543 (1993) · Zbl 0808.90103 · doi:10.1137/0803026 |
| [6] | Cheung, D.; Cucker, F., A new condition number for linear programming, Math. Prog., 91, 2, 163-174 (2001) · Zbl 1072.90564 · doi:10.1007/s101070100237 |
| [7] | Dontchev, AL; Lewis, AS; Rockafellar, RT, The radius of metric regularity, Trans. Am. Math. Soc., 355, 2, 493-517 (2003) · Zbl 1042.49026 · doi:10.1090/S0002-9947-02-03088-X |
| [8] | Drusvyatskiy, D.; Fazel, M.; Roy, S., An optimal first order method based on optimal quadratic averaging, SIAM J. Optim., 28, 1, 251-271 (2018) · Zbl 1382.65169 · doi:10.1137/16M1072528 |
| [9] | Epelman, M.; Freund, R., A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems, SIAM J. Optim., 12, 3, 627-655 (2002) · Zbl 1046.90038 · doi:10.1137/S1052623400373829 |
| [10] | Epelman, M.; Freund, RM, Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system, Math Program., 88, 3, 451-485 (2000) · Zbl 0989.65061 · doi:10.1007/s101070000136 |
| [11] | Freund, R., Complexity of convex optimization using geometry-based measures and a reference point, Math Program., 99, 197-221 (2004) · Zbl 1098.90095 · doi:10.1007/s10107-003-0435-1 |
| [12] | Freund, R.; Vera, J., Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm, SIAM J. Optim., 10, 155-176 (1999) · Zbl 0953.90044 · doi:10.1137/S105262349732829X |
| [13] | Guélat, J.; Marcotte, P., Some comments on Wolfe’s away step, Math. Program., 35, 110-119 (1986) · Zbl 0592.90074 · doi:10.1007/BF01589445 |
| [14] | Gutman, D., Enhanced basic procedures for the projection and rescaling algorithm, Optim. Lett., 13, 6, 1259-1267 (2019) · Zbl 1434.90134 · doi:10.1007/s11590-019-01390-4 |
| [15] | Hoffman, A., On approximate solutions of systems of linear inequalities, J. Res. Natl. Bureau Stand., 49, 4, 263-265 (1952) · doi:10.6028/jres.049.027 |
| [16] | Jaggi, M.: Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In ICML, volume 28 of JMLR Proceedings, pp. 427-435 (2013) |
| [17] | Karimi, S., Vavasis, S.: A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent. arXiv preprint arXiv:1712.09498 (2017) |
| [18] | Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank-Wolfe optimization variants. In: Advances in Neural Information Processing Systems (NIPS) (2015) |
| [19] | Lewis, A., Ill-conditioned convex processes and conic linear systems, Math. Oper. Res., 24, 4, 829-834 (1999) · Zbl 1074.90559 · doi:10.1287/moor.24.4.829 |
| [20] | Lu, H.; Freund, R.; Nesterov, Y., Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim., 28, 1, 333-354 (2018) · Zbl 1392.90090 · doi:10.1137/16M1099546 |
| [21] | Ma, C., Gudapati, N., Jahani, M., Tappenden, R., Takáč, M.: Underestimate sequences via quadratic averaging. arXiv preprint arXiv:1710.03695 (2017) |
| [22] | Necoara, I.; Nesterov, Y.; Glineur, F., Linear convergence of first order methods for non-strongly convex optimization, Math. Program., 175, 69-107 (2019) · Zbl 1412.90111 · doi:10.1007/s10107-018-1232-1 |
| [23] | Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Applied Optimization (2004) · Zbl 1086.90045 |
| [24] | Nesterov, Y., Gradient methods for minimizing composite functions, Math. Program., 140, 1, 125-161 (2013) · Zbl 1287.90067 · doi:10.1007/s10107-012-0629-5 |
| [25] | Ordóñez, F.; Freund, R., Computational experience and the explanatory value of condition measures for linear optimization, SIAM J. Optim., 14, 2, 307-333 (2003) · Zbl 1046.90001 · doi:10.1137/S1052623402401804 |
| [26] | Peña, J., Vera, J., Zuluaga, L.: New characterizations of Hoffman constants for system of linear constraints. To Appear in Math. Program. (2020) · Zbl 1465.90043 |
| [27] | Peña, J., Understanding the geometry on infeasible perturbations of a conic linear system, SIAM J. Optim., 10, 534-550 (2000) · Zbl 0957.15005 · doi:10.1137/S1052623497323674 |
| [28] | Peña, J.; Rodríguez, D., Polytope conditioning and linear convergence of the Frank-Wolfe algorithm, Math. Oper. Res., 44, 1, 1-18 (2019) · Zbl 1440.90048 |
| [29] | Ramdas, A.; Peña, J., Towards a deeper geometric, analytic and algorithmic understanding of margins, Optim. Methods Softw., 31, 2, 377-391 (2016) · Zbl 1382.90056 · doi:10.1080/10556788.2015.1099652 |
| [30] | Renegar, J., Incorporating condition measures into the complexity theory of linear programming, SIAM J. Optim., 5, 506-524 (1995) · Zbl 0838.90139 · doi:10.1137/0805026 |
| [31] | Renegar, J., Linear programming, complexity theory and elementary functional analysis, Math. Program., 70, 3, 279-351 (1995) · Zbl 0855.90085 |
| [32] | Teboulle, M., A simplified view of first order methods for optimization, Math. Program., 170, 67-96 (2018) · Zbl 1391.90482 · doi:10.1007/s10107-018-1284-2 |
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.
