1 Introduction and preliminaries
2 Results and discussion
3 Conclusions
4 Compact convex bodies
5 Generalized analytic center cutting plane algorithms for solving pseudomonotone variational inequalities
-
Step 1. (initialization)$$k = 0, \qquad j = 1,\qquad A^{k} = A_{j},\qquad b^{k} = b_{j},\qquad C_{j}^{k} = \bigl\{ x \in \mathbb{R}^{n};A_{j}^{k}x \le b_{j}^{k} \bigr\} ; $$
-
Step 2. (computation of an approximate analytic center)Find an approximate analytic center \(x_{j}^{k}\) of \(C_{j}^{k}\);
-
Step 3. (stop criterion)Compute \(g_{X}(x_{j}^{k}) = \max_{x \in X}F(x_{j}^{k})^{T}(x_{j}^{k} - x)\),if \(g_{X}(x_{j}^{k}) = 0\), then STOP,else GO TO step 4;
-
Step 4. (find an ε-solution for \(\varepsilon = \frac{1}{2^{j}}\))Compute \(g_{C_{j}}(x_{j}^{k}) = \max_{x \in C_{j}}F(x_{j}^{k})^{T}(x_{j}^{k} - x)\),if \(g_{C_{j}}(x_{j}^{k}) < \frac{1}{2^{j}}\), then increase j by one RETURN TO Step 1,else GO TO Step 5;
-
Step 5. (cut generation)Set\(H_{j}^{k} = \{ x \in \mathbb{R}^{n};F(x_{j}^{k})^{T}(x - x_{j}^{k}) = 0\}\) is the new cutting plane for \(\mathit{VI}(F, C_{j}^{k})\).$$A_{j}^{k + 1} = \left [ \textstyle\begin{array}{l} A_{j}^{k} \\ F(x_{j}^{k})^{T} \end{array}\displaystyle \right ],\qquad b_{j}^{k + 1} = \left [ \textstyle\begin{array}{l} b_{j}^{k} \\ F(x_{j}^{k})^{T}x_{j}^{k} \end{array}\displaystyle \right ], $$Increase k by one GO TO Step 2.
-
Step 3. (stop criterion)Compute \(g_{X}(x_{j}^{k}) = \max_{x \in X}F(x_{j}^{k})^{T}(x_{j}^{k} - x)\),if \(g_{X}(x_{j}^{k}) < \varepsilon\), then STOP,else GO TO step 4.
6 Generalized analytic center cutting plane algorithms for solving quasimonotone variational inequalities
-
Step 1. (initialization)Let \(\beta_{j} > 0\) be the strong monotonicity constant for \(\Gamma_{j}(y,x):\mathbb{R}^{n} \to \mathbb{R}^{n}\), with respect to y, and let \(\alpha _{j} \in (0, \beta_{j})\).$$k = 0,\qquad j = 1,\qquad A^{k} = A_{j},\qquad b^{k} = b_{j},\qquad C_{j}^{k} = \bigl\{ x \in \mathbb{R}^{n};A_{j}^{k}x \le b_{j}^{k} \bigr\} ; $$
-
Step 2. (computation of an approximate analytic center)Find an approximate analytic center \(x_{j}^{k}\) of \(C_{j}^{k}\);
-
Step 3. (stop criterion)Compute \(g_{X}(x_{j}^{k}) = \max_{x \in X}F(x_{j}^{k})^{T}(x_{j}^{k} - x)\),if \(g_{X}(x_{j}^{k}) = 0\), then STOP,else GO TO step 4;
-
Step 4. (find an ε-solution for \(\varepsilon = \frac{1}{2^{j}}\))Compute \(g_{C_{j}}(x_{j}^{k}) = \max_{x \in C_{j}}F(x_{j}^{k})^{T}(x_{j}^{k} - x)\),if \(g_{C_{j}}(x_{j}^{k}) < \frac{1}{2^{j}}\), then increase j by one RETURN TO Step 1,else GO TO Step 5;
-
Step 5. (auxiliary variational inequality)Let \(w_{j}(x_{j}^{k})\) satisfy the variational inequalityLet$$\bigl\langle F\bigl(x_{j}^{k}\bigr) + \Gamma_{j} \bigl(w_{j}\bigl(x_{j}^{k}\bigr),x_{j}^{k} \bigr) - \Gamma_{j}\bigl(x_{j}^{k},x_{j}^{k} \bigr),y - w_{j}\bigl(x_{j}^{k}\bigr) \bigr\rangle \ge 0,\quad\forall y \in C_{j}. $$where \(l(k, j)\) is the smallest integer which satisfies$$y_{j}^{k} = x_{j}^{k} + \rho_{j}^{l(k,j)}\bigl(w_{j}\bigl(x_{j}^{k} \bigr) - x_{j}^{k}\bigr) \quad \mbox{and}\quad G_{j} \bigl(x_{j}^{k}\bigr) = F\bigl(y_{j}^{k} \bigr), $$$$\bigl\langle F\bigl(x_{j}^{k} + \rho_{j}^{l(k,j)} \bigl(w_{j}\bigl(x_{j}^{k}\bigr) - x_{j}^{k}\bigr)\bigr),x_{j}^{k} - w_{j}\bigl(x_{j}^{k}\bigr) \bigr\rangle \ge \alpha_{j}\big\| w_{j}\bigl(x_{j}^{k}\bigr) - x_{j}^{k}\big\| ^{2}; $$
-
Step 6. (cutting plane generation)Set\(H_{j}^{k} = \{ x \in \mathbb{R}^{n};G(x_{j}^{k})^{T}(x - x_{j}^{k}) = 0\}\) is the new cutting plane for \(\mathit{VI}(F, C_{j}^{k})\).$$A_{j}^{k + 1} = \left [ \textstyle\begin{array}{l} A_{j}^{k} \\ G(x_{j}^{k})^{T} \end{array}\displaystyle \right ],\qquad b_{j}^{k + 1} = \left [ \textstyle\begin{array}{l} b_{j}^{k} \\ G(x_{j}^{k})^{T}x_{j}^{k} \end{array}\displaystyle \right ], $$Increase k by one GO TO Step 2.
-
Step 3. (stop criterion)Compute \(g_{X}(x_{j}^{k}) = \max_{x \in X}F(x_{j}^{k})^{T}(x_{j}^{k} - x)\),if \(g_{X}(x_{j}^{k}) < \varepsilon\), then STOP,else GO TO step 4.
7 Generalized analytic center cutting plane algorithms for variational inequalities with unbounded domains
-
Step 1. (initialization)$$k = 0,\qquad j = 1,\qquad A^{k} = A_{j},\qquad b^{k} = b_{j},\qquad C_{j}^{k} = \bigl\{ x \in \mathbb{R}^{n};A_{j}^{k}x \le b_{j}^{k} \bigr\} ; $$
-
Step 2. (find an ε-solution for \(\varepsilon = \frac{1}{2^{j}}\))Find an approximate analytic center \(x_{j}^{k}\) of \(C_{j}^{k}\).Compute \(g_{C_{j}}(x_{j}^{k}) = \max_{x \in C_{j}}F(x_{j}^{k})^{T}(x_{j}^{k} - x)\),if \(g_{C_{j}}(x_{j}^{k}) < \frac{1}{2^{j}}\), then increase j by one RETURN TO Step 1,else GO TO Step 3;
-
Step 3. (cut generation)Set\(H_{j}^{k} = \{ x \in \mathbb{R}^{n};F(x_{j}^{k})^{T}(x - x_{j}^{k}) = 0\}\) is the new cutting plane for \(\mathit{VI}(F, C_{j}^{k})\).$$A_{j}^{k + 1} = \left [ \textstyle\begin{array}{l} A_{j}^{k} \\ F(x_{j}^{k})^{T} \end{array}\displaystyle \right ],\qquad b_{j}^{k + 1} = \left [ \textstyle\begin{array}{l} b_{j}^{k} \\ F(x_{j}^{k})^{T}x_{j}^{k} \end{array}\displaystyle \right ], $$Increase k by one GO TO Step 2.