# A Quasi-Monte-Carlo-Based Feasible Sequential System of Linear Equations Method for Stochastic Programs with Recourse

Authors: Changyin Zhou; Rui Su; Zhihui Jiang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

A two-stage stochastic quadratic programming problem with inequality constraints is considered. By quasi-Monte-Carlo-based approximations of the objective function and its first derivative, a feasible sequential system of linear equations method is proposed. A new technique to update the active constraint set is suggested. We show that the sequence generated by the proposed algorithm converges globally to a Karush-Kuhn-Tucker (KKT) point of the problem. In particular, the convergence rate is locally superlinear under some additional conditions.


---

## Body

## 1. Introduction

Stochastic programming is a framework for modeling optimization problems that involve uncertainty. It has applications in a broad range of areas ranging between finance, transportation, and energy optimization [1, 2]. In the field of industrial production, stochastic programming is also widely used in stochastic control [3–7].We consider the following two-stage stochastic quadratic programming problem:(1a)minfx=Px+Qx,(1b)subject  tocx≤0,where(1c)Qx=∫ΩQx,ωpωdω,(1d)Qx,ω=max⁡-12yTGy+yThω-Tx∣Wy≤q,y∈Rs.P(·):Rn→R and c(·):Rn→Rm are twice continuously differentiable. G∈Rs×s is symmetric positive definite. T∈Rs×n, q∈Rt, and W∈Rt×s are fixed matrices or vectors. ω∈Rr and h(·) are random vectors. p(·):Rr→R+ is a continuously differentiable probability density function.LetF={x∈Rn∣c(x)≤0} and Z={y∈Rs∣Wy≤q}. We denote the active constraint by I0(x)={i∈I∣ci(x)=0}, where I={1,…,m}. Throughout the paper, the following hypotheses hold.Assumption 1.
F and Z are bounded.Assumption 2.
At everyx∈F, the vectors ∇ci(x), i∈I0(x) are linearly independent.A basic difficulty of solving stochastic optimization problem (1a), (1b), (1c), and (1d) is that the objective function with uncertainty can be complicated or difficult to compute even approximately. The aim of this paper is to give computational approaches based on quasi-Monte-Carlo sampling techniques. To solve stochastic programming problems, one usually resorts to deterministic optimization methods. This idea is a natural one and was used by many authors over the years [8–12]. Deterministic methods were also applied to stochastic programming problems which involve quadratic programming in a vast literature. The extended linear quadratic programming (ELQP) model was introduced by Rockafellar and Wets [13, 14]. Qi and Womersley [15] proposed an sequence quadratic programming (SQP) algorithm for ELQP problems. To solve ELQP, Chen et al. [16] suggested a Newton-type approach and showed that this method is globally convergent and locally superlinear convergent. At the same time, Birge et al. [17] investigated a stochastic Newton method for ELQP with inequality constraint Ax≤b. Global convergence and local superlinear convergence of the method were established.In order to get a numerical solution of (1a), (1b), (1c), and (1d) based on quasi-Monte-Carlo techniques, consider the following approximation of (1c):(2)Qnkx=1nk∑i=0nk-1ξiQx,ωi,where ωi∈Ω and ξi is generated by lattice rules [18, 19]. Consequently problem (1a), (1b), (1c), and (1d) is approximated by (3a)minfnkx=Px+Qnkx,(3b)subject  tocx≤0.Since Z is bounded, it follows from [17] that f(x) is twice continuously differentiable. Moreover, from [16], the approximated objective function fnk(x) has the following continuous first derivative in Rn:(4)gnkx=∇Px-1nkTT∑i=0nk-1ξiz∗x,ωi,where z∗x,ωi=arg⁡max⁡{-(1/2)zTGz+zT(h(ωi)-Tx)∣z∈Z}.Let{nk}k=1∞ be an integer sequence satisfying 1≤n1≤⋯≤nk≤nk+1≤⋯ and nk→∞ as k→∞. Generate observations {ωi, i=1,…,nk} on the unit hypercube according to an integration rule. Here, we choose quasi-Monte-Carlo sequences [20]. Since F and Z are compact, it follows from [20] (or [21]) that there exists a constant C>0 such that, for any x∈F,(5)fx-fnkx≤Clog⁡nkm-1nk,(6)∇fx-gnkx≤Clog⁡nkm-1nk.The paper addresses a feasible sequential system of linear equations (SSLE) approach to solve (1a), (1b), (1c), and (1d). This study is strongly motivated by recent successful development of various SSLE algorithms for deterministic optimization problems and quasi-Monte-Carlo simulation techniques. SSLE methods for deterministic optimization problems have been proposed by many authors over the years. An interested reader is referred to the literature [22–26] for excellent surveys. Our algorithm has the following interesting features.(a)
Without assuming isolatedness of the accumulation point or boundedness of the Lagrange multiplier approximation sequence, every accumulation point of the iterative sequence generated by the proposed algorithm converges to a KKT point of problem (1a), (1b), (1c), and (1d).(b)
At each iteration, we only to solve four symmetric systems of linear equations with a common coefficient matrix and a simple structure. In the proposed algorithm the last system of linear equation only needs to be solved for achieving a local one-step superlinear convergence rate.(c)
In order to achieve the “working set,” the multiplier functionλ(x)≔(∇cxT∇c(x)+diag⁡(ci2(x)))-1∇cxT∇f(x) is needed to be obtained firstly in [27]. The multiplier function also is suggested by Facchinei et al. [28], while our algorithm provides a new technique to update the “working set,” consequently, without calculating the multiplier function.(d)
In order to find a search direction, a quadratic programming subproblem needs to be solved at each iteration in [17]. Consequently, the Hessian of objective function needs to be approximated by Monte Carlo (or quasi-Monte-Carlo) rule, while for the SSLE methods the approximation is not necessary. Our algorithm solves four linear systems of equations with only the first-order derivative of objective function involved.The remainder of this paper is organized as follows. Section2 gives the algorithm of (1a), (1b), (1c), and (1d) and shows the proposed algorithm is well defined. In Section 3 we discuss the convergence of algorithm in detail. We proceed in Section 4 by showing the local superlinear convergence. Finally, our conclusions are presented in Section 5.


