# Convergence Analysis on an Accelerated Proximal Point Algorithm for Linearly Constrained Optimization Problems

Authors: Sha Lu; Zengxin Wei
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Proximal point algorithm is a type of method widely used in solving optimization problems and some practical problems such as machine learning in recent years. In this paper, a framework of accelerated proximal point algorithm is presented for convex minimization with linear constraints. The algorithm can be seen as an extension to Gu¨ler’s methods for unconstrained optimization and linear programming problems. We prove that the sequence generated by the algorithm converges to a KKT solution of the original problem under appropriate conditions with the convergence rate of O1/k2.


---

## Body

## 1. Introduction

Proximal point algorithm (abbr. PPA) is a type of method widely used in solving optimization problems, fixed point problems, maximal monotone operator problems, and so on. The framework of the proximal point method is closely related to many algorithms. It even can do more interpretation and generalization of some other methods and algorithms. In recent years, combining the idea of the proximal point method or the proximal terms with some existing algorithms shows that it can improve the performance of the original algorithms in a certain extent. The main step of the PPA is to compute a subproblem consisting of proximal point operator. In some practical problems with suitable conditions, the proximal point subproblems may be expressed as convex optimization problems with smaller scales or better properties which make them even have closed form solutions. In recent years, the proximal point method, together with its relative models, and several types of PPAs have been used in machine learning, image recognition, signal processing, and so on [1–3].The original PPA can be seen in Martinet [4, 5] about the research of the fixed point problem and the variational inequality. For any given x0 in a Hilbert space, Martinet [4] gave an iterative sequence xkk∈N for variational inequality problem by a PPA based on the following inclusion relation:(1)xk+1∈I+ckT−1xk,where ck is a sequence of positive integers and T is a maximal monotone operator. Later, in the unconstrained minimization of fx, where f· is a proper lower semicontinuous convex function in a Hilbert space, Rockafellar [6, 7] presented a more practical PPA which had the iteration as(2)xk+1≈argminfx+12βkx−xk2.Ifβk≥β>0, for all k, it was proved that the PPA weakly converges to a zero solution of the maximal monotone operator T. And when βk⟶∞, the convergence rate is superlinear. In 1991, Gu¨ler [8] further discussed the PPA and its convergent property. He proved that, under weaker conditions, that is, when βkk∈N satisfies ∑k=0∞βk⟶∞, the PPA is convergent. Furthermore, its global convergence rate can be given as(3)fxk−fx∗=O1∑j=0k−1βj.For solving the convex programming problem with Lipschitz continuous gradients, Nesterov [9] gave an accelerated gradient method, which added a step to the gradient descent direction in order to reduce the times of iterations and obtained the iterative estimation of general first-order methods. The idea of acceleration was then introduced into other optimization algorithms, such as Gu¨ler [10], who gave two new PPAs by adding auxiliary point series and adopting acceleration strategy. Compared with (3), his accelerated algorithms obtained better convergence rate:(4)fxk−fx∗=O1∑j=0k−1βj2.Gu¨ler [11] also applied this method to linear programming and proposed new augmented Lagrangian multiplier algorithms. While the iteration subproblems were solved inexactly, the algorithms not only maintained the global convergent property but also provided faster global convergence rates and can terminate in finite iterations to obtain the primal and dual optimal solutions. In the literature of Birge et al. [12], the authors further generalized Gu¨ler’s accelerated proximal point method to unconstrained nonsmooth convex optimization problems. They gave a model algorithm and then presented a family of PPAs which generated xk+1 under a different rule from the classical PPA. Under weaker conditions, the estimation of the global convergence rate is obtained. They also discussed the application of PPA on stochastic programming and the variant proximal bundle method. More research studies on the proximal point method can be found in the review of Parikh and Boyd [13]. In recent years, much effort has been made to accelerate various first-order methods and the convergence analysis for linearly constrained convex optimization. For example, Ke and Ma [14] proposed an accelerated augmented Lagrangian method for solving the linearly constrained convex programming and showed its convergence rate is O1/k2. Xu [15] proposed two accelerated methods for solving structured linearly constrained convex programming and discussed their convergence rate under different conditions. Zhang et al. [16] applied the proximal method of multipliers for equality constrained optimization problems and proved that, under linear independence constraint qualification and the second-order sufficiency optimality condition, it is linearly convergent. And when the penalty parameter increases to +∞, it is superlinear.Now, we consider an accelerated PPA for solving convex optimization problem with linear equality constraints:(5)Pminx∈ℛnfx,s.t.Ax=b,where fx:Rn⟶R∪+∞ is a proper lower semicontinuous (not necessary smooth) convex function and A∈Rm×n, b∈Rm. Our main work is as follows. (1) By using the Lagrange function, the KKT system, and the original-dual relations, we construct appropriate auxiliary sequences by quadratic convex functions φkx and auxiliary points yk. Then, we update xk and the Lagrange multipliers, respectively, to extend the accelerated PPA to general convex optimization problems. (2) In the extended algorithm, the parameter αk which is related to the convergence rate is updated with an introduced constant c. The update of αk in Gu¨ler’s algorithm can be seen as a special case with c=1. (3) When the iteration subproblems are solved exactly, the algorithm has the convergence rate of O1/k2 in terms of the objective residual of the associated Lagrange function.The remaining parts of this paper are organized as follows. In Section2, a framework of the accelerated PPA is presented for constrained optimization problem (5). In Section 3, the global convergence is established under mild assumptions. In Section 4, the convergence rate based on the function values is given. In Section 5, we conclude this paper with some remarks.


