Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

An efficient algorithm for second-order cone linear complementarity problems


Authors: Lei-Hong Zhang and Wei Hong Yang
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
Published electronically: November 7, 2013
MathSciNet review: 3194127
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2004i:90101), https://doi.org/10.1080/1055678031000122586
  • [2] 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 (99h:90103), https://doi.org/10.1287/moor.23.3.719
  • [3] 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 (2008k:90131), https://doi.org/10.1016/j.cam.2007.01.029
  • [4] 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 (98g:90034), https://doi.org/10.1090/S0025-5718-98-00932-6
  • [5] 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 (2004f:90142), https://doi.org/10.1023/A:1022996819381
  • [6] 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 (2006g:90123), https://doi.org/10.1007/s10107-005-0617-0
  • [7] 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 (93f:90001)
  • [8] 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 (electronic). MR 1885570 (2002m:90084), https://doi.org/10.1137/S1052623400380365
  • [9] 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 (97g:65006)
  • [10] M. Seetharama Gowda and Yoon Song, On semidefinite linear complementarity problems, Math. Program. 88 (2000), no. 3, Ser. A, 575-587. MR 1782157 (2001e:90111), https://doi.org/10.1007/PL00011387
  • [11] M. Seetharama Gowda and Roman Sznajder, Automorphism invariance of P- and GUS-properties of linear transformations on Euclidean Jordan algebras, Math. Oper. Res. 31 (2006), no. 1, 109-123. MR 2205521 (2007i:90086), https://doi.org/10.1287/moor.1050.0182
  • [12] 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 (2008k:49020), https://doi.org/10.1137/060653640
  • [13] 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 (2005h:17059), https://doi.org/10.1016/j.laa.2004.03.028
  • [14] 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 (electronic). MR 2144183 (2006f:90081), https://doi.org/10.1137/S1052623403421516
  • [15] 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 (2005h:90140), https://doi.org/10.1016/j.cam.2004.05.018
  • [16] 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 (95m:90001)
  • [17] 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 (2011a:90119), https://doi.org/10.1007/s10589-008-9180-y
  • [18] Christian Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 4, 851-868. MR 1410705 (97g:90148), https://doi.org/10.1137/S0895479894273134
  • [19] 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 (94e:90004)
  • [20] 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 (97m:90088), https://doi.org/10.1137/S1052623494269035
  • [21] 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 (2009i:90150), https://doi.org/10.1137/060676775
  • [22] 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 (97k:65091), https://doi.org/10.1137/S0895479895281484
  • [23] R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK users' guide, Solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. Software, Environments, and Tools, vol. 6, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. MR 1621681
  • [24] James M. Ortega, The Newton-Kantorovich theorem, Amer. Math. Monthly 75 (1968), 658-660. MR 0231218 (37 #6773)
  • [25] 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 (2010d:90117), https://doi.org/10.1007/s00245-008-9054-9
  • [26] 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 (2004a:90094), https://doi.org/10.1287/moor.28.1.39.14258
  • [27] G. W. Stewart, Matrix algorithms. Vol. II, Eigensystems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. MR 1853468
  • [28] J. Stoer and R. Bulirsch, Introduction to numerical analysis, 2nd ed., Springer-Verlag, NY, 1991.
  • [29] 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, https://doi.org/10.1080/10556789908805762
  • [30] 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.
  • [31] 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 (electronic). MR 2274506 (2007k:90137), https://doi.org/10.1137/04061427X

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C33, 65K05, 65F99

Retrieve articles in all journals with MSC (2010): 90C33, 65K05, 65F99


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

DOI: https://doi.org/10.1090/S0025-5718-2013-02795-0
Keywords: Second-order cone, Linear complementarity problem, globally uniquely solvable property, bisection iteration, Newton's iteration
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.
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society