We study Newton's method and method based on linearization for solving quasi-variational inequalities in a finite-dimensional real vector space. Projection methods were the most studied methods for solving quasi-variational inequalities and they have linear rates of the convergence. In the paper we establish sufficient conditions for the convergence of Newton's method and method of linearization, derive an estimates of the rate of their convergence.
and Lipschitz continuous if
The paper is organized as follows. In the second section, we introduce the problem of quasi-variational inequality and recall the main known results that will be used in the next sections. In the third section, we present a first-order iterative method based on exterior linearization for solving quasi-variational inequalities. Some other methods based on linearization for minimiziation problems were described in [Antipin et al., 1994, Ciric, 1987]. For now, we do not know that somebody discussed linearized method for solving quasi-variational inequality. In the first part of this section we formulate sufficient conditions for the convergence. In the next theorem we give the estimate of the rate of convergence of the proposed method. The last section contains the Newton’s method for solving quasi-variational inequalities in the case of the moving set. 2
In this paper we denote by E a finite-dimensional real vector space. The operator F : E monotone if → E is strongly ⟨F (u) − F (v); u − v⟩ ≥
∥u − v∥2; ∀u; v ∈ E; ∥F (u) − F (v)∥ ≤ L∥u − v∥; ∀u; v ∈ E: The constant ≥ 0 is a parameter of strong monotonicity of operator F , and L is a parameter of Lipschitz continuity. If = 0, then F is a monotone operator. From the definitions (1) and (2), it is clear that ≤ L.
The problem of our interest is the following quasi-variational inequality: find x∗ ∈ C(x∗) for which ⟨F (x∗); y − x∗⟩ ≥ 0; ∀y ∈ C(x∗); where C : E 7→ 2E is a set valued mapping with non-empty closed convex values C(x) ⊆ E for all x in E.
If C(x) = C then quasi-variational inequality (3) becomes a conventional variational inequality. It is well known that if F (x) = f ′(x) is a potential operator, then this variational inequality can be interpreted as a necessary condition of optimality in the problem of minimizing the function f on the set C.
In the study of convergence of our methods, we will also use the following theorem: Theorem 2.1 [Vasiliev, 2002] Let be operator F : E → E strongly monotone with parameter continuous with Lipschitz constant L > 0. Then > 0 and Lipschitz ∥F (x) − F (y)∥2 +
L∥x − y∥2 ≤ (L + )⟨F (x) − F (y); x − y⟩; ∀x; y ∈ E holds.
By PC (x) we denote the Euclidean projection of point x onto the set C. The necessary and sufficient characterizations of the projection are as follows:
PC (x) ∈ C; ⟨PC (x) − x; z − PC (x)⟩ ≥ 0 ∀z ∈ C:
In what follows, we will use known fixed point reformulation of the quasi-variational inequality (3): Lemma 2.2 Let C(x) be a closed convex valued set in E, for all x ∈ E. Then x∗ ∈ C(x∗) is solution of problem (3) if and only if x∗ = PC(x )[x∗ −
F (x∗)]:
The geometric meaning of (4) is simple: a step along the F (x∗) from the point x∗ after the projection again reaches the point x∗. The discrepancy C(x)(x − F (x)) − x can be regarded as a transformation of space E into E. This transformation defines a vector field. Formally, the problem can be described by where initial point x0 ∈ E is given, k; k ≥ 0 is parameter of the method.
Computational experience has shown that application of the projection is justified if C(x) is a simple set. But, if the admissible set has a complicated structure, projection becomes too complex operation, in which case it is better to approximate the set C(x) by family of simpler sets. It seems natural to take approximating families of the admissible set as the family of polygons for an exterior approximation. (1) (2) (3) (4) (5)
The theorem of existence of solutions shows a notable difference between variational and quasi-variational inequalities. For example, if F is strongly monotone and Lipschitz continuous on a closed and convex set, then the variational inequality has a unique solution. On the other hand, the following statement is the first result related to the existence of solutions of quasi-variational inequalities (3): Theorem 2.3 [Noor et al.,1994] If the map F is Lipschitz continuous and strongly monotone on E with constants L and > 0, respectively, and C is a set-valued mapping with nonempty closed and convex values such that ∥PC(x)(z) − PC(y)(z)∥ ≤ l∥x − y∥; l + √1 − 2=L2 < 1; ∀ x; y; z ∈ E: then the problem (3) has a unique solution.
Nesterov and Scrimali [Nesterov et al, 2011] proved that in (6) is sufficient to require l < L . Now we mention that assumption (6) is a kind of strengthening of the contraction property for multifunction C(x). An example of such a mapping is given in the following lemma: Theorem 2.4 [Nesterov et al, 2011] Let function c : E → E be Lipschitz continuous with Lipschitz constant l and set C0 be a closed convex set. Then satisfies (6) with the same value of l.
C(x) := c(x) + C0 This case of quasi-variational inequalities is most often discussed in the literature and it is known as the moving set. In the last section we will consider Newton’s method for solving quasi-variational inequalities in the case of moving set. 3
Let X ⊂ E be defined by
X = {x ∈ E : x ∈ C(x)} = {x ∈ E : gi(x; x) ≤ 0; i = 1; 2; : : : ; m}: This set is called the feasible set of quasi-variational inequality (3). Let us suppose that solution set of quasivariational inequality (3) is non-empty
X∗ = {x∗ ∈ X : ⟨F (x∗); y − x∗⟩ ≥ 0; ∀y ∈ C(x∗)} ̸= ∅: In the theorems 2.3 and 2.4 are given sufficient conditions for X∗ ̸= ∅.
In the most practical settings, the set valued mapping C is defined through a parametric set of inequality constraints [Facchinei et al., 2014, Fukushima, 2007]: (6) (7) (8) (9)
C(x) = {y ∈ E : gi(x; y) ≤ 0; i = 1; : : : ; m}; where gi : E ×E → R, for all i = 1; : : : ; m. We will suppose that gi(x; ·) are convex and continuously differentiable on E, for each x ∈ E and for each i = 1; : : : ; m.
The convexity of gi(x; ·) is obviously needed in order to guarantee that C(x) be convex, while we require the differentiability assumption to be able to write down the KKT conditions of the quasi-variational inequality (3). Let us remark that a point x∗ ∈ E satisfies the KKT conditions if multipliers ∗ = ( 1∗; : : : ; ∗m) ∈ R+m exist such that ⟨ ⟩
≥ 0; ∀y ∈ E; i=1 gi(x∗m;x∗) ≤ 0; i = 1; : : : ; m ∑ i∗gi(x∗; x∗) = 0; i=1 Note that gi(x∗; x∗) ≤ 0 for each i = 1; : : : ; m, means that x∗ ∈ C(x∗). In [Facchinei et al., 2014] was proven the following theorem Theorem 3.1 Suppose that gi(x; ·) are convex and continuously differentiable on E, for each x ∈ E and for each i = 1; : : : ; m. If a point x∗, together with a suitable vector ∗ ∈ R+m of multipliers, satisfies the KKT system (9), then x∗ is a solution of the quasi-variational inequlity (3). Vice versa, if x∗ is a solution of the quasi-variational inequlity (3) and the constraints gi, i = 1; : : : ; m, satisfy the Slater’s condition, then multipliers exist such that the pair (x∗; ∗) satisfies the KKT conditions (9).
To construct sequence {xk}, we use the idea of the approximation of the given set C(x) from outside by polyhedron CL(x)
CL(x) = {y ∈ H : gi(x; x) + ⟨@2gi(x; x); y − x⟩ ≤ 0; i = 1; : : : m}: Now, (5) replace with and there exists a point x∞ ∈ X∗ such that lim inf ∥xk+1 − xk∥ = 0; k→∞ lim ∥xk − x∞∥ = 0: k→∞
Now, we consider strongly monotone operator F . In this case we suppose that quasi-variational inequality (3) has unique solution, i. e. X∗ = {x∗}: In the following theorem we give an estimate of convergence rate of the proposed method.
Theorem 3.3 Suppose that the following conditions are fulfilled:
1) Functions gi(x; ·) are convex, differentiable and satisfy the Slater’s condition, @2gi(x; x) are Lipschitz continuous with constant L, for all i = 1; : : : ; m.
2) F : E → E is Lipschitz continuous with constant L and strongly monotone operator with constant > 0. 3) Solution set X∗ = {x∗}. 4) Sequence { k} satisfies: 0 < ≤ k ≤ ¯ ∀k ≥ 0 and ¯ < min {
1 L + ;
1 2L∥ ∗∥ } :
Then where
∥xk+1 − x∗∥2 ≤ qk( ; ¯)∥x0 − x∗∥2; q( ; ¯) = 1 + 6 ¯L∥ ∗∥ + 8 ¯2 2 − 8 10 − 12 ¯L∥ ∗∥2
:
It is well known that Newton method for solving nonlinear equations and unconstrained minimization problems converges quadratically. First attempt to generalize Newton method to solve variational inequality problems was made by [Josephy, 1979]. If we turn our attention to local Newton-type methods for quasi-variational inequalities, the pioneering work was done in [Outrata et al.,1995]. In [Facchinei et al., 2015] also has been considered the application of the one variant of Newton method for some classes of quasi-variational inequalities. Here, we propose one different variant of Newton method for quasi-variational inequalities in the case of the moving set. We consider quasi-variational inequality (3) when the set valued mapping C(x) is given by (4), i.e.
C(x) := c(x) + C0; where c : E → E is Lipschitz continuous with Lipschitz constant l and set C0 is a closed convex set in E.
Algorithm 4.1. Newton method generates a sequence {xk}, where x0 is chosen in E and xk+1 is determined to be a solution of the quasi-variational inequality problem obtained by linearizing F at the current iterate xk, i.e., xk+1 − c(xk+1) ∈ C0 and ⟨F (xk) + F ′(xk)(xk+1 − xk); z − xk+1⟩ ≥ 0; (11) for all z such that z − c(xk+1) ∈ C0.
The strongly monotonicity of F ensures that the linearized problem (11) always has a unique solution z. The linearized problem (11) is usually easier to solve than the original problem (3). Algorithm 4.1 is an implicit type Newton method, which is difficult to implement. It is possible to consider other variant of this method, for example:
Algorithm 4.2. For given x0 ∈ E, find the approximate solution by solving the variational inequality obtained by linearizing F at the current iterate xk, i.e., xk+1 ∈ C(xk) and
⟨F (xk) + F ′(xk)(xk+1 − xk); z − xk+1⟩ ≥ 0; for all z ∈ C(xk).
It will be proven that, under suitable assumptions, the sequence generated by Newton method (11) quadratically converges to a solution x∗ of the original problem (3), if the starting point x0 is chosen sufficiently close to the solution x∗ of quasi-variational inequality (3).
Theorem 4.1 Suppose that the following conditions are fulfilled: 1. Operator F : E → E is strongly monotone with parameter of strong monotonicity with constant L and > 0, Lipschitz continuous ∥F ′(x)∥ ≤ L; ∀x ∈ E; 2. C0 ⊂ E is closed, convex set in a finite-dimensional real space E, function c : E → E is Lipschitz continuous with constant l < =L and multifunction C : E → 2E has a form C(x) := c(x) + C0, (x ∈ E); 3. Initial approximation x0 ∈ E satisfy q =
L(1 + l) 2( − lL) ∥x0 − x∗∥ < 1; where x∗ is a solution of quasi-variational inequality (3).
Then, sequence (xk) from (11) exists and converges to the unique solution x∗ of quasi-variational inequality (3) and the following estimate is valid ∥xk − x∗∥ ≤ 2( − lL) q2k ; k = 0; 1; : : : L(1 + l)