American Institute of Mathematical Sciences

Advanced
October  2011, 7(4): 977-989. doi: 10.3934/jimo.2011.7.977

A smoothing homotopy method based on Robinson's normal equation for mixed complementarity problems

Zhengyong Zhou 1, and  Bo Yu 2,

1. 

School of Mathematical Sciences, Dalian University of Technology, Dalian, Liaoning 116024, China
2. 

School of Mathematical Science, Dalian University of Technology, Dalian, Liaoning 116024, China

Received  January 2011 Revised  June 2011 Published  August 2011

In this paper, a probability-one homotopy method for solving mixed complementarity problems is proposed. The homotopy equation is constructed by using the Robinson's normal equation of mixed complementarity problem and a $C^2$-smooth approximation of projection function. Under the condition that the mixed complementarity problem has no solution at infinity, which is a weaker condition than several well-known ones, existence and convergence of a smooth homotopy path from almost any starting point in $\mathbb{R}^n$ are proven. The homotopy method is implemented in Matlab and numerical results on the MCPLIB test collection are given.
Keywords: homotopy method., Complementarity problems, smoothing.
Mathematics Subject Classification: 90C33, 65D10, 65H2.
Citation: Zhengyong Zhou, Bo Yu. A smoothing homotopy method based on Robinson's normal equation for mixed complementarity problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 977-989. doi: 10.3934/jimo.2011.7.977
References:
[1]

K. Ahuja, L. T. Watson and S. C. Billups, Probability-one homotopy maps for mixed complementarity problems,, Comput. Optim. Appl., 41 (2008), 363.  doi: 10.1007/s10589-007-9107-z.  Google Scholar

[2]

E. L. Allgower and K. Georg, "Numerical Continuation Methods, An Introduction,", Springer Series in Computational Mathematics, 13 (1990).   Google Scholar

[3]

S. C. Billups, A homotopy-based algorithm for mixed complementarity problems,, SIAM J. Optim., 12 (2002), 583.  doi: 10.1137/S1052623498337431.  Google Scholar

[4]