## 2. Algorithm

The Lagrangian function associated with problem (1a), (1b), (1c), and (1d) is defined by (7)Lx,λ=fx+λTcx.A point x∗ in F is called a KKT point of problem (1a), (1b), (1c), and (1d), if there exits λ∗ such that the following KKT conditions hold:(8)∇xLx∗,λ∗=0,λ∗≥0,cix∗λi∗=0,∀i∈I,where(9)∇xLx,λ=∇fx+∑i=1mλi∇cix.For x,y∈F, let (10)Ix,y,λ,ε≔i∈I∣cix+ερy,λ>0,where ε is a nonnegative parameter and ρ(y,λ)=Φ(y,λ) with (11)Φy,λ≔∇yLy,λmin⁡-cy,λ.From the definition of ρ(x,λ), ρ(x∗,λ∗)=0 if and only if (x∗,λ∗) satisfies KKT conditions (8). In order to achieve the active constraint set in our algorithm, the estimate of set I(x,y,λ,ε) is defined by (12)Inkx,y,λ,ε≔i∈I∣cix+εψnky,λ>0,where(13)ψnky,λ=21nkδ22+ρnky,λ41/4,ρnky,λ=Φnky,λ,Φnky,λ≔∇yLnky,λmin⁡-cy,λ,∇yLnky,λ=gnky+∑i=1mλi∇ciy,and δ2 is a positive parameter in (1/2,1). Since f(x) and c(x) are continuously differentiable, it follows from Theorem  3.15 in [28] that ρnk(x,λ) is nonnegative and continuous on Rn+m. Hence, from (6) and continuous differentiability of fnk(x), we have that ρnk(y,λ)→ρ(x∗,λ∗), as nk→∞, (y,λ)→(x∗,λ∗).For simplicity, letI(nk,k+1,ε)≔Ink(xk+1,xk,λk,ε), and (14)Mnk,k+1≔Hk+1∇cnk,xk+1∇cnk,xk+1T0,where(15)∇cnk,xk+1≔∇cixk+1∣i∈Ink,k+1,ε.Now we formally state our algorithm.Algorithm 3.
m
m
m j
(S.0) (Initialization)
Parameters:σ∈(0,1), σ1∈(0,1), θ∈(0,1), η∈(2,3), u∈(0,1/2), β∈(0,1), δ1∈(0,1/2), δ2=1-δ1;
Data:0<w0<1, M>0, λ0=0∈Rm, ε0>0, symmetric positive define matrix H0∈Rn×n, x0=x1∈F, and ci(x0)<0, for every i∈I. Sequence {αk} satisfies αk>0, for all k, and ∑k=0∞αk<+∞;
Choosen0, n1 such that 1/n0δ2∈(0,α0), and 1/n1δ2∈(0,α1);
Generate observations{ωi:i=0,…,n0} by quasi-Monte-Carlo rules and calculate gn0(x0);
Setk≔1.
(S.1) (Choose Working Set)
(S1.1)
Ifψnk-1(xk-1,λk-1)>M, then set ψnk-1(xk-1,λk-1)=M.
(S1.2)
Setε≔εk, w≔wk.
(S1.3)
CalculateI(nk-1,k,εk) and M(nk-1,k).
(S1.4)
If(M(nk-1,k))<w, then set ε=σε, w=σ1w, and go to (S1.3).
(S1.5)
Setεk+1=ε, wk+1=w.
(S.2) (Computation of Search Direction)
IfI(nk-1,k,εk)=∅, then run the following step (S2.1)–(S2.4); otherwise go to (S2.5).
(S2.1)
Setl≔0.
(S2.2)
Generate observations{ωi:i=0,…,nk+l} by quasi-Monte-Carlo rules and calculate gnk+l(xk).
(S2.3)
Setdk0=dk1=dk2=dk3=-Hkgnk+l(xk).
(S2.4)
If1/nk+lδ2>Mdk2, then set l=l+1 and go to (S2.2); otherwise set n¯k=nk+l, λk=0, lk=l, and go to (S.3).
(S2.5)
Setl≔0.
(S2.6)
Generate observations{ωi:i=0,…,nk+l} by quasi-Monte-Carlo rules and calculate gnk+l(xk).
(S2.7)
Compute(dk0,λk0) by solving the system of linear equation in (d,λ)(16)Mnk-1,kdλ=-gnk+lxk0.
Setλk≔λk00∈Rm.
(S2.8)
Let(17)υik=λik0,i∈Γk0-,min⁡-cixk,λik0,i∈Ink-1,k,εk∖Γk0-,
whereΓk0-={i∈I(nk-1,k,ε)∣λik0<0}.
Compute(dk1,λk1) by solving the system of linear equation in (d,λ)(18)Mnk-1,kdλ=-gnk+lxkυk.
If1/nk+lδ2>Mdk1, then set l=l+1 and go to (S2.6); otherwise set n¯k=nk+l, and lk=l.
(S2.9)
Compute(dk2,λk2) by solving the system of linear equation in (d,λ)(19)Mnk-1,kdλ=-gnk+lxkμk,
where(20)μk=υk-ρke,ρk=θ-1gnk+lxkTdk11+∑i∈Ink-1,k,εkλik0dk1ηdk1η.
(S2.10)
Compute(dk3,λk3) by solving the system of linear equation in (d,λ)(21)Mnk-1,kdλ=-gnk+lxkωk,
where(22)ωk=∇cnk-1,xkTdk2-cnk-1,xk+dk2-dk2ηe.
(S.3) Ifdk3-dk2>dk2, then set dk3=dk2.
Choosetk, the first number t in the sequence {1,β,β2,…} satisfying (23)fn¯kxk+tdk2+t2dk3-dk2-fn¯kxk≤utgn¯kxkTdk2+αk,(24)cixk+tdk2+t2dk3-dk2<0,i∈I.(S.4) Compute Nk such that 1/Nkδ2∈(0,αk+1).
Setnk+1=max⁡{Nk,n¯k}, and xk+1≔xk+tkdk2+tk2(dk3-dk2). Generate a new symmetric positive define matrix Hk+1. Set k≔k+1 and go to (S.1).Remarks
(a)
The main purpose of (S.1) is to generate a working set and ensure that the matrixM(nk-1,k) is nonsingular, for every k. Hence, (dki,λki) is well defined, for all i∈{0,1,2,3}. The calculation of set I(nk-1,k,εk) specially is different from the one proposed in [27]. We use the solution λk1 of system (18) as a substitute for the multiplier function proposed in [27]. Moreover, M(nk-1,k) is also uniformly bounded. Details will subsequently be given.
(b)
From the construction of the algorithm, four linear systems need to be solved at each iteration. To ensure the iterate sequence globally converges to KKT point of (1a), (1b), (1c), and (1d), we only need to solve the previous three linear systems (16), (18), and (19). The linear systems (16) and (19) play important roles in proving the global convergence. The main aim of the linear system (21) is to guarantee the one-step superlinear convergence rate of the algorithm under mild conditions.
(c)
It is not difficult to show that there existstk, the first number of the sequence {1,β,β2,…}, which satisfies the linear search (23) and (24). In Section 4 we will show that tk=1, for sufficiently large k. Hence, the Maratos effect will be avoided.
(d)
In numerical experimentsHk is usually updated by the Broyden-Fletcher-Goldfarb-Shanno (BFGS) formula [27, 29]. At any iteration k Algorithm 3 stops as the following termination criteria, with εstop∈(0,1) and maximum iterations Nmax:(25)(i)Φnkxk,λk<εstop,or  (ii)k=Nmax.The rest of section is devoted to show that Algorithm3 is well defined. We firstly give the following hypothesis on the choice of the matrix Hk.Assumption 4.
There exist positive constantsC1 and C2 such that for all k and d∈Rn(26)C1d2≤dTHkd≤C2d2.It is not difficult to see fromci(xk)<0, for every k in nonnegative integer set N, the inner iteration (S.1) terminates finitely.Lemma 5.
∇
f
(
x
k
)
=
0, if there exists some k such that the following conditions hold.
(a)I(nk-1,k,εk)=∅, (b) 1/(nk+l)δ2>Mdk2 for all l≥0.Proof.
From condition (b), we have thatdk2→0. It follows that (27)∇fxk≤∇fxk-gnk+lxk+gnk+lxk≤Clog⁡nk+lm-1nk+l+Hkdk2⟶0.From independence of k and l, the result follows.Lemma 6.
∇
f
(
x
k
)
=
0, if there exists some k such that the following conditions hold.
(a)I(nk-1,k,εk)≠∅, (b) 1/nk+lδ2>Mdk1 for all l≥0.Proof.
From condition (b),dk1→0. It follows that, as l→∞(28)gnk+lxkTdk1=-dk0Hkdk0-∑i∈Γk0-λik02-∑i∈Ink-1,k,εk∖Γk0-λik0min⁡-cixk,λik0=0.Therefore, we get dk0→0, and (29)λik0⟶0ifi∈Γk0-,λik0cixk⟶0ifi∈Ink-1,k,εk∖Γk0-.Since ci(xk)<0, λk0→0, we have, as l→∞,(30)∇fxk≤∇fxk-gnk+lxk+gnk+lxk=∇fxk-gnk+lxk+∇cnk-1,xkλk0+Hkdk0⟶0.This completes the proof.It is easy to see from Lemmas5 and 6 that xk is a unconstrained stationary point of f, if we are not able to get the next iteration xk+1 from the current iteration xk; that is, the inner iterations (S2.1)–(S2.8) terminate infinitely. Since we always have xk∈F, this means that xk is actually a KKT point of problem (1a), (1b), (1c), and (1d). In the following section, we assume that the inner iterations (S2.1)–(S2.8) terminate finitely for all k∈N; namely, there always exists l0∈N such that, for every k∈N, one of the following conditions holds.(i)
I(nk-1,k,εk)=∅, 1/(nk+l0)δ2≤Mdk2.(ii)
I(nk-1,k,εk)≠∅, 1/(nk+l0)δ2≤Mdk1.Therefore, the algorithm generates an infinite iterative sequence {xk}.Lemma 7.
If there existsk0 such that I(nk-1,k,εk)=∅ for all k>k0, then there exists ε¯>0 such that εk≥ε¯ for all k∈N.Proof.
SinceI(nk-1,k,εk)=∅, we have that M(nk-1,k)-1=Hk-1. So the result follows from Assumption 4.Lemma 8.
If there existk0 and subset K⊂N such that I(nk-1,k,εk)≠∅ with k∈K and all k>k0, then εk+1=εk for sufficiently large k.Proof.
Assume to contrary that for anyk0∈K there always exists k>k0 such that εk+1≠εk. From construction of the algorithm, we have that εk→0. By Assumption 1 and the finiteness of set I, without loss of generality, we can assume that(i)
{xk}K→x∗ with x∗∈F and εk+1<εk for all k∈K;(ii)
I(nk-1,k,εk), k∈K keep changeless.For simplicity, let IK≔I(nk-1,k,εk). Since ψnk-1(xk-1,λk-1) is bounded, it follows from εk→0 that IK⊂I0(x∗) for sufficiently large k. Hence, by Assumption 4 and step (S.1), we get (31)∇cIKxkT∇cIKxk⟶∇cIKx∗T∇cIKx∗=0,which contradicts with Assumption 2, and the proof is complete.From Lemmas7 and 8 we can directly obtain Lemma 9.Lemma 9.
There existsε¯>0 such that εk>ε¯ for all k.SinceF is compact, we get Lemma 10.Lemma 10.
M
(
n
k
-
1
,
k
) is nonsingular and uniformly bounded with respect to k∈N; that is, there exists W¯>0 and M¯>0 such that, for all k∈N,(32)W¯≤det⁡Mnk-1,k≤M¯.From Assumption1 and Lemma 10, the following lemma is then obvious.Lemma 11.
{
(
d
k
j
,
λ
k
j
)
} are bounded for j=0,1,2,3.Lemma 12.
IfI(nk-1,k,εk)≠∅, the following results hold.(a)
gnk+l(xk)Tdk0=-dk0Hkdk0 for 0≤l≤lk.(b)
gnk+l(xk)Tdk1≤gnk+l(xk)Tdk0 for 0≤l≤lk.(c)
gnk+lk(xk)Tdk2≤θgnk+lk(xk)Tdk1.Proof.
(a) is a direct consequence of linear system (16). It is easy to see from linear systems (16), (18), and (19) that (33)dk0THkdk1=-gnk+lxkTdk0,dk1THkdk0+λk0Tυk=-gnk+lxkTdk1,dk0THkdk2=-gnk+lkxkTdk0,dk2THkdk0+λk0Tμk=-gnk+lkxkTdk2.Therefore, we have (34)gnk+lxkTdk1=gnk+lxkTdk0-λk0Tυk=gnk+lxkTdk0-∑i∈Γk0-λik02-∑i∈Ink-1,k,εk∖Γk0-λik0min⁡-cixk,λik0≤gnk+lxkTdk0,gnk+lkxkTdk2=gnk+lkxkTdk1+λk0Tυk-μk=gnk+lkxkTdk1+θ-1gnk+lkxkTdk1∑i∈Ink-1,k,εkλik0dk1η1+∑i∈Ink-1,k,εkλik0dk1η≤θgnk+lkxkTdk1.This completes the proof.


