论文标题
通过新的优点功能，牛顿硬阈值追求稀疏LCP
Newton Hard Thresholding Pursuit for Sparse LCP via A New Merit Function
论文作者
论文摘要
在Bimatrix游戏和投资组合部分问题等许多应用中，线性互补问题（LCP）的解决方案自然稀少。尽管这引起了硬度，但稀疏性可更快地进行优化，并实现相对较大的规模计算。在此激励的情况下，我们考虑了稀疏的LCP，研究了解决方案集的存在和界限，并引入了新的优点功能，这使我们能够将问题转换为稀疏性约束优化的优化。事实证明，对于某些选定的参数，该函数是连续的差异，并且连续差异两次。有趣的是，如果所涉及的矩阵是正半芬矿，则它也是凸。然后，我们探索设置与稀疏LCP的解决方案与稀疏性限制优化的固定点之间的关系。最后，采用了牛顿硬阈值追求来解决稀疏性约束模型。数值实验表明，可以通过新的优点函数有效解决问题。
Solutions to the linear complementarity problem (LCP) are naturally sparse in many applications such as bimatrix games and portfolio section problems. Despite that it gives rise to the hardness, sparsity makes optimization faster and enables relatively large scale computation. Motivated by this, we take the sparse LCP into consideration, investigating the existence and boundedness of its solution set as well as introducing a new merit function, which allows us to convert the problem into a sparsity constrained optimization. The function turns out to be continuously differentiable and twice continuously differentiable for some chosen parameters. Interestingly, it is also convex if the involved matrix is positive semidefinite. We then explore the relationship between the solution set to the sparse LCP and stationary points of the sparsity constrained optimization. Finally, Newton hard thresholding pursuit is adopted to solve the sparsity constrained model. Numerical experiments demonstrate that the problem can be efficiently solved through the new merit function.
