# Modified Lagrangian Methods for Separable Optimization Problems

Authors: Abdelouahed Hamdi; Aiman A. Mukheimer
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

We propose a convergence analysis of a new decomposition method to solve structured optimization problems. The proposed scheme is based on a class of modified Lagrangians combined with the allocation of resources decomposition algorithm. Under mild assumptions, we show that the method generates convergent primal-dual sequences.


---

## Body

## 1. Introduction

The interest for large-scale optimization problems [1] has grown over the past twenty years and it is likely to continue to increase during the upcoming decades; while on the one hand, the systemic approach to modeling real systems results in more and more complicated models, the increasing computing power of the microprocessors, along with the recent advancements in parallel architectures on the other hand, seems to push back the limits of practical treatment of these models. Decomposition methods (including splitting, partitioning, and parallel methods) are practical candidates to solve large problems where an internal structure allows to identify the “weakly coupled subsystems.” It should be clear that the reduction of the dimension of the original problem is not the only motivation for decomposing it into subproblems. Other important motivations are as follows:(i)
partitioning heterogeneous models when it is the juxtaposition of various parts of the model which turns its numerical treatment difficult (as in mixed models with continuous and discrete variables) [2];(ii)
decentralizing the decision-making such that the decomposition procedure could lead to autonomous subsystems, which are capable of computing their own part of the global solution independently without the need of a centralized decision level [2, 3];(iii)
parallelizing the computation among different processors [1, 2].Our objective in this paper is to present a family of decomposition algorithms based on proximal-like techniques, which are suitable for decentralized and parallelized computations. The algorithm can be seen as a separable version of the nonlinear rescaling principle method [4] and is closely related to three known techniques: the Partial Inverse method, proposed by Spingarn in 1985 [5, 6], the Alternate Direction Multiplier method [7, 8], proposed originally by Gabay and Mercier [9] for the splitting of variational inequalities, and the Separable Augmented Lagrangian Algorithm (SALA) developed by Hamdi [10–12].We will use a simplified framework to present the algorithm called theφ-SALA. It is tailored towards minimizing a convex separable function with separable constraints. A nice feature of the φ-SALA is that it preserves separability, as each iteration splits into a proximal step on the dual function and a projection step on the subspace. On the other hand, it yields the proximal decomposition on the graph of a maximal operator that has been introduced by Mahey et al. [13] for quadratic choice of the auxiliary functions φ.The first drawback associated with the classical quadratic multiplier method (augmented lagrangian [14, 15]) and/or the nonlinear rescaling principle algorithm is that the augmented Lagrangian function and also the rescaled Lagrangian function are no long separable even when the original problem is separable. In other words, when applied to separable constraints like g(x)=∑i=1pgi(xi), the terms ∥∑i=1pgi(xi)∥ or (1/k)φ(k∑i=1pgi(xi)) are no long separable. However, some careful reformulation of the problem (e.g., by introducing additional variables) may preserve some of the given separable structure, thus giving a chance to the augmented Lagrangian framework, to play again an important role in the development of efficient decomposition schemes.The second drawback associated with the multiplier methods is the fact that it is only differentiable once even when the problem’s data allow for higher differentiability, disabling the application of efficient Newton type methods. In fact such a lack of continuity in the second derivative can significantly slow down the rate of convergence of these methods and thus causing algorithmic failure. One way of coping with this difficulty is to use the recently developed nonquadratic multiplier methods based on entropy-like proximal methods (see [3, 16–20]), and thereby leading to multiplier methods of which are twice continuously differentiable as opposed to the classical quadratic multiplier (if the original problem is also C2). This is an important advantage since Newton type methods can then be applied.With respect to the first drawback, in [10, 11], Hamdi has proposed a separable augmented Lagrangian algorithm (SALA) which can be derived from the resource directive subproblems associated with the coupling constraints ((SALA) was developed for non-convex and convex separable problems.). And in this paper, we alleviate the second drawback by using the Nonlinear Re-scaling NR method, so as to get a separable augmented Lagrangian function, which is at least twice continuously differentiable.It is worth citing here some recent works where decomposition methods related to our subject were developed (to the best of our knowledge). The most recent one is a modification of the original algorithm (SALA) [10–12] where Guèye et al. [21] replaced the scalar penalty parameter in [10] by a diagonal positive definite matrix of scaling factors. Their convergence analysis was done for only affine constraints. Auslender and Teboulle [22] proposed the entropic proximal decomposition method inducing C∞-lagrangians for solving the structured convex minimization problems and variational inequalities based on the combination of their recent logarithmic-quadratic proximal point theory [23, 24] with the Chen-Teboulle decomposition scheme [25]. Kyono and Fukushima [26] proposed an extension of the Chen-Teboulle decomposition scheme [25] combined with the Bregman-based proximal point algorithm. Kyona and Fukushima their method was developed for solving large-scale Variational Inequalities (VIPs) (see [26] and for more developments on VIPs see [27–29] and references therein.). Hamdi and Mahey [11] proposed a stabilized version of the original (SALA) by using a primal proximal regularization that yields to better numerical stability, specially for nonconvex minimization problems. For other references on decomposition methods, one may refer to [5, 7, 11, 12, 25, 26, 30–34] and to Hamdi’s survey on decomposition methods based on augmented lagrangian functions [35] and references therein.The remainder of this paper is organized as follows. In Section2, we present the nonlinear rescaling principle of Polyak. In Section 3, we describe the application of the nonlinear rescaling method in conjunction with (SALA) to a general structured convex program in order to yield to the decomposition method presented in [30], which can be seen as separable augmented lagrangian method. Section 4 is dedicated to the extended convergence analysis of the proposed algorithm.


