Theoretical and numerical investigation of the D-gap function for box constrained variational inequalities.

*(English)*Zbl 0920.90134Summary: The D-gap function, recently introduced by J.-M. Peng, allows a smooth unconstrained minimization reformulation of the general variational inequality problem. This paper is concerned with the D-gap function for variational inequality problems over a box or, equivalently, mixed complementarity problems. The purpose of this paper is twofold. First we investigate theoretical properties in depth of the D-gap function, such as the optimality of stationary points, bounded level sets, global error bounds and generalized Hessians. Next, we present a nonsmooth Gauss-Newton type algorithm for minimizing the D-gap function, and report extensive numerical results for the whole set of problems in the MCPLIB test problem collection.

##### MSC:

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

49J40 | Variational inequalities |

##### Keywords:

optimization reformulation; D-gap function; smooth unconstrained minimization; variational inequality; mixed complementarity; nonsmooth Gauss-Newton type algorithm##### Software:

MCPLIB
PDF
BibTeX
XML
Cite

\textit{C. Kanzow} and \textit{M. Fukushima}, Math. Program. 83, No. 1 (A), 55--87 (1998; Zbl 0920.90134)

Full Text:
DOI

##### References:

[1] | P.T. Harker, J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming 48 (1990) 161–220. · Zbl 0734.90098 |

[2] | M.C. Ferris, J.-S. Pang, Engineering and economic applications of complementarity problems, SIAM Review (to appear). · Zbl 0891.90158 |

[3] | S.P. Dirkse, M.C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems, Optimisation: Methods and Software 5 (1995) 319–345. |

[4] | S.C. Billups, S.P. Dirkse, M.C. Ferris, A comparison of algorithms for large scale mixed complementarity problems, Computational Optimization and Applications 7 (1997) 3–25. · Zbl 0883.90116 |

[5] | C. Chen, O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications 5 (1996) 97–138. · Zbl 0859.90112 |

[6] | F. Facchinei, A. Fischer, C. Kanzow, A semismooth Newton method for variational inequalities: The case of box constraints, in: M.C. Ferris, J.-S. Pang (Eds.), Complementarity and Variational Problems: State of the Art, SIAM, Philadelphia, PA, 1997, pp. 76–90. · Zbl 0886.90152 |

[7] | S.A. Gabriel, J.J. Moré, Smoothing of mixed complementarity problems, in: M.C. Ferris, J.-S. Pang (Eds.), Complementarity and Variational Problems: State of the Art, SIAM, Philadelphia, PA, 1997, pp. 105–116. · Zbl 0886.90154 |

[8] | S.P. Dirkse, M.C. Ferris, P.V. Preckel, T. Rutherford, The GAMS callable program library for variational and complementarity solvers Technical Report 94-07, Computer Sciences Department, University of Wisconsin, Madison, WI, 1994. |

[9] | M. Fukushima, Merit functions for variational inequality and complementarity problems, in: G. Di Pillo, F. Giannessi (Eds.), Nonlinear Optimization and Applications, Plenum Press, New York, 1996, pp. 155–170. · Zbl 0996.90082 |

[10] | J.-M. Peng, Equivalence of variational inequality problems to unconstrained minimization, Mathematical Programming (to appear). · Zbl 0887.90171 |

[11] | N. Yamashita, K. Taji, M. Fukushima, Unconstrained optimization reformulations of variational inequality problems, Journal of Optimization Theory and Applications 92 (1997) 439–456. · Zbl 0879.90180 |

[12] | 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 |

[13] | 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 |

[14] | A. Auslender, Optimisation: Méthodes Numériques, Masson, Paris, 1976. |

[15] | P. Marcotte, J.-P. Dussault, A note on a globally convergent Newton method for solving monotone variational inequalities. Operations Research Letters 6 (1987) 35–42. · Zbl 0623.65073 |

[16] | G. Auchmuty, Variational principles for variational inequalities, Numerical Functional Analysis and Optimization 10 (1989) 863–874. · Zbl 0678.49010 |

[17] | M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Mathematical Programming 53 (1992) 99–110. · Zbl 0756.90081 |

[18] | J.-M. Peng, Y.-X. Yuan, Unconstrained methods for generalized complementarity problems, Technical Report, Institute of Computational Mathematics and Scientific Computing, Academia Sinica, Beijing, China, 1994. · Zbl 1006.65069 |

[19] | O. L. Mangasarian, M.V. Solodov, Nonlinear complementarity as unconstrained and constrained minimization, Mathematical Programming 62 (1993) 277–297. · Zbl 0813.90117 |

[20] | N. Yamashita, M. Fukushima, On stationary points of the implicit Lagrangian for nonlinear complementarity problems, Journal of Optimization Theory and Applications 84 (1995) 653–663. · Zbl 0824.90131 |

[21] | Z.-Q. Luo, O.L. Mangasarian, J. Ren, M.V. Solodov, New error bounds for the linear complementarity problem, Mathematics of Operations Research 19 (1994) 880–892. · Zbl 0833.90113 |

