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-375. 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, Springer-Verlag, Berlin, 1990.  Google Scholar

[3]

S. C. Billups, A homotopy-based algorithm for mixed complementarity problems, SIAM J. Optim., 12 (2002), 583-605. 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, 1995), Comput. Optim. Appl., 7 (1997), 3-25. 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-626. 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-138. 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-540. 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-616. 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-316. 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-345. doi: 10.1080/10556789508805619.  Google Scholar

[11]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Vol. I, Springer Series in Operations Research, Springer-Verlag, New York, 2003.  Google Scholar

[12]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Vol. II, Springer Series in Operations Research, Springer-Verlag, New York, 2003.  Google Scholar

[13]

X. Fan and B. Yu, Homotopy method for solving variational inequalities with bounded box constraints, Nonlinear Anal., 68 (2008), 2357-2361. 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, Part I, Comput. Optim. Appl., 12 (1999), 207-227. 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-713. doi: 10.1137/S0036144595285963.  Google Scholar

[16]

S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems, in "Complementarity and Variational Problems" (Baltimore, MD, 1995), SIAM, Philadelphia, PA, 1997, 105-116.  Google Scholar

[17]

C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria," Prentice-Hall, Englewood Cliffs, New Jersey, 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-220. 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-373. 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-230. 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-131. 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-35.  Google Scholar

[23]

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

[24]

T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver," Working paper, Department of Economics, University of Colorado, Boulder, 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-413. 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-187. 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-599. 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-689. 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, Piecewise Smooth, Semismooth and Smoothing Methods (Lausanne, 1997), Appl. Optim., 22, Kluwer Acad. Publ., Dordrecht, (1999), 421-441.  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-375. 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, Springer-Verlag, Berlin, 1990.  Google Scholar

[3]

S. C. Billups, A homotopy-based algorithm for mixed complementarity problems, SIAM J. Optim., 12 (2002), 583-605. 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, 1995), Comput. Optim. Appl., 7 (1997), 3-25. 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-626. 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-138. 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-540. 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-616. 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-316. 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-345. doi: 10.1080/10556789508805619.  Google Scholar

[11]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Vol. I, Springer Series in Operations Research, Springer-Verlag, New York, 2003.  Google Scholar

[12]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Vol. II, Springer Series in Operations Research, Springer-Verlag, New York, 2003.  Google Scholar

[13]

X. Fan and B. Yu, Homotopy method for solving variational inequalities with bounded box constraints, Nonlinear Anal., 68 (2008), 2357-2361. 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, Part I, Comput. Optim. Appl., 12 (1999), 207-227. 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-713. doi: 10.1137/S0036144595285963.  Google Scholar

[16]

S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems, in "Complementarity and Variational Problems" (Baltimore, MD, 1995), SIAM, Philadelphia, PA, 1997, 105-116.  Google Scholar

[17]

C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria," Prentice-Hall, Englewood Cliffs, New Jersey, 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-220. 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-373. 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-230. 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-131. 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-35.  Google Scholar

[23]

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

[24]

T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver," Working paper, Department of Economics, University of Colorado, Boulder, 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-413. 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-187. 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-599. 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-689. 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, Piecewise Smooth, Semismooth and Smoothing Methods (Lausanne, 1997), Appl. Optim., 22, Kluwer Acad. Publ., Dordrecht, (1999), 421-441.  Google Scholar

[1]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021150
[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]

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

Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 429-443. doi: 10.3934/jimo.2018049
[5]

Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial & Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005
[6]

Xin Li, Feng Bao, Kyle Gallivan. A drift homotopy implicit particle filter method for nonlinear filtering problems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021097
[7]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[8]

Xiao-Hong Liu, Wei-Zhe Gu. Smoothing Newton algorithm based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones. Journal of Industrial & Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363
[9]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[10]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141
[11]

Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241
[12]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080
[13]

Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042
[14]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030
[15]

Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645
[16]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[17]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020147
[18]

Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial & Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317
[19]

Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145
[20]

Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy