# Parallel Variable Distribution Algorithm for Constrained Optimization with Nonmonotone Technique

Authors: Congying Han; Tingting Feng; Guoping He; Tiande Guo
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

A modified parallel variable distribution (PVD) algorithm for solving large-scale constrained optimization problems is developed, which modifies quadratic subproblemQPl at each iteration instead of the QPl0 of the SQP-type PVD algorithm proposed by C. A. Sagastizábal and M. V. Solodov in 2002. The algorithm can circumvent the difficulties associated with the possible inconsistency of QPl0 subproblem of the original SQP method. Moreover, we introduce a nonmonotone technique instead of the penalty function to carry out the line search procedure with more flexibly. Under appropriate conditions, the global convergence of the method is established. In the final part, parallel numerical experiments are implemented on CUDA based on GPU (Graphics Processing unit).


---

## Body

## 1. Introduction

In this paper, we consider the following nonlinear programming problem:(1)minf(x),s.t.c(x)≤0,
where f:Rn→R and c(x):Rn→Rm are all continuously differentiable. Suppose the feasible set X in (1) is described by a system of inequality constraints:
(2)Z={x∈Rn∣ci(x)≤0,I={i∣i=1,2,…,m}}.In this paper, we give a new algorithm based on the method in [1], which partitions the problem variables x∈Rn into p blocks x1,…,xp, such that
(3)x=(x1,…,xp),xl∈Rnl,l=1,…,p,∑l=1p‍nl=n.And assume thatX has block-separable structure. Specifically,
(4)c(x)={c1(x1),c2(x2),…,cp(xp)},cl(xl):Rnl⟶Rml,l∈{1,2,…,p},∑l=1p‍ml=m.Parallel variable distribution (PVD) algorithm for solving optimization problems was first proposed by Ferris and Mangasarian [2], in 1994, in which the variables are distributed among p processors. Each processor has the primary responsibility for updating its block of variables while allowing the remaining secondary variables to change in a restricted fashion along some easily computable directions. The distinctive novel feature of this algorithm is the presence of the “forget-me-not” term which allows for a change in “secondary” variables. This makes PVD fundamentally different from the block Jacobi [3] and coordinate descent [4] methods. The forget-me-not approach improves robustness and accelerates convergence of the algorithm and is the key to its success. In 1997, Solodov [5] proposed useful generalizations that consist, for the general unconstrained case, of replacing exact global solution of the subproblems by a certain natural sufficient descent condition, and, for the convex case, of inexact subproblem solution in the PVD algorithm. Solodov [6] proposed an algorithm applied the PVD approach to problems with general convex constraints directly use projected gradient residual function as the direction and show that the algorithm converges, provided that certain conditions are imposed on the change of secondary variables. In 2002, Sagastizábal and Solodov [1] proposed two new variants of PVD for the constrained case. Without assuming convexity of constraints, but assuming block-separable structure, they showed that PVD subproblems can be solved inexactly by solving their quadratic programming approximations. This extends PVD to nonconvex (separable) feasible sets and provided a constructive practical way of solving the parallel subproblems. For inseparable constraints, but assuming convexity, they developed a PVD method based on suitable approximate projected gradient directions. The approximation criterion was based on a certain error bound result, and it was readily implementable. In 2011, Zheng et al. [7] gave a parallel SSLE algorithm, in which the PVD subproblems are solved inexactly by serial sequential linear equations, for solving large-scale constrained optimization with block-separable structure. Without assuming the convexity of constraints, the algorithm is proved to be globally convergent to a KKT point. Han et al. [8] proposed an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems with the idea of [9] in 2009, which based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function. And in particular, different from [9] the linear rate of convergence does not depend on the number of processors.In this paper, we use [1] as our main reference on SQP-type PVD method for problems (1) and (4). Firstly, we introduce the algorithm in [1] simply. The original problem is distributed into p parallel subproblems which treatment among p parallel processors. The algorithm of [1] may result in that the linear constraints in quadratic programming subproblems are inconsistent or the solution of quadratic programming subproblems is unbounded, so that the algorithm may fail. This drawback has been overcome by many researchers, such as [10]. In [1], exact penalty function is used as merit function to carry out the line-search. For the penalty function, as pointed out by Fletcher and Leyffer [11], the biggest drawback is that the penalty parameter estimates could be problematic to obtain. To overcome this drawback, we use a nonmonotone technique to carry out the line search instead of penalty function.Recent research [12–14] indicates that the monotone line search technique may have some drawbacks. In particular, enforcing monotonicity may considerably reduce the rate of convergence when the iteration is trapped near a narrow curved valley, which can result in very short steps or zigzagging. Therefore, it might be advantageous to allow the iterative sequence to occasionally generate points with nonmonotone objective values. Grippo et al. [12] generalized the Armijo rule and proposed a nonmonotone line search technique for Newton’s method which permits increase in function value, while retaining global convergence of the minimization algorithm. In [15], Sun et al. give several nonmonotone line search techniques, such as nonmonotone Armijo rule, nonmonotone Wolfe rule, nonmonotone F-rule, and so on. Several numerical tests show that the nonmonotone line search technique for unconstrained optimization and constrained optimization is efficient and competitive [12–14, 16]. Recently, [17] gives a method to overcome the drawback of zigzagging with nonmonotone line search technique to determine the step length, which makes the algorithm more flexible.In this paper, we combine [1] with the ideas of [10, 17] and propose an infeasible SQP-type Parallel Variable Distribution algorithm for constrained optimization with nonmonotone technique.The paper is organized as follows. The algorithm is presented in Section2. In Section 3, under mild assumptions, some global convergence results are proved. The numerical results are shown in Section 4. And conclusions are given in the last section.


