Search

DC (Difference of Convex functions) programming and DCA (DC Algorithm) play a key role in nonconvex programming framework. These tools have a rich and successful history of thirty five years of development, and the research in recent years is being increasingly explored to new trends in the development of DCA: design novel DCA variants to improve standard DCA, to deal with the scalability and with broader classes than DC programs. Following these trends, we address in this paper the two wide classes of nonconvex problems, called partial DC programs and generalized partial DC programs, and investigate an alternating approach based on DCA for them. A partial DC program in two variables $$(x,y)\in \mathbb {R}^{n}\times {\mathbb {R}}^{m}$$ takes the form of a standard DC program in each variable while fixing other variable. A so-named alternating DCA and its inexact/generalized versions are developed. The convergence properties of these algorithms are established: both exact and inexact alternating DCA converge to a weak critical point of the considered problem, in particular, when the Kurdyka–Łojasiewicz inequality property is satisfied, the algorithms furnish a Frechet/Clarke critical point. The proposed algorithms are implemented on the problem of finding an intersection point of two nonconvex sets. Numerical experiments are performed on an important application that is robust principal component analysis. Numerical results show the efficiency and the superiority of the alternating DCA comparing with the standard DCA as well as a well known alternating projection algorithm.

International audience; Difference-of-Convex programming and related algorithms, which constitute the backbone of nonconvex programming and global optimization, were introduced in 1985 by Pham Dinh Tao and have been extensively developed by Le Thi Hoai An and Pham Dinh Tao since 1994 to become now classic and increasingly popular. That algorithm is a descent method without linesearch and every limit point of its generated sequence is a critical point of the related Difference-of-Convex program. Determining its convergence rate is a challenging problem. Its knowledge is crucial from both theoretical and practical points of view. In this work, we treat this problem for the class of Difference-of-Convex programs with subanalytic data by using the nonsmooth form of the Lojasiewicz inequality. We have successfully proved that the whole sequence is convergent, if it is bounded, provided that the objective function is subanalytic continuous on its domain and one of the two Difference-of-Convex components is differentiable with locally Lipschitz derivative. We also established a result on the convergence rate, which depended on the Lojasiewicz exponent of the objective function. Finally, for both classes of trust-region subproblems and nonconvex quadratic programs, we showed that the Lojasiewicz exponent was one half, and thereby, our proposed algorithms applied to these Difference-of-Convex programs were Root-linearly convergent.

In this paper, we present some inverse function theorems and implicit function theorems for set-valued mappings between Frechet spaces. The proof relies on Lebesgue's Dominated Convergence Theorem and on Ekeland's variational principle. An application to the existence of solutions of differential equations in Frechet spaces with non-smooth data is given.

This paper sheds new light on regularity of multifunctions through various characterizations of directional H\"older /Lipschitz metric regularity, which are based on the concepts of slope and coderivative. By using these characterizations, we show that directional H\"older /Lipschitz metric regularity is stable, when the multifunction under consideration is perturbed suitably. Applications of directional H\"older /Lipschitz metric regularity to investigate the stability and the sensitivity analysis of parameterized optimization problems are also discussed.

The paper concerns a new method to obtain a direct proof of the openness at linear rate/metric regularity of composite set-valued maps on metric spaces by the unification and refinement of several methods developed somehow separately in several works of the authors. In fact, this work is a synthesis and a precise specialization to a general situation of some techniques explored in the last years in the literature. In turn, these techniques are based on several important concepts (like error bounds, lower semicontinuous envelope of a set-valued map, local composition stability of multifunctions) and allow us to obtain two new proofs of a recent result having deep roots in the topic of regularity of mappings. Moreover, we make clear the idea that it is possible to use (co)derivative conditions as tools of proof for openness results in very general situations., Comment: 29 pages

International audience; In this paper, we establish some new characterizations of metric regularity of implicit multifunctions in complete metric spaces by using lower semicontinuous envelopes of the distance functions to set-valued mappings. Through these new characterizations it is possible to investigate implicit multifunction theorems based on coderivatives and on contingent derivatives as well as the perturbation stability of implicit multifunctions.

In this paper, we investigate the use of DC (Difference of Convex functions) models and algorithms in the application of trust-region methods to the solution of a class of nonlinear optimization problems where the constrained set is closed and convex (and, from a practical point of view, where projecting onto the feasible region is computationally affordable). We consider DC local models for the quadratic model of the objective function used to compute the trust-region step, and apply a primal-dual subgradient method to the solution of the corresponding trust-region subproblems. One is able to prove that the resulting scheme is globally convergent to first-order stationary points. The theory requires the use of exact second-order derivatives but, in turn, the computation of the trust-region step asks only for one projection onto the feasible region (in comparison to the calculation of the generalized Cauchy point which may require more). The numerical efficiency and robustness of the proposed new scheme when applied to bound-constrained problems is measured by comparing its performance against some of the current state-of-the-art nonlinear programming solvers on a vast collection of test problems.

