65. Capra-Cutting Plane Method Applied to Sparse Optimization
Invited abstract in session WC-9: Generalized convexity and monotonicity 4, stream Generalized convexity and monotonicity.
Wednesday, 14:00-16:00Room: B100/8013
Authors (first author is the speaker)
| 1. | Seta Rakotomandimby
|
| ENPC | |
| 2. | Adrien Le Franc
|
| CERMICS, École des Ponts ParisTech | |
| 3. | Jean-Philippe Chancelier
|
| CERMICS Ecole des Ponts et Chaussées, Université Paris Est | |
| 4. | Michel De Lara
|
| École des Ponts ParisTech |
Abstract
In 1960, Kelley proposed a cutting plane method to minimize a continuous convex objective function over a compact set. This iterative method consists at each step in minimizing a polyhedral approximation of the objective function before improving the approximation by a
valid affine cut. In generalized convexity, the affine functions giving the cuts are replaced by some family of base functions. This base functions are chosen so that the objective function is their supremum, making it abstract convex. In this framework, the Kelley's algorithm has been generalized to continuous abstract convex functions. We continue the generalization
of the cutting plane method by providing a convergence result that can be applied to lower semicontinuous objective functions.
This convergence result is motivated by the Capra-convexity results on the ℓ0 pseudonorm, which is lower semicontinuous. As explicit formulas for the Capra-subdifferential of the ℓ0 pseudonorm have been calculated, we can now implement Capra-cutting plane methods for the sparse problem of minimizing ℓ0 over a compact set.
Keywords
- Global optimization
- Non-smooth optimization
- Derivative-free optimization
Status: accepted
Back to the list of papers