## 3. Convergence

Lemma 13.
Suppose the following conditions hold.(i)
{xk}K→x∗.(ii)
I(nk-1,k,εk)=∅ for every k∈K.(iii)
There existsK0⊂K such that {xk-1,λk-1}K0→(x¯∗,λ¯∗), and ρ(x¯∗,λ¯∗)≠0.Then x∗ is a stationary point; namely, ∇f(x∗)=0.Proof.
We show the conclusion by contradiction. Suppose that∇f(x∗)≠0. Without loss of generality, we assume that {dk2}K→d¯≠0 and Hk→H∗. So there exists γ1>0 such that for sufficiently large k∈K(35)gnk+lkxkTdk2=gnk+lkxk-∇fxkTdk2+∇fxkTHk-1gnk+lkxk≤-∇fxkTHk-1∇fxk+Clog⁡nk+lkm-1nk+lkdk2+∇fxkTHk-1≤-γ1.Since ρ(x¯∗,λ¯∗)≠0, for sufficiently big k∈K0, there exists ρ0>0 such that (36)ψnk-1xk-1,λk-1>ρ0.So (37)cixk≤-ε¯ψnk-1xk-1,λk-1≤-ε¯ρ0.Let γ=min⁡{γ1,ε¯ρ0}. Since {dk2}K→d¯≠0, it is obvious that o(tdk)=o(t). So we have that, for sufficiently large k∈K,(38)fnk+lkxk+tdk2-fnk+lkxk≤fxk+tdk2-fxk+fnk+lkxk+tdk2-fxk+tdk2+fxk-fnk+lkxk≤fxk+tdk2-fxk+2·Clog⁡nk+lkm-1nk+lk=t∇gnk+lkxkTdk2+t∇fxk-∇gnk+lkxkTdk2+ot+2·Clog⁡nk+lkm-1nk+lk≤t∇gnk+lkxkTdk2+ot+tdk2+2·Clog⁡nk+lkm-1nk+lk≤ut∇gnk+lkxkTdk2-1-utγ+ot+tdk2+2·Clog⁡nk+lkm-1nk+lk.Therefore, we have(39)fnk+lkxk+tdk2-fnk+lkxk≤ut∇gnk+lkxkTdk2-1-utγ+ot+αk.By (37), for all i∈I(40)cixk+tdk2=cixk+t∇cixkTdk2+ot≤-γ+t∇cixkTdk2+ot.It follows that from (39) and (40) that there exists t¯>0 independent of k such that, for any t∈(0,t¯], both (23) and (24) hold. From (39), there exists k0 such that, for all k≥k0 with k∈K, t¯≥tk≥βt¯,(41)fnk+lkxk+tkdk2-fnk+lkxk≤-ut¯βγ+αk.It is not difficult to see from (23) and Lemma 12 that, for sufficiently large k,(42)fxk+tkdk2-fxk=fnk+lkxk+tkdk2-fnk+lkxk+fxk+tkdk2-fnk+lkxk+tkdk2+fnk+lkxk-fxk≤fnk+lkxk+tkdk2-fnk+lkxk+αk≤utkgnk+lkxkTdk2+αk+αk≤2αk.Combining with (41), we get (43)∑k=k0∞fxk+1-fxk≤∑k=k0,k∉K∞2αk+∑k≥k0,k∈K∞fnk+lkxk+tkdk2-fnk+lkxk+αk≤∑k=k0∞4αk+∑k≥k0,k∈K∞-ut¯βγ⟶-∞.It follows that f(xk)→-∞, which contradicts with the fact that {f(xk)} is bounded, and the proof is complete.Lemma 14.
Suppose the following conditions hold.(i)
{xk}K→x∗.(ii)
I(nk-1,k,εk)=∅ for every k∈K.(iii)
There existsK0⊂K such that {xk-1,λk-1}K0→(x¯∗,λ¯∗), and ρ(x¯∗,λ¯∗)=0.
IfI(nk-2,k-1,εk-1)=∅ for every k∈K0, then x∗ is a stationary point; namely, ∇f(x∗)=0.Proof.
From the above conditions, we have that, for everyk∈K0, λk=λk-1=0, ∇f(x¯∗)=0, and therefore (44)dkj-1K0⟶H∗-1∇fx¯∗=0,j=0,1,2,3.It follows that as k→∞ and k∈K0(45)xk=xk-1+tkdk2-1+tk2dk3-1-dk2-1⟶x¯∗=x∗.This completes the proof.Letπkj, j=0,1,2,3, denote the vectors on Rm with components πikj, respectively, where (46)πikj≔λikj,i∈Ink-1,k,εk,0,i∈I∖Ink-1,k,εk.Lemma 15.
Suppose conditions (i)–(iii) hold in Lemma14. If I(nk-2,k-1,εk-1)≠∅ for every k∈K0, then x∗ is a stationary point; namely, ∇f(x∗)=0.Proof.
Without loss of generality, we suppose thatIK≔I(nk-1,k,εk) and IK0≔I(nk-2,k-1,εk-1) keep changeless.
From condition (iii) in Lemma14(47)ρnkxk-1,λk-1K0⟶0,ψnk-1xk-1,λk-1K0⟶0.Combining with the first equation of linear system (16), {dk0-1}K0→0. It is easy to see from (47) that (48)min⁡-cixk-1,λik0-1K0⟶0fori∈Ink-2,k-1,εk-1∖Γk0-1-,λik0-1K0⟶0fori∈Γk0-1-.Therefore, we have (49)dkj-1K0⟶0,πkj-1K0⟶λ¯∗,j=1,2,3.So we get(50)xk=xk-1+tkdk2-1+tk2dk3-1-dk2-1⟶x¯∗,and for sufficiently large k∈K0(51)dk2-1=Odk1-1,dk3-1=Odk1-1.Let I0+(x¯∗)={i∈I∣λ¯i∗>0}. Since (x¯∗,λ¯∗) is a KKT pair of problem (1a), (1b), (1c), and (1d), we have (52)I0+x¯∗⊂IK0.Therefore, from (50)(53)x∗=x¯∗,cix∗=cix¯∗=0,i∈I0+x¯∗.If there is M>0 such that dk0-1≥Mdk1-1, then we have from (51) that for arbitrary i∈I0+(x¯∗) and sufficiently large k∈K0(54)cixk+ε¯ψnk-1xk-1,λk-1=cixk+ε¯21nk-1δ22+ρnk-1xk-1,λk-141/4≥cixk+21/4ε¯∇xLnk-1xk-1,λk-12+∑i=1mmin⁡-cixk-1,λik-121/4=cixk+21/4ε¯Hk-1dk0-12+∑i=1mmin⁡-cixk-1,λik-121/4≥cixk+2-1/2ε¯Hk-1dk0-11/2+∑i=1mmin⁡-cixk-1,λik-121/4>0.For dk1-1=0dk0-1, since M(nk-1,k) is nonsingular(55)dk1-1=O∑i=1mmin⁡-cixk-1,λik-12.So we can also get that for sufficiently large k∈K0(56)cixk+ε¯ψnk-1xk-1,λk-1>0.So we have(57)I0+x¯∗⊂IK⊂I0x∗.Since IK=∅, I0+(x¯∗)=∅. It follows that λ¯∗=0, and, therefore, ∇f(x∗)=0. This completes the proof.Lemma 16.
Suppose that{(xk,λk)}K→(x∗,λ∗). If {gnk+lk(xk)Tdk2}K→0, then (x∗,λ∗) is a KKT pair of problem (1a), (1b), (1c), and (1d).Proof.
If, for everyk∈K, I(nk-1,k,εk)=∅, the result can be directly obtained from dk2=-Hkgnk(xk) and λk=0. Without loss of generality, we suppose that, for all k∈K,(i)
I(nk-1,k,εk)≠∅,(ii)
IK≔I(nk-1,k,εk) keep changeless.By Lemma 12 and linear systems (16), (18), and (19), we have (58)gnk+lkxkTdk2≤θgnk+lkxkTdk1≤-dk0THkdk0-∑i∈Γk0-λik02-∑i∈IK∖Γk0-λik0min⁡-cixk,λik0⟶0.So (59)dk0K⟶0,λk0υkK⟶0.Let λ∗ be an arbitrary accumulation point of {λk0}K. Since ∇f(x) and ∇c(x) are continuously differentiable, we get from (6), (16), and (59) that (60)∇fx∗+∇cx∗λ∗=0,λi∗≥0,λi∗ciλi∗=0,cix∗≤0,i∈I.This completes the proof.Lemma 17.
Assume that the following conditions hold:(i)
{(xk,λk)}K→(x∗,λ∗).(ii)
there exists subsetK0⊂K such that {(xk-1,λk-1)}K0→(x¯∗,λ¯∗) and ρ(x¯∗,λ¯∗)≠0.Then (x∗,λ∗) is a KKT pair of problem (1a), (1b), (1c), and (1d).Proof.
Assume to the contrary that(x∗,λ∗) is not a KKT pair of problem (1a), (1b), (1c), and (1d). Without loss of generality, we suppose that conditions (i) and (ii), which are given in proof for Lemma 16, hold for all k∈K. It is not difficult to see from Lemma 16 that there exists γ1>0 such that, for sufficiently large k∈K,(61)gnk+lkxkTdk1<-γ1,gnk+lkxkTdk2<-γ1.So that, for sufficiently large k∈K,(62)fnk+lkxk+tdk2-fnk+lkxk≤ut∇gnk+lkxkTdk2-1-utγ1+ot+αk.From (61), dk1K does not converge to 0. Therefore, without loss of generality, we also can suppose that dk1K→d1≠0 and Hk→H∗. Since ρ(x¯∗,λ¯∗)≠0, for sufficiently large k∈K0, there exists ρ0>0 such that (63)ψnk-1xk-1,λk-1>ρ0.It follows that IK⊃I0(x∗). So, for every i∈IK,(64)cixk+tdk2+t2dk3-dk2=cixk+t∇cixkTdk2+ot=cixk+tλik0-tρk+ot,λik0<0,cixk+t·min⁡-cixk,λik0-tρk+ot,λik0≥0,and, for i∉IK,(65)cixk+tdk2+t2dk3-dk2=cixk+t∇cixkTdk2+ot≤-12ε¯ρ0+Ot.In a way similar to the proof of Lemma 13, we get that {f(xk)}K0→-∞, which contradicts with the boundedness of f(x), x∈F. This completes the proof.Lemma 18.
Assume that the following conditions hold.(i)
{(xk,λk)}K→(x∗,λ∗).(ii)
There exists subsetK0∈K such that {(xk-1,λk-1)}K0→(x¯∗,λ¯∗) and ρ(x¯∗,λ¯∗)=0.(iii)
I(nk-1,k,εk)≠∅ for every k∈K.If I(nk-2,k-1,εk-1)=∅ for every k∈K0, then (x∗,λ∗) is a KKT pair of problem (1a), (1b), (1c), and (1d).Proof.
Without loss of generality, we suppose thatIK≔I(nk-1,k,εk) keep changeless. Let (66)Mx∗≔H∗∇cIKx∗∇cIKx∗T0.By Lemma 10, M(x∗) is nonsingular. Therefore, there exists d¯ such that {dk0}K→d¯ and (d¯,λ∗) is the unique solution of the following linear system:(67)Mx∗dλ=∇fx∗0.From Lemma 13, λk-1=0 for every k∈K0, and(68)dkj-1K0⟶0,j=0,1,2,3,where dkj-1=-Hk-1gnk-1+lk-1(xk-1).
So we get, ask→∞ and k∈K0,(69)xk=xk-1+tkdk2-1+tk2dk3-1-dk2-1⟶x¯∗=x∗.It follows from Lemma 13 that ∇f(x∗)=∇f(x∗¯)=0. Therefore, we have that d¯=0, λ∗=0, and the proof is complete.Lemma 19.
Assume that conditions (i)–(iii) in Lemma18 hold. If I(nk-2,k-1,εk-1)≠∅ for every k∈K0, then (x∗,λ∗) is a KKT pair of problem (1a), (1b), (1c), and (1d).Proof.
Without loss of generality, we suppose thatIK≔I(nk-1,k,εk) and IK0≔I(nk-2,k-1,εk-1) keep changeless. In a way similar to Lemma 15, we have(70)x∗=x¯∗,I0+x¯∗⊂IK⊂I0x∗.Let π∗=(λi∗∣i∈IK) and π¯∗ denote a vector with the following components:(71)π¯i∗=λ¯i∗,i∈I0+x∗,0,i∈IK∖I0+x∗.Since (x∗,λ¯∗) is a KKT pair of (1a), (1b), (1c), and (1d), we have from (70) that 0π¯∗ is the solution of the following linear system:(72)Mx∗dλ=∇fx∗0.On the other hand, since {(xk,λk)}K→(x∗,λ∗), there exists d∗ such that {dk0}K→d∗. From Assumption 2, M(x∗) is nonsingular. Therefore, (d∗,λ∗) is unique solution of the linear system (72). So we have that π∗=π¯∗. So λ∗=λ¯∗, and the proof is complete.From Lemmas13–19, we have the following.Theorem 20.
If{(xk,λk)}K→(x∗,λ∗), then (x∗,λ∗) is a KKT pair of problem (1a), (1b), (1c), and (1d).