## 2. Nonlinear Rescaling Principle

Letf be a convex real-valued function and let (g1(x),…,gp(x))T be finite concave real-valued functions on Rn, and consider the convex programming problem:(C)min⁡x∈Rn{f(x):gi(x)≥0,i=1,m¯}.
Recently nonquadratic augmented lagrangian have received much attention in the literature; see, for example, ([3, 4, 16–20, 36] and references therein.). These methods basically rely on applying new class of proximal-like maps on the dual of (C), see [20], and in turns are in fact equivalent to using the nonlinear re-scaling method, as shown in [37]. In this paper we use the nonlinear re-scaling principle to construct smooth lagrangian decomposition methods. Thus, we begin by summarizing this approach; for details see [4, 18, 37] and references therein.The main idea of the nonlinear re-scaling principle (called here the NR method) is considering a class of strictly concave and smooth enough scalar function with particular properties, and using it to transform the constraints terms of the classical lagrangian. The NR method alternates at each step the unconstrained minimization of the classical lagrangian for the equivalent problem with the lagrange multiplier update. It allows for generating a wide class of augmented lagrangian methods (for instance, the exponential multiplier method, the modified log-barrier method, and the Log-sigmoid multiplier method [18], etc.).Let us consider the following class ofC2 functions φ defined of ℝand satisfying the following properties:(P1)
φ′(t)>0, for all t∈ℝ;(P2)
φ′′(t)<0, for all t∈ℝ;(P3)
φ(0)=0;(P4)
φ′(0)=1;(P5)
m-1≤φ′′(t)<0, for all t∈ℝ and φ′′(t)≤-M-1, for all t<0, where M,m>0;(P6)
(-φ)∞(-1)≥0;(P7)
(-φ)∞(1)=0.Note that from (P2) and (P3) the functionsφ and φ′ are one-to-one and φ is strictly concave. Let φ∈Φ, then we have for any k>0,(2.1)t≥01kφ(tk)≥0.
The nonlinear re-scaling principle is based on the idea of transforming the original problem (C) to an equivalent problem, namely, to one which has the same set of optimal solutions as (C). To this end, let us consider here a parameterized transformed problems written as follows:([Ck,φ])min⁡x∈Rn{f(x):k-1φ(kgi(x))≥0,i=1,m¯}.
Clearly, problem ([Ck,φ]) is also convex and has the same feasible set as (C). The nonlinear re-scaling iterations are based on the classical lagrangian function denoted here by Pk(x,u) associated to the problem ([Ck,φ]); that is,(2.2)Pk(x,u)=f(x)-∑i=1mk-1uiφ(kgi(x))
and can be resumed as follows.Algorithm 2.1.
Givenφ∈Φ, u0>0, k>0, generate the sequence {xk,uk}:
Findxk+1∈argminx∈RnPk(x,uk)=f(x)-∑i=1mk-1uikφ(kgi(x)).
Updateuik+1=uikφ′(kgi(xk+1)),
i=1,…,m.Remark 2.2.
Note that the multipliers are nonnegative for allk by (P1). Also, it is worth to mention the possibility to change the penalty parameter k at each iteration s. In [37], the authors propose a dynamic scaling parameters update as follows: kik+1=k/uik+1. This update will be used in our decomposition scheme in the next section.
The NR algorithm allows a generation of a wide class of augmented lagrangian. Typical examples include the choicesφ(t)=et-1 to get the exponential multiplier method, or φ(t)=-log(1-t) to get the modified log-barrier function method. Convergence analysis of Algorithm 2.1 is given in [4, 18, 37, 38].


