×

Relatively smooth convex optimization by first-order methods, and applications. (English) Zbl 1392.90090

Summary: The usual approach to developing and analyzing first-order methods for smooth convex optimization assumes that the gradient of the objective function is uniformly smooth with some Lipschitz constant \(L\). However, in many settings the differentiable convex function \(f(\cdot)\) is not uniformly smooth – for example, in \(D\)-optimal design where \(f(x):=-\ln\det(HXH^T)\) and \(X:=\mathbf D\mathrm{iag }(x)\), or even the univariate setting with \(f(x):=-\ln(x)+x^2\). In this paper we develop a notion of “relative smoothness” and relative strong convexity that is determined relative to a user-specified “reference function” \(h(\cdot)\) (that should be computationally tractable for algorithms), and we show that many differentiable convex functions are relatively smooth with respect to a correspondingly fairly simple reference function \(h(\cdot)\). We extend two standard algorithms – the primal gradient scheme and the dual averaging scheme – to our new setting, with associated computational guarantees. We apply our new approach to develop a new first-order method for the \(D\)-optimal design problem, with associated computational complexity analysis. Some of our results have a certain overlap with the recent work [H. H. Bauschke et al., Math. Oper. Res. 42, No. 2, 330–348 (2017; Zbl 1364.90251)].

MSC:

90C25 Convex programming
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
90C06 Large-scale problems in mathematical programming

Citations:

Zbl 1364.90251

Software:

MVE
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. D. Ahipasaoglu, P. Sun, and M. J. Todd, {\it Linear convergence of a modified Frank-Wolfe algorithm for computing minimum volume enclosing ellipsoids}, Optim. Methods Softw., 23 (2008), pp. 5-19. · Zbl 1146.90047
[2] K. Anstreicher, {\it Large step volumetric potential reduction algorithms for linear programming}, Ann. Oper. Res,, 62 (1996), pp. 521-538. · Zbl 0848.90080
[3] K. M. Anstreicher, {\it The volumetric barrier for semidefinite programming}, Math. Oper. Res., 25 (2000), pp. 365-380. · Zbl 1073.90533
[4] C. L. Atwood, {\it Optimal and efficient designs of experiments}, Ann. Math. Statist., 40 (1969), pp. 1570-1602. · Zbl 0182.51905
[5] M. Avriel, {\it Nonlinear Programming: Analysis and Methods}, Prentice-Hall, Englewood Cliffs, NJ, 1976.
[6] H. H. Bauschke, J. Bolte, and M. Teboulle, {\it A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications}, Math. Oper. Res., 42 (2017), pp. 330-348. · Zbl 1364.90251
[7] A. Belloni and R. M. Freund, {\it On the second-order feasibility cone: Primal-dual representation and efficient projection}, SIAM J. Optim., 19 (2008), pp. 1073-1092. · Zbl 1194.90123
[8] C. Croux, G. Haesbroeck, and P. J. Rousseeuw, {\it Location adjustment for the minimum volume ellipsoid estimator}, Statist. Comput., 12 (2002), pp. 191-200.
[9] F. John, {\it Extremum problems with inequalities as subsidiary conditions}, in Studies and Essays, Presented to R. Courant on His 60th Birthday, Interscience, New York, 1948, pp. 187-204. · Zbl 0034.10503
[10] L. G. Khachiyan, {\it Rounding of polytopes in the real number model of computation}, Math. Oper. Res., 21 (1996), pp. 307-320. · Zbl 0856.68066
[11] L. G. Khachiyan and M. J. Todd, {\it On the complexity of approximating the maximal inscribed ellipsoid for a polytope}, Math. Program., 61 (1993), pp. 137-159. · Zbl 0792.90088
[12] J. Kiefer and J. Wolfowitz, {\it The equivalence of two extremum problems}, Canad. J. Math., 12 (1960), pp. 363-365. · Zbl 0093.15602
[13] E. M. Knorr, R. T. Ng, and R. H. Zamar, {\it Robust space transformations for distance-based operations}, in Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2001, pp. 126-135.
[14] A. Nemirovsky and D. B. Yudin, {\it Problem Complexity and Method Efficiency in Optimization}, Wiley, New York, 1983.
[15] Y. Nesterov, {\it Introductory Lectures on Convex Optimization: A Basic Course}, Kluwer Academic, Boston, 2003. · Zbl 1086.90045
[16] Y. Nesterov, {\it Smooth minimization of non-smooth functions}, Math. Program., 103 (2005), pp. 127-152. · Zbl 1079.90102
[17] Y. Nesterov, {\it Primal-dual subgradient methods for convex problems}, Math. Program., 120 (2009), pp. 221-259. · Zbl 1191.90038
[18] Y. Nesterov, {\it Gradient methods for minimizing composite functions}, Math. Program., 140 (2013), pp. 125-161. · Zbl 1287.90067
[19] B. Polyak, {\it Introduction to Optimization}, Optimization Software, New York, 1987.
[20] P. Sun and R. M. Freund, {\it Computation of minimum-volume covering ellipsoids}, Oper. Res., 52 (2004), pp. 690-706. · Zbl 1165.90571
[21] M. J. Todd, {\it Minimum-Volume Ellipsoids: Theory and Algorithms}, MOS-SIAM Ser. Optim. 23, SIAM, Philadelphia, 2016. · Zbl 1360.90006
[22] P. Tseng, {\it On Accelerated Proximal Gradient Methods for Convex-Concave Optimization}, Technical report, MIT, Cambridge, MA, 2008.
[23] P. M. Vaidya, {\it A new algorithm for minimizing convex functions over convex sets}, in Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989, IEEE Computer Society, Los Angeles, 1989, pp. 338-343.
[24] Y. Ye, {\it A new complexity result for minimizing a general quadratic function with a sphere constraint}, in Recent Advances in Global Optimization, C. Floudas and P. Pardalos, eds., Princeton University Press, Princeton, NJ, 1992, pp. 19-31.
[25] E. A. Yildirim, {\it On the minimum volume covering ellipsoid of ellipsoids}, SIAM J. Optim., 17 (2006), pp. 621-641. · Zbl 1128.90048
[26] C. Zalinescu, {\it Convex Analysis in General Vector Spaces}, World Scientific, Singapore, 2002. · Zbl 1023.46003
[27] Y. Zhang, {\it An Interior-Point Algorithm for the Maximum-Volume Ellipsoid Problem}, Department of Computational and Applied Mathematics, Technical report TR98-15, Rice University, Houston, TX, 1998.
[28] Y. Zhou, Y. Liang, and L. Shen, {\it A Unified Approach to Proximal Algorithms using Bregman Distance}, Technical report, Syracuse University, Syracuse, NY, 2016.
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.