## 4. Rate of Convergence

In this section, we will establish the superlinear convergence of Algorithm3. We suppose that the algorithm generates an infinite iterative sequence {xk} and there exists k0 such that I(nk-1,k,εk)≠∅ with k>k0. That is, (S2.1)–(S2.4) will never be run when k>k0 and the inner iterations (S2.5)–(S2.8) terminate finitely. Let τ∗=(x∗,λ∗) be an accumulation point of the sequence {(xk,λk)} generated by Algorithm 3. We assume that ∇2f, ∇2ci, i∈I are locally Lipschitz continuous on a neighborhood of x∗. To ensure the whole sequence {(xk,λk)} converges to (x∗,λ∗), we need the following assumption.Assumption 21.
The second-order sufficient condition holds atτ∗; that is, the Hessian ∇xxL(x∗,λ∗) is positive definite on the space {α∣〈∇ci(x∗),α〉=0, ∀i∈I0(x∗)}.We first introduce a useful proposition as follows.Proposition 22 (see [25, Proposition  4.1]).
Assume thatω∗∈Rt is an isolated accumulation point of a sequence {ωk}⊂Rt such that for every subsequence {ωk}K converges to ω∗; there is an infinite subset K¯⊂K such that {ωk+1-ωk}K¯→0; then the whole sequence {ωk} converges to ω∗.Lemma 23.
If{xk}K→x∗, then {dk0}K→0.Proof.
Assume to the contrary that there exists subsetK¯⊂K such that {dk0}K¯→d¯≠0. By the finiteness of set I and boundedness of sequence {λk}, there exists subset K0⊂K¯ such that {λk}K0→λ∗ and I(nk-1,k,εk), k∈K0 keep changeless. It is not difficult to see from linear system (18) that(73)ρx∗,λ∗=H∗d¯≠0.On the other hand, from Theorem 20, (x∗,λ∗) is a KKT pair of problem (1a), (1b), (1c), and (1d); it follows that ρ(x∗,λ∗)=0, which contradicts with (73). So we have that {dk0}K→0.Lemma 24.
If{xk}K→x∗, then {λk}K→λ∗.Proof.
Since multiplierλ∗ is unique with respect to x∗ and {λk} is bounded, it follows from Theorem 20 that {λk}K→λ∗.Lemma 25.
If{(xk,λk)}K→(x∗,λ∗), then {(xk-1,λk-1)}K→(x∗,λ∗).Proof.
Suppose that(x¯∗,λ¯∗) is a arbitrary accumulation point of {(xk-1,λk-1)}K. Then, from Theorem 20(74)ψnk-1xk-1,λk-1K0⟶ρx¯∗,λ¯∗=0,K0⊂K.In a way similar to the proof of Lemmas 18 and 19, we get that x∗=x¯∗, λ∗=λ¯∗. From the boundedness of {(xk-1,λk-1)}K, the result follows.Lemma 26.
If{xk}K→x∗, then {dkj}K→0, j=0,1,2,3.Proof.
By Lemma25, I(nk-1,k,εk)⊂I0(x∗). From Lemma 23, the result follows.Lemma 27.
Under Assumptions1, 2, 4, and 21, the whole sequence {(xk,λk)} converges to (x∗,λ∗).Proof.
Suppose that{xk}K→x∗. Assumptions 2 and 21 imply that x∗ is an isolated accumulation point of {xk} [30]. By (S.3) in Algorithm 3, dk3-dk2≤dk2. It follows from Lemma 23 that (75)xk+1-xk≤dk2+dk3-dk2≤2dk2⟶0.Therefore, we have from Proposition 22 that the whole sequence {xk} converges to x∗. By Lemma 24, we have that λk converges to λ∗. This completes the proof.Assumption 28.
The strict complementarity condition holds atτ∗; that is, λ∗-c(x∗)≠0.Lemma 29.
LetI0+(x∗)={i∈I∣λi∗>0}; then for all sufficiently big k(76)I0+x∗=Ink-1+lk,k,εk=I0x∗.Proof.
By Theorem20 and Lemma 27, it is easy to see that (77)ψnk-1xk-1,λk1-1⟶ρx¯∗,λ¯∗=0.In a way similar to the proof of (70) in Theorem 20, we have the following result:(78)I0+x∗⊂Ink-1+lk,k,εk⊂I0x∗.By Assumption 28, the result follows.By Lemmas23, 27, and 29, we can directly obtain the following corollary.Corollary 30.
If Assumptions1, 2, 4, and 21 hold, then for every i=0,1,2,3(79)dki⟶0,λki⟶λ∗ask⟶∞.By linear systems (18), (19), and (21), we have (80)Mnk-1,kdk2-dk1λk2-λk1=0ρke,Mnk-1,kdk3-dk2λk3-λk2=0ωk-μk.Combining with the fact that ρk=o(dk12) and ωk-μk=O(dk22), we have the following.Lemma 31.
For sufficiently largek, the following results hold.(81)dk2-dk1=odk12,λk2-λk1=odk12,dk3-dk2=Odk22,λk3-λk2=Odk22.Assumption 32.
The sequence of matrices{Hk} satisfies (82)PkHk-∇xx2Lx∗,λ∗dk2dk2⟶0,where Pk=E-Nk(NkTNk)-1NkT, Nk=∇cI0(x∗)(xk).Note. Assumption 32 is an extended Dennis-Moré condition. It is used in Qp-free algorithm for nonlinear optimization problems by Yang et al. [27]. We will show that it is a sufficient condition for our algorithm to be superlinearly convergent. In order to show the superlinear convergence, we first introduce the following proposition.Proposition 33 (see [27, Lemma  4.3]).
For sufficiently largek, the direction dk2 can be decomposed into(83)dk2=Pkdk2+d~k2,with d~k2=O(cI0(x∗)(xk))+o(dk12).Lemma 34.
For sufficiently largek, if I(nk-1,k,εk)≠∅, then the step tk=1 is accepted.Proof.
Fori∉I0(x∗), due to ci(x∗)<0, it is not difficult to see from Corollary 30 that when k is sufficiently large, ci(xk+dk3)<0. For i∈I0(x∗), we have from linear system (21) and Lemma 31 that(84)cixk+dk3=cixk+dk2+∇cixk+dk2Tdk3-dk2+Odk3-dk22=cixk+dk2+∇cixk+dk2Tdk3-dk2+Odk23=-dk2η+Odk23=odk22.
It follows fromη∈(2,3) that, for sufficiently large k, ci(xk+dk3)<0. So when k is sufficiently large, xk+dk3 is a strictly feasible point of problem (1a), (1b), (1c), and (1d). By (21) and (81), we have (85)cixk+dk3=cixk+∇cixkTdk3+12dk3T∇2cixkdk3+odk22=∇cixkTdk3-dk2+∇cixkTdk2-dk1+12dk3T∇2cixkdk3+odk22=∇cixkTdk3-dk2+12dk2T∇2cixkdk2+odk22.Combining with (84), we have(86)∇cixkTdk3-dk2+12dk2T∇2cixkdk2=odk22.It follows that for sufficiently large k(87)∇fxkTdk3-dk2=∇fxk-gn¯kxkTdk3-dk2+gn¯kxkTdk3-dk2=-dk2THkdk3-dk2-∑i∈I0x∗λik2∇cixkTdk3-dk2+odk22=12∑i∈I0x∗λik2dk2T∇2cixkdk2+odk22.
From Proposition33 and Assumption 32, we have that(88)12dk2THk-∇2fxk+∑i∈I0x∗λik2∇2cixkdk2=12dk2THk-∇xx2Lxk,λk2dk2=12dk2TPkHk-∇xx2Lxk,λk2dk2+12dk2THk-∇xx2Lxk,λk2d~k2=12dk2TPkHk-∇xx2Lx∗,λ∗dk2+ocI0x∗xk+odk22=ocI0x∗xk+odk22.From linear system (19), for sufficiently large k,(89)∇fxkTdk2=fxkTdk2-gn¯kxkTdk2+gn¯kxkTdk2≤gn¯kxkTdk2+2Clog⁡n¯km-1n¯k≤12gn¯kxkTdk2+12-dk2THkdk2+∑i∈I0x∗λik2cixk+12αk+odk22.Since λik2→λi∗>0 for all i∈I0(x∗), we have, for sufficiently large k,(90)12∑i∈I0x∗λik2cixk+ocI0x∗xk<0.By (87), (88), and (89), we get(91)fn¯kxk+dk3-fn¯kxk=fn¯kxk+dk3-fxk+dk3+fxk-fn¯kxk+fxk+dk3-fxk≤∇fxkTdk3+12dk2T∇2fxkdk2+odk22+2Clog⁡n¯km-1n¯k≤∇fxkTdk2+∇fxkTdk3-dk2+12dk2T∇2fxkdk2+odk22+12αk=∇fxkTdk2+12∑i∈I0x∗λik2dk2T∇2cixkdk2+12dk2T∇2fxkdk2+odk22+12αk≤12gn¯kxkTdk2+12∑i∈I0x∗λik2cixk+ocI0x∗xk+odk22+αk≤ugn¯kxkTdk2+u-12dk2THkdk2-∑i∈I0x∗λik2cixk+odk22+αk≤ugn¯kxkTdk2+u-12dk2THkdk2+odk22+αk≤ugn¯kxkTdk2+αk,which completes the proof.Theorem 35.
Under stated assumptions, we have(92)xk+1-x∗=oxk-x∗.Proof.
By the definition ofPk, we have(93)PkHkdk3=-Pkgn¯kxk=-Pk∇fxk-∇fx∗+λ∗∇cI0x∗xk-∇cI0x∗x∗-Pkgn¯kxk-∇fxk=-Pk∇xx2Lx∗,λ∗xk-x∗+oxk-x∗+odk3.It follows from (93) that(94)Pk∇xx2Lx∗,λ∗xk+dk3-x∗=-PkHk-∇xx2Lx∗,λ∗dk3+oxk-x∗+odk3.Since cI0(x∗)(x∗)=0, it is clear from linear system (21) that(95)∇cI0x∗xkTdk3=-cI0x∗xk+odk3=-∇cI0x∗xkTxk-x∗+oxk-x∗+odk3.Let Gk≔Pk∇xx2Lx∗,λ∗∇cI0x∗xk and Bk≔-PkHk-∇xx2Lx∗,λ∗dk30.
From (94) and (95), we have(96)Gkxk+dk3-x∗=Bk+oxk-x∗+odk3.From Assumption 21, it is not difficult to see that when k is sufficiently large, Gk have full column rank. It follows from (96) and Assumption 32 that (97)xk+dk3-x∗=oxk-x∗+odk3,which implies that (98)xk+dk3-x∗=oxk-x∗.This completes the proof.In sequel, we consider the following case: the KKT pointx∗ of problem (1a), (1b), (1c), and (1d) is an unconstrained stationary with multiplier vector λ∗=0. It is clear that ∇f(x∗)=0 and also I0(x∗)=∅ in this case. Therefore, we have form the construction of Algorithm 3 that, for sufficiently large k, I(nk-1,k,εk)=∅. In order to show the superlinear convergence under this case. we firstly give two well-known propositions.Proposition 36.
Assume thatf(x) is twice continuously differentiable and ∇2f(x) is Lipschitz continuous on open convex subset D of F. Then, for arbitrary x,u,v∈D, we have (99)∇fu-∇fv-∇2fxu-v≤γ2u-x+v-xu-v,where γ is a Lipschitz constant.Proposition 37.
Assume thatf(x) and ∇2f(x) satisfy the conditions in Proposition 36. If ∇2f(x) is symmetric positive definite, then there exist ε>0, β>α>0 such that when max⁡{u-x,v-x}≤ε with u,v∈D(100)αu-x≤∇fu-∇fv≤u-v.In order to obtain the superlinear convergence of problem (1a), (1b), (1c), and (1d) under the condition I0(x∗)=∅, we give the following assumption.Assumption 38.
The sequence of matrices{Hk} satisfies (101)Hk-∇xx2Lx∗,λ∗dk2dk2⟶0.Lemma 39.
IfI0(x∗)=∅, then the step tk=1 is accepted for sufficiently large k.Proof.
SinceI0(x∗)=∅, ci(x∗)≠0, ∀i∈I. It follows from dk2→0 that, for sufficiently large k, ci(xk+dk2)≠0, ∀i∈I. That is, xk+dk2 is strictly feasible. To the end, we show that inequality (23) also holds when tk=1. By (5), (6), and gn¯k(xK)=-Hkdk2, we have, for sufficiently large k,(102)fn¯kxk+dk2-fn¯kxk=fxk+dk2-fxk+fn¯kxk+dk2-fxk+dk2+fxk-fn¯kxk≤∇fxkTdk2+12dk2T∇2fxkdk2+12αk+odk2=gn¯kxkTdk2+∇fxk-gn¯kxkTdk2+12dk2T∇2fxkdk2+12αk+odk2≤-12dk2THkdk2+12dk2T∇2fxk-Hkdk2+αk+odk2≤-12dk2THkdk2+αk+odk2≤-udk2THkdk2+αk=ugn¯kxkTdk2+αk,which completes the proof.Theorem 40.
Assume thatI0(x∗)=∅. If f(x) and ∇2f(x) satisfy the conditions in Propositions 36 and 37, then(103)xk+1-x∗=oxk-x∗.Proof.
Sincegn¯k(xk)=-Hkdk2, we have(104)Hk-∇2fx∗xk+1-xk=-gn¯kxk-∇2fx∗xk+1-xk=∇fxk-gn¯kxk+∇fxk+1-∇fxk-∇2fx∗xk+1-xk-∇fxk+1.It follows from Proposition 36 that(105)∇fxk+1xk+1-xk≤Hk-∇2fx∗xk+1-xkxk+1-xk+∇fxk+1-∇fxk-∇2fx∗xk+1-x∗xk+1-xk+∇fxk-gn¯kxkxk+1-xk≤Hk-∇2fx∗xk+1-xkxk+1-xk+∇fxk-gn¯kxkxk+1-xk+12xk-x∗+xk+1-x∗.By inequality (6), we have(106)∇fxk-gn¯kxkxk+1-xk≤1dk2·Clog⁡n¯km-1n¯kδ1·1n¯kδ2≤M·Clog⁡n¯km-1n¯kδ1⟶0.Hence, from (105) and (106), we have (107)∇fxk+1dk2⟶0ask⟶∞.By ∇f(x∗)=0 and Proposition 37,(108)∇fxk+1=∇fxk+1-∇fx∗≥βxk+1-x∗⟶0.So, we have(109)∇fxk+1dk2≥βxk+1-x∗xk+1-x∗+xk-x∗⟶0,which implies that (110)xk+1-x∗xk-x∗⟶0.This completes the proof.