## 3. Separable Modified Lagrangian Algorithm

In this section, we recall the generalization of the separable augmented lagrangian algorithm (SALA) algorithm (see [10, 11]) called (φ SALA) proposed in [30], to solve large-scale convex inequality constrained programs with separable structure. We are concerned here with block separable nonlinear constrained optimization problems:(SP)min⁡x∈Rn{F(x)=∑i=1pfi(xi):x∈Ω},
where fi:ℝni→ℝare all convex functions, and(3.1)Ω={x∈Rn:∑i=1pgij(xi)≥0,j=1,m¯}
is the convex set where gij are defined from ℝni→ℝfor j=1,m¯, i=1,p¯, ∑i=1pni=n. Along this work, all the functions fi, gij are C2 and we assume the following.(A1)
The optimal setX* of (SP) is nonempty and bounded.(A2)
The Slater’s condition holds, that is,(3.2)∃x̅∈Rn:∑i=1pgij(x̅i)>0,j=1,m¯.Now, to construct our decomposition algorithm, we use them allocation vectors yj∈A={z∈ℝp∣∑i=1pzi=0} to get the equivalent problem (If (x*,y*) is an optimal solution to (SPy) then x* is an optimal solution to (SP).),(SPy)min⁡∑i=1pfi(xi)suchthatgij(xi)+yij≥0,j=1,m¯,i=1,p¯,∑i=1pyij=0j=1,m¯,xi∈Rni,i=1,p¯,
to which we propose to apply the nonlinear re-scaling principle with partial elimination of the constraints. We mean that only the constraints gij(xi)+yij≥0 are replaced by the equivalent ones (1/λ)φ(λ(gij(xi)+yij))≥0. Then for any λ>0, the following minimization problem:([SP(y,φ)])min⁡x∑i=1pfi(xi)s.t1λφ[λ(gij(xi)+yij)]≥0j=1,m¯,i=1,p¯∑i=1pyij=0j=1,m¯
is equivalent to the (SPy) and according to Algorithm 2.1, for all u0∈ℝ++pm, λ0=(λ110,…,λpm0) where λij0=λ(uij0)-1, we have the following iterative scheme: (3.3)(xk+1,yk+1)⟶min⁡∑i=1pyij=0,j=1,m¯Θλk(x,y,uk),(3.4)uijk+1=uijkφ′(λijk(gij(xik+1)+yijk+1)),(3.5)λijk+1=λ(uijk+1)-1,∀i,j,
where Θλ(x,y,u) denotes the classical lagrangian for ([SPy,φ]) given by(3.6)Θλ(x,y,u)=∑i=1pfi(xi)-1λ∑i=1p∑j=1muijφ[λ(gij(xi)+yij)],
where u=(u11,u21,…,up1,u12,…,up2,…,u1m,…,upm)∈ℝ++pm.The minimization in (3.3) is done by alternating the minimization with respect to x, then followed by the one w.r.t. the allocation variable y; that is, we fix y=yk and find(3.7)xk+1∈Argmin⁡xΘλk(x,yk,uk)=Argmin⁡x∑i=1p{fi(xi)-∑j=1m1λijkuijkφ[λ(gij(xi)+yijk)]}.
Then we can split the above minimization into p independent sub-problems with low dimension. That is,(3.8)xik+1∈Argmin⁡xi{fi(xi)-∑j=1m1λijkuijkφ[λijk(gij(xi)+yijk)]}.
And now we fix x=xk+1 to solve for yk+1(3.9)yk+1∈Argmin{∑i=1p∑j=1m-1λijkuijkφ[λijk(gij(xik+1)+yij)]:∑i=1pyij=0}.
The following lemma gives an important link between the allocation variable and the lagrange dual variable.Lemma 3.1.
According to  (3.9), uk+1 and yk+1 are orthogonal and satisfy
(3.10)yijk+1=-gij(xik+1)+δjk+1,i=1,p¯,j=1,m,¯(3.11)ujk+1=ujkφ′(λjkδjk+1),j=1,m¯,
where δjk+1=p-1∑i=1pgij(xik+1).Proof.
For anyj=1,m¯, by writing the classical lagrangian to (3.9)
(3.12)Lk(zj,tj)=∑i=1p-1λijkuijkφ[λijk(gij(xik+1)+yij)]+∑i=1pyijtj,
where tj∈ℝ, j=1,m¯, and using the optimality, with (3.4), we show that
(3.13)tj=uijk+1=uijkφ′[λijk(gij(xik+1)+yijk+1)],
which means that uk+1 does not depend on i; that is, uijk+1=uljk+1, for all i, l=1,p¯, and uij can be replaced by uj for all i=1,p¯.
Now, according to (P1) and after straightforward calculations, we reach (3.10). Equation (3.11) is obtained directly using (3.4) and (3.10). The orthogonality of the vectors uk+1 and yk+1 is direct.
(3.14)〈u,y〉=∑j=1m∑i=1puijyij=∑j=1muj∑i=1pyij=0.One can observe that also the penalty parameters(λ1j,λ2j,…,λpj) belong to the set V={(a1,…,ap):a1=⋯=ap}, and finally our algorithm (φSALA) can be stated as follows.Algorithm 3.2.
We have the following steps.Step 1.
Selectφ∈Φ, u0∈ℝ++mpwhereuj∈V, j=1,m¯, λ>0, y0=(y1,…,ym), where yj∈A, j=1,m¯and λ0=(λ11,…,λpm) where λj0=λ(uj0)-1, ϵ1>0, ϵ2>0, ϵ3>0.Step 2.
Determine: for anyi=1,p¯(3.15)xik+1:=argmin⁡xi∈Rni{fi(xi)-∑j=1m1λjkujkφ(λjk(gij(xi)+yijk))}.Step 3.
Ifv1≤ϵ1, v2≤ϵ2, v3≤ϵ3 where(3.16)v1=∑j=1m∑i=1p|ujk(gij(xik+1)+yijk)|,v2=max⁡1≤j≤m{(-δjk+1)},v3=|F(xk)-F(xk+1)|.Stop.Else:
go to Step4.Step 4.
Update and go back to Step2:(3.17)yijk+1=-gij(xik+1)+δjk+1i=1,p̅,j=1,m̅ujk+1=ujkφ′(λjkδjk+1),λjk+1=λ(ujk+1)-1.The following proposition gives us some properties ofΘλ.Proposition 3.3.
(1)Θλ(x,y,u) is strictly convex in x∈ℝn for any u∈ℝ++mp,y∈ℝmp, λ>0.
(2) For any K.K.T point(x*,y*,u*) of (SPy) One has(i)
Θλ(x*,y*,u*)=L(x*,y*,u*)=∑i=1pfi(xi*),(ii)
∇xΘλ(x*,y*,u*)=∇xL(x*,y*,u*)=0,(iii)
∇x2Θλ(x*,y*,u*)=∇x2L(x*,y*,u*)-φ′′(0)∇G(x*)Λ∇G(x*)′, where Λ=diag(uij*)(i,j)=(1,1)(p,m)and G(x)=(λ11g11(x1),…,λmpgmp(xp)).Proof.
(1)Θλ(x,y,u)=∑i=1pfi(xi)-∑j=1m(1/λij)uijφ(λij(gij(xi)+yij)). Since gij, φ, i=1,p¯, j=1,m¯ are concave, strictly concave (resp.) and φ is increasing. Then Θ is strictly convex in x∈ℝn for any u∈ℝ++mp, y∈ℝmp, λ>0.
(2) Let(x*,y*,u*) be any K.K.T point of (SPy) then (i)
we have(3.18)Θλ(x*,y*,u*)=∑i=1p[fi(xi*)-∑j=1m1λijuij*φ(λij(gij(xi*)+yij*))],L(x*,y*,u*)=∑i=1p[fi(xi*)-∑j=1muij*(gij(xi*)+yij*)]=∑i=1pfi(xi*)
from the complementary condition.
(3.19)⟹φ(λij(gij(xi*)+yij*))=0⟹uij*φ(λij(gij(xi*)+yij*))=0,
then we get
(3.20)Θλ(x*,y*,u*)=∑i=1pfi(xi*).(ii)
We have(3.21)∇xΘλ(x*,y*,u*)=∑i=1p{∇xfi(xi*)-∑j=1muij*φ′(λij(gij(xi*)+yij*))∇xgij(xi*)}.
Similarly, if uij*≠0 then gij(x*)+yij*=0 therefore φ′(λij(gij(xi*)+yij*))=1. This means that
(3.22)∇xΘλ(x*,y*,u*)=∑i=1p(∇xfi(xi*)-∑j=1muij*∇xgij(xi*))=∇xL(x*,y*,u*)=0.(iii)
From (ii) we can calculate∇x2Θλ(x*,y*,u*),
(3.23)∇x2Θλ(x,y,u)=∑i=1p[∇x2fi(xi)-∑j=1mλijuijφ′′(λij(gij(xi)+yij))(∇xgij(xi))(∇xgij(xi))′-∑j=1muijφ′(λij(gij(xi)+yij))∇x2gij(xi)].
At (x*,y*,u*), we have
(3.24)∇x2Θλ(x*,y*,u*)=∑i=1p(∇x2fi(xi*)-∑j=1m[λijuij*φ′′(λij(gij(xi*)+yij*))(∇xgij(xi*))(∇xgij(xi*))′+uij*φ′(λij(gij(xi*)+yij*))∇x2gij(xi*)]∑j=1m)=∑i=1p{∇x2fi(xi*)-∑j=1muij*∇x2gij(xi*)}-∑i=1p∑j=1mλijuij*φ′′(λij(gij(xi*)+yij*))(∇xgij(xi*))(∇xgij(xi*))′=∇x2L(x*,y*,u*)-∑i=1p∑j=1mλijuij*φ′′(λij(gij(xi*)+yij*))(∇xgij(xi*))×(∇xgij(xi*))′=∇x2L(x*,y*,u*)-φ′′(0)∑i=1p∑j=1mλijuij*(∇xgij(xi*))(∇xgij(xi*))′.
Let
(3.25)G(x)=(λ11g11(x1),…,λp1gp1(xp),λ12g12(x1),…,λmpgmp(xp))
then
(3.26)∇G(x)=(λ11∇g11(x1)λ21∇g21(x2)⋯∇λmpgmp(xp))n×pm.
That is, the first column is the gradient ∇g11(x1) and so on. Let Λ=diag(uij*)(i,j)=(1,1)(p,m) that is, the diagonal is
(3.27)(u11*,u21*,…,up1*,u12*,…,ump*).
Then,
(3.28)∇G(x*)Λ=(∇g11(x1*)u11*λ11∇g21(x2*)u21*λ21⋯∇gmp(xp*)ump*λmp)n×pm,∇G(x*)Λ(∇G(x*))′=(λ11∇g11(x1*)u11*⋯λpm∇gmp(xp*)ump*)((∇g11(x1*))′⋯(∇gmp(xp*))′)=∑i=1p∑j=1mλijuij*(∇gij(xi*))(∇gij(xi*))′.
Then
(3.29)∇x2Θλ(x*,y*,u*)=∇x2L(x*,y*,u*)-φ′′(0)∇G(x*)Λ(∇G(x*))′.Remark 3.4.
The analysis presented in this paper differs from the short one presented in [30]. In this paper, our analysis is made possible by the strong tool of recession functions.
Assumption (A1) can be written in terms of recession functions (f∞(d)=limt→∞(f(x+td)-f(x))/t, for all x∈domf for convex proper and lower semicontinuous functions. In our case the functions are convex proper and continuous.)(3.30)F∞(d)≤0,(-∑i=1pgij)∞(d)≤0,∀j=1,m¯⟹d=0.
Further, since ∑i=1pgij is not identically +∞, [39, Theorem  9.3, page  77], allows us to reformulate (A1) as follows:(3.31)F∞(d)>0,∑i=1p(-gij)∞(di)>0,∀j=1,m¯,∀d≠0.
The next proposition shows that the minimization subproblems are solvable.Proposition 3.5.
IfX* is nonempty and bounded, then for any u∈ℝ++mp, y∈ℝpm and λ>0(3.32)Argmin{Θλ(x,y,u):x∈Rn}≠∅andbounded.Proof.
To this goal, we need to show that(Θλ)∞(d)>0 for any d∈ℝn,d≠0. According to Proposition  2.1 in [40] and Proposition  2.6.1 in [41], we can express the recession function of Θλ as follows
(3.33)(Θλ)∞(d)=F∞(d)+∑j=1m∑i=1p(ujkλjψ(λj(gij(xi)+yij)))∞(di),
where ψ(t)=-φ(-t).
If, we denoteI+={(i,j):(-gij)∞(di)>0}, I-={(i,j):(-gij)∞(di)≤0}, then(3.34)(Θλ)∞(d)=F∞(d)+∑(i,j)∈I+mujkλjψ∞(λj(-gij)∞(di))+∑(i,j)∈I-mujkλjψ∞(λj(-gij)∞(di))
and by using
(3.35)ψ∞(s)={sψ∞(1)ifs>0,-sψ∞(-1)ifs≤0,
we have
(3.36)(Θλ)∞(d)=F∞(d)+ψ∞(1)∑(i,j)∈I+ujk(-gij)∞(di)-ψ∞(-1)∑(i,j)∈I-ujk(-gij)∞(di).
Now, since ψ∞(-1)=(-φ)∞(1)=0, the above relation becomes
(3.37)(Θλ)∞(d)=F∞(d)+ψ∞(1)∑(i,j)∈I+ujk(-gij)∞(di),
and finally, using (3.31) and (P6)  the proof is complete.


## 4. Convergence Analysis

In this section, we present the convergence analysis of the sequence(xk,yk,uk) for a wide class of constraint transformations φ∈Φ under some assumptions on the input data. To this goal, we give the following main two propositions.Proposition 4.1.
UnderA1 and A2, the dual sequence {uk} is bounded.Proof.
LetDλ(u′)=minx,y{Θλ(x,y,u′):∑iyij=0.} and let the vector π such that πij≤gij(xi)+yij, for all i=1,p¯, j=1,m¯. Then, it is easy to see that
(4.1)Dλ(u′)=min⁡π{P̃(π)-∑j=1m1λj∑i=1puij′φ(λπij)},
where P̃ denotes the perturbation function associated to ([SPy,φ]) and defined by
(4.2)P̃(π)=min⁡x,y{F(x):gij(xi)+yij≥πij,y∈A}.
So, by adding and subtracting the term ∑j=1m(1/λj)wij′φ[λπij], for w′ with the same structure as u′, and if we set B={(x,y):gij(xi)+yij≥πij,y∈A}, we obtain
(4.3)Dλ(u′)=min⁡π{min⁡(x,y)∈BF(x)-∑i,j1λjwij′φ(λπij)+∑i,j1λjwij′φ(λπij)-∑i,j1λjuij′φ(λπij)}.
That is,
(4.4)Dλ(u′)=min⁡π,(x,y)∈B{F(x)-∑j=1m1λj∑i=1pwij′φ(λπij)+∑j=1m1λj∑i=1p[wij′-uij′]φ(λπij)}
which can be rewritten also as follows:
(4.5)Dλ(u′)=min⁡π{P̃(π)-∑j=1m1λj∑i=1pwij′φ(λπij)+∑j=1m1λj∑i=1p(wij′-uij′)φ(λπij)}
and then we have
(4.6)Dλ(u′)≥Dλ(w′)+min⁡π∑j=1m1λj∑i=1p(wij′-uij′)φ(λπij).
Using (P1), (P3), and (P4) and if we take w′=uk, u′=uk+1, we can show that when xk+1 is not feasible, uk+1≥uk and it is easy to see that the minimum in this case equals zero and we have Dλ(uk+1)≥Dλ(uk)≥⋯≥Dλ(u0), for all k≥0. Thus, using the fact that Dλ is concave, L* is bounded, and uk+1 is in the dual level set, the sequence {uk} is bounded.Proposition 4.2.
UnderA1, A2,  the primal sequence {xk} is bounded.Proof.
Let(xk+1,yk+1)∈Argminx{Θλk(x,y,uk):∑iyij=0} and fix x̅∈X* and y̅ij=-gij(xi̅)+p-1∑gij(xi̅). It is clear that
(4.7)F(xk+1)-∑j∑iujkλjkφ[λjk(gij(xik+1)+yijk+1)]≤Θλk(x̅,y̅,uk),
and using the feasibility of x̅, we obtain directly
(4.8)F(xk+1)-∑j∑iujkλjkφ[λjk(gij(xik+1)+yijk+1)]≤F(x̅).
Now, let us assume that the primal sequence is unbounded, then the sequence wk=xk/∥xk∥ is bounded and limk→∞wk=d≠0.
Letϵ1 and ϵ2 such that(4.9)F∞(d)>ϵ1,(∑i-gij)∞(d)>ϵ2,
and take k0 such that
(4.10)F(xk+1)≥ϵ1‖xk‖,∀k≥k0,(4.11)∑i(-gij)(xik+1)>ϵ2‖xk+1‖,∀k≥k0.
By dividing both sides in (4.8) by ∥xk+1∥, we get(4.12)F(xk+1)‖xk+1‖-∑i,jujkλjkφ[λjk(gij(xik+1)+yijk+1)]‖xk+1‖≤F(x̅)‖xk+1‖,
and according to (4.11) and the monotonicity of φ, and by denoting νk=λjk∥xk+1∥/p, (4.12) becomes
(4.13)F(xk+1)‖xk+1‖-∑i,jujkλjk‖xk+1‖φ[-ϵ2νk]≤F(x̅)‖xk+1‖.
Since the dual sequence is bounded, at the limit we have
(4.14)ϵ1-∑i,juj̅plim⁡k→∞φ(-ϵ2νk)νk≤0.
Since limk→∞νk=+∞ and using φ(t)=-ψ(-t), we can rewrite (4.14) as follows:
(4.15)ϵ1+∑i,juj̅plim⁡k→∞ψ(ϵ2νk)νk≤0.
Since
(4.16)lim⁡k→∞ψ(ϵ2νk)νk=lim⁡t→∞ψ(ϵ2t)t=ψ∞(ϵ2),
and (4.15) is equivalent to
(4.17)ϵ1+∑juj̅ψ∞(ϵ2)≤0.
If ϵ2≤0 then ψ∞(ϵ2)=-ϵ2ψ∞(-1)=0 and then ϵ1≤0.
Ifϵ2>0 then ψ∞(ϵ2)=ϵ2ψ∞(1).
Now by lettingϵ1→F∞(d) and ϵ2→(∑i(-gij)∞(d)), we deduct that(4.18)F∞(d)≤0,∑i(-gij)∞(d)≤0,
and since X* is not empty and is bounded, then d=0 which contradicts the fact that d≠0. Thus, what we assumed is false, and the primal sequence {xk}k is bounded.Proposition 4.3.
Let the sequences{xk,yk,uk} generated by ΨSALA and assume that there exist x* a  primal solution to the original problem (SP). Then the following inequality holds:
(4.19)∑i=1pfi(xik+1)≤∑i=1pfi(xi*)+∑i=1puk+1θik+1(gi(xi*)-gi(xik+1)),
where
(4.20)θik+1=Ψ′[λ(gi(xik+1)+yik)]∣Ψ′[λ(gi(xik+1)+yik+1)].Proof.
See [30].Proposition 4.4.
Let the sequences{xk,yk,uk}generated by ΨSALA  and assume that there exists a saddle point  (x*,y*,u*) of the Lagrangian l(x,y,u) associated to problem (SP). Then the following inequality holds:
(4.21)∑i=1pfi(xi*)≤∑i=1pfi(xik+1)+〈u*,δk+1〉.Proof.
See [30].Proposition 4.5.
All the three sequences{xk}, {uk}, and {yk} generated in Algorithm 2.1 are bounded.Theorem 4.6.
Lety¯ and u¯, the respective limit point of the bounded sequences {yk} and {uk} generated by ΨSALA. Then one has the following properties:(i)
limsupk→∞∑i=1pgi(xik+1)≥0;(ii)
limsupk→∞(gi(xik+1)+yik+1)≥0;(iii)
limk→∞〈uk+1,gi(xik+1)+yik+1〉=0.Proof.
See  [30].Theorem 4.7.
If the assumptionsA1,  A2, and  A3 are satisfied, then one has the following.(1)
Any limit point (x,u) of the sequence {(xk,uk)} is in the set X*×L*.(2)
The sequencesf(xk) and d(uk) are convergent and(4.22)lim⁡s→∞f(xk)=f(x*),lim⁡s→∞d(uk)=d(u*).Proof.
Letu̅ be any limit point of the sequence {uk}, then there exists a subsequence converging to u̅. Without restricting the generality, we can assume uk→u̅. For j such that u̅ij>0, then
(4.23)lim⁡s→∞uijk+1uijk=1,
and since uijk+1=uijkφ′((λijk/p)∑i=1pgij(xik)), i=1,p¯, j=1,m¯, then
(4.24)lim⁡s→∞φ′(λijkp∑i=1pgij(xik))=1.
Since lims→∞uijk=u̅ij>0, we have λijkuijk=λ>0. Therefore, λijk=(λ/uijk)>0. Then,
(4.25)lim⁡s→∞λij≥λu̅ij>0
and then,
(4.26)lim⁡s→∞∑i=1pgij(xik)=0;
therefore,
(4.27)lim⁡s→∞(uijk+1∑i=1pgij(xik+1))=0.
Now, we will prove that the set{∑i=1pgij(xik)|j=1,m¯,s∈ℕ} is bounded. Since {xk} is bounded, there exists δ∈ℝsuch that ∥xk∥≤δ. Let B̅(0,δ)⊆ℝn be the closed ball of center zero and radius δ then(4.28)xk∈B̅(0,δ),∀k∈N.
Since Cj(x)=∑i=1pgij(xi) is continuous for all j=1,m¯, then, Cj(B̅(0,δ)) is closed and bounded for all j=1,m¯. Then there exists Mj≥0such that
(4.29)|∑i=1pgij(xi)|≤Mj,∀x∈B̅(0,δ),∀j=1,m¯.
Let ρ = max{Mj:j=1,m¯}, then
(4.30)|∑i=1pgij(xi)|≤ρ,∀x∈B̅(0,δ),∀j=1,m¯.
Therefore, |∑i=1pgij(xik)|≤ρ, for all j=1,m¯, for all k∈ℕ, which means {∑i=1pgij(xik)∣j=1,m¯,s∈ℕ} is a bounded set.
Thus, forj such that u̅ij=0, and the above result, we get(4.31)lim⁡s→∞(uijk+1∑i=1pgij(xik+1))=0.
That is,
(4.32)lim⁡s→∞(uijk+1∑i=1pgij(xik+1))=0∀j=1,m¯.
Also, if x̅ is a limit point of {xk}, keeping in mind that (see the proof given by Polyak in [38]) max{-gij(xik}→0, then
(4.33)lim⁡s→∞∑i=1pgij(xik+1)≥0∀j=1,m¯.
On another hand, from (4.32) we get
(4.34)∇xL̅(x̅,u̅)=0⟹∇F(x̅)-∑j=1m∑i=1pu̅ij∇gij(x̅i)=0,(4.35)u̅ij≥0,j=1,m¯,u̅ij∑i=1pgij(x̅i)=0,from(4.32),∑i=1pgij(x̅i)≥0,from(4.33).
Since the Lagrange of problem (SP) is
(4.36)L̅(x,u)=F(x)-∑j=1m∑i=1puijgij(xi)
and it is convex, then from (4.34)
(4.37)x̅∈Argmin⁡x∈RnL̅(x,u̅)
and then
(4.38)F(x̅)=F(x̅)-∑j=1mu̅ij(∑i=1pgij(x̅i))=L̅(x̅,u̅)≤L̅(x,u̅),∀x∈Rn.
Also, we know that ∑i=1pgij(x̅i)≥0, for all j=1,m¯, and for any uij≥0:-∑j=1m∑i=1puijgij(x̅i)≤0 which implies
(4.39)⟹L̅(x̅,u)=F(x̅)-∑j=1m∑i=1puijgij(x̅i)≤F(x̅)=L̅(x̅,u̅)
and then
(4.40)L̅(x̅,u)≤L̅(x̅,u̅)≤L̅(x,u̅)
for allx∈ℝn, for all u≥0, and by the saddle point theorem we have
(4.41)(x̅,u̅)∈X*×L*.
Since {d(uk)} is an increasing sequence bounded above by d(u*) then it is convergent. Let {(xkl,ukl)} be any convergent subsequence of {(xk,uk)}. Then from (3.4)
(4.42)lim⁡l→∞L(xkl,ukl)=F(x*)=d(u*).
Since ∇xL̅(xk,uk)=0(4.43)⟹min⁡x∈RnL̅(x,uk)=L̅(xk,uk)⟹d(uk)=L̅(xk,uk)⟹lim⁡l→∞L̅(xkl,ukl)=lim⁡l→∞d(ukl)=d(u*).
Then {d(uk)} converges to d(u*). The remaining proof is similar to the one given in [30].In the previous theorem, we proved the boundedness of the primal and dual sequences, but for the sequence of allocation vectors{yk} we can get the boundedness directly by proving that the set(4.44){gij(xik)∣j=1,m¯,i=1,p¯,k∈N}
is bounded. (The same way as we proved that the set {∑i=1pgij(xik)∣j=1,m¯,k∈ℕ} is bounded.).



---

*Source: 471854-2012-05-13.xml*