A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints
This paper deals with the Variational Inequality Problem (VIP): to find \(x \in [l,u]\): such that \( (v-x)^TF(x) \geq 0 \forall v \in [l,u]\), where \(F: \mathbb{R}^n \to \mathbb{R}^n\) is a continuously differentiable function, \(lu \in \mathbb{R}^n \bigcup\{ -\infty,+\infty\} \), \(l<u\) . Reformulating (VIP) as the non-smooth equations system: \((\phi_0)_i (x)= x_i-\text{mid}(l_i,u_i,x_i-F_i (x))=0\), \(i=1 \ldots n\), and approximating the componentwise median operator \(\text{mid}(.)\) by the Gabriel-More function: \[ (p_\mu)_i (s)= \int_{-\infty}^{+\infty} \text{mid}(l_i,u_i,s- \mu t) \rho(t) dt=0, \quad i=1, \dots,\rho, \] the authors formulate a continuation algorithm on the parametrized system \(H_{\mu}(x,y)=(y-F(x) x_i -(p_ \mu)_i (x_i-y_i)\), \( i=1,\dots)\). It is considered a neighborhood of the smoothing path and the slice \(N (\beta,\mu^0)=\{z \mid \|H_{\mu}(x,y)\|\leq \beta \mu\), \(0< \mu <\mu^0 \},\) \(\beta,\mu^0 > 0\). The properties of the Gabriel-More function, the \(\mu\)-reduction strategy, and some assumptions on \(F'\) and on \( \nabla H_{\mu}(x^ky^k)\) \(\forall k\) imply the global convergence of the proposed algorithm. For the local convergence analysis it is assumed that \({ x^k,y^k }\) converges to \((\bar x, \bar y)\), the Jacobian of \(H_0(\bar x, \bar y)\) is nonsingular and a non-degeneracy assumption (\(\min \{\bar x_i -l_i,u_i-x_i +{y_i}\} \in 0\), \(\forall i=1 \dots n.\)). In addition the authors present a hybrid continuation algorithm (A2) by adding an optional Newton step to the algorithm A1. A global convergence result for A2 is proved under the assumption that \(F\) is a \(P_0\) function and that the slice \({ N}(\beta,\mu^0)\) is bounded. Conditions for this last assumption to hold are also discussed in the paper, particularly in the context of nonlinear complementarity problem. The authors prove the local quadratic convergence of A2 under the additional assumption that all the Clarke generalized Jacobian of \(H_0(\bar x, \bar y)\) are nonsingular. A2 converges finitely for affine problems. Under the assumption established for the convergence of A2 the global and quadratic local convergence of both algorithms is proved.
scientific article; zbMATH DE number 1565498