## 5. Conclusion

In this paper, by quasi-Monte-Carlo-based approximations of the objective function and its first derivative, we have proposed a feasible sequential system of linear equations method for two-stage stochastic quadratic programming problem with inequality constraint. A new technique to update the “working set” is suggested. The feature of the new technique is that, in order to update the “working set,” at each iteration we directly make use of the solutionλk0 of linear system (16), while we do not calculate the inverse of matrix M-1(x) [27]. Moreover, it also does not need to approximate the Hessian by Monte Carlo (or quasi-Monte-Carlo) rule. Therefore, our algorithm saves the computational cost. The other remarkable feature of this technique is that it can accurately identify active constraints of problem (1a), (1b), (1c), and (1d). It should be pointed out that the technique also is useful for deterministic nonlinear programming problem with inequality constraints. We have shown that the sequence generated by the proposed algorithm converges to a KKT point of the problem globally. In particular the convergence rate is locally superlinear under some additional conditions. To get the superlinear convergence of the algorithm, we still need the strict complementarity assumption. However, we believe that, by using quasi-Monte-Carlo-based approximations and the new identification technique, it is possible to find a new algorithm without strict complementarity assumption. Moreover, how to use parallel optimization techniques [31–33] for the large scale stochastic programs with recourse is an important topic for further research.



---

*Source: 1564642-2017-08-24.xml*