Proximal Point Algorithms for General Variational Inequalities

This paper presents a unified framework of proximal point algorithms (PPAs) for solving general variational inequalities (GVIs). Some existing PPAs for classical variational inequalities, including both the exact and inexact versions, are extended to solving GVIs. Consequently, several new PPA-based algorithms are proposed. M. Li was supported by NSFC Grant 10571083 and SRFDP Grant 200802861031. L.Z. Liao was supported in part by grants from Hong Kong Baptist University and the Research Grant Council of Hong Kong. X.M. Yuan was supported in part by FRG/08-09/II-40 from Hong Kong Baptist University and NSFC Grant 10701055.     

On convergence criteria of generalized proximal point algorithms

We analyze some generalized proximal point algorithms which include the previously known proximal point algorithms as special cases. Weak and strong convergence of the proposed proximal point algorithms are proved under some mild conditions.     

Fast proximal algorithms for nonsmooth convex optimization

In the lines of our previous approach to devise proximal algorithms for nonsmooth convex optimization by applying Nesterov fast gradient concept to the Moreau–Yosida regularization of a convex function, we develop three new proximal algorithms for nonsmooth convex optimization. In these algorithms, the errors in computing approximate solutions for the Moreau–Yosida regularization are not fixed beforehand, while preserving the complexity estimates already established. We report some preliminary computational results to give a first estimate of their performance.     

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.     

Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a unified approach

This paper focuses on some customized applications of the proximal point algorithm (PPA) to two classes of problems: the convex minimization problem with linear constraints and a generic or separable objective function, and a saddle-point problem. We treat these two classes of problems uniformly by a mixed variational inequality, and show how the application of PPA with customized metric proximal parameters can yield favorable algorithms which are able to make use of the models’ structures effectively. Our customized PPA revisit turns out to unify some algorithms including some existing ones in the literature and some new ones to be proposed. From the PPA perspective, we establish the global convergence and a worst-case O(1/t) convergence rate for this series of algorithms in a unified way.     

The interior proximal extragradient method for solving equilibrium problems

In this article we present a new and efficient method for solving equilibrium problems on polyhedra. The method is based on an interior-quadratic proximal term which replaces the usual quadratic proximal term. This leads to an interior proximal type algorithm. Each iteration consists in a prediction step followed by a correction step as in the extragradient method. In a first algorithm each of these steps is obtained by solving an unconstrained minimization problem, while in a second algorithm the correction step is replaced by an Armijo-backtracking linesearch followed by an hyperplane projection step. We prove that our algorithms are convergent under mild assumptions: pseudomonotonicity for the two algorithms and a Lipschitz property for the first one. Finally we present some numerical experiments to illustrate the behavior of the proposed algorithms.     

Properties and Iterative Methods for the Lasso and Its Variants

The lasso of Tibshirani （1996） is a least-squares problem regularized by the l1 norm. Due to the sparseness promoting property of the l1 norm, the lasso has been received much attention in recent years. In this paper some basic properties of the lasso and two variants of it are exploited. Moreover, the proximal method and its variants such as the relaxed proximal algorithm and a dual method for solving the lasso by iterative algorithms are presented.     

Proximal minimizations with D-functions and the massively parallel solution of linear network programs

This paper discusses the massively parallel solution of linear network programs. It integrates the general algorithmic framework of proximal minimization with D-functions (PMD) with primal-dual row-action algorithms. Three alternative algorithmic schemes are studied: quadratic proximal point, entropic proximal point, and least 2-norm perturbations. Each is solving a linear network problem by solving a sequence of nonlinear approximations. The nonlinear subproblems decompose for massively parallel computing. The three algorithms are implemented on a Connection Machine CM-2 with up to 32K processing elements, and problems with up to 16 million variables are solved. A comparison of the three algorithms establishes their relative efficiency. Numerical experiments also establish the best internal tactics which can be used when implementing proximal minimization algorithms. Finally, the new algorithms are compared with an implementation of the network simplex algorithm executing on a CRAY Y-MP vector supercomputer.     

Implicit iterative algorithms for asymptotically nonexpansive mappings in the intermediate sense and Lipschitz-continuous monotone mappings

