Subgradient selector in the generalized cutting plane method with an application to sparse optimization

Duality in convex analysis devotes a prominent role to affine functions, as proper convex lower semicontinuous functions are supremum of such functions. This property is used in the Kelley’s algorithm, to minimize a proper convex lower semicontinuous function by sequentially approximating it from below by maxima of affine functions (cuts). Affine functions are deduced from a bilinear pairing. In generalized convexity, the usual bilinear form is replaced by some bivariate function, called coupling. The Moreau-Rockafellar subdifferential of a function is replaced by the -subdifferential. Kelley’s algorithm then becomes the generalized -cutting plane method to minimize a -subdifferentiable objective function. In this paper, we prove a convergence result whose scope makes it possible to tackle sparse optimization problems. For this purpose, we introduce a selection of -subgradients involved in a pointwise locally equicontinuous property, together with the coupling and the objective function. Under the assumptions of the convergence result, we discuss a necessary condition on the continuity points of the function to be minimized. Finally, we give an example of converging Capra-cutting plane method for the minimization of the pseudonorm on a compact set.