A New Descent Method for Symmetric Non-monotone Variational Inequalities with Application to Eigenvalue Complementarity Problems
Pages 923 - 940
Abstract
In this paper, a modified Josephy---Newton direction is presented for solving the symmetric non-monotone variational inequality. The direction is a suitable descent direction for the regularized gap function. In fact, this new descent direction is obtained by developing the Gauss---Newton idea, a well-known method for solving systems of equations, for non-monotone variational inequalities, and is then combined with the Broyden---Fletcher---Goldfarb---Shanno-type secant update formula. Also, when Armijo-type inexact line search is used, global convergence of the proposed method is established for non-monotone problems under some appropriate assumptions. Moreover, the new algorithm is applied to an equivalent non-monotone variational inequality form of the eigenvalue complementarity problem and some other variational inequalities from the literature. Numerical results from a variety of symmetric and asymmetric eigenvalue complementarity problems and the variational inequalities show a good performance of the proposed algorithm with regard to the test problems.
References
[1]
Nagurney, A.: Variational inequalities. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, 2nd edn, pp. 3989---3994. Springer, New York (2009)
[2]
Signorini, A.: Questioni di elasticiá non linearizzata e semilinearizzata. Rend. Mat. Appl. Ser. 18, 95---139 (1959). (in Italian)
[3]
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer, New York (2003)
[4]
Adly, S., Rammal, H.: A new method for solving Pareto eigenvalue complementarity problems. Comput. Optim. Appl. 55, 703---731 (2013)
[5]
Adly, S., Seeger, A.: A nonsmooth algorithm for cone-constrained eigenvalue problems. Comput. Optim. Appl. 49, 299---318 (2011)
[6]
Chen, H.S.: A family of NCP function and a descent method for the nonlinear complementarity problem. Comput. Optim. Appl. 40, 39---404 (2008)
[7]
Judice, J., Faustino, A.: A sequential LCP algorithm for bilevel linear programming. Ann. Oper. Res. 34, 89---106 (1992)
[8]
Júdice, J.J., Sherali, H.D., Ribeiro, I.M., Rosa, S.S.: On the asymmetric eigenvalue complementarity problem. Optim. Methods Softw. 24, 549---568 (2009)
[9]
Pinto da Costa, A., Seeger, A.: Numerical resolution of cone constrained eigenvalue problems. Comput. Appl. Math. 28, 37---61 (2009)
[10]
da Costa, A.P., Seeger, A.: Cone constrained eigenvalue problems: theory and algorithms. Comput. Optim. Appl. 45, 25---57 (2010)
[11]
Seeger, A.: Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions. Linear Algebra Appl. 292, 1---14 (1999)
[12]
Zhou, Y., Gowda, M.S.: On the finiteness of the cone spectrum of certain linear transformations on Euclidean Jordan algebras. Linear Algebra Appl. 431, 772---782 (2009)
[13]
Queiroz, M., Júdice, J., Humes, J.R.C.: The symmetric eigenvalue complementarity problem. Math. Comput. 73, 1849---1863 (2004)
[14]
Júdice, J., Raydan, M., Rosa, S.S., Santos, S.A.: On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm. Numer. Algorithms 47, 391---407 (2008)
[15]
Le Thi, H.A., Moeini, M., Pham Dinh, T., Júdice, J.J.: A DC programming approach for solving the symmetric eigenvalue complementarity problem. Comput. Optim. Appl. 51, 1097---1117 (2012)
[16]
Pinto da Costa, A., Martins, J.A.C., Figueiredo, I.N., Júdice, J.J.: The directional instability problem in systems with frictional contacts. Comput. Methods Appl. Mech. Eng. 193, 357---384 (2004)
[17]
Dirkse, S.P., Ferris, M.C.: The PATH solver: a non-monotone stabilization scheme for mixed complementarity problems. Optim. Methods Softw. 5, 123---156 (1995)
[18]
Munson, T.S.: Algorithms and Environments for Complementarity. Ph.D. Thesis, University of Wisconsin-Madison, Wisconsin (2000)
[19]
Josephy, N.H.: Newton's method for generalized equations. Technical Summary Report no. 1965, Mathematics Research Center, University of Wisconsin, Madison (1979)
[20]
Josephy, N.H.: Quasi-Newton method for generalized equations. Technical Summary Report no. 1966, Mathematics Research Center, University of Wisconsin, Madison ( 1979)
[21]
Robinson, S.M.: Generalized equations. In: Bachem, A., Grotschel, M., Korte, B. (eds.) Mathematical Programming: The State of the Art, pp. 346---367. Springer, Berlin (1982)
[22]
Bonnans, J.F.: Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29, 161---186 (1994)
[23]
Eaves, B.C.: A locally quadratically convergent algorithm for computing stationary points. Technical Report SOL 78-13, Department of Operations Research, Stanford University (1978)
[24]
Robinson, S.M.: Strongly regular generalized equations. Math. Oper. Res. 5, 43---62 (1980)
[25]
Pang, J.S., Chart, D.: Iterative methods for variational and complementarity problems. Math. Program. 24, 284---313 (1982)
[26]
Harker, P.T., Pang, J.S.: Finite dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math. Program. 48, 161---220 (1990)
[27]
Marcotte, P., Dussault, J.P.: A note on a globally convergent Newton method for solving monotone variational inequalities. Oper. Res. Lett. 6, 35---42 (1987)
[28]
Marcotte, P.: A new algorithm for solving variational inequalities with application to the traffic assignment problem. Math. Program. 33, 339---351 (1985)
[29]
Taji, K., Fukushima, M., Ibaraki, T.: A globally convergent Newton method for solving strongly monotone variational inequalities. Math. Program. 58, 369---383 (1993)
[30]
Taji, K.: A note on globally convergent Newton method for strongly monotone variational inequalities. J. Oper. Res. Soc. Jpn. 51, 310---316 (2008)
[31]
Peng, J.M., Fukushima, M.: A hybrid Newton method for solving the variational inequality problem via the D-gap function. Math. Program. 86, 367---386 (1999)
[32]
Long, J., Zeng, S.: A projection-filter method for solving nonlinear complementarity problems. Appl. Math. Comput. 216, 300---307 (2010)
[33]
Auslender, A.: Optimisation : Methodes Numeriques. Masson, Paris (1976)
[34]
Fukushima, M.: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99---110 (1992)
[35]
Bras, C.P., Fukushima, M., Júdice, J.J., Rosa, S.S.: Variational inequality formulation of the asymmetric eigenvalue complementarity problem and its solution by means of gap functions. Pac. J. Optim. 8, 197---215 (2012)
[36]
Li, D., Fukushima, M.: A globally and super linearly convergent Gauss---Newton based BFGS method for symmetric nonlinear equations. SIAM J. Numer. Anal. 37, 152---172 (1999)
[37]
Li, D.H., Fukushima, M.: On the global convergence of the BFGS method for nonconvex unconstrained optimization problems. SIAM J. Optim. 11, 1054---1064 (2001)
[38]
Li, D.H., Fukushima, M.: A modified BFGS method and its global convergence in nonconvex minimization. J. Comput. Appl. Math. 129, 15---35 (2001)
[39]
Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227---244 (1993)
[40]
Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
[41]
Sun, D., Fukushima, M., Qi, L.: A computable generalized Hessian of the D-gap function and Newton-type methods for variational inequality problems. In: Ferris, M.C., Pang, J.-S. (eds.) Complementarity and Variational Problems: State of the Arts, pp. 452---472. SIAM, Philadelphia (1997)
[42]
Byrd, R., Nocedal, J.: A tool for analysis of Quasi---Newton methods with application to unconstrained minimization. SIAM J. Numer. Anal. 26, 727---739 (1989)
[43]
Júdice, J.J., Sherali, H.D., Ribeiro, I.: The eigenvalue complementarity problem. Comput. Optim. Appl. 37, 139---156 (2007)
[44]
Niu, Y.S., Pham Dinh, T., Le Thi, H.A., Júdice, J.J.: Efficient DC programming approaches for the asymmetric eigenvalue complementarity problem. Optim. Methods Softw. 28, 812---829 (2013)
[45]
Kojima, M., Shindo, S.: Extensions of Newton and Quasi---Newton methods to systems of $$ PC^{1} $$PC1 equations. J. Oper. Res. Soc. Jpn. 29, 352---374 (1986)
[46]
Pang, J.-S., Gabriel, S.A.: NE/SQP: a robust algorithm for the nonlinear complementary problem. Math. Program. 60, 295---337 (1993)
[47]
Harker, P.T.: Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities. Math. Program. 41, 29---59 (1988)
[48]
Marcotte, P.: Application of Khobotov's algorithm to variational inequalities and network equilibrium problems. INFORM 29, 258---271 (1991)
[49]
Dafermos, S.: Traffic equilibrium and variational inequalities. Transp. Sci. 14, 42---54 (1980)
- A New Descent Method for Symmetric Non-monotone Variational Inequalities with Application to Eigenvalue Complementarity Problems
Recommendations
A monotone semismooth Newton type method for a class of complementarity problems
In this paper, we propose a modified semismooth Newton method for a class of complementarity problems arising from the discretization of free boundary problems and establish its monotone convergence. We show that under appropriate conditions, the method ...
Smoothing Newton method for nonsmooth second-order cone complementarity problems with application to electric power markets
AbstractThis paper is dedicated to solving a nonsmooth second-order cone complementarity problem, in which the mapping is assumed to be locally Lipschitz continuous, but not necessarily to be continuously differentiable everywhere. With the help of the ...
Regularization Algorithms for Solving Monotone Ky Fan Inequalities with Application to a Nash-Cournot Equilibrium Model
We make use of the Banach contraction mapping principle to prove the linear convergence of a regularization algorithm for strongly monotone Ky Fan inequalities that satisfy a Lipschitz-type condition recently introduced by Mastroeni. We then modify the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2017 Springer Science+Business Media New York.
Publisher
Plenum Press
United States
Publication History
Published: 01 June 2017
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in