Hybrid extragradient proximal algorithm coupled with parametric approximation and penalty/barrier methods

In this article we study the hybrid extragradient method coupled with approximation and penalty schemes for convex minimization problems. Under certain hypotheses, which include, for example, the case of Tikhonov regularization, we prove asymptotic convergence of the method to the solution set of our minimization problem. When we use schemes of penalization or barrier, we can show asymptotic convergence using the well-known fast/slow parameterization techniques and exploiting the existence and finite length of an optimal path.     

Hybrid methods with regularization for minimization problems and asymptotically strict pseudocontractive mappings in the intermediate sense

In this paper we introduce an iterative algorithm for finding a common element of the fixed point set of an asymptotically strict pseudocontractive mapping S in the intermediate sense and the solution set of the minimization problem (MP) for a convex and continuously Frechet differentiable functional in Hilbert space. The iterative algorithm is based on several well-known methods including the extragradient method, CQ method, Mann-type iterative method and hybrid gradient projection algorithm with regularization. We obtain a strong convergence theorem for three sequences generated by our iterative algorithm. In addition, we also prove a new weak convergence theorem by a modified extragradient method with regularization for the MP and the mapping S.     

Interior projection-like methods for monotone variational inequalities

We propose new interior projection type methods for solving monotone variational inequalities. The methods can be viewed as a natural extension of the extragradient and hyperplane projection algorithms, and are based on using non Euclidean projection-like maps. We prove global convergence results and establish rate of convergence estimates. The projection-like maps are given by analytical formulas for standard constraints such as box, simplex, and conic type constraints, and generate interior trajectories. We then demonstrate that within an appropriate primal-dual variational inequality framework, the proposed algorithms can be applied to general convex constraints resulting in methods which at each iteration entail only explicit formulas and do not require the solution of any convex optimization problem. As a consequence, the algorithms are easy to implement, with low computational cost, and naturally lead to decomposition schemes for problems with a separable structure. This is illustrated through examples for convex programming, convex-concave saddle point problems and semidefinite programming.The work of this author was partially supported by the United States–Israel Binational Science Foundation, BSF Grant No. 2002-2010.     

A projection method for solving nonlinear problems in reflexive Banach spaces

We study the convergence of an iterative algorithm for finding common fixed points of finitely many Bregman firmly nonexpansive operators in reflexive Banach spaces. Our algorithm is based on the concept of the so-called shrinking projection method and it takes into account possible computational errors. We establish a strong convergence theorem and then apply it to the solution of convex feasibility and equilibrium problems, and to finding zeroes of two different classes of nonlinear mappings.     

Extragradient method for solving quasivariational inequalities

We study methods for solving a class of the quasivariational inequalities in Hilbert space when the changeable set is described by translation of a fixed, closed and convex set. We consider one variant of the gradient-type projection method and an extragradient method. The possibilities of the choice of parameters of the gradient projection method in this case are wider than in the general case of a changeable set. The extragradient method on each iteration makes one trial step along the gradient, and the value of the gradient at the obtained point is used at the first point as the iteration direction. In the paper, we establish sufficient conditions for the convergence of the proposed methods and derive a new estimate of the rates of the convergence. The main result of this paper is contained in the convergence analysis of the extragradient method.     

An inexact spectral bundle method for convex quadratic semidefinite programming

We present an inexact spectral bundle method for solving convex quadratic semidefinite optimization problems. This method is a first-order method, hence requires much less computational cost in each iteration than second-order approaches such as interior-point methods. In each iteration of our method, we solve an eigenvalue minimization problem inexactly, and solve a small convex quadratic semidefinite program as a subproblem. We give a proof of the global convergence of this method using techniques from the analysis of the standard bundle method, and provide a global error bound under a Slater type condition for the problem in question. Numerical experiments with matrices of order up to 3000 are performed, and the computational results establish the effectiveness of this method.     

Pointwise and Ergodic Convergence Rates of a Variable Metric Proximal Alternating Direction Method of Multipliers

In this paper, we obtain global pointwise and ergodic convergence rates for a variable metric proximal alternating direction method of multipliers for solving linearly constrained convex optimization problems. We first propose and study nonasymptotic convergence rates of a variable metric hybrid proximal extragradient framework for solving monotone inclusions. Then, the convergence rates for the former method are obtained essentially by showing that it falls within the latter framework. To the best of our knowledge, this is the first time that global pointwise (resp. pointwise and ergodic) convergence rates are obtained for the variable metric proximal alternating direction method of multipliers (resp. variable metric hybrid proximal extragradient framework).     

Two strong convergence theorems for Bregman strongly nonexpansive operators in reflexive Banach spaces

We study the convergence of two iterative algorithms for finding common fixed points of finitely many Bregman strongly nonexpansive operators in reflexive Banach spaces. Both algorithms take into account possible computational errors. We establish two strong convergence theorems and then apply them to the solution of convex feasibility, variational inequality and equilibrium problems.     

The Extragradient Method for Solving Variational Inequalities in the Presence of Computational Errors

In a Hilbert space, we study the convergence of the subgradient method to a solution of a variational inequality, under the presence of computational errors. Most results known in the literature establish convergence of optimization algorithms, when computational errors are summable. In the present paper, the convergence of the subgradient method for solving variational inequalities is established for nonsummable computational errors. We show that the subgradient method generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant.     

Maximal Monotone Operators and the Proximal Point Algorithm in the Presence of Computational Errors