## 2. An Accelerated PPA for Constrained Convex Optimization

For an unconstrained optimization problem,(6)minx∈Rnfx,the classical PPA generates the next iteration point by(7)xk+1≔Pβkfxk=argminz∈Rnfz+12βkz−xk2.And the main accelerating idea of Nesterov [9] and Gu¨ler [10] is to construct a sequence of auxiliary quadratic convex functions φkx which can be seen as estimations of fx but with better functional states. While k increases, the difference between the auxiliary functions and the original objective function is compressed such that, for any x∈Rn,(8)φkx−fx≤1−αk−1φk−1x−fx,αk−1∈0,1.Then, in each iteration of the algorithm, it producesxk satisfying(9)fxk≤φk∗≔φkvk∗=minx∈Rnφkx,where vk∗ is the minimal point of φkx. Thus, while the minimal point x∗ exists, since fx is proper, it obtains(10)fxk−fx∗≤φkx∗−fx∗≤∏j=0k−11−αjφ0x∗−fx∗.Since∏j=0k−11−αj⟶0k⟶+∞, the sequence xkk∈N minimizes fx and the speed that fx converges to f∗ is related to ∏j=0k−11−αj.The key steps in the accelerated algorithm are the construction of the auxiliary quadratic convex functions with suitable estimation onfx, the producing of xk satisfying (15), and the selection of the compressing factor αk. Inspired by Nesterov’s estimate sequences and the PPA given by Gu¨ler[10], we consider the constrained optimization problem (5). It is known that the dual problem of (5) is(11)Dminλ∈ℛmf∗A⊤λ−λ⊤b,where f∗ is the Fenchel conjugate function of f. And the augmented Lagrangian function associated with (5) is defined as(12)ℒσx,λ≔fx−λ⊤Ax−b+σ2Ax−b2,where λ∈Rm is the multiplier and σ>0 is a penalty parameter. To simplify the discussion, we denote the proximal point about function f at a given y as(13)yp=Pβfy≔argminz∈Rnfz+12βz−y2.Firstly, we construct a series of quadratic regular functions for (12) before the accelerated PPA is given. For given x0,λ0, and a0>0, let(14)φ0x≔ℒσx0,λ0+a02x−x02=fx0−λ0⊤Ax0−b+σ2Ax0−b2+a02x−x02,(15)φk+1x≔1−αkφkx+αkfykp+1βkyk−ykp⊤x−ykp+1−αkλk⊤Axk−b−σ2Axk−b2−λk⊤Aykp−b+12+αkσAykp−b2,k≥0.Sincefx is convex and φkx is a quadratic regular function, for any k∈N, φkx can be written in the canonical form:(16)φkx=φkvk∗+ak2x−vk∗2,where vk∗ means the minimizer of φkx.On the contrary, from (15), we have(17)φk+1x=1−αkφkvk∗+ak2x−vk∗2+αkfykp+1βkyk−ykp⊤x−ykp+1−αkλk⊤Axk−b−σ2Axk−b2−λk⊤Aykp−b+12+αkσAykp−b2.Comparing the second terms of (16) and (17), it implies(18)ak+1=1−αkak.It is not hard to see that the minimum values and the minimizers between two adjacent quadratic functions have the following relationships:(19)φk+1vk+1∗=1−αkφkvk∗+ak2vk+1∗−vk∗2+αkfykp+1βkyk−ykp⊤vk+1∗−ykp+1−αkλk⊤Axk−b−σ2Axk−b2−λk⊤Aykp−b+12+αkσAykp−b2,and(20)vk+1∗=vk∗−αkak+1βkyk−ykp.If we generate the iteration points byxk+1≔ykp for k≥0, the following lemma shows the relationship between the Lagrange function, the proximal point ykp, the constructed quadratic estimation function φkx, and its minimizer vk+1∗.Lemma 1.
Suppose fork≥0, φkx, ℒσx,λ, xk, vk∗, and ykp are defined as previously mentioned. Let c∈0,2,(21)yk=1−αkxk+αkvk∗,αk21−αkakβk=c,λ˜k+1=λ˜k−αkσAxk+1−b.Then, we have(22)φk+1vk+1∗≥ℒσxk+1,λ˜k+12βk2−cyk−xk+12≥ℒσxk+1,λ˜k.Proof.
We prove it by induction. Whilek=0, (22) is obvious. Now, assume(23)φkvk∗≥ℒσxk,λ˜k−1.
Sincefx is convex, fx+1/2βkx−yk2 is strong convex, from the definition of ykp; then, we have(24)0∈∂fykp+1βkykp−yk.
By convexity, for anyx∈Rn, it has(25)fx≥fykp+1βkyk−ykp⊤x−ykp.
Then, by (23),(26)φkvk∗≥fxk−λ˜k−1⊤Axk−b+σ2Axk−b2≥fykp+1βkyk−ykp⊤xk−ykp−λ˜k−1⊤Axk−b+σ2Axk−b2.
Substitute (18) and (26) into (20), it implies(27)φk+1vk+1∗≥1−αkfykp+1βkyk−ykp⊤xk−ykp−λ˜k−1⊤Axk−b+σ2Axk−b2+ak+12vk+1∗−vk∗+αkfykp+1βkyk−ykp⊤vk+1∗−ykp+1−αkλ˜k−1⊤Axk−b−σ2Axk−b2−λ˜k−1⊤Aykp−b+12+αkσAykp−b2=fykp+1−αkβkyk−ykp⊤xk−ykp+αk22ak+1βk2yk−ykp2+αkβkyk−ykp⊤vk+1∗−ykp−λk⊤Aykp−b+σ2Aykp−b2=ℒσykp,λ˜k+αk22ak+1βk2yk−ykp2+1βkyk−ykp⊤1−αkxk+αkvk+1∗−ykp.
Notice that, in the last term of (27), by using yk=1−αkxk+αkvk∗, it turns out(28)1−αkx+αkvk+1∗−ykp=αkvk+1∗−vk∗+yk−ykp.
Thus, by (20), we gain(29)yk−ykp⊤1−αkx+αkvk+1∗−ykp=1−αk2ak+1βkyk−ykp2.
Substituting this formula into (27), it deduces(30)φk+1vk+1∗≥ℒσykp,λ˜k+αk22ak+1βk2yk−ykp2+1βk1−αk2ak+1βkyk−ykp2=ℒσykp,λ˜k+1βk1−αk22ak+1βkyk−ykp2.
By using ofak+1=1−αkak, αk2/1−αkakβk=c<2, and xk+1=ykp, we have(31)φk+1vk+1∗≥ℒσxk+1,λ˜k+12βk2−cyk−xk+12≥ℒσxk+1,λ˜k.
From Lemma1, φk+1vk+1∗ can be seen as an upper bound estimation of the Lagrange function on xk+1,λ˜k. vk∗, yk, αk, and λ˜k all can be updated by explicit formulas. Thus, we give the accelerated PPA for the constrained optimization problem (5) as follows.
Accelerated PPA for constrained convex optimizationC−APPA:(i)
Step 0: letx0∈Rn,λ˜−1=λ˜0∈Rm. Choose β0>0,σ>0,a>0,c∈0,2.Letv0∗≔x0,a0≔a.(ii)
Step 1: letβk>0,(32)αk≔cakβk2+4cakβk−cakβk2,(33)yk≔1−αkxk+αkvk∗.(iii)
Step 2: compute the proximal point and the updating(34)xk+1≔argminx∈Rnfx−λ˜k⊤Ax−b+σ2Ax−b2+12βkx−yk2,(35)=argminx∈Rnfx+σ2Ax−b−λ˜kσ2+12βkx−yk2,(36)λk+1≔λ˜k−σAxk+1−b,(37)ak+1≔1−αkak,(38)vk+1∗≔vk∗+αkak+1βkxk+1−yk,(39)λ˜k+1≔λ˜k+αkλk+1−λ˜k.(iv)
Step 3: letk≔k+1 and go to Step 1.Remark 1.
It is obvious that0<αk<1 by the definition. Actually, from (10), the convergence of the algorithm relates to ∏1−αk. In the later Theorem 1, it needs to assume the nonzero lower bound such that αk≥α¯>0. In particular, when cαkβk=1, it obtains αk=5−1/2.Remark 2.
In the iterations,xk+1 can be computed from (34) or (35), which has the same result though they have different quadratic terms. We will use these two different subproblem forms in later discussion on convergence for convenience. One is used to prove the sequence converges to the KKT solution and the other (35), which is more suitable for measuring changes in function values and the constraints, is used in the analysis on the convergence rate.Remark 3.
In the problem (35), scaled proximal terms also can be used such as x−ykQ2, where Q is a positive semidefinite matrix. For some structured function fx and appropriately chosen Q, the augmented term can be linearized, and it makes (35) have a closed form solution. Or in practice, we can solve the problem inexactly, but it may not retain O1/k2 convergence rate, which we will show in the following sections under the same assumptions. Further discussion will be out of the scope of this paper, and we leave the discussion on inexactly solving cases and their numerical experiments to another paper.


