Non-convex Optimization via Strongly Convex Majorization-minimization

Mayeli, Azita

Canadian mathematical bulletin, Tome 63 (2020) no. 4, pp. 726-737

Résumé

In this paper, we introduce a class of nonsmooth nonconvex optimization problems, and we propose to use a local iterative minimization-majorization (MM) algorithm to find an optimal solution for the optimization problem. The cost functions in our optimization problems are an extension of convex functions with MC separable penalty, which were previously introduced by Ivan Selesnick. These functions are not convex; therefore, convex optimization methods cannot be applied here to prove the existence of optimal minimum point for these functions. For our purpose, we use convex analysis tools to first construct a class of convex majorizers, which approximate the value of non-convex cost function locally, then use the MM algorithm to prove the existence of local minimum. The convergence of the algorithm is guaranteed when the iterative points $x^{(k)}$ are obtained in a ball centred at $x^{(k-1)}$ with small radius. We prove that the algorithm converges to a stationary point (local minimum) of cost function when the surregators are strongly convex.

Détail

DOI : 10.4153/S0008439519000730

Mots-clés : Cost function, local majorizer and minimizer, surregator, Moreau envelope, infimal convolution, convex function, stationary point