Sparse Solutions Of Complementarity Problems

Complementarity problems are classic and important research subjects in mathe-matical programming, which have been widely applied in many fields such as engineer-ing, economics and traffic equilibrium. On the other hand, sparse optimization is a new research subject in the field of optimization, and the study of its theory, model and al-gorithms is developing rapidly. Finding a sparse solution of complementarity problems is a fusion of complementarity problems and sparse optimization, which has great sig-nificance in both theory and practice. This dissertation is devoted to some fundamental results on theory and computation of the sparse solution of complementarity problems, including the existence and uniqueness of solution in the aspect of theory, and four al-gorithms for effectively solving the sparse solutions of complementarity problems in the aspect of computation. The main results in the dissertation are summarized as follows:To find sparse solutions of the linear complementarity problems (LCPs), we show the uniqueness of sparse solutions for Z-matrix linear complementarity problems. By employing the FB complementarity function, we propose a non-constrained minimiza-tion model with an lp (0<p<1) norm regularization and show that it can approximate sparse solutions very well by sequentially decreasing the regularization parameter. We establish a threshold lower bound for any nonzero entry in its local minimizers, which can be used to identify zero entries precisely in computed solutions. We also consider the choice of regularization parameter to achieve desired sparsity. Based on the theo-retical results, we design a sequential smoothing gradient method (SSG) to solve the model. Numerical results demonstrate that the sequential smoothing gradient method can effectively solve the regularized model and obtain minimal zero norm solutions of linear complementarity problems.To improve the computation efficiency of finding sparse solutions of the linear complementarity problems (LCPs), we propose a projection constrained minimization model with an l1 norm regularization, by transforming the complementarity constraints into a fixed point equation of projection type. Through developing a thresholding rep-resentation of solutions for a key subproblem of this regularization model, we design a Shrinkage-Thresholding Projection (STP) algorithm to solve this model and also an-alyze convergence of the STP algorithm. Numerical results demonstrate that the STP method can efficiently solve this regularized model and obtain a sparsest solution of the LCP with high quality.To obtain a better approximation for the involved l0 norm in finding sparse so-lutions of the linear complementarity problems (LCPs), we propose a projection con-strained minimization model with an l1//2 norm regularization. A half thresholding projection (HTP) algorithm is then designed for this regularization model and the con-vergence of the HTP algorithm is studied. Numerical results demonstrate that the HTP algorithm can effectively solve this regularization model and produce very sparse solu-tions of LCPs with high quality.To find sparse solutions of nonlinear complementarity problems (NCPs), a pro-jection constrained minimization model with an l1 norm regularization is proposed for relaxation and an extragradient thresholding algorithm (ETA) is then designed for this regularized model. Furthermore, we analyse the convergence of this algorithm and show that any cluster point of the sequence generated by ETA is a solution of NCP. Numerical results demonstrate that the ETA can effectively solve l1 regularized model and produce very sparse solutions of co-coercive NCPs with high quality.Finally, the main contributions of this dissertation are summarized and some future research issues are discussed.