## 3. Global Convergence

Assumption 1.
Assume thatf is a proper lower semicontinuous convex function and x0∈Rn is a feasible point of (5).
From Corollaries 28.2.2 and 28.3.1 of [17], under Assumption 1, the KKT set of (5) is nonempty. Moreover, x¯ is the solution of (5) iff there exists λ¯∈Rm such that x¯,λ¯ satisfies the KKT system:(40)A⊤λ¯∈∂fx¯,Ax¯=b.
Denotexke=xk−x¯, λke=λk−λ¯, and λ˜ke=λ˜k−λ¯. We have the lemmas as follows.Lemma 2.
Suppose thatxk,λk is generated by C-APPA and x¯,λ¯ is a KKT solution of (5). Then, for k=1,2,…,, it has(41)λk+1e+σ1−αkAxk+1e,Axk+1e=−σαk2Axk+1e2−12σαkλk+1e+σ1−αkAxk+1e2−λke+σ1−αk−1Axke2.Proof.
By the first-order optimization condition of (34) and together with (36), we have(42)A⊤λk+1−1βkxk+1−yk∈∂fxk+1,(43)A⊤λk−1βk−1xk−yk−1∈∂fxk.
Sincefx is proper lower semicontinuous convex function and by Theorem 12.17 of Rockalellar and Wets [18], ∂f is a maximal monotone operator and there exists a self-adjoint positive semidefinite linear operator Σf such that, for any x,x′∈domf with u∈∂fx and u′∈∂fx′,(44)fx≥fx′+u′,x−x′+12x−x′Σf2,(45)u−u′,x−x′≥x−x′Σf2.
Notice thatx¯ and λ¯ satisfy the KKT system, and it implies(46)λk+1e,Axk+1e−1βkxk+1−yk,xk+1e≥xk+1eΣf2.
By using of (36) and (39), it is easy to know that(47)Axk+1−b=Axk+1−x¯=1σλ˜k−λk+1=−1σαkλ˜k+1−λ˜k.
Thus,(48)λk+1e,Axk+1e+λ˜ke−λk+1e,Axk+1e−σAxk+1−b,Axk+1e−1βkxk+1−yk,xk+1e≥xk+1eΣf2.
By (36) and (39) in the algorithm, we have(49)λ˜k=λk+αk−1−1λk−λ˜k−1=λk−σαk−1−1Axk−b,and(50)λk+1=λk−σαk−1Axk−b+σAxk−Axk+1.
Then,(51)λk+1e+σ1−αkAxk+1e+σαkAxk+1−b=λke+σ1−αk−1Axke.
From the basic relations,(52)2u,v=u2+v2−u−v2=u+v2−u2−v2,it deduces(53)λk+1e+σ1−αkAxk+1e,Axk+1−b=12σαkλke+σ1−αk−1Axke2−12σαkλk+1e+σ1−αkAxk+1e2−σαk2Axk+1−b2.
SinceAx¯=b,Axk+1−b=Axk+1e, we gain (41) by (53).Lemma 3.
Suppose thatxk,λk is generated by C-APPA and x¯,λ¯ is a KKT solution of (5). Then, for k=1,2,…, it has(54)λke−λk+1e,Axk+1e−σAxk+1−b,Axk+1e≤−2xk+1−xkΣf2−1βk−1βk−1xk+1−xk2−1βkxk+1−yk2−xk−yk2+1βk−1xk−yk−12+σαk−1−12Axke2−σαk−12Axk+1e2−σ2Axk+1e−Axke2.Proof.
From(55)1βkxk+1−yk−1βk−1xk−yk−1,xk+1−xk≥121βk−1βk−1xk+1−xk2+12βkxk+1−yk2−xk−yk2−12βk−1xk−yk−12,and together with (42), (43), and (45), we have(56)A⊤λk+1−λk−1βkxk+1−yk+1βk−1xk−yk−1,xk+1−xk≥xk+1−xkΣf2.
Then,(57)λk+1−λk,Axk+1−xk−1βkxk+1−yk−1βk−1xk−yk−1,xk+1−xk≥xk+1−xkΣf2.
By (55), it deduces(58)λk+1−λk,Axk+1−xk≥121βk−1βk−1xk+1−xk2+12βkxk+1−yk2−xk−yk2−12βk−1xk−yk−12+xk+1−xkΣf2.
From (50) and (55), we can obtain(59)σAxke−Axk+1e,Axk+1e=Axk+1e−Axke,λk+1−λk+σαk−1−1Axk+1e−Axke,Axke≥xk+1−xkΣf2+121βk−1βk−1xk+1−xk2+12βkxk+1−yk2−xk−yk2−12βk−1xk−yk−12+σ1−αk−12Axke2−σ1−αk−12Axk+1e2+σ1−αk−12Axk+1−xk2.
Also by using of (50), it has(60)σ1−αkAxk+1e+λke−λk+1e−σAxk−b=σ2−αkAxk+1e−2−αk−1Axke.
Since0<αk<1 for all k and by (59), (60), and (50), it deduces(61)σ1−αkAxk+1e,Axk+1e+λke−λk+1e,Axk+1e−σAxke,Axk+1e=2σAxk+1e−Axke,Axk+1e−σαkAxk+1e,Axk+1e+σαk−1Axke,Axk+1e≤−2xk+1−xkΣf2−1βk−1βk−1xk+1−xk2−1βkxk+1−yk2−xk−yk2+1βk−1xk−yk−12+σ1−αk−1Axk+1e−Axke,Axke−σαkAxk+1e2+σαk−1Axk+1e,Axke=−2xk+1−xkΣf2−1βk−1βk−1xk+1−xk2−1βkxk+1−yk2−xk−yk2+1βk−1xk−yk−12+σαk−1−12Axke2−σαk−12Axk+1e2−σ2Axk+1e−Axke2.
Thus, (54) is true.
Now, fork>0, we construct the following ϕk and turn to the analysis of the convergence of the algorithm:(62)ϕk≔σαk−12Axke2+12σαkλke+σ1−αk−1Axke2+1βk−1xk−yk−12.
The theorem shows that the sequenceϕkk>0 decreases monotonically under appropriate conditions, and then C-APPA is convergent since ϕk≥0 for all k≥0.Theorem 1.
Suppose the solution set of (5) is nonempty. Denote x¯,λ¯ as one solution satisfying the KKT system. Let ϕkk>0 be defined as (62) and xk,λk is generated by C-APPA. Then,(63)ϕk−ϕk+1≥2xk+1−xkΣf2+xk+1eΣf2+12βkxk−yk2+xk+1−yk2+xk+1e2+σαk−12Axk+1e2+σ22−αk−1Axk+1−xk2.Furthermore, for all k=1,2,…,, if there exists α¯>0 and β¯>0 such that αk≥α¯ and βk≥β¯, then(64)limk⟶∞Axk=b,limk⟶∞xk=x¯,limk⟶∞λ˜k=limk⟶∞λk=λ¯.Proof.
From Lemmas1 and 2, we can substitute (49), (41), and (54) into the left side of inequality (48). Since(65)λk+1e,Axk+1e+σ1−αkAxk+1e,Axk+1e+λ˜ke−λk+1e,Axk+1e−σAxk+1−b,Axk+1e−1βkxk+1−yk,xk+1e≤σαk−12Axke2−σαk2Axk+1e2−12σαkλk+1e+σ1−αkAxk+1e2−λke+σ1−αk−1Axke2−2xk+1−xkΣf2+1βk−1xk−yk−12−1βkxk+1−yk2+1βkxk−yk2+σ1−αk−αk−12Axk+1e2−σ22−αk−1Axk+1e−Axke2−12βkxk+1−yk2−12βkxk+1e2+12βkyk−x¯2,then by using of (62) and (48), we obtain(66)ϕk−ϕk+1≥2xk+1−xkΣf2+xk+1eΣf2+12βkxk−yk2+xk+1−yk2+xk+1e2+σαk−12Axk+1e2+σ22−αk−1Axk+1−xk2,which deduces the sequence ϕkk>0 is nonnegative and monotone nonincreasing. When the sequence is infinite, σαk−1/2Axke2,1/2σαkλke+σ1−αk−1Axke2,and1/βk−1xk−yk−12 are all bounded. Let k⟶∞, and by (66), we have(67)xk+1eΣf2⟶0,12βkxk−yk2⟶0,12βkxk+1−yk2⟶0,12βkxk+1e2⟶0,σαk−12Axk+1e2⟶0,σ22−αk−1Axk+1−xk2⟶0.
Sinceα¯ and β¯ are the lower bounds of αk and βk, respectively, it can be known that Axke, 1/2σαkλke+σ1−αk−1Axke2, xk−yk, xk+1−yk, xk+1e, Axk+1e, and Axk+1−xk are all bounded. By xk+1e=xk+1−x¯ and xk+1≤xk+1e+x¯, it has xk+1 is bounded. Also, λk is bounded. We denote the convergent subsequence of xk,λk as(68)limki⟶∞xki,λki=x∞,λ∞,ki⊆0,1,…,.
By (42) and (43), it has(69)A⊤λki−1βki−1xki−yki−1∈∂fxki.
Then, by taking limits ofki on both sides of (69) simultaneously, it deduces(70)A⊤λ∞∈∂fx∞,Ax∞−b=0.
Assume for general thatx¯,λ¯=x∞,λ∞. Thus, by the definition of ϕk, there must exist subsequence xki,λki such that(71)limki⟶∞ϕki=0.
Becauseϕk is nonincreasing and bounded, ϕkk∈N converges to 0. By (62), it has(72)λke+σ1−αkAxke⟶0,Axke⟶0,for k⟶∞. Thus, by 0≤λke≤λke+σ1−αkAxke+σAxke, it obtains(73)limk⟶∞λk=λ¯.
Also, byxke=xk−x¯,Ax¯=b,Axke⟶0,xk+1e⟶0, we have(74)limk⟶∞xk=x¯,limk⟶∞Axk=b.
From(75)λ˜k−λ¯≤λk+1−λ¯+σAxk+1−b,we get limk⟶∞λ˜k=λ¯.


