Many tasks in imaging can be modeled via the minimization of a nonconvex composite function. A popular class of algorithms for solving such problems are majorization-minimization techniques which iteratively approximate the composite nonconvex function by a majorizing function that is easy to minimize. Most techniques, e.g. gradient descent, utilize convex majorizers in order guarantee that the majorizer is easy to minimize. In our work we consider a natural class of nonconvex majorizers for these functions, and show that these majorizers are still sufficient for a provably convergent optimization scheme under quite general assumptions. Numerical results illustrate that by applying this scheme, one can often obtain superior local optima compared to previous majorization-minimization methods, when the nonconvex majorizers are solved to global optimality. Finally, we illustrate the behavior of our algorithm for depth super-resolution from raw time-of-flight data.
Finally, a recent preprint @cite_12 proposes to solve composite minimization problems with a different approach, namely a nonlinear splitting variant, reformulating the problem to and introducing an augmented Lagrangian formulation with an additional variable @math that mimics the dual variable of the convex setting. This is a quite interesting result, as it shows that the complementarity of forward-backward splitting and augmented Lagrangian methods can be extended into the composite setting. Whereas our method is a generalization of forward-backward splittings, their work generalizes ADMM @cite_40 . Critically both ours and their approach rely on the efficient solution of a nonlinear programming task as intermediate step in the algorithm. For us, this is the nonconvex majorizer eq:aux , the corresponding problem in [Eq. (6.3)] bolte_nonconvex_2018 is the minimization of eq:ALM for @math : Both subproblems are in general equally difficult as they are connected for @math , identifying @math and @math .
@cite_40 @cite_12
2045079045 2783928198
For variational problems of the form Infv∈V f(Av)+g(v) , we propose a dual method which decouples the difficulties relative to the functionals f and g from the possible ill-conditioning effects of the linear operator A. The approach is based on the use of an Augmented Lagrangian functional and leads to an efficient and simply implementable algorithm. We study also the finite element approximation of such problems, compatible with the use of our algorithm. The method is finally applied to solve several problems of continuum mechanics. We introduce a novel approach addressing global analysis of a difficult class of nonconvex-nonsmooth optimization problems within the important framework of Lagrangian-based methods. This genuine nonlinear class captures many problems in modern disparate fields of applications. It features complex geometries, qualification conditions, and other regularity properties do not hold everywhere. To address these issues we work along several research lines to develop an original general Lagrangian methodology which can deal, all at once, with the above obstacles. A first innovative feature of our approach is to introduce the concept of Lagrangian sequences for a broad class of algorithms. Central to this methodology is the idea of turning an arbitrary descent method into a multiplier method. Secondly, we provide these methods with a transitional regime allowing us to identify in finitely many steps a zone where we can tune the step-sizes of the algorithm for the final converging regime. Then, despite the min-max nature of Lagrangian methods, using an original Lyapunov method we prove that each bounded sequence generated by the resulting monitoring schemes are globally convergent to a critical point for some fundamental Lagrangian-based methods in the broad semialgebraic setting, which to the best of our knowledge, are the first of this kind.