User:Eugene M. Izhikevich/Proposed/Variational inequality
Dr. Vincent Acary accepted the invitation on 13 September 2008 (self-imposed deadline: 13 January 2009).
General variational inequality (VI)
To Be Written see definition Stampacchia Lions
Finite-Dimensional Variational inequality (VI)
Definition and basic properties
The VI problem may be defined as follows:
Let \(X\) be a non empty subset of \( \mathbb R^n\) and let \(F\) be a mapping from \(\mathbb R^n \)into itself. The variational inequality problem, denoted by \(\mathrm{VI}(X,F)\ ,\) is to find a vector \(z\in\mathbb R^n\) such that \[ F^{T}(z) (y-z) \ge 0, \, \forall \;y \in X. \quad \quad (1) \] We denote the solution set by \(\Omega\ .\)
Usually, the set \(X\) is assumed to closed and convex. The function \(F\) is also assumed to be continuous, nevertheless some generalized VI are also defined for set-valued mappings (Harker and Pang(1990)). If \(X\) is a closed set and \(F\) continuous, the solution set of \(\mathrm{VI}(X,F)\) denoted by \(\mathrm{SOL}(X,F)\) is always a closed set.
A geometrical interpretation of the \(\mathrm{VI}(X,F)\) leads to the equivalent formulation in terms of inclusion into a normal cone of \(X\ ,\) i.e. \[ -F(x) \in N_X(x)\quad\quad (2) \] or equivalently \[ 0 \in F(x) + N_X(x)\quad\quad (3) \]
This may be deduced directly from the variational definition of a normal cone. It is noteworthy that the \(\mathrm{VI}(X,F)\) extends the problem of solving nonlinear equations of the form \(F(x)=0\ ,\) taking \(X=\mathbb R^n\) in (1). If \(F(z)=Mz +q\) is affine, the \(\mathrm{VI}(X,F)\) is called Afiine VI (AVI)and is denoted by \(\mathrm{AVI}(X,q,M)\ .\)
For \(X\) a polyhedral set , we say that the \(\mathrm{VI}(X,F)\) is linearly constrained, or is a linearly constrained VI. An important case is the box constrained VI where the set \(X\) is a closed box (possibly unbounded) of \(\mathbb R^n\ ,\) i.e. \[ K = \{x\in \mathbb R^n \;\mid\; -\infty \leq a_i \leq x \leq b_i \leq +\infty \} \]
Basic Existence and Uniqueness properties
The basic ingredients for the existence and possibly the uniqueness of solutions of VIs are (a) the degree theory and the fixed point approaches and (b) the monotonicity property. The degree theory and the fixed point approaches for VI are well presented in (Goeleven et al. (2003)). The P-property and its variants can not be applied to general VI} but some notions of F-uniqueness can be introduced. The notion of copositivity can be also a good substitute in the more general framework of VI (see Facchinei and Pang2003) for more details).
Quasi-variational Inequalities.
Let \(X\) be a multi-valued mapping \(\mathbb R^{n} \rightsquigarrow \mathbb R^{n}\) and let \(F\) be a mapping form \(\mathbb R^n\) into itself. The quasi-variational inequality problem, denoted by \(\mathrm{QVI}(X,F)\) is to find a vector \(z\in\mathbb R^n\) such that \[ F^{T}(z) (y-z) \ge 0, \, \forall y \in X(z) \]
This problem is a very hard problem from the existence and uniqueness point of view. Unfortunately, the frictional contact problem studied in the following chapter belongs to this class of problems.
For the reader interested in the theory of VI and QVI we refer to (Goeleven et al (2003), Facchinei and Pang (2003)) and the survey paper (Harker.Pang (1990)). In these works, some extensions of VIs can be also found where \(F\) is multivalued.
Links with the Complementarity Problems and Constrained Minimization Problem
The following complementarity problem over cones can be defined: Given a closed convex cone \(K\subset \mathbb R^n\) and a mapping \(F : \mathbb R^{n} \rightarrow \mathbb R^{n}\ ,\) the complementarity problem, denoted by \(\mathrm{CP}(K,F)\ ,\) is to find a vector \({z} \in \mathbb R^n\) such that \[ K \ni {z} \perp F(z) \in K^{*} \] where \(K^{*}\) is the dual (negative polar) cone of \(K\) defined by \[ K^{*} = \{d \in \mathbb R^n \mid v^T d \geq 0, \forall v \in K \} \]
We say that a vector \(x\) is feasible to the \(\mathrm{CP}(K,F)\) if\( {z} \in K \text{ and } F(z) \in K^{\star}\)
When \(K\) is the nonnegative orthant \(\mathbb R^n_+\ ,\) the CP} is a Nonlinear Complmentarity Problem (NCP). Furthermore, if \(F(z)=mx+q\) is affine, \(\mathrm{CP}(\mathbb R^n_+, F)\) is a Linear Complementarity Problem \(\mathrm{LCP}(M,q)\ .\)
Let \(X=K\subset \mathbb R^n\) be a cone. A vector \(x\) solves the \(\mathrm{VI}(X,F)\) if and only if \(x\) solves the \(\mathrm{CP}(K,F)\ .\) If \(K\) is equal to the non negative orthant of \(\mathbb R^n_+\ ,\) a vector \(x\) solves the \(\mathrm{VI}(X,F)\) if and only if \(x\) solves the \(\mathrm{NCP}(F)\ .\)
A box-constrained VI is equivalent to a MCP or a MCP} choosing the bounds \(a_i\) and \(b_i\) in the right way. If, in \(\mathrm{CP}(K,F)\ ,\) \(K\) is polyhedral and \(F\) is affine, we get an LCP.
An interesting non polyhedral example is when \( K = \{z \in \mathbb R^{n+1} \mid z_0 \geq \| (z_1, \ldots z_n) \| \} \) is the so--called second--order cone or ice--cream cone.
Let us consider for instance the following nonlinear programming NLP problem \[ \begin{array}{ll} \text{minimize} & G(z)\\ \text{subject to} & z \in K \\ \end{array} \] where \(G\) is supposed continuously differentiable. If the set \(K\) is convex, any local minimizer \(\bar z\) of (1) must satisfy the following first order optimality conditions: \[ (y-\bar z )^T \nabla G(\bar z)\geq 0, \forall y \in K \] The latter problem defines clearly \(\mathrm{VI}(K,\nabla G)\ .\) If the function \(G\) is convex, the stationary point which solves \(\mathrm{VI}(K,\nabla G)\) does solve (1) (and is unique if \(G\) is strictly convex). Therefore, under the convexity assumptions on \(G\) and \(K\ ,\) the NLP is equivalent to \(\mathrm{VI}(K,\nabla G)\ .\)
The converse relation between a general \(\mathrm{VI}(K,F)\) and the NLP can be obtained if the mapping \(F\) is a gradient map, that is if it exists a mapping \(G\) such that \(F=\nabla G\ .\) The question relies on the integrability of \(F\) which is closely related to the symmetry of the Jacobian matrix \(\nabla F^{T}\) as the following theorem shows.
Theorem Let \(F: \Omega \subset \mathbb R^n \rightarrow \mathbb R^n\) be a continuously differentiable mapping on a convex set \(\Omega\ ;\) then the following statements are equivalent:
- there exists a real-valued function \(G\) such that \(F(x)= \nabla G^{T}(x)\) on \(\Omega\ ,\)
- the Jacobian matrix, \(\nabla F^{T}(x)\) is symmetric on \(\Omega\ ,\)
- the integral of \(F\) along any closed curve in \(\Omega\) is zero.
Thanks to this condition, we see how the VI, and therefore its specializations,CP, NCP, LCP may be related to an optimization problem. We see also in the preceding sections that if the problem is more structured, as can be the case with the specializations of the VIs, it is possible to have deeper equivalences.
Merit and Gap Functions for VI
To Be Written
Links with Nonsmooth and Generalized equations
To Be Written
Main Types of Algorithms for the VI and QVI
The equation--based reformulations of VI and the merit function equivalences pave the way to four main types of algorithms:
- Projection--type and splitting methods.
- Minimization of merit functions.
- Generalized Newton Methods.
- Interior and smoothing methods.
To Be Written
References
- Harker.Pang1990
- Facchinei.Pang2003
- Goeleven.ea2003