## 2. A Modified SQP-Type PVD Method with Nonmonotone Technique

To describe our algorithm, we first give the modified quadratic subproblems of SQP method. Givenxk∈Rn, we distribute it into p blocks, as the iterate xlk∈Rnl,l=1…,p,Hl∈Rnl×nl,l=1,2,…,p denote an approximate Hessian.We usezl∈R to perturb the subproblem of QPl0 of [1] and give a new subproblem QPl instead of it. Consider
(5)QPl(xlk,Hlk)={min(dl,zl)∈Rnl+1zl+12dlTHlkdls.t.(glk)Tdl≤zl,ci(xlk)+∇ci(xlk)Tdl≤zl,i∈Il={1,…,ml}.For convenience, givenx, the lth block of ∇f(x) will be denoted by
(6)gl=(Inl×nl0n-l×n-l)∇f(x).In (5), glk is gl in step k. Note that (5) is always feasible for dl=0,zl=maxi∈Il{ci(xlk),0}. To test whether constraints are satisfied or not, we denote the violation function h(x) as follows:
(7)h(x)=∥c(x)+∥,where ci(x)+=max{ci(x),0}, i∈I, ∥·∥ denotes the Euclidean norm on Rm. It is easy to see that h(x)=0 if and only if x is a feasible point (h(x)>0 if and only if x is infeasible).We describe our modified PVD algorithm as follows.Algorithm A.
Consider the following.Step 0.
Start with anyx0∈Rn. Choose parameters u∈(0,1/2), β∈(1/2,1), γ∈(0,1), positive integer M>0, and positive definite matrices Hl0∈Rnl×nl, l∈{1,2,…,p}. Set k=0, m(k)=0.Havingxk, check a stopping criterion. If it is not satisfied, compute xk+1 as follows.Step 1.
Parallelization. For each processorl∈{1,2,…,p}, solve subproblem (5) to get (dlk,zlk). If dlk=0, l=1,…,p stop, otherwise return to Step 2.Step 2.
Synchronization. Set(8)dk=(d1k,…,dpk),gkT=((g1k)T,…,(gpk)T),Hk=(H1k⋱Hpk).
IfgkTdk≤-(1/2)dkTHkdk, return to Step 3; otherwise, set λk=1 and return to Step 4.Step 3.
Chooseλk which is the largest one in the sequence {1,γ,γ2,…} satisfying:
(9)f(xk+λdk)≤max0≤j≤m(k)[f(xk-j)]-λμdkTHkdk.Step 4.
Setxk+1=xk+λkdk. Let h¯=max0≤j≤m(k)[h(xk-j)]. If h(xk+1)≤βh¯, then set m(k+1)=min{m(k)+1,M}, update Hlk to Hlk+1,l=1,…,p, set k=k+1, and go to Step 1. Otherwise, let k=k+1, call Restoration Algorithm of [17] to obtain xkr, let xk=xkr, m(k)=m(i), and go to Step 1.Remark 1.
In Step3 of Algorithm A, the nonmonotone parameter m(k) satisfies
(10)m(0)=0,0≤m(k)≤min{m(k-1)+1,M},k≥1.
For the convenience, we denotef(xl(k))=max0≤j≤m(k)[f(xk-j)], where k-m(k)≤l(k)≤k.In a restoration algorithm, we aim to decrease the value ofh(x) more precisely, we will use a trust region type method to obtain h(xk)→0, k→∞ by the help of the nonmonotone technique. Let
(11)Mki(d)=h(xki)-h(xki+d),Ψki(d)=h(xki)-∥(c(xki)+∇c(xki)Td)+∥,andrki=Mki(d)/Ψki(d).Algorithm B is similar to the restoration phase given by Su and Yu [17], we describe the Restoration Algorithm as follows.Algorithm B.
Consider the following.Step 0.
Assumexk0=xk, Δ0>0, i=0, η∈(0,1), m(i)=0.Step 1.
Ifh(xki)≤βh-, then xkr=xki stop.Step 2.
Compute(12)maxΨki(d)s.t.∥d∥≤Δi
to getdki. Calculate rki.Step 3.
Ifrki≤η, then let xki+1=xki, Δi+1=Δi/2, i=i+1, m(i)=min{m(i-1)+1,M} and go to Step 2.Step 4.
Ifrki>η, then let xki+1=xki+dki, Δi+1=2Δi, i=i+1, m(i)=min{m(i-1)+1,M} and go to Step 1.


## 3. The Convergence Properties

To prove the global convergence of Algorithm A, we make the following assumptions.Assumptions(A1)
The iterate{xk} remains in compacted subset S⊂Rn.
(A2)
The objective functionf and the constraint functions cj(j∈I) are twice continuously differentiable on Rn.
(A3)
For allxl∈Rnl, the set {∇ci(xl):i∈Il(xl)} is linearly independent, where Il(xl)={i∈Il:ci(xl)=Φl(xl),Φl(xl)=maxi∈Il{ci(xl),0}}.
(A4)
There exist two constants0<a≤b such that a∥dl∥2≤dlTHlkdl≤b∥dl∥2, l=1,…,p for all iteration k and dl∈Rnl.
(A5)
The solution of problem (12) satisfies
(13)Ψki(d)=h(xki)-∥(c(xki)+∇c(xki)Td)+∥Ψki(d)≥β2Δimin{h(xki),Δi},where β2 is a constant.Remark 2.
Assumptions (A1) and (A2) are the standard assumptions. (A3) is the LICQ constraint qualification. (A4) plays an important role in obtaining the convergence results. (A5) is the sufficient reduction condition which guarantees the global convergence in a trust region method. Under the assumptions,f is bounded below and the gradient function gl,l=1,…,p is uniformly continuous in Sl, where S=(S1,…,Sp).Remark 3.
We can use quasi-Newton BFGS methods to updateHlk, different from [18], we can use a small modification of ylk to make Hlk reserve positive definite according to the formula (33) of [17].Similar to Lemma  1 in [19], we can get the following conclusions.Lemma 4.
Suppose (A1)–(A4) hold,Hlk,l=1,…,p is a symmetric positive definite, then dlk is well defined and (dlk,zlk) is the unique KKT point of (5). Furthermore, dlk is bounded over compact subsets of Sl×Pl, where Pl is the set of symmetric positive definite nl×nl matrices.Proof.
First note that the feasible set for (5) is nonempty, since (dl,zl)=(0,maxi∈Il{ci(xl),0}) is always feasible. It is clear that, if (dlk,zlk) is a solution to (5) if an only if dlk solves the unconstrained problem
(14)mindl∈Rnl12dlTHlkdl+max{(glk)Tdl,maxi∈Il{ci(xlk)+∇ci(xlk)Tdl}},(15)zl=max{(glk)Tdl,maxi∈Il{ci(xlk)+∇ci(xlk)Tdl}}.
Since the function being minimized in (14) is strictly convex and radially unbounded, it follows that dlk is well defined and unique as a global minimizer for the convex problem (5) and thus unique as a KKT point for that problem. So we have
(16)Hlkdlk+vglk+∇cl(xlk)Tμlk=0,(17)1-v-∑i=1ml‍ui=0,
due to (17) and ui≥0,v≥0, we have ui,i∈Il is bounded. Since f,ci is twice continuously differentiable and assumption (A1) holds, for all xl∈Sl, ∥-(vgl+∇cl(xlk)Tμlk∥ is bounded, set the maximum is M. For (16), ∥Hlkdlk∥≤M and combining with Assumption (A4), we have a∥dlk∥2≤dlkTHlkdlk≤∥dlk∥∥Hlkdlk∥≤M∥dlk∥, so that ∥dlk∥≤M/a; therefore, dlk is bounded on Sl×Pl.Lemma 5.
Suppose thatxlk∈Rnl,l=1,…,p,Hlk is positive definite matrix, and (dlk,zlk) is the solution of QPl. Then we have the results (B1) and (B2).(B1)
The following inequality holds:(18)zlk≤Φl(xlk)-12(dlk)THlkdlk,l=1,…,p,
where Φl(xl)=maxi∈Il{ci(xl),0}.(B2)
Ifdlk=0 then zlk=0,l=1,…,p, and xk=(x1k,…,xpk) is a KKT point of problem (1).Proof.
(B1) Sinced¯l=0, z¯l=maxi∈Il{ci(xl),0} is a feasible point of QPl, from the optimality of (dlk,zlk), we have
(19)zlk+12(dlk)THlkdlk≤z¯l+0=maxi∈Il{ci(xlk),0}.
Together with the definination of Φl(xlk), implies that (18) holds.
(B2) Since(dlk,zlk) is the solution of (5), there exists v∈R and μ∈Rml such that the KKT condition of (5), while dlk=0, we have
(20)vglk+∇cl(xlk)Tμlk=0,(21)1-v-∑i=1ml‍uik=0,(22)-zlk≤0,ci(xlk)-zlk≤0,i∈Il,(23)vzlk=0,v≥0,(24)uik[ci(xlk)-zlk]=0,uik≥0,i∈Il.
By the definition of Φl(xlk) and (22), Φl(xlk)≤zlk. Then, from (18) and dlk=0, Φl(xlk)≥zlk. From (24), it follows that
(25)uik=0,∀i∉Il0={i∈Il:ci(xlk)=Φl(xlk)}.
Hence, it follows from Assumption (A3) Together with (20) and (21) that v>0. For (23) we have zlk=0.
From (22) and (24), we have
(26)uikci(xlk)=0,uik≥0,i∈Il,ci(xlk)≤0,i∈Il,
due to (20) and set ρik=uik/v, we have
(27)glk+∇cl(xlk)Tρlk=0.
Taking into account separability of constraintsc(x), and let I=∪l=1pIl, then
(28)ρikci(xk)=0,ρik≥0,i∈I,ci(xk)≤0,i∈I,gk+∇ci(xk)Tρk=0;
that is,xk is a KKT point of (1).Lemma 6 (see [17, Lemma 3]).
In Step3, the line search procedure is well defined.Lemma 7 (see [17, Lemma 4]).
Under Assumption (A5), the Restoration Algorithm (Algorithm B) terminates finitely.From Lemmas6 and 7, we know that the Algorithm A and Algorithm B are well implemented.The following Lemma implies that every cluster point of{xk} which generated by Algorithm A is a feasible point of problem (1).Lemma 8.
Let{xk} be an infinite sequence generated by Algorithm A, then h(xk)→0(k→∞).Theorem 9.
Suppose{xk} is an infinite sequence generated by Algorithm A, dlk,l=1,…,p is the solution of (5), dk=(d1k,…,dpk), then limk→∞∥dlk∥=0, l=1,…,p.Proof.
By Assumption (A1), there exists a pointx* such that xk→x* for k∈K, where K is an infinite index set. By Algorithm A and Lemma 8, we consider the following two possible cases.Case I. K0={k∈K∣gkTdk≤-(1/2)dkTHkdk} is an infinite index set. In this case, we have
(29)f(xk+λkdk)≤f(xl(k))-λkμdkTHkdkf(xk+λkdk)=f(xl(k))-λkμ∑l=1p‍dlkTHlkdlk.Sincem(k+1)≤m(k)+1, we obtain
(30)f(xl(k+1))=max0≤j≤m(k+1)[f(xk+1-j)]f(xl(k+1))≤max0≤j≤m(k)+1[f(xk+1-j)]f(xl(k+1))=max{f(xl(k)),f(xk+1)}f(xl(k+1))=f(xl(k)).Hence form(k)≤M, it holds
(31)f(xl(k))≤f(xl(l(k)-1))-λl(k)-1μdl(k)-1THl(k)-1dl(k)-1f(xl(k))=f(xl(l(k)-1))-λl(k)-1μ∑l=1p‍(dll(k)-1)THll(k)-1dll(k)-1.Sincef is bounded below, {f(xl(k))} converges. Due to (31), we can obtain
(32)limk→∞λl(k)-1μ∑l=1p‍(dll(k)-1)THll(k)-1dll(k)-1=0.By Lemma6, there exists λ¯>0 such that λl(k)-1≥λ¯. By Assumption (A4), we obtain
(33)limk→∞∥dll(k)-1∥=0,l=1,…,p.From the uniform continuity off(x), this implies that
(34)limk→∞f(xl(k)-1)=limk→∞f(xl(k)).Letl¯(k)=l(k+M+2), for any given j≥1, we can have
(35)limk→∞∥dll¯(k)-j∥=0,l=1,…,p,(36)limk→∞f(xl¯(k)-j)=limk→∞f(xl(k)).Ifj=1, since {l¯(k)}⊂{l(k)}, (35) and (36) follow from (33) and (34). For a given number j>1, we have
(37)f(xl¯(k)-j)≤f(xl(l¯(k)-j-1))-λl¯(k)-j-1μdl¯(k)-j-1THl¯(k)-j-1dl¯(k)-j-1.Using the same arguments above, we obtain(38)limk→∞∥dll¯(k)-j-1∥=0,l=1,…,p,limk→∞f(xl¯(k)-j-1)=limk→∞f(xl(k)).Therefore (35) and (36) hold for any given j≥1.Now for anyk, xk+1=xl¯(k)-∑j=1l¯(k)-k-1‍λl¯(k)-jdl¯(k)-j, from Remark 1, we obtain l¯(k)=l(k+M+2)<k+M+2, that is l¯(k)-k-1≤M+1. Since dl¯(k)-j={d1l¯(k)-j,…,dpl¯(k)-j} together with (35), we can obtain limk→∞∥dl¯(k)-j∥=0, 1≤j≤l¯(k)-k-1. Therefore,
(39)limk→∞∥xk+1-xl¯(k)∥=0.Since{f(xl(k))} admits a limit, by the uniform continuity of f on S, it holds
(40)limk→∞f(xk)=limk→∞f(xl¯(k)-1)=limk→∞f(xl(k)).Then by the relation (29), we have
(41)limk→∞∑l=1p‍λkμdlkTHlkdlk=0.Using the same arguments for deriving (33), we obtain that
(42)limk→∞∥dlk∥=0,l=1,…,p.Case II. K0 is a finite index set, which implies K1={k∈K∣gkTdk>-(1/2)dkTHkdk} is an infinite index set.Iflimk→∞∥dlk∥=0,l=1,…,p does not hold, then there exists a positive number ε>0 and an infinite index set K2, such that ∥dlk∥>ε, for all k∈K2⊂K1. Since (dlk,zlk) is the solution of QPl. By the KKT condition of (5), we have
(43)Hlkdlk+vglk+∇cl(xlk)Tμlk=0,(44)1-v-∑i=1ml‍ui=0,(45)glkTdlk-zlk≤0,(46)ui[ci(xlk)+∇ci(xlk)Tdlk-zlk]=0,ui≥0,i∈Il.Sincev≥0, ui≥0 and (44), we obtain 0≤ui≤1, therefore there exists M¯l satisfied ∥ulk∥≤M¯l.By Lemma8, h(xk)→0 implies hl(xlk)→0. Hence there exists k0, such that for k>k0,k∈K2, it holds
(47)hl(xlk)≤aε22M¯l≤a∥dlk∥22M¯l≤dlkTHlkdlk2M¯l,l=1,…,p.Consequently, from (43), we deduce
(48)vglkTdlk=-dlkTHlkdlk-μlkT∇cl(xlk)dlkvglkTdlk=-dlkTHlkdlk+∑i=1ml‍ui(ci(xlk)-zlk)vglkTdlk≤-dlkTHlkdlk+M¯lhl(xlk)-∑i=1ml‍uizlkvglkTdlk≤-dlkTHlkdlk+M¯lhl(xlk)-∑i=1ml‍uiglkTdlk.Together with (44), (47), and transpose
(49)glkTdlk=(∑i=1ml‍ui+v)glkTdlkglkTdlk≤-dlkTHlkdlk+M¯lhl(xlk)glkTdlk≤-dlkTHlkdlk+12dlkTHlkdlkglkTdlk=-12dlkTHlkdlk.Taking into account separability of constraintsc(x), then
(50)gkTdk=∑l=1p‍glkTdlkgkTdk≤-∑l=1p‍12dlkTHlkdlkgkTdk=-12dkTHkdk,
which contradicts the definition of K1. The proof is complete.Theorem 10.
Suppose{xk} is an infinite sequence generated by Algorithm A and the assumptions in Theorem 9 hold. Then every cluster point of {xk} is a KKT point of problem (1).Proof.
By Assumption (A2), there existsx*, such that xk→x*,k∈K. From Lemma 8, we have h(xk)→0,k∈K, which means that x* is a feasible point. From Theorem 9, we have limk→∞∥dlk∥=0,l=1,…,p. By Lemma 5, dlk→0 implies that zlk→0,l=1,…,p, that is, dl*=0,l=1,…,p,zl*=0,l=1,…,p.
Compare the KKT condition of (5) with the KKT condition of problem (1), and let ρ*=(ρ1*,…ρp*),ρl*=(ui*/v,i∈Il),I=∪l=1pIl.
Taking into account separability of constraintsc(x) and x, we conclude
(51)g*+ρ*∇c*=0,c(x*)≤0,ρi*≥0,ρi*Tci(x*)=0,i∈I.
Thereforex* is a KKT point of problem (1).


## 4. Numerical Results

To get some insight into computational properties of our approach in Section2, we considered the same test problems taken from [1]. Choose Problem 1 of [1] as follows:
(52)min∑i=1p-1‍∑j=i+1p‍∑t=1v‍x(i-1)v+tx(j-1)v+ts.t.∑t=1v‍x(i-1)v+t2-1=0,i=1,…,p.In our test, we only verify our convergence theory without comparing with serial algorithms. In the future, we will propose the convergent rate of the parallel algorithm.Not having access to a parallel computer, we have carried out on Graphics Processing Unit (GPU) to solve them and implement the algorithm on Compute Unified Device Architecture (CUDA) [20]. However, the input and output are implemented by CPU. And all the subproblems are solved on blocks which are constructed into many threads. If there are p blocks in GPU, which is equivalent to p processors in a parallel computer. Many threads of the block can achieve a large number of vector calculations in current block.We have implemented Algorithm A in C language. All codes were run under Visual Studio 2008 and Cuda 4.0 on the DELL Precision T7400. In Table1, we report the number of iterations and the running times for Algorithms A on Problem (52). The results in Table 1 confirm that the proposed approach certainly makes sense. We solve the subproblem (5) which is a positive semidefinite quadratic programs by the modified interior-point methods. And the Restoration Algorithm of [17] is solved by Trust-region Approach combined with local pattern search methods. All algorithms are coded by C language without using any function from optimization Toolbox; hence the results are not the best. In Table 1, n denotes the dimensions of test problem and ν denotes the variable number of one block. There is less iteration number of QPl subproblem with more numbers of blocks for high-dimensional problem, which shows the algorithm is reliable.Table 1
Results for Algorithm A.
Problem 1n, νν = 3
P
Algorithm A
Iteration number
Iteration number ofQPl subproblem
Running times
n
=
6
2
5
52
0.5
n
=
12
4
10
66
0.5
n
=
24
8
15
78
1
n
=
48
16
9
46
2
n
=
96
32
6
50
9
n
=
192
64
7
24
13


## 5. Conclusion

The PVD algorithm which was proposed in 1994 is used to solve unconstrained optimization problems or has a special case of convex block-separable constraints. In 1997, M. V. Solodov proposed useful generalizations that consist, for the general unconstrained case, of replacing exact global solution of the subproblems by a certain natural sufficient descent condition, and, for the convex case, of inexact subproblem solution in the PVD algorithm. M. V. Solodov proposed a PVD approach in 1998 which applied to problems with general convex constraints directly and show that the algorithm converges. In 2002, C. A. Sagastizábal et al. propose two variants of PVD for the constrained case: without assuming convexity of constraints, but assuming block-separable structure and for inseparable constraints, but assuming convexity. In this paper, we propose the modified algorithm of [1] used to the general constraints but with block-separable structure.In a word, the algorithm above is a special structure of the objective function or constraints with a special structure. In the further, we will study the parallel algorithm with general inseparable constraints.



---

*Source: 295147-2013-04-04.xml*