[22] | C. Kanzow, Nonlinear complementarity as unconstrained optimization, Journal of Optimization Theory and Applications 88 (1996) 139–155. · Zbl 0845.90120 |

[23] | H. Jiang, Unconstrained minimization approaches to nonlinear complementarity problems, Journal of Global Optimization 9 (1996) 169–181. · Zbl 0868.90122 |

[24] | F. Facchinei, C. Kanzow, On unconstrained and constrained stationary points of the implicit Lagrangian, Journal of Optimization Theory and Applications 92 (1997) 99–115. · Zbl 0914.90249 |

[25] | J.-M. Peng, The convexity of the implicit Lagrangian, Journal of Optimization Theory and Applications 92 (1997) 331–341. · Zbl 0886.90147 |

[26] | N. Yamashita, M. Fukushima, Equivalent unconstrained minimization and global error bounds for variational inequality problems, SIAM Journal on Control and Optimization 35 (1997) 273–284. · Zbl 0873.49006 |

[27] | R. Andreani, A. Friedlander, J.M. Martínez, On the solution of finite-dimensional variational inequalities using smooth optimization with simple bounds, Technical Report, Department of Applied Mathematics, University of Campinas, Campinas, Brazil, September 1995. |

[28] | F. Facchinei, A. Fischer, C. Kanzow, Inexact Newton methods for semismooth equations with applications to variational inequality problems, in: G. Di Pillo, F. Giannessi (Eds.), Nonlinear Optimization and Applications, Plenum Press, New York, 1996, pp. 125–139. · Zbl 0980.90101 |

[29] | F. Facchinei, A. Fischer, C. Kanzow, Regularity properties of a semismooth reformulation of variational inequalities. SIAM Journal of Optimization (to appear). · Zbl 0913.90249 |

[30] | J.-S. Pang, Newton’s method for B-differentiable equations, Mathematics of Operations Research 15 (1990) 311–341. · Zbl 0716.90090 |

[31] | J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Mathematical Programming 51 (1991) 101–131. · Zbl 0733.90063 |

[32] | B. Xiao, P.T. Harker, A nonsmooth Newton method for variational inequalities, I: Theory, Mathematical Programming 65 (1994) 151–194. · Zbl 0812.65048 |

[33] | B. Xiao, P.T. Harker, A nonsmooth Newton method for variational inequalities, II: Numerical results, Mathematical Programming 65 (1994) 195–216. · Zbl 0812.65049 |

[34] | D.P. Bertsekas, J.N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ, 1989. |

[35] | L. Qi, J. Sun, A nonsmooth version of Newton’s method, Mathematical Programming 58 (1993) 353–367. · Zbl 0780.90090 |

[36] | L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Mathematics of Operations Research 18 (1993) 227–244. · Zbl 0776.65037 |

[37] | H. Jiang, L. Qi, X. Chen, D. Sun, Semismoothness and superlinear convergence in nonsmooth optimization and nonsmooth equations, in: G. Di Pillo, F. Giannessi (Eds.), Nonlinear Optimization and Applications, Plenum Press, New York, 1996, pp. 197–212. · Zbl 0991.90123 |

[38] | F. Facchinei, Minimization ofSC 1 functions and the Maratos effect, Operations Research Letters 17 (1995) 131–137. · Zbl 0843.90108 |

[39] | C. Geiger, C. Kanzow, On the resolution of monotone complementarity problems, Computational Optimization Applications 5 (1996) 155–173. · Zbl 0859.90113 |

[40] | F. Facchinei, J. Soares, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM Journal of Optimization 7 (1997) 225–247. · Zbl 0873.90096 |

[41] | A. Fischer, A special Newton-type optimization method, Optimization 24 (1992) 269–284. · Zbl 0814.65063 |

[42] | C. Kanzow, N. Yamashita, M. Fukushima, New NCP-functions and their properties, Journal of Optimization Theory and Applications (to appear). · Zbl 0886.90146 |

[43] | J.H. Wu, M. Florian, P. Marcotte, A general descent framework for the monotone variational inequality problem, Mathematical Programming 61 (1993) 281–300. · Zbl 0813.90111 |

[44] | J.E. Dennis, Jr., R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, NJ, 1983. |

[45] | H. Jiang, L. Qi, Local uniqueness and iterative methods for nonsmooth variational inequalities, Journal of Mathematical Analysis and Applications 196 (1995) 314–331. · Zbl 0845.65028 |

[46] | J.-S. Pang, L. Qi, Nonsmooth equations: Motivation and algorithms, SIAM Journal of Optimization 3 (1993) 443–465. · Zbl 0784.90082 |

[47] | F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983 (reprint by SIAM, Philadelphia, PA, 1990). · Zbl 0582.49001 |

[48] | T. De Luca, F. Facchinei, C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Mathematical Programming 75 (1996) 407–439. · Zbl 0874.90185 |

[49] | R. Barrett, M. Berry, T.F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, PA, 1994. · Zbl 0814.65030 |

[50] | L. Grippo, F. Lampariello, S. Lucidi, A nonmonotone linesearch technique for Newton’s method, SIAM Journal of Numerical Analysis 23 (1986) 707–716. · Zbl 0616.65067 |

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.