Solving box constrained variational inequalities by using the natural residual with D-gap function globalization.

*(English)*Zbl 0941.90070Summary: We present a new method for the solution of the Box constrained Variational Inequality Problem (BVIP). Basically, this method is a nonsmooth Newton method applied to a reformulation of BVIP as a system of nonsmooth equations involving the natural residual. The method is globalized by using the D-gap function. We show that the proposed algorithm is globally and fast locally convergent. Moreover, if the problem is described by an affine function, the algorithm has a finite termination property. Numerical results for some large-scale variational inequality problems are reported.

##### MSC:

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

90C53 | Methods of quasi-Newton type |

65K10 | Numerical optimization and variational techniques |

##### Keywords:

variational inequality problem; mixed complementarity problem; natural residual; D-gap function; Newton’s method; global convergence; quadratic convergence; finite termination
PDF
BibTeX
Cite

\textit{C. Kanzow} and \textit{M. Fukushima}, Oper. Res. Lett. 23, No. 1--2, 45--51 (1998; Zbl 0941.90070)

Full Text:
DOI

##### References:

[1] | Calamai, P.H.; Moré, J.J., Projected gradient methods for linearly constrained problems, Math. programming, 39, 93-116, (1987) · Zbl 0634.90064 |

[2] | T. De Luca, F. Facchinei, C. Kanzow, A theoretical and numerical comparison of some semismooth algorithms for complementarity problems, Mathematical Programming Technical Report 97-15, Computer Sciences Department, University of Wisconsin, Madison, WI, December 1997. · Zbl 0964.90046 |

[3] | Dirkse, S.P.; Ferris, M.C., The PATH solver: a non-monotone stabilization scheme for mixed complementarity problems, Optim. methods software, 5, 123-156, (1995) |

[4] | Dirkse, S.P.; Ferris, M.C., MCPLIB: a collection of nonlinear mixed complementarity problems, Optim. methods software, 5, 319-345, (1995) |

[5] | Fischer, A., Solution of monotone complementarity problems with locally Lipschitzian functions, Math. programming, 76, 513-532, (1997) · Zbl 0871.90097 |

[6] | Fischer, A.; Kanzow, C., On finite termination of an iterative method for linear complementarity problems, Math. programming, 74, 279-292, (1996) · Zbl 0855.90125 |

[7] | Fukushima, M., Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. programming, 53, 99-110, (1992) · Zbl 0756.90081 |

[8] | M. Fukushima, J.-S. Pang, Minimizing and stationary sequences of merit functions for complementarity problems and variational inequalities, in: M.C. Ferris, J.-S. Pang (Eds.), Complementarity and Variational Problems: State of the Art, SIAM, Philadelphia, PA, 1997, pp. 91-104. · Zbl 0886.90153 |

[9] | Gafni, E.M.; Bertsekas, D.P., Two-metric projection methods for constrained optimization, SIAM. J. control optim., 22, 936-964, (1984) · Zbl 0555.90086 |

[10] | Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone linesearch technique for newton’s method, SIAM J. numer. anal., 23, 707-716, (1986) · Zbl 0616.65067 |

[11] | C. Kanzow, Semismooth Newton-type Methods for the Solution of Nonlinear Complementarity Problems, Habilitation Thesis, Institute of Applied Mathematics, University of Hamburg, Hamburg, Germany, April 1997. |

[12] | C. Kanzow, M. Fukushima, Theoretical and numerical investigation of the D-gap function for box constrained variational inequalities, Math. Programming 83 (1998) 55-87. · Zbl 0920.90134 |

[13] | Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. control optim., 15, 959-972, (1977) · Zbl 0376.90081 |

[14] | Peng, J.-M., Equivalence of variational inequality problems to unconstrained optimization, Math. programming, 78, 347-356, (1997) |

[15] | J.-M. Peng, M. Fukushima, A hybrid Newton method for solving the variational inequality problem via the D-gap function, Technical Report, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan, May 1997. |

[16] | Qi, L., Convergence analysis of some algorithms for solving nonsmooth equations, Math. oper. res., 18, 227-244, (1993) · Zbl 0776.65037 |

[17] | L. Qi, Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variational inequality problems, Applied Mathematics Report 97/14, School of Mathematics, The University of New South Wales, Sydney, Australia, July 1997 (revised September 1997). |

[18] | D. Sun, M. Fukushima, L. Qi, A computable generalized Hessian of the D-gap function and Newton-type methods for variational inequality problems, in: M.C. Ferris, J.-S. Pang (Eds.), Complementarity and Variational Problems: State of the Art, SIAM, Philadelphia, PA, 1997, pp. 452-473. · Zbl 0886.90165 |

[19] | Yamashita, N.; Taji, K.; Fukushima, M., Unconstrained optimization reformulations of variational inequality problems, J. optim. theory appl., 92, 439-456, (1997) · Zbl 0879.90180 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.