Comparison of two kinds of approximate proximal point algorithms for monotone variational inequalities

This paper proposes two kinds of approximate proximal point algorithms （APPA） for monotone variational inequalities, both of which can be viewed as two extended versions of Solodov and Svaiter＇s APPA in the paper ＂Error bounds for proximal point subproblems and associated inexact proximal point algorithms＂ published in 2000. They are both prediction- correction methods which use the same inexactness restriction; the only difference is that they use different search directions in the correction steps. This paper also chooses an optimal step size in the two versions of the APPA to improve the profit at each iteration. Analysis also shows that the two APPAs are globally convergent under appropriate assumptions, and we can expect algorithm 2 to get more progress in every iteration than algorithm 1. Numerical experiments indicate that algorithm 2 is more efficient than algorithm 1 with the same correction step size,

Comparison of two approximal proximal point algorithms for monotone variational inequalities

Proximal point algorithms （PPA） are attractive methods for solving monotone variational inequalities （MVI）. Since solving the sub-problem exactly in each iteration is costly or sometimes impossible, various approximate versions ofPPA （APPA） are developed for practical applications. In this paper, we compare two APPA methods, both of which can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. By extending the general forward-backward splitting methods, we obtain Algorithm Ⅰ; in the same way, Algorithm Ⅱ is proposed by spreading the general extra-gradient methods. Our analysis explains theoretically why Algorithm Ⅱ usually outperforms Algorithm Ⅰ. For computation practice, we consider a class of MVI with a special structure, and choose the extending Algorithm Ⅱ to implement, which is inspired by the idea of Gauss-Seidel iteration method making full use of information about the latest iteration. And in particular, self-adaptive techniques are adopted to adjust relevant parameters for faster convergence. Finally, some numerical experiments are reported on the separated MVI. Numerical results showed that the extending Algorithm II is feasible and easy to implement with relatively low computation load.

MODIFIED APPROXIMATE PROXIMAL POINT ALGORITHMS FOR FINDING ROOTS OF MAXIMAL MONOTONE OPERATORS

In order to find roots of maximal monotone operators, this paper introduces and studies the modified approximate proximal point algorithm with an error sequence {e k} such that || ek || \leqslant hk || xk - [(x)\tilde]k ||\left\| { e^k } \right\| \leqslant \eta _k \left\| { x^k - \tilde x^k } \right\| with ?k = 0￥ ( hk - 1 ) < + ￥\sum\limits_{k = 0}^\infty {\left( {\eta _k - 1} \right)} and infk \geqslant 0 hk = m\geqslant 1\mathop {\inf }\limits_{k \geqslant 0} \eta _k = \mu \geqslant 1 . Here, the restrictions on {η k} are very different from the ones on {η k}, given by He et al (Science in China Ser. A, 2002, 32 (11): 1026–1032.) that supk \geqslant 0 hk = v < 1\mathop {\sup }\limits_{k \geqslant 0} \eta _k = v . Moreover, the characteristic conditions of the convergence of the modified approximate proximal point algorithm are presented by virtue of the new technique very different from the ones given by He et al.

Approximate Customized Proximal Point Algorithms for Separable Convex Optimization

Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint.We design two types of inexact error criteria for the subproblems.The first one is absolutely summable error criterion,under which both subproblems can be solved inexactly.When one of the two subproblems is easily solved,we propose another novel error criterion which is easier to implement,namely relative error criterion.The relative error criterion only involves one parameter,which is more implementable.We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms.The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.

The Developments of Proximal Point Algorithms

The problem of finding a zero point of a maximal monotone operator plays a central role in modeling many application problems arising from various fields,and the proximal point algorithm(PPA)is among the fundamental algorithms for solving the zero-finding problem.PPA not only provides a very general framework of analyzing convergence and rate of convergence of many algorithms,but also can be very efficient in solving some structured problems.In this paper,we give a survey on the developments of PPA and its variants,including the recent results with linear proximal term,with the nonlinear proximal term,as well as the inexact forms with various approximate criteria.

PROXIMAL POINT ALGORITHM WITH ERRORS FOR GENERALIZED STRONGLY NONLINEARQUASIVARIATIONAL INCLUSIONS

In this paper, a class of generalized strongly nonlinear quasivariational inclusions are studied. By using the properties of the resolvent operator associated with a maximal monotone; mapping in Hilbert space, an existence theorem of solutions for generalized strongly nonlinear quasivariational inclusion is established and a new proximal point algorithm with errors is suggested for finding approximate solutions which strongly converge to the exact solution of the generalized strongly, nonlinear quasivariational inclusion. As special cases, some known results in this field are also discussed.

