ITERATIVE METHODS FOR VI AND NC PROBLEMSThis set of slides is about a broad class of methods for numericallysolving variational inequality (VI) and nonlinear complementarity (NC)problems.A very good survey of this area is available in a paper by J.S. Pangand D. Chan, “Iterative methods for variational and complementarityproblems,” Mathematical Programming 24 (1982), 284–313 which isused extensively in this set of slides.Another valuable article is by P.T. Harker and J.S. Pang, “Finite-dimensional variational inequality and nonlinear complementarity prob-lems: A survey of theory, algorithms and applications,” MathematicalProgramming 48 (1990), 161–220.For this discussion, we let K be a closed convex subset of Rnand letf : Rn→ Rnbe given.The variational inequality problem VI(K, f)Find x∗∈ K such that(y − x∗)Tf(x∗) ≥ 0 for all y ∈ K.The nonlinear complementarity problem NC(Rn+,f)Find x ∈ Rnsuch thatx ≥ 0,f(x) ≥ 0, and xTf(x)=0.As we know, these two problems have the same solution set whenK = Rn+.Ordinarily, we will assume that f is at least a differentiable mapping.A general approximation algorithmGiven xk∈ K, let xk+1∈ SOL VI(K, fk) where fkis an approxima-tion to f at xk.When fk(x)=f(xk)+A(xk)(x − xk) and A(xk) ∈ Rn×n, we havea linear approximation method.In the above, f is replaced by an affine transformation, fk.Otherwise, we have a nonlinear approximation method.These terms say nothing about how the approximating problem is tobe solved.Families of linear approximation methods(i) Newton’s method. In this case, A(xk)=∇f(xk), the Jacobianof f at xk.(ii) Quasi-Newton method. In this case, A(xk) is an approximationto the true Jacobian.(iii) Successive overrelaxation (SOR) where eitherA(xk)=L(xk)+D(xk)/ωorA(xk)=U(xk)+D(xk)/ωand 0 <ω<2 is the overrelaxation parameter. The matricesL(xk) and U(xk) are triangular whereas D(xk) is diagonal. Theyare all based on ∇F (xk). When ω =1, we obtain the Gauss-Seidel method.(iv) Linearized Jacobi method. Here A(xk)=D(xk), a diagonal ma-trix.(v) Projection methods. In this case, A(xk)=G for all k where Gis a fixed symmetric positive definite matrix.Approaches to proving convergence of the iterates(i) The symmetry approach. This depends on f being the gradient ofa smooth function, g. When this is the case, the VI (K, f) can beviewed as the optimality conditions of the optimization problemminimize g(x)subject to x ∈ KThe values g(xk) can be used to measure progress. What is reallyneeded here is for g to be twice continuously differentiable. Thispertains to the integrability issue.(ii) The norm contraction approach.(iii) The vector contraction approach.(iv) The monotone approach.In these different approaches, there is a distinction between local andglobal convergence results.Norm contraction: Local resultsPreliminariesLet G ∈ Rn×nbe a symmetric, positive definite matrix.If x ∈ Rn, the G-norm of x is kxkG:= (xTGx)1/2.The induced G-norm of B ∈ Rn×niskBkG:= maxkxkG=1kBxkG.When G = I, the G-norm k·kGis the Euclidean norm k·k2.kBk2= ρ(BTB)1/2where ρ(·) is the spectral radius.When B = BT, kBk2= ρ(B) and kxkG= kG1/2xk2where G1/2isany nonsingular matrix such thatG =(G1/2)T(G1/2).G1/2can be taken to be a Cholesky factor of G.For any symmetric positive definite matrix G,kG−1k2= ρ(G−1)=1αwhereα = minkyk2=1yTGy.Note that under these circumstances, the eigenvalues of G are realand positive. Writing them asλ1≥ λ2≥···≥λnwe haveλ1= maxkyk2=1yTGy and λn= minkyk2=1yTGy.If G ∈ Rn×n, its symmetric part is the matrix˜G =12(G + GT). RecallthatyTGy ≡ yT˜Gy for all y.An important connectionAgain we assume K is a nonempty closed convex subset of Rnand f :Rn→ Rn. We are interested in a solution to the problem VI(K, f).Let G ∈ Rn×nbe a symmetric positive definite matrix, and let k·kGdenote the corresponding G-norm on Rn: that is, kxkG=(xTGx)1/2.This can be used to define the G-projection of y ∈ Rnonto K:prG,K(y) = arg minx∈Kky − xkG.Proposition. Let K, f, and G be as above. Then x∗solves VI(K, f)if and only ifx∗=prG,Kx∗− G−1f(x∗),that is, if and only if x∗is a fixed point of the mapping H : Rn→ Rngiven byH(x)=prG,Kx − G−1f(x).Since H(x)=x if and only if H(x)−x =0, the variational inequalityproblem is equivalent to solving this special set of equations.Local convergence of the norm contraction algorithmIn the following, we assume that VI(K, f) has a solution.Theorem. Let K be a nonempty closed convex set. Let f : Rn→ Rnbe continuous, and let A : Rn→ Rn×nbe continuous. Suppose x∗solves VI(K, f). If there exists a positive definite matrix G and ascalar b ∈ (0, 1) such that A(x∗) − G is positive semidefinite and forall x, y ∈ N1(a neighborhood of x∗)k˜G−1(f(x) − f(y) − A(y)(x − y)) k˜G≤ bkx − yk˜G, (1)then provided x0is chosen in a suitable neighborhood of x∗, thesequence given by the linear approximation method is well definedand converges to the solution x∗.Proof. Since A(x∗)−G is positive semidefinite, it follows that A(x∗)is positive definite. Since A is continuous, there exists a neighborhoodN2of x∗such that A(y) is positive definite for all y ∈ N2. For suchy, definefy(x)=f(y)+A(y)(x − y).By a theorem of Stampacchia, VI(K, fy) has a unique solution. SinceG is p ositive definite, its symmetric part˜G is also positive definite. Itfollows that the norm in (1) is well defined.Now choose ε>0 so that 0 <r<b/(1 − ε) < 1. [This just amountsto choosing 0 <ε<1 − b which is clearly possible.] Now define aneighborhood N3of x∗such thatk(˜G−1/2)T(A(x∗) − A(y))˜G−1/2k2≤ ε.It is not restrictive to assume that the neighborhoods N1,N2,N3areall defined with respect to the˜G norm. Let N = N1∩ N2∩ N3.Choose iterate x0∈ N. Then x1is well defined and is actually theunique solution of VI(K, f0). This and the fact that x∗∈ K imply(x∗− x1)Tf(x0)+A(x0)(x1− x0)≥ 0. (2)Since x∗solves VI(K, f) and x1∈ K, we have(x1− x∗)Tf(x∗) ≥ 0. (3)In (2), we can write the factor x1− x0as x1− x∗+ x∗− x0. Then byfirst adding the inequalities (2) and (3) and then rearranging terms,we obtain(x1−x∗)TA(x0)(x1−x∗) ≤ (x1−x∗)Tf(x∗) − f(x0) − A(x0)(x∗− x0).(4)We can write A(x0)=A(x∗)+(A(x0) − A(x∗)) so that(x1− x∗)TA(x0)(x1− x∗)=(x1− x∗)TA(x∗)(x1− x∗)+(x1− x∗)T(A(x0) − A(∗))(x1− x∗) ≥(x1− x∗)T˜G(x1−