We present a natural extension of DC programming and DCA for modeling and solving general DC programs with DC constraints. Two resulting approaches consist in reformulating those programs as standard DC programs in order to use standard DCAs for their solutions. The first one is based on penalty techniques in DC programming, while the second linearizes concave functions in DC constraints to build convex inner approximations of the feasible set. They are proved to converge to KKT points of general DC programs under usual constraints qualifications. Both designed algorithms can be viewed as a sequence of standard DCAs with updated penalty (resp. relaxation) parameters.

We investigate difference of convex functions (DC) programming and the DC algorithm (DCA) to solve the block clustering problem in the continuous framework, which traditionally requires solving a hard combinatorial optimization problem. DC reformulation techniques and exact penalty in DC programming are developed to build an appropriate equivalent DC program of the block clustering problem. They lead to an elegant and explicit DCA scheme for the resulting DC program. Computational experiments show the robustness and efficiency of the proposed algorithm and its superiority over standard algorithms such as two-mode K-means, two-mode fuzzy clustering, and block classification EM.

This special issue of the Vietnam Journal of Mathematics is dedicated to Professor Michel Thera on the occasion of his 70th birthday. It follows the successful international conference entitled “New Trends in Optimization and Variational Analysis for Application”, which was organized in Michel’s honor at the University of Quy Nhon on December 7–10, 2016.Due to Michel Th´era’s eminence in mathematics, we received so many high-quality articles of invited experts that we had to divide them into two regular journal issues with more than 400 pages. We would like to thank all authors for their excellent contributions, and all reviewers for their responsible work and constructive comments which did help to improve the submitted manuscripts significantly.

This thesis is devoted to present some results in the scope of Newton-type methods applied for inclusion involving set-valued mappings. In the first part, we follow the Kantorovich's and/or Smale's approaches to study the convergence of Josephy-Newton method for generalized equation (GE) in Banach spaces. Such results can be viewed as an extension of the classical Kantorovich's theorem as well as Smale's (alpha, gamma)-theory which were stated for nonlinear equations. The second part develops an algorithm using set-valued differentiation in order to solve GE. We proved that, under some suitable conditions imposed on the input data and the choice of the starting point, the algorithm produces a sequence converging at least linearly to a solution of considering GE. Moreover, by imposing some stronger assumptions related to the approximation of set-valued part, the proposed method converges locally superlinearly. The last part deals with inclusions involving maps defined on Riemannian manifolds whose values belong to an Euclidean space. Using the relationship between the geometric structure of manifolds and the retraction maps, we show that, our scheme converges locally superlinearly to a solution of the initial problem. With some more regularity assumptions on the data involved in the problem, the quadratic convergence (local and semi-local) can be ensured.; Le but de cette thèse est d'étudier la méthode de Newton pour résoudre numériquement les inclusions variationnelles, appelées aussi dans la littérature les équations généralisées. Ces problèmes engendrent en général des opérateurs multivoques. La première partie est dédiée à l'extension des approches de Kantorovich et la théorie (alpha, gamma) de Smale (connues pour les équations non-linéaires classiques) au cas des inclusions variationnelles dans les espaces de Banach. Ceci a été rendu possible grâce aux développements récents des outils de l'analyse variationnelle et non-lisse tels que la régularité métrique. La seconde partie est consacrée à l'étude de méthodes numériques de type-Newton pour les inclusions variationnelles en utilisant la différentiabilité généralisée d'applications multivoques où nous proposons de linéariser à la fois les parties univoques (lisses) et multivoques (non-lisses). Nous avons montré que, sous des hypothèses sur les données du problème ainsi que le choix du point de départ, la suite générée par la méthode de Newton converge au moins linéairement vers une solution du problème de départ. La convergence superlinéaire peut-être obtenue en imposant plus de conditions sur l'approximation multivaluée. La dernière partie de cette thèse est consacrée à l'étude des équations généralisées dans les variétés Riemaniennes à valeurs dans des espaces euclidiens. Grâce à la relation entre la structure géométrique des variétés et les applications de rétractions, nous montrons que le schéma de Newton converge localement superlinéairement vers une solution du problème. La convergence quadratique (locale et semi-locale) peut-être obtenue avec des hypothèses de régularités sur les données du problème.

Voir à la fin du fichier de thèse