Spectral Gradient Algorithm Based on the Generalized Fiser-Burmeister Function for Sparse Solutions of LCPS

Chang Gao, Zhensheng Yu, Feiran Wang

College of Science, University of Shanghai for Science and Technology, Shanghai, China.

DOI: 10.4236/ojs.2015.56057                

Abstract

This paper considers the computation of sparse solutions of the linear complementarity problems LCP(q, M). Mathematically, the underlying model is NP-hard in general. Thus an lp(0 < p < 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.

Keywords

Linear Complementarity Problem, Sparse Solution, Spectral Gradient, Generalized Fischer-Burmeister

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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.
[2]	Ferris, M.C., Mangasarian, O.L. and Pang, J.S. (2001) Complementarity: Applications, Algorithms and Extensions. Kluwer Academic Publishers, Dordrecht.
[3]	Gao, J.D. (2013) Optimal Cardinality Constrained Portfolio Selection. Operations Research, 61, 745-761. http://dx.doi.org/10.1287/opre.2013.1170
[4]	Xie, J., He, S. and Zhang, S. (2008) Randomized Portfolio Selection with Constraints. Pacific Journal of Optimization, 4, 87-112.
[5]	Cottle, R.W., Pang, J.S. and Stone, R.E. (1992) The Linear Complementarity Problem. Academic Press, Boston.
[6]	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
[7]	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
[8]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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.
[14]	Chen, X.J., Xu, F. and Ye, Y. (2010) Lower Bound Theory of Nonzero Entries in Solutions of l2-lp Minimiization. SIAM: SIAM Journal on Scientific Computing, 32, 2832-2852. http://dx.doi.org/10.1137/090761471
[15]	Chen, X. and Xiang, S. (2011) Implicit Solution Function of P0 and Z Matrix Linear Complementarity Constrains. Mathematical Programming, 128, 1-18. http://dx.doi.org/10.1007/s10107-009-0291-8