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 and 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.

[2]

E. L. Allgower and K. Georg, "Numerical Continuation Methods, An Introduction," Springer Series in Computational Mathematics, 13, Springer-Verlag, Berlin, 1990.

[3]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17]

C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria," Prentice-Hall, Englewood Cliffs, New Jersey, 1981.

[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.

[19]

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

[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.

[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.

[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.

[23]

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

[24]

T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver," Working paper, Department of Economics, University of Colorado, Boulder, 1993.

[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.

[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.

[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.

[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.

[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.

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.

[2]

E. L. Allgower and K. Georg, "Numerical Continuation Methods, An Introduction," Springer Series in Computational Mathematics, 13, Springer-Verlag, Berlin, 1990.

[3]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17]

C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria," Prentice-Hall, Englewood Cliffs, New Jersey, 1981.

[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.

[19]

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

[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.

[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.

[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.

[23]

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

[24]

T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver," Working paper, Department of Economics, University of Colorado, Boulder, 1993.

[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.

[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.

[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.

[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.

[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.

[1]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021150
[2]

Yan Li, Liping Zhang. A smoothing Newton method preserving nonnegativity for solving tensor complementarity problems with $ P_0 $ mappings. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022041
[3]

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

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

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

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

Xin Li, Feng Bao, Kyle Gallivan. A drift homotopy implicit particle filter method for nonlinear filtering problems. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 727-746. doi: 10.3934/dcdss.2021097
[8]

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 and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[9]

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 and Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363
[10]

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 and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[11]

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

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

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

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

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

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

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[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 and Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317
[19]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (1) : 157-172. doi: 10.3934/jimo.2020147
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy