An efficient algorithm for second-order cone linear complementarity problems

Zhang, Lei-Hong; Yang, Wei Hong

doi:10.1090/S0025-5718-2013-02795-0

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 P- and GUS-properties of linear transformations on Euclidean Jordan algebras, Math. Oper. Res. 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