Proximal point algorithm for a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings

We introduced a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings. Using the resolvent operator method in Hilbert spaces, we suggested a new proximal point algorithm for finding approximate solutions, which strongly converge to the exact solution of a fuzzy set-valued variational inclusion with (H,η)-monotone. The results improved and generalized the general quasi-variational inclusions with fuzzy set-valued mappings proposed by Jin and Tian Jin MM, Perturbed proximal point algorithm for general quasi-variational inclusions with fuzzy set-valued mappings, OR Transactions, 2005, 9(3): 31-38, (In Chinese); Tian YX, Generalized nonlinear implicit quasi-variational inclusions with fuzzy mappings, Computers & Mathematics with Applications, 2001, 42: 101-108.

A PROXIMAL POINT ALGORITHM FOR A SYSTEM OF GENERALIZED MIXED VARIATIONAL INEQUALITIES

This paper introduces and considers a new system of generalized mixed variational inequal- ities in a Hilbert space, which includes many new and known systems of variational inequalities and generalized variational inequalities as special cases. By using the two concepts of η-subdifferential and η-proximal mappings of a proper function, the authors try to demonstrate that the system of generalized mixed variational inequalities is equivalence with a fixed point problem. By applying the equivalence, a new and innovative η-proximal point algorithm for finding approximate solutions of the system of generalized mixed variational inequalities will be suggested and analyzed. The authors also study the convergence analysis of the new iterative method under much weaker conditions. The results can be viewed as a refinement and improvement of the previously known results for variational inequalities.

PROXIMAL POINT ALGORITHM FOR MINIMIZATION OF DC FUNCTION

In this paper we present some algorithms for minimization of DC function (difference of two convex functions). They are descent methods of the proximal-type which use the convex properties of the two convex functions separately. We also consider an approximate proximal point algorithm. Some properties of the ε-subdifferential and the ε-directional derivative are discussed. The convergence properties of the algorithms are established in both exact and approximate forms. Finally, we give some applications to the concave programming and maximum eigenvalue problems.

On the Convergence Rate of a Proximal Point Algorithm for Vector Function on Hadamard Manifolds

The proximal point algorithm has many interesting applications,such as signal recovery,signal processing and others.In recent years,the proximal point method has been extended to Riemannian manifolds.The main advantages of these extensions are that nonconvex problems in classic sense may become geodesic convex by introducing an appropriate Riemannian metric,constrained optimization problems may be seen as unconstrained ones.In this paper,we propose an inexact proximal point algorithm for geodesic convex vector function on Hadamard manifolds.Under the assumption that the objective function is coercive,the sequence generated by this algorithm converges to a Pareto critical point.When the objective function is coercive and strictly geodesic convex,the sequence generated by this algorithm converges to a Pareto optimal point.Furthermore,under the weaker growth condition,we prove that the inexact proximal point algorithm has linear/superlinear convergence rate.

STRONG CONVERGENCE OF MONOTONE HYBRID METHOD FOR FIXED POINT ITERATION PROCESSES

K. Nakajo and W. Takahashi in 2003 proved the strong convergence theorems for nonex-pansive mappings, nonexpansive semigroups, and proximal point algorithm for zero point of monotone operators in Hilbert spaces by using the hybrid method in mathematical programming. The purpose of this paper is to modify the hybrid iteration method of K. Nakajo and W. Takahashi through the monotone hybrid method, and to prove strong convergence theorems. The convergence rate of iteration process of the monotone hybrid method is faster than that of the iteration process of the hybrid method of K. Nakajo and W. Takahashi. In the proofs in this article, Cauchy sequence method is used to avoid the use of the demiclosedness principle and Opial＇s condition.

On the Convergence Rate of a Class of Proximal-Based Decomposition Methods for Monotone Variational Inequalities

A unified efficient algorithm framework of proximal-based decomposition methods has been proposed for monotone variational inequalities in 2012,while only global convergence is proved at the same time.In this paper,we give a unified proof on theO(1/t)iteration complexity,together with the linear convergence rate for this kind of proximal-based decomposition methods.Besides theε-optimal iteration complexity result defined by variational inequality,the non-ergodic relative error of adjacent iteration points is also proved to decrease in the same order.Further,the linear convergence rate of this algorithm framework can be constructed based on some special variational inequality properties,without necessary strong monotone conditions.

A New Stopping Criterion for Eckstein and Bertsekas’s Generalized Alternating Direction Method of Multipliers

In this paper,we propose a new stopping criterion for Eckstein and Bertsekas’s generalized alternating direction method of multipliers.The stopping criterion is easy to verify,and the computational cost is much less than the classical stopping criterion in the highly influential paper by Boyd et al.(Found Trends Mach Learn 3(1):1–122,2011).

