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.

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.

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.

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.

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.

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.