In this paper, we introduce some implicit iterative algorithms for finding a common element of the set of fixed points of an asymptotically nonexpansive mapping in the intermediate sense and the set of solutions of the variational inequality problem for a monotone, Lipschitz-continuous mapping. These implicit iterative algorithms are based on two well-known methods: extragradient and approximate proximal methods. We obtain some weak convergence theorems for these implicit iterative algorithms. Based on these theorems, we also construct some implicit iterative processes for finding a common fixed point of two mappings, such that one of these two mappings is taken from the more general class of Lipschitz pseudocontractive mappings and the other mapping is asymptotically nonexpansive.     

Halpern projection methods for solving pseudomonotone multivalued variational inequalities in Hilbert spaces

In this paper, we introduce new approximate projection and proximal algorithms for solving multivalued variational inequalities involving pseudomonotone and Lipschitz continuous multivalued cost mappings in a real Hilbert space. The first proposed algorithm combines the approximate projection method with the Halpern iteration technique. The second one is an extension of the Halpern projection method to variational inequalities by using proximal operators. The strongly convergent theorems are established under standard assumptions imposed on cost mappings. Finally we introduce a new and interesting example to the multivalued cost mapping, and show its pseudomontone and Lipschitz continuous properties. We also present some numerical experiments to illustrate the behavior of the proposed algorithms.

     

Proximal-Point Algorithm Using a Linear Proximal Term

Proximal-point algorithms (PPAs) are classical solvers for convex optimization problems and monotone variational inequalities (VIs). The proximal term in existing PPAs usually is the gradient of a certain function. This paper presents a class of PPA-based methods for monotone VIs. For a given current point, a proximal point is obtained via solving a PPA-like subproblem whose proximal term is linear but may not be the gradient of any functions. The new iterate is updated via an additional slight calculation. Global convergence of the method is proved under the same mild assumptions as the original PPA. Finally, profiting from the less restrictions on the linear proximal terms, we propose some parallel splitting augmented Lagrangian methods for structured variational inequalities with separable operators. B.S. He was supported by NSFC Grant 10571083 and Jiangsu NSF Grant BK2008255.     

Modified parallel projection methods for the multivalued lexicographic variational inequalities using proximal operator in Hilbert spaces

In this paper, building upon projection methods and parallel splitting-up techniques with using proximal operators, we propose new algorithms for solving the multivalued lexicographic variational inequalities in a real Hilbert space. First, the strong convergence theorem is shown with Lipschitz continuity of the cost mapping, but it must satisfy a strongly monotone condition. Second, the convergent results are also established to the multivalued lexicographic variational inequalities involving a finite system of demicontractive mappings under mild assumptions imposed on parameters. Finally, some numerical examples are developed to illustrate the behavior of our algorithms with respect to existing algorithms.     

A simplified view of first order methods for optimization

We discuss the foundational role of the proximal framework in the development and analysis of some iconic first order optimization algorithms, with a focus on non-Euclidean proximal distances of Bregman type, which are central to the analysis of many other fundamental first order minimization relatives. We stress simplification and unification by highlighting self-contained elementary proof-patterns to obtain convergence rate and global convergence both in the convex and the nonconvex settings, which in turn also allows to present some novel results.     

Solving policy design problems: Alternating direction method of multipliers-based methods for structured inverse variational inequalities

Inverse variational inequalities have broad applications in various disciplines, and some of them have very appealing structures. There are several algorithms (e.g., proximal point algorithms and projection-type algorithms) for solving the inverse variational inequalities in general settings, while few of them have fully exploited the special structures. In this paper, we consider a class of inverse variational inequalities that has a separable structure and linear constraints, which has its root in spatial economic equilibrium problems. To design an efficient algorithm, we develop an alternating direction method of multipliers (ADMM) based method by utilizing the separable structure. Under some mild assumptions, we prove its global convergence. We propose an improved variant that makes the subproblems much easier and derive the convergence result under the same conditions. Finally, we present the preliminary numerical results to show the capability and efficiency of the proposed methods.     

Construction of proximal distances over symmetric cones

Abstract

