Inexact proximal point method for piecewise-star-convex function

We propose and analyze an inexact proximal point method for minimizing locally Lipschitz functions on Euclidean spaces with a piecewise star-convex structure. More precisely, the space is covered by finitely many closed convex sets, and on each set the objective function satisfies a star-convex inequality with respect to the minimizers of its restriction. This class includes, in particular, convex and star-convex functions. Under uniform bounds on the proximal parameters, we first prove that the inexact proximal scheme is well defined, the objective function values decrease and every accumulation point is Clarke stationary. We then use the piecewise geometry to show that any accumulation point in the interior of a region minimizes the objective function over that region and is therefore a local minimizer. We further prove that the iterates eventually remain in a single region and that the whole sequence converges under a summability condition on the error tolerance sequence. In particular, when the partition consists of only one region, namely, when the objective function is star-convex, the method is globally convergent. Therefore, the piecewise star-convex structure yields stronger conclusions than the accumulation-point stationarity that is typically obtained for general nonconvex functions. In addition, once the iterates remain in a fixed region, we obtain a sublinear rate of order \(\mathcal{O}(1/k)\) for the objective function values. We also prove that an \(\varepsilon\)-approximate Clarke stationary point is computed in at most \(\mathcal{O}(1/\varepsilon^{2})\) iterations. In the piecewise strongly star-convex setting, the method achieves linear convergence. Numerical examples illustrate the behavior of the proposed algorithm.

Article

Download

View PDF