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.

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-Like Method for Updating Simultaneously Mass and Stiffness Matrices of Finite Element Model

The problem of correcting simultaneously mass and stiffness matrices of finite element model of undamped structural systems using vibration tests is considered in this paper.The desired matrix properties,including satisfaction of the characteristic equation,symmetry,positive semidefiniteness and sparsity,are imposed as side constraints to form the optimal matrix pencil approximation problem.Using partial Lagrangian multipliers,we transform the nonlinearly constrained optimization problem into an equivalent matrix linear variational inequality,develop a proximal point-like method for solving the matrix linear variational inequality,and analyze its global convergence.Numerical results are included to illustrate the performance and application of the proposed method.

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.

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.

BEST PROXIMITY POINT THEOREMS FOR SINGLE- AND SET-VALUED NON-SELF MAPPINGS

We study the existence of best proximity points for single-valued non-self map-pings. Also, we prove a best proximity point theorem for set-valued non-self mappings in metric spaces with an appropriate geometric property. Examples are given to support the usability of our results.

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.

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.

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.

On the Convergence Rate of an Inexact Proximal Point Algorithm for Quasiconvex Minimization on Hadamard Manifolds

In this paper,we present an analysis about the rate of convergence of an inexact proximal point algorithm to solve minimization problems for quasiconvex objective functions on Hadamard manifolds.We prove that under natural assumptions the sequence generated by the algorithm converges linearly or superlinearly to a critical point of the problem.

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.

Inexact Proximal Point Methods for Quasiconvex Minimization on Hadamard Manifolds

In this paper we present two inexact proximal point algorithms to solve minimization problems for quasiconvex objective functions on Hadamard manifolds.We prove that under natural assumptions the sequence generated by the algorithms are well defined and converge to critical points of the problem.We also present an application of the method to demand theory in economy.

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.

A Variational Principle and Best Proximity Points

We generalize Ekeland＇s Variational Principle for cyclic maps. We present applications of this version of the variational principle for proving of existence and uniqueness of best proximity points for different classes of cyclic maps.

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.

Proximal Methods with Bregman Distances to Solve VIP on Hadamard Manifolds with Null Sectional Curvature

We present an extension of the proximal point method with Bregman distances to solve variational inequality problems(VIP)on Hadamard manifolds with null sectional curvature.Under some natural assumptions,as for example,the existence of solutions of the VIP and the monotonicity of the multivalued vector field,we prove that the sequence of the iterates given by the method converges to a solution of the problem.Furthermore,this convergence is linear or superlinear with respect to the Bregman distance.

Proximal-Based Pre-correction Decomposition Methods for Structured Convex Minimization Problems

This paper presents two proximal-based pre-correction decomposition methods for convex minimization problems with separable structures.The methods,derived from Chen and Teboulle’s proximal-based decomposition method and He’s parallel splitting augmented Lagrangian method,remain the nice convergence property of the proximal point method and could compute variables in parallel like He’s method under the prediction-correction framework.Convergence results are established without additional assumptions.And the efficiency of the proposed methods is illustrated by some preliminary numerical experiments.

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.