The ABC of DC Programming
- PDF / 2,294,816 Bytes
- 28 Pages / 439.642 x 666.49 pts Page_size
- 85 Downloads / 198 Views
The ABC of DC Programming Welington de Oliveira1 Received: 5 April 2020 / Accepted: 13 October 2020 / © Springer Nature B.V. 2020
Abstract A function is called DC if it is expressible as the difference of two convex functions. In this work, we present a short tutorial on difference-of-convex optimization surveying and highlighting some important facts about DC functions, optimality conditions, and recent algorithms. The manuscript, accessible to a wide range of readers familiar with the convex analysis machinery, builds upon three pillars from variational analysis: directional derivative, ε-subdifferential, and the Legendre-Fenchel transform. Keywords DC programming · Variational analysis · Nonsmooth optimization Mathematics Subject Classification (2010) 49J52 · 49J53 · 49K99 · 90C26
1 Introduction The discipline of mathematical programming concerned with the theory and methods for finding extrema of difference-of-convex (DC) functions on sets of given vector spaces is called DC programming, a sub-field of nonlinear programming that finds many applications in engineering problems and data science [1]. Optimality conditions and relevant properties of DC optimization problems can be found in the pioneering works [2] and [3], and more recently in [4]. Algorithmic aspects of DC programming have been received significant attention lately, as shown by the recent papers [1, 5–13] and the textbooks [14, 15]. By adopting the point of view of mathematical analysis, the paper [16] surveys relevant results on DC functions defined in general normed linear spaces. Differently from [16], we restrict our analysis to the n-dimensional Euclidean space and focus on theoretical and numerical aspects of optimization problems involving DC functions. We aim at shedding light on the advantages and limitations of DC programming and specialized algorithms, pointing out what can numerically be done or expected when facing the problem of minimizing a DC function over (a convex subset of) Rn . To that end, we survey (and enhance a few) key con-
Welington de Oliveira
[email protected] 1
CMA – Centre de Math´ematiques Appliqu´ees, MINES ParisTech, PSL – Research University, Sophia Antipolis, France
W. de Oliveira
cepts and properties of DC functions and DC optimization, such as optimality conditions, duality, and numerical algorithms. Concerning numerical methods for DC programming, we will not cover global optimization algorithms and focus only on local methods. DC programs are, in the general situation, NP-hard. We refer to [14, Part II] for a comprehensive presentation of several algorithms for globally solving DC programs; see also [17] and [18] for particular classes of DC programs. Beyond their practical interest, local solution methods play an essential role in global optimization, since algorithms of the latter class typically employ local methods to find stationary/critical points that, in turn, feed a specific search strategy for global solutions. DC programs cover a broad class of nonconvex optimization pr
Data Loading...
