Necessary conditions for local optimality in d.c. programming

Immanuel M. Bomze (immanuel.bomzeunivie.ac.at)
Claude Lemarechal (claude.lemarechalinrialpes.fr)

Abstract: Using $\eps$-subdifferential calculus for difference-of-convex (d.c.) programming, D\"ur 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 $\eps$-subdifferentials which involves only the original d.c.\ decomposition, even without imposing strong convexity. We relate this result with another inclusion condition on perturbed $\eps$-subdifferentials, which even can serve as a quantitative version of a criterion both necessary and sufficient for local optimality.

Keywords: approximate subdifferential; non-smooth optimization; optimality condition; strong convexity

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: ISDS Technical Report TR 2008-14, University of Vienna (Oct. 2008).

Download: [PDF]

Entry Submitted: 10/06/2008
Entry Accepted: 10/06/2008
Entry Last Modified: 11/18/2008

Modify/Update this entry