Abstract
The Karush-Kuhn-Tucker (KKT) system of the variational inequality problem over a set defined by inequality and equality constraints can be reformulated as a system of semismooth equations via an nonlinear complementarity problem (NCP) function. We give a sufficient condition for boundedness of the level sets of the norm function of this system of semismooth equations when the NCP function is metrically equivalent to the minimum function; and a sufficient and necessary condition when the NCP function is the minimum function. Nonsingularity properties identified by Facchinei, Fischer and Kanzow, 1998, SIAM J. Optim. 8, 850–869, for the semismooth reformulation of the variational inequality problem via the Fischer-Burmeister function, which is an irrational regular pseudo-smooth NCP function, hold for the reformulation based on other regular pseudo-smooth NCP functions. We propose a new regular pseudo-smooth NCP function, which is piecewise linear-rational and metrically equivalent to the minimum NCP function. When it is used to the generalized Newton method for solving the variational inequality problem, an auxiliary step can be added to each iteration to reduce the value of the merit function by adjusting the Lagrangian multipliers only.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
X. Chen Z. Nashed L. Qi (2000) ArticleTitleSmoothing methods and semismooth methods for nondifferentiable operator equations SIAM J. Numer. Anal. 38 1200–1216 Occurrence Handle10.1137/S0036142999356719
A.R. Conn L.N. Vicente C. Visweswariah (1999) ArticleTitleTwo-step algorithms for nonlinear optimization with structure applications SIAM J. Optim. 9 924–947 Occurrence Handle10.1137/S1052623498334396
T. Luca ParticleDe F. Facchinei C. Kanzow (1996) ArticleTitleA semismooth equation approach to the solution of nonlinear complementarity problems Math. Prog. 75 407–439 Occurrence Handle10.1016/S0025-5610(96)00028-7
T. Luca ParticleDe F. Facchinei C. Kanzow (2000) ArticleTitleA theoretical and numerical comparison of some semismooth algorithms for complementarity problems Comput. Optim. Appl. 16 173–205 Occurrence Handle10.1023/A:1008705425484
Facchinei, F., Fischer, A. and Kanzow, C. (1995). A Semismooth Newton Method for Variational Inequalities: Theoretical Results and Preliminary Numerical Results, Technical Report 102, Institute of Applied Mathematics, University of Hamburg, Hamburg, Germany.
F. Facchinei A. Fischer C. Kanzow (1996) Inexact Newton methods for semismooth equations with applications to variational inequality problems G. Pillo ParticleDi F. Giannessi (Eds) Nonlinear Optimization and Applications Plenum Press New York 125–139
F. Facchinei A. Fischer C. Kanzow (1998) ArticleTitleRegularity properties of a semismooth reformulation of variational inequalities SIAM J. Optim. 8 850–869 Occurrence Handle10.1137/S1052623496298194
F. Facchinei C. Kanzow (1997) ArticleTitleA nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems Math. Prog. 76 493–512 Occurrence Handle10.1016/S0025-5610(96)00058-5
F. Facchinei J.S. Pang (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, I-II Springer-Verlag New York
F. Facchinei J. Soares (1997) ArticleTitleA new merit function for nonlinear complementarity problems and a related algorithm SIAM J. Optim. 7 225–247 Occurrence Handle10.1137/S1052623494279110
Ferris, M.C. and Munson, T.S. (2000), Semismooth support vector machines, Data Mining Institute Technical Report 00-09, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin.
A. Fischer (1992) ArticleTitleA special Newton-type optimization method Optimization. 24 269–284
A. Fischer (1995) An NCP-function and its use for the solution of complementarity problems D Du L. Qi R. Womersley (Eds) Recent Advances in Nonsmooth Optimization World Scientific Publishers New Jersey 88–105
A. Fischer (1997) ArticleTitleSolution of monotone complementarity problems with locally Lipschitzian functions Math. Prog. 76 513–532 Occurrence Handle10.1016/S0025-5610(96)00059-7
H. Jiang (1999) ArticleTitleGlobal convergence analysis of the generalized Newton and Gauss-Newton methods of the Fischer-Burmeister equation for the complementarity problem Math. Oper. Res. 24 529–543
H. Jiang M. Fukushima L. Qi D. Sun (1998) ArticleTitleA trust region method for solving generalized complementarity problems SIAM J. Optim. 8 140–157 Occurrence Handle10.1137/S1052623495296541
H. Jiang L. Qi (1997) ArticleTitleA new nonsmooth equations approach to nonlinear complementarity problems SIAM J. Control Optim. 35 178–193 Occurrence Handle10.1137/S0363012994276494
H. Jiang L. Qi X. Chen D. Sun (1996) Semismoothness and superlinear convergence in nonsmooth optimization and nonsmooth equations G. Pillo ParticleDi F. Giannessi (Eds) Nonlinear Optimization and Applications Plenum Press New York 197–212
H. Jiang D. Ralph (1999) Global and local superlinear convergence analysis of Newton-type methods for semismooth equations with smooth least squares M. Fukushima L. Qi (Eds) Reformulation – Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods Kluwer Academic Publishers Nowell, MA 181–210
T.S. Munson F. Facchinei M.C. Ferris A. Fischer C. Kanzow (2001) ArticleTitleThe semismooth algorithm for large scale complementarity problems. INFORMS J Comput. 13 294–311
J.S. Pang L. Qi (1993) ArticleTitleNonsmooth equations: Motivation and algorithms SIAM J. Optim. 3 443–465 Occurrence Handle10.1137/0803021
H. Qi L. Qi D. Sun (2004) ArticleTitleSolving KKT systems via the trust region and the conjugate gradient methods SIAM J. on Optim. 14 439–463 Occurrence Handle10.1137/S105262340038256X
L. Qi (1993) ArticleTitleConvergence analysis of some algorithms for solving nonsmooth equations Math. Oper. Res. 18 227–244 Occurrence Handle10.1287/moor.18.1.227
L. Qi (1999) ArticleTitleRegular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variational inequality problems Math. Oper. Res. 24 440–471
L. Qi H. Jiang (1997) ArticleTitleSemismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton methods and quasi-Newton methods for solving these equations Math. Oper. Res. 22 301–325
L. Qi D. Ralph G. Zhou (2000) Semiderivative functions and reformulation methods for solving complementarity and variational inequality problems G. Pillo ParticleDi F. Giannessi (Eds) Nonlinear Optimization and Related Topics Kluwer Academic Publisher Nowell, MA 317–350
L. Qi J. Sun (1993) ArticleTitleA nonsmooth version of Newton’s method Math. Prog. 58 353–368 Occurrence Handle10.1007/BF01581275
Rockafellar, R.T. (1970), Convex Analysis. Princeton, NJ.
P. Tseng (1996) ArticleTitleGlobal behaviour of a class of merit functions for the nonlinear complementarity problem J. Optim. Theory Appl. 89 17–37 Occurrence Handle10.1007/BF02192639
N. Yamashita M. Fukushima (1997) ArticleTitleModified Newton methods for solving semismooth reformulations of monotone complementarity problems Math. Prog. 76 469–491 Occurrence Handle10.1016/S0025-5610(96)00057-3
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is dedicated to Alex Rubinov on the occasion of his 65th Birthday
This work is supported by the Research Grant Council of Hong Kong
Rights and permissions
About this article
Cite this article
Qi, L. Boundedness and Regularity Properties of Semismooth Reformulations of Variational Inequalities. J Glob Optim 35, 343–366 (2006). https://doi.org/10.1007/s10898-005-3842-4
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10898-005-3842-4