## 4. The Convergence Rate of C-APPA

Suppose that (34) is solved exactly in the iteration and we denote xk+1=ykp. Let(76)Fx,λ˜k=fx+σ2Ax−b−λ˜kσ2,(77)φ0x=Fx,λ˜−1+a02x−x02,(78)φk+1x=1−αkφkx+αkFxk+1,λ˜k−1βkxk+1−yk⊤x−xk+1−1−αkFxk,λ˜k−1−Fxk,λ˜k.Lemma 4.
Suppose thatxk+1, λ˜k, and φkx are generated by algorithm C-APPA. Then, for all k=0,1,…,, it has(79)φk+1x−Fx,λ˜k≤1−αkφkx−Fx,λ˜k−1+1−αkθk+1x,where(80)θk+1x=Fx,λ˜k−1−Fx,λ˜k+Fxk,λ˜k−Fxk,λ˜k−1.Proof.
By (78), it has(81)φk+1x−Fx,λ˜k=1−αkφkx−Fx,λ˜k−1+1−αkFx,λ˜k−1−Fxk,λ˜k−1−Fx,λ˜k+Fxk,λ˜k−αkFx,λ˜k−Fxk+1,λ˜k+1βkxk+1−yk⊤x−xk+1.
Becausexk+1 is the minimizer of (34), we have(82)A⊤λ˜k−σA⊤Axk+1−b−1βkxk+1−yk∈∂fxk+1.
Then, by the definition ofFx,λ˜k, it implies(83)A⊤λ˜k−σA⊤Axk+1−b−1βkxk+1−yk+σA⊤Axk+1−b−λ˜kσ=−1βkxk+1−yk∈∂Fxk+1,λ˜k.
From the convexity ofFx,λ˜k, for any x∈domf, we have(84)Fx,λ˜k−Fxk+1,λ˜k+1βkxk+1−yk⊤x−xk+1≥0.
Substituting it into (81), then (79) can be proved.
The following lemma shows that, for anyk≥0, if vk∗ is the minimizer of φkx and we write φkx as the canonical form(85)φkx=φkvk∗+ak2x−vk∗2,then φkvk∗ is the upper bound of Fx,λ on xk.Lemma 5.
Suppose thatφkx and Fx,λ˜k are defined as (76)–(78), respectively, and the other sequences are generated by algorithm C-APPA. Then, φ0v0∗≥Fx0,λ˜−1, and for all k≥1, it has(86)φkvk∗≥Fxk,λ˜k−1+2−c2βkxk−yk−12≥Fxk,λ˜k−1.Proof.
We prove it by induction. By (77) and v0∗=x0, (86) is true for k=0. Now, suppose for k, φkvk∗≥Fxk,λ˜k−1. Then, by (78), (85), (37), and (38), it implies(87)φk+1vk+1∗=1−αkφkvk∗+1−αkak2vk+1∗−vk∗2−1−αkFxk,λ˜k−1−Fxk,λ˜k+αkFxk+1,λ˜k−αkβkxk+1−yk⊤vk+1∗−xk+1≥1−αkFxk,λ˜k−1+αk22ak+1βk2xk+1−yk2−1−αkFxk,λ˜k−1−Fxk,λ˜k+αkFxk+1,λ˜k−αkβkxk+1−yk⊤vk+1∗−xk+1=1−αkFxk,λ˜k−Fxk+1,λ˜k+Fxk+1,λ˜k−αk22ak+1βk2xk+1−yk2−αkβkxk+1−yk⊤vk∗−xk+1.
SinceFx,λ˜k is convex and −1/βkxk+1−yk⊤∈∂Fxk+1,λ˜k, then(88)Fxk,λ˜k−Fxk+1,λ˜k≥−1βkxk+1−yk⊤xk−xk+1.
Substituting it into (87) and by using of (33), we have(89)φk+1vk+1∗≥Fxk+1,λ˜k−1−αk1βkxk+1−yk⊤xk−xk+1−αk22ak+1βk2xk+1−yk2−αkβkxk+1−yk⊤vk∗−xk+1=Fxk+1,λ˜k+1βk1−αk22ak+1βkxk+1−yk2.
Notice thatak+1 and αk are defined as (37) and (33), respectively, and it deduces(90)αk2ak+1βk=αk21−αkakβk=c<2,which means(91)φk+1vk+1∗≥Fxk+1,λ˜k+2−c2βkxk+1−yk2≥Fxk+1,λ˜k.
The following bounded conclusion ofAkc is similar to the one of βk given in Lemma 2.2 by Gu¨ler [10], but it introduces a parameter c in order to have more flexibility. So, here we omit the proving detail for concision.Lemma 6.
LetAkc=∏i=0k−11−αi. Then, for all k>0,(92)11+ca0∑j=0k−1βj2≤Akc≤11+ca0/2∑j=0k−1βj2.
Now, we give the main convergence conclusion of C-APPA.Theorem 2.
Suppose that the solution set of (5) is nonempty and bounded. Denote x¯,λ¯ as a solution satisfying the KKT system and inffx¯>−∞. Let x0 be an initial feasible point and xk,λk is generated by algorithm C-APPA.(1)
DenoteΔkj=Πi=1j1−αk−i. Then, it has(93)ℒσxk+1,λ˜k−ℒσx¯,λ¯+σ1−αk∑j=0kΔkjαk−j−1Axk−j−b2≤a0Ak+1c2x¯−x02.(2)
If, for anyk=1,2,…,, there exists α¯>0 and β¯>0 such that αk≥α¯ and βk≥β¯, then(94)ℒσxk+1,λ˜k−fx¯≤2x¯−x02ck2β¯=O1k2.Proof.
Letθ0x=0,p0x=0,α−1=0, and(95)pk+1x=1−αk−1pkx+θk+1x,k=0,1,2,…,Δk0=1−αk,Δkj=Πi=1j1−αk−i,k>0.
It can be seen that(96)pk+1x=θk+1x+∑j=1kΔkjθk+1−jx.
By (79), it deduces(97)φk+1x−Fx,λ˜k≤Πi=0k1−αiφ0x−Fx,λ˜−1+1−αkpk+1x.
Also by Lemma5, we have(98)Fxk+1,λ˜k−Fx,λ˜k≤φk+1x−Fx,λ˜k≤Πi=0k1−αiφ0x−Fx,λ˜−1+1−αkpk+1x.
Then, by using of (76)–(78), it obtains(99)ℒσxk+1,λ˜k−ℒσx¯,λ¯=fxk+1−λ˜k⊤Axk+1−b+σ2Axk+1−b2−fx¯≤fxk+1+σ2Axk+1−b−λ˜kσ2−fx¯+σ2Ax¯−b−λ˜kσ2≤Πi=0k1−αiφ0x¯−Fx¯,λ˜−1+1−αkpk+1x¯=Πi=0k1−αifx¯+σ2Ax¯−b−λ˜0σ2+a02x¯−x02−fx¯−σ2Ax¯−b−λ˜0σ2+1−αkpk+1x¯=a0Ak+1c2x¯−x02+1−αkpk+1x¯.
From (81), we have(100)θk+1x=σ2Ax−b−λ˜k−1σ2−Ax−b−λ˜kσ2+σ2Axk−b−λ˜kσ2−Axk−b−λ˜k−1σ2=λ˜k−λ˜k−1⊤Ax−b+λ˜k−1−λ˜k⊤Axk−b,which obtains(101)θk+1x¯=λ˜k−1−λ˜k⊤Axk−b.
By (36) and (39), we deduce(102)λ˜k−λ˜k−1=αk−1σAxk−b.
Thus,(103)θk+1x¯=−αk−1σAxk−b2,pk+1x¯=θk+1x¯+∑j=1kΔkjθk+1−jx¯=−σαk−1Axk−b2+∑j=1kΔkjαk−j−1Axk−j−b2≤0.
From (99), it has(104)ℒσxk+1,λ˜k−ℒσx¯,λ¯+σ1−αk∑j=0kΔkjαk−j−1Axk−j−b2≤a0Ak+1c2x¯−x02.
When the assumptions are true,xk,λ˜k converges to a certain KKT solution x¯,λ¯ from Theorem 1. Furthermore, from Lemma 6, it obtains(105)ℒσxk+1,λ˜k−fx¯=ℒσxk+1,λ˜k−ℒσx¯,λ¯≤a0Ak+1c2x¯−x02≤a0x¯−x021+ca/2∑j=0k−1βj2≤2a0x¯−x02ca∑j=0k−1βj2.
Whileβk≥β¯, it holds that(106)ℒσxk+1,λ˜k−fx¯≤2x¯−x02ck2β¯=O1k2.


## 5. Conclusions

In this paper, a framework of accelerated PPA is presented for constrained convex optimization. The algorithm can be seen as an extension to Gu¨ler’s methods for unconstrained optimization and linear programming problems. Different from [11], where the accelerated proximity point method is used on the dual problem of the linear programming, our algorithm directly uses the accelerating technique both on the proximal point operator and the Lagrange multiplier for the original problem in the iterations by constructing appropriate auxiliary sequences with the quadratic convex functions and auxiliary points. We prove that the sequence generated by the algorithm converges to a KKT solution under suitable conditions. Also, it retains a similar convergence rate on objective function values.This paper has paid more attention on analyzing the convergence of the accelerated PPA for solving convex minimization with linear constrains. In the iterations of C-APPA, computing the proximal mapping ofFx,λ˜k is required. Usually, the proximal point of yk is hard to know exactly. Then, series of xk+1,vk+1∗,yk, and other auxiliary quantities being updated and calculated by a nonprecision rule should be considered. Several inexactly accelerated PPAs, the convergent properties under some proper conditions, and the numerical results are going to be given in another paper of ours. And more research on different inexact conditions, their further applications, and testings in practice would be further carried out in the future.



---

*Source: 8873507-2020-11-10.xml*