Research ArticleOpen AccessGoogle Scholar indexed
Spectral Gradient Algorithm Based on the Generalized Fiser-Burmeister Function for Sparse Solutions of LCPS
College of Science, University of Shanghai for Science and Technology, Shanghai, China
College of Science, University of Shanghai for Science and Technology, Shanghai, China
College of Science, University of Shanghai for Science and Technology, Shanghai, China
- 1 College of Science, University of Shanghai for Science and Technology, Shanghai, China
- 2 College of Science, University of Shanghai for Science and Technology, Shanghai, China
- 3 College of Science, University of Shanghai for Science and Technology, Shanghai, China
Open Journal of Statistics·Volume 05 (2015)·Pages 543–551·Published 13 October 2015·DOI10.4236/ojs.2015.56057
Copy link · social · email
Abstract
This paper considers the computation of sparse solutions of the linear complementarity problems LCP(<i>q</i>, <i>M</i>). Mathematically, the underlying model is NP-hard in general. Thus an <i>lp</i>(0 <<i> p </i>< 1) regularized minimization model is proposed for relaxation. We establish the equivalent unconstrained minimization reformation of the NCP-function. Based on the generalized Fiser-Burmeister function, a sequential smoothing spectral gradient method is proposed to solve the equivalent problem. Numerical results are given to show the efficiency of the proposed method.
KeywordsLinear Complementarity ProblemSparse SolutionSpectral GradientGeneralized Fischer-Burmeister
- Facchinei, F. and Pang, J.S. (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research, Vol. I & II, Springer, New York.
- Ferris, M.C., Mangasarian, O.L. and Pang, J.S. (2001) Complementarity: Applications, Algorithms and Extensions. Kluwer Academic Publishers, Dordrecht.
- Gao, J.D. (2013) Optimal Cardinality Constrained Portfolio Selection. Operations Research, 61, 745-761. http://dx.doi.org/10.1287/opre.2013.1170
- Xie, J., He, S. and Zhang, S. (2008) Randomized Portfolio Selection with Constraints. Pacific Journal of Optimization, 4, 87-112.
- Cottle, R.W., Pang, J.S. and Stone, R.E. (1992) The Linear Complementarity Problem. Academic Press, Boston.
- Shang, M.J., Zhang, C. and Xiu, N.H. (2014) Minimal Zero Norm Solutions of Linear Complementarity Problems. Journal of Optimization Theory and Applications, 163, 795-814. http://dx.doi.org/10.1007/s10957-014-0549-z
- Barzilai, J. and Borwein, J.M. (1988) Two Point Step Size Gradient Method. IMA Journal of Numerical Analysis, 8, 174-184. http://dx.doi.org/10.1093/imanum/8.1.141
- Raydan, M. (1997) The Barzilai-Borwein Gradient Method for the Large Scale Unconstrained Optimization Problem. SIAM Journal on Optimization, 7, 26-33. http://dx.doi.org/10.1137/S1052623494266365
- Raydan, M. (1993) On the Barzilai and Borwein Choice of Step Length for the Gradient Method. IMA Journal of Numerical Analysis, 13, 321-326. http://dx.doi.org/10.1093/imanum/13.3.321
- Chen, J.-S. and Pan, S.-H. (2010) A Neural Network Based on the Generalized Fischer-Burmeister Function Fornonlinear Complementarity Problem. Information Sciences, 180, 697-711. http://dx.doi.org/10.1016/j.ins.2009.11.014
- Chen, J.-S. and Pan, S.-H. (2008) A Family of NCP Functions and a Descent Method for the Nonlinear Complementarity Problem. Computation Optimization and Application, 40, 389-404. http://dx.doi.org/10.1007/s10589-007-9086-0
- Chen, J.-S. and Pan, S.-H. (2008) A Regularization Semismooth Newton Method Based on the Generalized Fischer-Burmeister Function for P0-NCPs. Journal of Computation and Applied Mathematics, 220, 464-479. http://dx.doi.org/10.1016/j.cam.2007.08.020
- Chen, J.-S., Gao, H.-T. and Pan, S.-H. (2009) A Derivative-Free R-Linearly Convergent Derivative-Free Algorithm for the NPCs Based on the Generalized Fischer-Burmeister Merit Function. Journal of Computation and Applied Mathematics, 232, 455-471.