Convergence Analysis and Applications of the Glowinski–Le Tallec Splitting Method for Finding a Zero of the Sum of Two Maximal Monotone Operators

Many problems of convex programming can be reduced to finding a zero of the sum of two maximal monotone operators. For solving this problem, there exists a variety of methods such as the forward–backward method, the Peaceman–Rachford method, the Douglas–Rachford method, and more recently the -scheme. This last method has been presented without general convergence analysis by Glowinski and Le Tallec and seems to give good numerical results. The purpose of this paper is first to present convergence results and an estimation of the rate of convergence for this recent method, and then to apply it to variational inequalities and structured convex programming problems to get new parallel decomposition algorithms.     

Computing a global optimal solution to a design centering problem

In this paper we present a method for solving a special three-dimensional design centering problem arising in diamond manufacturing: Find inside a given (not necessarily convex) polyhedral rough stone the largest diamond of prescribed shape and orientation. This problem can be formulated as the one of finding a global maximum of a difference of two convex functions over ³ and can be solved efficiently by using a global optimization algorithm provided that the objective function of the maximization problem can be easily evaluated. Here we prove that with the information available on the rough stone and on the reference diamond, evaluating the objective function at a pointx amounts to computing the distance, with respect to a Minkowski gauge, fromx to a finite number of planes. We propose a method for finding these planes and we report some numerical results.     

An inexact proximal point method for solving generalized fractional programs

In this paper, we present several new implementable methods for solving a generalized fractional program with convex data. They are Dinkelbach-type methods where a prox-regularization term is added to avoid the numerical difficulties arising when the solution of the problem is not unique. In these methods, at each iteration a regularized parametric problem is solved inexactly to obtain an approximation of the optimal value of the problem. Since the parametric problem is nonsmooth and convex, we propose to solve it by using a classical bundle method where the parameter is updated after each ‘serious step’. We mainly study two kinds of such steps, and we prove the convergence and the rate of convergence of each of the corresponding methods. Finally, we present some numerical experience to illustrate the behavior of the proposed algorithms, and we discuss the practical efficiency of each one.      

Convergence of a hybrid viscosity approximation method for finding zeros of m-accretive operators

Numerical Algorithms - For finding a zero of an m-accretive operator in a real Banach space, we consider an implicit hybrid viscosity approximation method and show that its explicit variant...     

Convergence of the Approximate Auxiliary Problem Method for Solving Generalized Variational Inequalities

We consider an extension of the auxiliary problem principle for solving a general variational inequality problem. This problem consists in finding a zero of the sum of two operators defined on a real Hilbert space H: the first is a monotone single-valued operator; the second is the subdifferential of a lower semicontinuous proper convex function . To make the subproblems easier to solve, we consider two kinds of lower approximations for the function : a smooth approximation and a piecewise linear convex approximation. We explain how to construct these approximations and we prove the weak convergence and the strong convergence of the sequence generated by the corresponding algorithms under a pseudo Dunn condition on the single-valued operator. Finally, we report some numerical experiences to illustrate the behavior of the two algorithms.     

Coupling the Auxiliary Problem Principle and Epiconvergence Theory to Solve General Variational Inequalities

Many algorithms for solving variational inequality problems can be derived from the auxiliary problem principle introduced several years ago by Cohen. In recent years, the convergence of these algorithms has been established under weaker and weaker monotonicity assumptions: strong (pseudo) monotonicity has been replaced by the (pseudo) Dunn property. Moreover, well-suited assumptions have given rise to local versions of these results.In this paper, we combine the auxiliary problem principle with epiconvergence theory to present and study a basic family of perturbed methods for solving general variational inequalities. For example, this framework allows us to consider barrier functions and interior approximations of feasible domains. Our aim is to emphasize the global or local assumptions to be satisfied by the perturbed functions in order to derive convergence results similar to those without perturbations. In particular, we generalize previous results obtained by Makler-Scheimberg et al.     

The Glowinski–Le Tallec splitting method revisited in the framework of equilibrium problems in Hilbert spaces

In this paper, we introduce a new approach for solving equilibrium problems in Hilbert spaces. First, we transform the equilibrium problem into the problem of finding a zero of a sum of two maximal monotone operators. Then, we solve the resulting problem using the Glowinski–Le Tallec splitting method and we obtain a linear rate of convergence depending on two parameters. In particular, we enlarge significantly the range of these parameters given rise to the convergence. We prove that the sequence generated by the new method converges to a global solution of the considered equilibrium problem. Finally, numerical tests are displayed to show the efficiency of the new approach.     

A parallel descent algorithm for convex programming

In this paper, we propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5.     

On conditions to have bounded multipliers in locally lipschitz programming

For a nonlinear programming problem with locally Lipschitz objective and inequality constraint functions and continuously differentiable equality constraint functions, a necessary and sufficient condition is presented for the set of multiplier vectors to be nonempty and bounded.This author's work was supported by the National Science Foundation under Grant No. MCS 78-06716.     

Hybrid Methods for Solving Simultaneously an Equilibrium Problem and Countably Many Fixed Point Problems in a Hilbert Space

This paper presents a framework of iterative methods for finding a common solution to an equilibrium problem and a countable number of fixed point problems defined in a Hilbert space. A general strong convergence theorem is established under mild conditions. Two hybrid methods are derived from the proposed framework in coupling the fixed point iterations with the iterations of the proximal point method or the extragradient method, which are well-known methods for solving equilibrium problems. The strategy is to obtain the strong convergence from the weak convergence of the iterates without additional assumptions on the problem data. To achieve this aim, the solution set of the problem is outer approximated by a sequence of polyhedral subsets.