OJS  Vol.5 No.6 , October 2015
Spectral Gradient Algorithm Based on the Generalized Fiser-Burmeister Function for Sparse Solutions of LCPS
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.

Cite this paper
Gao, C. , Yu, Z. and Wang, F. (2015) Spectral Gradient Algorithm Based on the Generalized Fiser-Burmeister Function for Sparse Solutions of LCPS. Open Journal of Statistics, 5, 543-551. doi: 10.4236/ojs.2015.56057.
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

 
 
Top