Search

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. Second, 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. Funding: The research of Jerome Bolte is sponsored by the Air Force Office of Scientific Research, Air Force Material Command, USAF [Grant number FA9550-15-1-0500] and the FMJH Program Gaspard Monge in optimization and operations research. The research of Shoham Sabach was partially supported by the German Israel Foundation, GIF [Grant G-1243-304.6/2014]. The research of Marc Teboulle was partially supported by the Israel Science Foundation, ISF [Grants 998/12 and 1844/16], and the German Israel Foundation, GIF [Grant G-1243-304.6/2014]. Keywords: nonlinear composite minimization * nonconvex and nonsmooth minimization * Lagrangian-based methods * proximal method of multipliers * semialgebraic optimization * nonsmooth Kurdyka-tojasiewicz property * global convergence, 1. Introduction Consider the following nonconvex and nonlinear composite minimization problem: (CM) minimize{f(x) = [f.sub.0](x) + h(F(x)): x [member of] [R.sup.n]}, where * [f.sub.0]: [R.sup.n] [right arrow] R is a [...]

Abstract. The proximal gradient and its variants is one of the most attractive first-order algorithm for minimizing the sum of two convex functions, with one being nonsmooth. However, it requires [...]

Several entropy-like proximal mapping methods for convex programming are investigated. Such an approach replaces quadratic regularization kernels with convex statistical distances known as phi-divergences. To this end, the convergence characteristics of the iterative algorithms generated by the use of such schemes for convex programming are studied. This is followed by the application of the resulting algorithm to the dual of a convex program. The results show a wide variety of nonquadratic multiplier techniques and confirm their convergence.

Entropy-like regularization processes can supply a fairly general stucture for building smoothing and approximation methods to use with optimization problems, according to an investigation of a new type of approximation functions. The quadratic kernel is replaced and entropy-like distances are used, and results that are obtained are similar in many ways to that resulting from use of the quadratic kernel. Entropic proximal functions can also be used to build augmented Lagrangians.

We propose a unifying framework that combines smoothing approximation with fast first order algorithms for solving nonsmooth convex minimization problems. We prove that independently of the structure of the convex nonsmooth function involved, and of the given fast first order iterative scheme, it is always possible to improve the complexity rate and reach an O(ε-1) efficiency estimate by solving an adequately smoothed approximation counterpart. Our approach relies on the combination of the notion of smoothable functions that we introduce with a natural extension of the Moreau-infimal convolution technique along with its connection to the smoothing mechanism via asymptotic functions. This allows for clarification and unification of several issues on the design, analysis, and potential applications of smoothing methods when combined with fast first order algorithms. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing a fractional quadratic problem involving the ratio of two indefinite quadratic functions, subject to a two-sided quadratic form constraint. This formulation is motivated by the so-called regularized total least squares (RTLS) problem. A key difficulty with this problem is its nonconvexity, and all current known methods to solve it are guaranteed only to converge to a point satisfying first order necessary optimality conditions. We prove that a global optimal solution to this problem can be found by solving a sequence of very simple convex minimization problems parameterized by a single parameter. As a result, we derive an efficient algorithm that produces an ∊-global optimal solution in a computational effort of O(n3 log ∊-1). The algorithm is tested on problems arising from the inverse Laplace transform and image deblurring. Comparison to other well-known RTLS solvers illustrates the attractiveness of our new method. [ABSTRACT FROM AUTHOR]

We consider the problem of finding a point in the intersection of an affine set with a compact convex set, called a convex linear system (CLS). The conditional gradient method is known to exhibit a sublinear rate of convergence. Exploiting the special structure of (CLS), we prove that the conditional gradient method applied to the equivalent minimization formulation of (CLS), converges to a solution at a linear rate, under the sole assumption that Slater’s condition holds for (CLS). The rate of convergence is measured explicitly in terms of the problem’s data and a Slater point. Application to a class of conic linear systems is discussed. [ABSTRACT FROM AUTHOR]