In a finite-dimensional Euclidean space, we study the convergence of a proximal point method to a solution of the inclusion induced by a maximal monotone operator, under the presence of computational errors. Most results known in the literature establish the convergence of proximal point methods, when computational errors are summable. In the present paper, the convergence of the method is established for nonsummable computational errors. We show that the proximal point method generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant.     

Extragradient method for solving an optimal control problem with implicitly specified boundary conditions

An optimal control problem formulated as a system of linear ordinary differential equations with boundary conditions implicitly specified as a solution to a finite-dimensional minimization problem is considered. An extragradient method for solving this problem is proposed, and its convergence is studied.     

Iterative algorithms with the regularization for the constrained convex minimization problem and maximal monotone operators

In this paper, we prove a strong convergence theorem for finding a common element of the solution set of a constrained convex minimization problem and the set of solutions of a finite family of variational inclusion problems in Hilbert space. A strong convergence theorem for finding a common element of the solution set of a constrained convex minimization problem and the solution sets of a finite family of zero points of the maximal monotone operator problem in Hilbert space is also obtained. Using our main result, we have some additional results for various types of non-linear problems in Hilbert space.     

Backward–forward algorithms for structured monotone inclusions in Hilbert spaces

In this paper, we study the backward–forward algorithm as a splitting method to solve structured monotone inclusions, and convex minimization problems in Hilbert spaces. It has a natural link with the forward–backward algorithm and has the same computational complexity, since it involves the same basic blocks, but organized differently. Surprisingly enough, this kind of iteration arises when studying the time discretization of the regularized Newton method for maximally monotone operators. First, we show that these two methods enjoy remarkable involutive relations, which go far beyond the evident inversion of the order in which the forward and backward steps are applied. Next, we establish several convergence properties for both methods, some of which were unknown even for the forward–backward algorithm. This brings further insight into this well-known scheme. Finally, we specialize our results to structured convex minimization problems, the gradient-projection algorithms, and give a numerical illustration of theoretical interest.     

A hybrid inexact Logarithmic-Quadratic Proximal method for nonlinear complementarity problems

Inspired by the Logarithmic-Quadratic Proximal method [A. Auslender, M. Teboulle, S. Ben-Tiba, A logarithmic-quadratic proximal method for variational inequalities, Comput. Optim. Appl. 12 (1999) 31-40], we present a new prediction-correction method for solving the nonlinear complementarity problems. In our method, an intermediate point is produced by approximately solving a nonlinear equation system based on the Logarithmic-Quadratic Proximal method; and the new iterate is obtained by convex combination of the previous point and the one generated by the improved extragradient method at each iteration. The proposed method allows for constant relative errors and this yields a more practical Logarithmic-Quadratic Proximal type method. The global convergence is established under mild conditions. Preliminary numerical results indicate that the method is effective for large-scale nonlinear complementarity problems.     

Another version of the proximal point algorithm in a Banach space

In this paper, we study some non-traditional schemes of proximal point algorithm for nonsmooth convex functionals in a Banach space. The proximal approximations to their minimal points and/or their minimal values are considered separately for unconstrained and constrained minimization problems on convex closed sets. For the latter we use proximal point algorithms with the metric projection operators and first establish the estimates of the convergence rate with respect to functionals. We also investigate the perturbed projection proximal point algorithms and prove their stability. Some results concerning the classical proximal point method for minimization problems in a Banach space is also presented in this paper.     

A proximal point algorithm for finding a common zero of a finite family of maximal monotone operators in the presence of computational errors

In a Hilbert space, we study the convergence of a proximal point method to a common zero of a finite family of maximal monotone operators under the presence of computational errors. Most results known in the literature establish the convergence of proximal point methods, when computational errors are summable. In the present paper, the convergence of the method is established for nonsummable computational errors. We show that the proximal point method generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant.     

Modified subgradient extragradient method for variational inequality problems

In this paper, we introduce an algorithm as combination between the subgradient extragradient method and inertial method for solving variational inequality problems in Hilbert spaces. The weak convergence of the algorithm is established under standard assumptions imposed on cost operators. The proposed algorithm can be considered as an improvement of the previously known inertial extragradient method over each computational step. The performance of the proposed algorithm is also illustrated by several preliminary numerical experiments.     

Convergence rate of a proximal multiplier algorithm for separable convex minimization

In this paper, we analyse the convergence rate of the proximal algorithm proposed by us in the article [A proximal multiplier method for separable convex minimization. Optimization. 2016; 65:501–537], which has been proposed to solve a separable convex minimization problem. We prove that, under mild assumptions, the primal-dual sequences of the algorithm converge linearly to the optimal solution for a class of proximal distances.     

Multicriteria equilibrium programming: Extragradient method

Multicriteria equilibrium programming includes as its particular cases mathematical programming, saddle point calculation, the multicriteria search for Pareto solutions, minimization with an equilibrium choice of the feasible set, etc. An extragradient method is proposed for the numerical solution of the multicriteria equilibrium programming problem, and the convergence of this method is examined.     

General iterative methods for equilibrium and constrained convex minimization problem

The gradient-projection algorithm (GPA) plays an important role in solving constrained convex minimization problems. Based on Marino and Xu's method [G. Marino and H.-K. Xu, A general method for nonexpansive mappings in Hilbert space, J. Math. Anal. Appl. 318 (2006), pp. 43–52], we combine GPA and averaged mapping approach to propose implicit and explicit composite iterative algorithms for finding a common solution of an equilibrium and a constrained convex minimization problem for the first time in this article. Under suitable conditions, strong convergence theorems are obtained.