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