Abstract

Using ε-subdifferential calculus for difference-of-convex (d.c.) optimization, Dür proposed a condition sufficient for local optimality, and showed that this condition is not necessary in general. Here it is proved that whenever the convex part is strongly convex, this condition is also necessary. Strong convexity can always be ensured by changing the given d.c. decomposition slightly. This approach also allows for a formulation with perturbed ε-subdifferentials which involves only the original d.c. decomposition, even without imposing strong convexity. We relate this result with another inclusion condition on perturbed ε-subdifferentials, which even can serve as a quantitative version of a criterion both necessary and sufficient for local optimality.

Author information

Contact details are reproduced from the original publication and may be historical.

Claude Lemaréchal

INRIA Grenoble-Rhône-Alpes, 655 Avenue de l'Europe, 38334 Saint Ismier - Montbonnot, France

Claude.Lemarechal@inria.fr

Keywords

  • Approximate subdifferential
  • non-smooth optimization
  • optimality condition
  • strong convexity

References

  1. A. D. Alexandroff: Surfaces represented by the difference of convex functions, Dokl. Akad. Nauk SSSR, n. Ser. 72 (1950) 613–616.Google Scholar
  2. I.M. Bomze: Global optimization – a quadratic programming perspective, in: Nonlinear Optimization (Cetraro, 2007), I.M. Bomze et al. (eds.), Lect. Notes Math. 1989, Springer (2010), to appear.https://doi.org/10.1007/978-3-642-11339-0_1Google Scholar
  3. M. Dür: A parametric characterization of local optimality, Math. Methods Oper. Res. 57 (2003) 101–109.https://doi.org/10.1007/s001860200232Google Scholar
  4. P. Hartman: On functions representable as a difference of convex functions, Pacific J. Math. 9 (1959) 707–713.https://doi.org/10.2140/pjm.1959.9.707Google Scholar
  5. R. Horst, N. V. Thoai: DC programming: overview, J. Optimization Theory Appl. 103 (1999) 1–43.https://doi.org/10.1023/A:1021765131316Google Scholar
  6. J.-B. Hiriart-Urruty: Generalized differentiability, duality and optimization for problems dealing with differences of convex functions, in: Convexity and Duality in Optimization (Groningen, 1984), J. Ponstein (ed.), Lect. Notes Econ. Math. Syst. 256, Springer, Berlin (1985) 37–70.https://doi.org/10.1007/978-3-642-45610-7_3Google Scholar
  7. J.-B. Hiriart-Urruty: From convex optimization to nonconvex optimization. Part I: necessary and sufficient conditions for global optimality, in: Nonsmooth Optimization and Related Topics (Erice, 1988), F. C. Clarke, V. Demyanov, F. Gianessi (eds.), Plenum Press, New York (1989) 219–239.https://doi.org/10.1007/978-1-4757-6019-4_13Google Scholar
  8. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, Grundlehren der Mathematischen Wissenschaften 306, Springer, Berlin (1996).Google Scholar
  9. I. Singer: A Fenchel-Rockafellar type duality theorem for maximization, Bull. Aust. Math. Soc. 20 (1979) 193–198.https://doi.org/10.1017/S0004972700010844Google Scholar
  10. J. F. Toland: Duality in nonconvex optimization, J. Math. Anal. Appl. 66 (1978) 399–415.https://doi.org/10.1016/0022-247X(78)90243-3Google Scholar
  11. J. F. Toland: A duality principle for nonconvex optimization and the calculus of variations, Arch. Rat. Mech. Anal. 71 (1979) 41–61.https://doi.org/10.1007/BF00250669Google Scholar

Suggested citation

I. M. Bomze, C. Lemaréchal. “Necessary Conditions for Local Optimality in Difference-of-Convex Programming.” Journal of Convex Analysis 17 (2010), No. 2, 673–680. https://doi.org/10.68381/jca17045

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2010. Rights now held by Banach Press LLC.