稀疏约束互补问题的算法研究

Sparsity constrained complementarity problems are fusions of complementarity problems and sparse optimization, which have wide applications in economy, traffic and mechanics. The problem is to find a solution of the complementarity problem that satisfies the sparse constraints, which is an NP-hard problem. The study on algorithms to the problem is just starting in the world. A lot of important problems are worth studying. Based on the demand from the real applications, we plan to do the following research work:.(1) Choose the proper complementarity functions and establish the equivalent reformulations of the sparsity constrained complementarity problem; .(2) Provide the optimality conditions to the sparsity constrained nonlinear optimization problem with particular structures;.(3) Provide projection representations on noncovex sets with particular structures and design a fast and robust projection type algorithms; .(4) Global convergence of the algorithms will be proved theorectically, the analysis on the computational complexity and the local convergence rate will be given;.(5) Algorithms will be modular designed to deal with large scale problems, and numerical experiment will be proceeded. Applications of the algorithms to real problems such as the portfolio selection and traffic equilibriums will be given.

稀疏约束互补问题是将互补问题和稀疏优化相结合的产物，在经济、交通、力学等领域有广泛应用。该问题是在互补问题的解集中寻找满足给定稀疏性限制的解，是一个NP难问题。目前对该问题的算法研究工作还处于起步阶段，有许多重要的问题值得深入研究。本项目拟紧密结合实际问题的需求，开展如下研究工作:.（1）建立稀疏约束互补问题的等价问题并给出合适的互补函数；.（2）给出带有稀疏约束的具有特殊结构的非线性优化模型的最优性条件刻画；.（3）给出具有特殊结构的非凸集合上的投影表示和设计出快速有效的投影型算法；.（4）证明新算法的全局收敛性并给出计算复杂度和局部收敛速度分析；.（5）对新算法进行模块化设计和数值实验，使之适用于大规模问题的求解，并尝试应用到投资组合和交通均衡实际问题中。

稀疏约束互补问题是将互补问题和稀疏优化这两个优化问题相结合的产物，在经济、交通、力学等领域中有着广泛的应用。该问题是在互补问题解集中寻找满足给定的稀疏性限制的解，是一个NP难问题。对稀疏约束互补问题的理论和算法进行研究，既有理论价值又有实际应用价值。.为了求解稀疏约束线性互补问题，首先设计了一种新型的互补函数，引入该函数得到了一种新的价值函数。该价值函数具有很好的微分性质。当参数满足一定条件时，该价值函数是连续可微和二次连续可微的。更有意义的是，当线性互补问题（LCP）中的矩阵是半正定时，价值函数还具有凸性。借助该价值函数，可以将稀疏线性互补问题转化为稀疏约束优化问题。该项目不仅探讨了稀疏LCP解集的存在性和唯一性，而且深入研究了稀疏LCP的解和稀疏约束优化问题的稳定点之间的关系。最后，一种二阶方法——牛顿硬阈值追踪方法（NHTP）被构建，用来求解稀疏约束优化问题。该算法被证明具有低计算复杂性和全局收敛性。针对不同的参数r和s，对比已有的HTP算法和ETA算法，进行了数值实验，实验表明NHTP算法求解成功率更高，运算速度更快。.此外，该项目还研究了混合矩阵极小化问题的算法和应用。在算法方面，将低秩矩阵、稀疏正则和非凸函数结合在一起，提出了一种新的非凸混合矩阵极小化模型，设计了增广拉格朗日方法，所得到子问题都具有显示解。在理论上证明了当参数大于一定阈值时，由算法产生的序列收敛到非凸混合矩阵极小化问题的稳定点。数值实验表明，在处理高维数据时，非凸混合矩阵模型优于现有的模型。在应用方面，针对视频分析中的动态背景提取问题，提出了一种修正全变差正则化RPCA模型，建立了一种有效地sGS-ADMM方法求解该问题并进行了收敛性分析。.另外，在抽象空间Banach空间和Hilbert空间中，针对不同类型的不动点问题、变分不等式问题、变分包含问题等变分问题，设计了多种新的算法，并获得了一系列强收敛定理。