Real-Time Pricing for Smart Grid with Multiple Companies and Multiple Users Using Two-Stage Optimization

In this paper, we focus on the real-time interactions among multiple utility companies and multiple users and formulate real-time pricing(RTP) as a two-stage optimization problem. At the first stage, based on cost function, we propose a continuous supply function bidding mechanism to model the utility companies’ profit maximization problem, by which the analytic expression of electricity price is further derived. At the second stage, considering that individually optimal solution may not be socially optimal, we employ convex optimization with linear constraints to model the price anticipating users’ daily payoff maximum. Substitute the analytic expression of electricity price obtained at the first stage into the optimization problem at the second stage. Using customized proximal point algorithm(C-PPA), the optimization problem at the second stage is solved and electricity price is obtained accordingly. We also prove the existence and uniqueness of the Nash equilibrium in the mentioned twostage optimization and the convergence of C-PPA. In addition, in order to make the algorithm more practical, a statistical approach is used to obtain the function of price only through online information exchange, instead of solving it directly. The proposed approach offers RTP, power production and load scheduling for multiple utility companies and multiple users in smart grid. Statistical approach helps to protect the company’s privacy and avoid the interference of random factors, and C-PPA has an advantage over Lagrangian algorithm because the former need not obtain the objection function of the dual optimization problem by solving an optimization problem with parameters. Simulation results show that the proposed framework can significantly reduce peak time loading and efficiently balance system energy distribution.

A Homotopy Alternating Direction Method of Multipliers for Linearly Constrained Separable Convex Optimization

Linearly constrained separable convex minimization problems have been raised widely in many real-world applications.In this paper,we propose a homotopy-based alternating direction method of multipliers for solving this kind of problems.The proposed method owns some advantages of the classical proximal alternating direction method of multipliers and homotopy method.Under some suitable condi-tions,we prove global convergence and the worst-case O(k/1)convergence rate in a nonergodic sense.Preliminary numerical results indicate effectiveness and efficiency of the proposed method compared with some state-of-the-art methods.

PPA-Like Contraction Methods for Convex Optimization:A Framework Using Variational Inequality Approach

Linearly constrained convex optimization has many applications.The first-order optimal condition of the linearly constrained convex optimization is a monotone variational inequality(VI).For solving VI,the proximal point algorithm(PPA)in Euclideannorm is classical but abstract.Hence,the classical PPA only plays an important theoretical role and it is rarely used in the practical scientific computation.In this paper,we give a review on the recently developed customized PPA in Hnorm(H is a positive definite matrix).In the frame of customized PPA,it is easy to construct the contraction-type methods for convex optimization with different linear constraints.In each iteration of the proposed methods,we need only to solve the proximal subproblems which have the closed form solutions or can be efficiently solved up to a high precision.Some novel applications and numerical experiments are reported.Additionally,the original primaldual hybrid gradient method is modified to a convergent algorithm by using a prediction-correction uniform framework.Using the variational inequality approach,the contractive convergence and convergence rate proofs of the framework are more general and quite simple.

Viscosity Approximations by Generalized Contractions for Resolvents of Accretive Operators in Banach Spaces

In this paper, we prove a strong convergence theorem for resolvents of accretive operators in a Banach space by the viscosity approximation method with a generalized contraction mapping. The proximal point algorithm in a Banach space is also considered. The results extend some very recent theorems of W. Takahashi.

A Relaxed-PPA Contraction Method for Sparse Signal Recovery

Sparse signal recovery is a topic of considerable interest,and the literature in this field is already quite immense.Many problems that arise in sparse signal recovery can be generalized as a convex programming with linear conic constraints.In this paper,we present a new proximal point algorithm(PPA) termed as relaxed-PPA(RPPA) contraction method,for solving this common convex programming.More precisely,we first reformulate the convex programming into an equivalent variational inequality(VI),and then efficiently explore its inner structure.In each step,our method relaxes the VI-subproblem to a tractable one,which can be solved much more efficiently than the original VI.Under mild conditions,the convergence of the proposed method is proved.Experiments with l1 analysis show that RPPA is a computationally efficient algorithm and compares favorably with the recently proposed state-of-the-art algorithms.

A DECOMPOSITION METHOD FOR CONVEX MINIMIZATION PROBLEMS AND ITS APPLICATION

In this paper, we present a modified decomposition algorithm and its bundle style variant for convex programming problems with separable structure. We prove that these methods are globally and linearly convergent and discuss the application of the bundle variant in parallel computations.