## An efficient algorithm for second-order cone linear complementarity problems

HTML articles powered by AMS MathViewer

- by Lei-Hong Zhang and Wei Hong Yang PDF
- Math. Comp.
**83**(2014), 1701-1726 Request permission

## Abstract:

Recently, the globally uniquely solvable (GUS) property of the linear transformation $M\in \mathbb {R}^{n\times n}$ in the second-order cone linear complementarity problem (SOCLCP) receives much attention and has been studied substantially. Yang and Yuan contributed a new characterization of the GUS property of the linear transformation, which is formulated by basic linear-algebra-related properties. In this paper, we consider efficient numerical algorithms to solve the SOCLCP where the linear transformation $M$ has the GUS property. By closely relying on the new characterization of the GUS property, a globally convergent bisection method is developed in which each iteration can be implemented using only $2n^2$ flops. Moreover, we also propose an efficient Newton method to accelerate the bisection algorithm. An attractive feature of this Newton method is that each iteration only requires $5n^2$ flops and converges quadratically. These two approaches make good use of the special structure contained in the SOCLCP and can be effectively combined to yield a fast and efficient bisection-Newton method. Numerical testing is carried out and very encouraging computational experiments are reported.## References

- Alfred Auslender,
*Variational inequalities over the cone of semidefinite positive symmetric matrices and over the Lorentz cone*, Optim. Methods Softw.**18**(2003), no. 4, 359–376. The Second Japanese-Sino Optimization Meeting, Part II (Kyoto, 2002). MR**2019034**, DOI 10.1080/1055678031000122586 - James V. Burke and Song Xu,
*The global linear convergence of a noninterior path-following algorithm for linear complementarity problems*, Math. Oper. Res.**23**(1998), no. 3, 719–734. MR**1653734**, DOI 10.1287/moor.23.3.719 - Jein-Shan Chen and Shaohua Pan,
*A descent method for a reformulation of the second-order cone complementarity problem*, J. Comput. Appl. Math.**213**(2008), no. 2, 547–558. MR**2392576**, DOI 10.1016/j.cam.2007.01.029 - 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), no. 222, 519–540. MR**1458218**, DOI 10.1090/S0025-5718-98-00932-6 - X. D. Chen, D. Sun, and J. Sun,
*Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems*, Comput. Optim. Appl.**25**(2003), no. 1-3, 39–56. A tribute to Elijah (Lucien) Polak. MR**1996662**, DOI 10.1023/A:1022996819381 - Jein-Shan Chen and Paul Tseng,
*An unconstrained smooth minimization reformulation of the second-order cone complementarity problem*, Math. Program.**104**(2005), no. 2-3, Ser. B, 293–327. MR**2179239**, DOI 10.1007/s10107-005-0617-0 - Richard W. Cottle, Jong-Shi Pang, and Richard E. Stone,
*The linear complementarity problem*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1992. MR**1150683** - Masao Fukushima, Zhi-Quan Luo, and Paul Tseng,
*Smoothing functions for second-order-cone complementarity problems*, SIAM J. Optim.**12**(2001/02), no. 2, 436–460. MR**1885570**, DOI 10.1137/S1052623400380365 - Gene H. Golub and Charles F. Van Loan,
*Matrix computations*, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR**1417720** - M. Seetharama Gowda and Yoon Song,
*On semidefinite linear complementarity problems*, Math. Program.**88**(2000), no. 3, Ser. A, 575–587. MR**1782157**, DOI 10.1007/PL00011387 - M. Seetharama Gowda and Roman Sznajder,
*Automorphism invariance of*, Math. Oper. Res.**P**- and**GUS**-properties of linear transformations on Euclidean Jordan algebras**31**(2006), no. 1, 109–123. MR**2205521**, DOI 10.1287/moor.1050.0182 - M. Seetharama Gowda and R. Sznajder,
*Some global uniqueness and solvability results for linear complementarity problems over symmetric cones*, SIAM J. Optim.**18**(2007), no. 2, 461–481. MR**2338447**, DOI 10.1137/060653640 - M. Seetharama Gowda, Roman Sznajder, and J. Tao,
*Some $\mathbf P$-properties for linear transformations on Euclidean Jordan algebras*, Linear Algebra Appl.**393**(2004), 203–232. MR**2098615**, DOI 10.1016/j.laa.2004.03.028 - Shunsuke Hayashi, Nobuo Yamashita, and Masao Fukushima,
*A combined smoothing and regularization method for monotone second-order cone complementarity problems*, SIAM J. Optim.**15**(2004/05), no. 2, 593–615. MR**2144183**, DOI 10.1137/S1052623403421516 - Shunsuke Hayashi, Takahiro Yamaguchi, Nobuo Yamashita, and Masao Fukushima,
*A matrix-splitting method for symmetric affine second-order cone complementarity problems*, J. Comput. Appl. Math.**175**(2005), no. 2, 335–353. MR**2108579**, DOI 10.1016/j.cam.2004.05.018 - Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal,
*Convex analysis and minimization algorithms. I*, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 305, Springer-Verlag, Berlin, 1993. Fundamentals. MR**1261420** - Zheng-Hai Huang and Tie Ni,
*Smoothing algorithms for complementarity problems over symmetric cones*, Comput. Optim. Appl.**45**(2010), no. 3, 557–579. MR**2600896**, DOI 10.1007/s10589-008-9180-y - Christian Kanzow,
*Some noninterior continuation methods for linear complementarity problems*, SIAM J. Matrix Anal. Appl.**17**(1996), no. 4, 851–868. MR**1410705**, DOI 10.1137/S0895479894273134 - M. Kojima, N. Megiddo, T. Noma, and A. Yoshise,
*A unified approach to interior point algorithms for linear complementarity problems*, Lecture Notes in Computer Science, vol. 538, Springer-Verlag, Berlin, 1991. MR**1226025**, DOI 10.1007/3-540-54509-3 - Masakazu Kojima, Susumu Shindoh, and Shinji Hara,
*Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices*, SIAM J. Optim.**7**(1997), no. 1, 86–125. MR**1430559**, DOI 10.1137/S1052623494269035 - Lingchen Kong, Jie Sun, and Naihua Xiu,
*A regularized smoothing Newton method for symmetric cone complementarity problems*, SIAM J. Optim.**19**(2008), no. 3, 1028–1047. MR**2460730**, DOI 10.1137/060676775 - R. B. Lehoucq and D. C. Sorensen,
*Deflation techniques for an implicitly restarted Arnoldi iteration*, SIAM J. Matrix Anal. Appl.**17**(1996), no. 4, 789–821. MR**1410702**, DOI 10.1137/S0895479895281484 - R. B. Lehoucq, D. C. Sorensen, and C. Yang,
*ARPACK users’ guide*, Software, Environments, and Tools, vol. 6, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. MR**1621681**, DOI 10.1137/1.9780898719628 - James M. Ortega,
*The Newton-Kantorovich theorem*, Amer. Math. Monthly**75**(1968), 658–660. MR**231218**, DOI 10.2307/2313800 - Shaohua Pan and Jein-Shan Chen,
*A damped Gauss-Newton method for the second-order cone complementarity problem*, Appl. Math. Optim.**59**(2009), no. 3, 293–318. MR**2491700**, DOI 10.1007/s00245-008-9054-9 - Jong-Shi Pang, Defeng Sun, and Jie Sun,
*Semismooth homeomorphisms and strong stability of semidefinite and Lorentz complementarity problems*, Math. Oper. Res.**28**(2003), no. 1, 39–63. MR**1961266**, DOI 10.1287/moor.28.1.39.14258 - G. W. Stewart,
*Matrix algorithms. Vol. II*, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. Eigensystems. MR**1853468**, DOI 10.1137/1.9780898718058 - J. Stoer and R. Bulirsch,
*Introduction to numerical analysis, 2nd ed.*, Springer-Verlag, NY, 1991. - K. C. Toh, M. J. Todd, and R. H. Tütüncü,
*SDPT3—a MATLAB software package for semidefinite programming, version 1.3*, Optim. Methods Softw.**11/12**(1999), no. 1-4, 545–581. Interior point methods. MR**1778429**, DOI 10.1080/10556789908805762 - W. H. Yang and Y. Yuan,
*The GUS-property of second-order cone linear complementarity problems,*Math. Programming Ser. A, DOI: 10.1007/s10107-012-0523-1. - Akiko Yoshise,
*Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones*, SIAM J. Optim.**17**(2006), no. 4, 1129–1153. MR**2274506**, DOI 10.1137/04061427X

## Additional Information

**Lei-Hong Zhang**- Affiliation: Department of Applied Mathematics, Shanghai University of Finance and Economics, 777 Guoding Road, Shanghai 200433, People’s Republic of China
- Email: longzlh@gmail.com
**Wei Hong Yang**- Affiliation: Corresponding author. School of Mathematical Sciences, Fudan University, Shanghai, 200433, People’s Republic of China
- Email: whyang@fudan.edu.cn
- Received by editor(s): June 30, 2010
- Received by editor(s) in revised form: September 1, 2011, and October 30, 2012
- Published electronically: November 7, 2013
- Additional Notes: The research of the first author was supported by the Natural Science Foundation of China, NSFC-11101257.

The research of the second author was supported by the Natural Science Foundation of China, NSFC-10801040. - © Copyright 2013 American Mathematical Society
- Journal: Math. Comp.
**83**(2014), 1701-1726 - MSC (2010): Primary 90C33, 65K05; Secondary 65F99
- DOI: https://doi.org/10.1090/S0025-5718-2013-02795-0
- MathSciNet review: 3194127