This paper is devoted to the study of proximal distances defined over symmetric cones, which include the non-negative orthant, the second-order cone and the cone of positive semi-definite symmetric matrices. Specifically, our first aim is to provide two ways to build them. For this, we consider two classes of real-valued functions satisfying some assumptions. Then, we show that its corresponding spectrally defined function defines a proximal distance. In addition, we present several examples and some properties of this distance. Taking into account these properties, we analyse the convergence of proximal-type algorithms for solving convex symmetric cone programming (SCP) problems, and we study the asymptotic behaviour of primal central paths associated with a proximal distance. Finally, for linear SCP problems, we provide a relationship between the proximal sequence and the primal central path.     

An Accelerated Inexact Proximal Point Algorithm for Convex Minimization

The proximal point algorithm is classical and popular in the community of optimization. In practice, inexact proximal point algorithms which solve the involved proximal subproblems approximately subject to certain inexact criteria are truly implementable. In this paper, we first propose an inexact proximal point algorithm with a new inexact criterion for solving convex minimization, and show its O(1/k) iteration-complexity. Then we show that this inexact proximal point algorithm is eligible for being accelerated by some influential acceleration schemes proposed by Nesterov. Accordingly, an accelerated inexact proximal point algorithm with an iteration-complexity of O(1/k ²) is proposed.     

A sparse proximal implementation of the LP dual active set algorithm

We present an implementation of the LP Dual Active Set Algorithm (LP DASA) based on a quadratic proximal approximation, a strategy for dropping inactive equations from the constraints, and recently developed algorithms for updating a sparse Cholesky factorization after a low-rank change. Although our main focus is linear programming, the first and second-order proximal techniques that we develop are applicable to general concave–convex Lagrangians and to linear equality and inequality constraints. We use Netlib LP test problems to compare our proximal implementation of LP DASA to Simplex and Barrier algorithms as implemented in CPLEX. This material is based upon work supported by the National Science Foundation under Grant No. 0203270.     

Proximal penalty-duality algorithms for mixed optimality conditions

Preconditioned proximal penalty-duality two- and three-field algorithms for mixed optimality conditions, of evolution mixed constrained optimal control problems, are considered. Fixed point existence analysis is performed for corresponding evolution mixed governing variational state systems, in reflexive Banach spaces. Further, convergence analysis of the proximal penalty-duality algorithms is established via fixed point characterizations. In both analysis, a resolvent fixed point variational strategy is applied.     

An improved LQP-based method for solving nonlinear complementarity problems

The well-known logarithmic-quadratic proximal (LQP)method has motivated a number of efficient numerical algorithms for solving nonlinear complementarity problems (NCPs). In this paper,we aim at improving one of them, i.e., the LQP-based interior prediction-correction method proposed in [He, Liao and Yuan, J. Comp. Math., 2006, 24(1): 33–44], via identifying more appropriate step-sizes in the correction steps. Preliminary numerical results for solving some NCPs arising in traffic equilibrium problems are reported to verify the theoretical assertions.     

How good are the proximal point algorithms?

Proximal point algorithms are applicable to a variety of settings in optimization. See Rockafellar, R.T. (1976), and Spingarn, J.E. (1981) for examples. We consider a simple idealized proximal point algorithm using gradient minimization on C² convex functions. This is compared to the direct use of the same gradient method with an appropriate mollifier. The comparison is made by determining estimates of the costrequired to reduce the function to a given precision E. Our object is to assess the potential efficiency of these algorithms even if we do not know how to realize this potential.

We find that for distant starting values, proximal point algorithms are considerably less laborious than a direct method. However there is no essential improvement in the complexity - only in the numerical factors. This negative conclusion holds for the entire family of proximal point algorithms based on the gradient methods of this paper.

The algorithms considered may be important for large scale optimization problems. In applications, the precision e that is desired is usually fixed. Assume this is the case and assume that one is given a family of problems parameterized by the dimension

n. Suppose further that for all n, the condition number Q (defined below) is bounded. Then it will be seen below that for all n sufficiently large our algorithms will require a smaller number of steps than a polynomial algorithm with cost n |Ine|