S. C. Billups, S. P. Dirkse and M. C. Ferris, A comparison of large scale mixed complementarity problem solvers,, Computational Issues in High Performance Software for Nonlinear Optimization (Capri, 7 (1997), 3.  doi: 10.1023/A:1008632215341.  Google Scholar

[5]

S. C. Billups and L. T. Watson, A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems,, SIAM J. Optim., 12 (2002), 606.  doi: 10.1137/S105262340037758X.  Google Scholar

[6]

C. H. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,, Comput. Optim. Appl., 5 (1996), 97.  doi: 10.1007/BF00249052.  Google Scholar

[7]

X. Chen, L. Qi and D. Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities,, Math. Comp., 67 (1998), 519.  doi: 10.1090/S0025-5718-98-00932-6.  Google Scholar

[8]

X. Chen and Y. Ye, On homotopy-smoothing methods for box-constrained variational inequalities,, SIAM J. Control Optim., 37 (1999), 589.  doi: 10.1137/S0363012997315907.  Google Scholar

[9]

A. N. Daryina, A. F. Izmailov and M. V. Solodov, Numerical results for a globalized active-set Newton method for mixed complementarity problems,, Comput. Appl. Math., 24 (2005), 293.  doi: 10.1590/S0101-82052005000200008.  Google Scholar

[10]

S. P. Dirkse and M. C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems,, Optim. Methods Softw., 5 (1995), 319.  doi: 10.1080/10556789508805619.  Google Scholar

[11]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. I, I (2003).   Google Scholar

[12]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. \textbf{II}, II (2003).   Google Scholar

[13]

X. Fan and B. Yu, Homotopy method for solving variational inequalities with bounded box constraints,, Nonlinear Anal., 68 (2008), 2357.  doi: 10.1016/j.na.2007.01.063.  Google Scholar

[14]

M. C. Ferris and T. S. Munson, Interfaces to PATH 3.0: Design, implementation and usage,, Computational Optimization-A tribute to Olvi Mangasarian, 12 (1999), 207.  doi: 10.1023/A:1008636318275.  Google Scholar

[15]

M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems,, SIAM Rev., 39 (1997), 669.  doi: 10.1137/S0036144595285963.  Google Scholar

[16]

S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems,, in, (1995), 105.   Google Scholar

[17]

C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria,", Prentice-Hall, (1981).   Google Scholar

[18]

P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,, Math. Programming, 48 (1990), 161.  doi: 10.1007/BF01582255.  Google Scholar

[19]

C. Kanzow and H. Pieper, Jacobian smoothing methods for nonlinear complementarity problems,, SIAM J. Optim., 9 (1999), 342.  doi: 10.1137/S1052623497328781.  Google Scholar

[20]

D. H. Li and M. Fukushima, Smoothing Newton and quasi-Newton methods for mixed complementarity problems, Nonsmooth and Smoothing Methods (Hong Kong, 1998),, Comput. Optim. Appl., 17 (2000), 203.  doi: 10.1023/A:1026502415830.  Google Scholar

[21]

J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,, Math. Programming, 51 (1991), 101.  doi: 10.1007/BF01586928.  Google Scholar

[22]

L. Q. Qi, D. F. Sun and G. L. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities,, Math. Program., 87 (2000), 1.   Google Scholar

[23]

S. M. Robinson, Normal maps induced by linear transformations,, Math. Oper. Res., 17 (1992), 691.  doi: 10.1287/moor.17.3.691.  Google Scholar

[24]

T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver,", Working paper, (1993).   Google Scholar

[25]

D. F. Sun and R. S. Womersley, A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Gauss-Newton method,, SIAM J. Optim., 9 (1999), 388.  doi: 10.1137/S1052623496314173.  Google Scholar

[26]

D. F. Sun, R. S. Womersley and H. D. Qi, A feasible semismooth asymptotically Newton method for mixed complementarity problems,, Math. Program., 94 (2002), 167.  doi: 10.1007/s10107-002-0305-2.  Google Scholar

[27]

Q. Xu, B. Yu, G. C. Feng and C. Y. Dang, Condition for global convergence of a homotopy method for variational inequality problems on unbounded sets,, Optim. Methods Softw., 22 (2007), 587.  doi: 10.1080/10556780600887883.  Google Scholar

[28]

Q. Xu and C. Y. Dang, A new homotopy method for solving non-linear complementarity problems,, Optimization, 57 (2008), 681.  doi: 10.1080/02331930802355317.  Google Scholar

[29]

G. L. Zhou, D. F. Sun and L. Q. Qi, "Numerical Experiments for a Class of Squared Smoothing Newton Methods for Box Constrained Variational Inequality Problems,", Reformation: Nonsmooth, 22 (1999), 421.   Google Scholar

show all references

References:
[1]

K. Ahuja, L. T. Watson and S. C. Billups, Probability-one homotopy maps for mixed complementarity problems,, Comput. Optim. Appl., 41 (2008), 363.  doi: 10.1007/s10589-007-9107-z.  Google Scholar

[2]

E. L. Allgower and K. Georg, "Numerical Continuation Methods, An Introduction,", Springer Series in Computational Mathematics, 13 (1990).   Google Scholar

[3]

S. C. Billups, A homotopy-based algorithm for mixed complementarity problems,, SIAM J. Optim., 12 (2002), 583.  doi: 10.1137/S1052623498337431.  Google Scholar

[4]

S. C. Billups, S. P. Dirkse and M. C. Ferris, A comparison of large scale mixed complementarity problem solvers,, Computational Issues in High Performance Software for Nonlinear Optimization (Capri, 7 (1997), 3.  doi: 10.1023/A:1008632215341.  Google Scholar

[5]

S. C. Billups and L. T. Watson, A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems,, SIAM J. Optim., 12 (2002), 606.  doi: 10.1137/S105262340037758X.  Google Scholar

[6]

C. H. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,, Comput. Optim. Appl., 5 (1996), 97.  doi: 10.1007/BF00249052.  Google Scholar

[7]

X. Chen, L. Qi and D. Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities,, Math. Comp., 67 (1998), 519.  doi: 10.1090/S0025-5718-98-00932-6.  Google Scholar

[8]

X. Chen and Y. Ye, On homotopy-smoothing methods for box-constrained variational inequalities,, SIAM J. Control Optim., 37 (1999), 589.  doi: 10.1137/S0363012997315907.  Google Scholar

[9]

A. N. Daryina, A. F. Izmailov and M. V. Solodov, Numerical results for a globalized active-set Newton method for mixed complementarity problems,, Comput. Appl. Math., 24 (2005), 293.  doi: 10.1590/S0101-82052005000200008.  Google Scholar

[10]

S. P. Dirkse and M. C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems,, Optim. Methods Softw., 5 (1995), 319.  doi: 10.1080/10556789508805619.  Google Scholar

[11]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. I, I (2003).   Google Scholar

[12]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. \textbf{II}, II (2003).   Google Scholar

[13]

X. Fan and B. Yu, Homotopy method for solving variational inequalities with bounded box constraints,, Nonlinear Anal., 68 (2008), 2357.  doi: 10.1016/j.na.2007.01.063.  Google Scholar

[14]

M. C. Ferris and T. S. Munson, Interfaces to PATH 3.0: Design, implementation and usage,, Computational Optimization-A tribute to Olvi Mangasarian, 12 (1999), 207.  doi: 10.1023/A:1008636318275.  Google Scholar

[15]

M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems,, SIAM Rev., 39 (1997), 669.  doi: 10.1137/S0036144595285963.  Google Scholar

[16]

S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems,, in, (1995), 105.   Google Scholar

[17]

C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria,", Prentice-Hall, (1981).   Google Scholar

[18]

P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,, Math. Programming, 48 (1990), 161.  doi: 10.1007/BF01582255.  Google Scholar

[19]

C. Kanzow and H. Pieper, Jacobian smoothing methods for nonlinear complementarity problems,, SIAM J. Optim., 9 (1999), 342.  doi: 10.1137/S1052623497328781.  Google Scholar

[20]

D. H. Li and M. Fukushima, Smoothing Newton and quasi-Newton methods for mixed complementarity problems, Nonsmooth and Smoothing Methods (Hong Kong, 1998),, Comput. Optim. Appl., 17 (2000), 203.  doi: 10.1023/A:1026502415830.  Google Scholar

[21]

J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,, Math. Programming, 51 (1991), 101.  doi: 10.1007/BF01586928.  Google Scholar

[22]

L. Q. Qi, D. F. Sun and G. L. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities,, Math. Program., 87 (2000), 1.   Google Scholar

[23]

S. M. Robinson, Normal maps induced by linear transformations,, Math. Oper. Res., 17 (1992), 691.  doi: 10.1287/moor.17.3.691.  Google Scholar

[24]

T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver,", Working paper, (1993).   Google Scholar

[25]

D. F. Sun and R. S. Womersley, A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Gauss-Newton method,, SIAM J. Optim., 9 (1999), 388.  doi: 10.1137/S1052623496314173.  Google Scholar

[26]

D. F. Sun, R. S. Womersley and H. D. Qi, A feasible semismooth asymptotically Newton method for mixed complementarity problems,, Math. Program., 94 (2002), 167.  doi: 10.1007/s10107-002-0305-2.  Google Scholar

[27]

Q. Xu, B. Yu, G. C. Feng and C. Y. Dang, Condition for global convergence of a homotopy method for variational inequality problems on unbounded sets,, Optim. Methods Softw., 22 (2007), 587.  doi: 10.1080/10556780600887883.  Google Scholar

[28]

Q. Xu and C. Y. Dang, A new homotopy method for solving non-linear complementarity problems,, Optimization, 57 (2008), 681.  doi: 10.1080/02331930802355317.  Google Scholar

[29]

G. L. Zhou, D. F. Sun and L. Q. Qi, "Numerical Experiments for a Class of Squared Smoothing Newton Methods for Box Constrained Variational Inequality Problems,", Reformation: Nonsmooth, 22 (1999), 421.   Google Scholar

[1]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196
[2]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184
[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[4]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[5]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[6]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[7]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[8]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[9]

Ian Schindler, Kyril Tintarev. Mountain pass solutions to semilinear problems with critical nonlinearity. Conference Publications, 2007, 2007 (Special) : 912-919. doi: 10.3934/proc.2007.2007.912
[10]

Valeria Chiado Piat, Sergey S. Nazarov, Andrey Piatnitski. Steklov problems in perforated domains with a coefficient of indefinite sign. Networks & Heterogeneous Media, 2012, 7 (1) : 151-178. doi: 10.3934/nhm.2012.7.151
[11]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Recent progresses in the theory of nonlinear nonlocal problems. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446
[12]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[13]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[14]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[15]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[16]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072
[17]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065
[18]

Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91
[19]

Elvise Berchio, Filippo Gazzola, Dario Pierotti. Nodal solutions to critical growth elliptic problems under Steklov boundary conditions. Communications on Pure & Applied Analysis, 2009, 8 (2) : 533-557. doi: 10.3934/cpaa.2009.8.533
[20]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (35)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences