互补问题的稀疏解

发布时间：2018-07-22 15:26

【摘要】：互补问题是优化领域中的一个经典而重要的研究课题.它在工程、经济与交通均衡等领域都有着广泛的应用.而稀疏优化是优化领域的一个新的研究课题,它的理论、模型和算法正在迅猛发展.求互补问题的稀疏解,是互补问题和稀疏优化两课题的融合,具有重要的理论和应用价值.本文初步探讨了互补问题稀疏解的一些理论,例如存在性和唯一性等,并提出了四种有效算法求解互补问题的稀疏解.主要结果概括如下：针对线性互补问题稀疏解,在理论方面,给出了Z矩阵线性互补问题稀疏解的唯一性.在算法设计方面,借助FB互补函数,提出了一个带有p(0p1)范数正则项的无约束极小化模型.该模型随着正则参数的减小能够很好地逼近稀疏解.随后建立了局部最优解每一非零分量的阈值下界.该下界在数值计算中,对确定零分量起到了精确的界定作用；接着考虑了如何选取合适的正则参数,使最优解达到希望的稀疏度；最后,基于以上理论,提出序列光滑梯度算法(SSG)来求解lp范数正则极小化模型.数值实验表明SSG算法能够有效地求解lp范数正则极小化模型并得到线性互补问题的稀疏解.为了进一步提高求解线性互补问题稀疏解算法的效率,我们将互补约束转化为投影形式的不动点方程,由此提出了一个带有f1范数正则项的投影约束极小化模型.紧接着给出了正则问题子问题解的阈值表示定理,并由此设计了一种收缩阈值投影算法(STP).最后,应用此算法求解上述l1正则投影极小化问题,并给出了算法的收敛性.数值实验表明,STP算法能有效的求解l1正则投影极小化模型,而且能得到]LCPs的高质量稀疏解.在求解线性互补问题稀疏解时,为了更好的逼近向量的l0范数,我们提出了一个带有l1/2范数正则项的投影约束极小化模型,进而设计了一种半阈值投影算法(HTP),并建立了算法的收敛性.最后数值试验说明HTP算法能有效求解l1/2正则投影极小化问题,并且输出LCPs的高质量稀疏解.针对非线性互补问题的稀疏解,首先提出了一种带有f1范数正则项的投影约束极小化模型,接着设计了外梯度阈值算法(ETA)并给出了算法的收敛性分析,证明了ETA算法产生的序列的任一聚点就是NCP问题的解.最后,数值实验显示ETA算法能有效求解l1正则投影极小化模型,并且能输出余强制非线性互补问题的高质量稀疏解.最后总结了本文的主要贡献,并对进一步可能的研究方向进行了展望.
[Abstract]:Complementarity problem is a classical and important research topic in the field of optimization. It is widely used in engineering, economy and traffic balance. Sparse optimization is a new research topic in the field of optimization, and its theory, model and algorithm are developing rapidly. Finding the sparse solution of the complementarity problem is the fusion of the complementary problem and the sparse optimization problem, which has important theoretical and practical value. In this paper, we discuss some theories of sparse solution of complementarity problem, such as existence and uniqueness, and propose four effective algorithms to solve sparse solution of complementarity problem. The main results are summarized as follows: for the sparse solution of linear complementarity problem, the uniqueness of sparse solution for Z-matrix linear complementarity problem is given in theory. In the aspect of algorithm design, an unconstrained minimization model with p (0p1) norm canonical term is proposed by means of FB complementary function. The model can approach the sparse solution well with the decrease of the regular parameters. Then the threshold lower bound for each nonzero component of the local optimal solution is established. The lower bound plays an accurate role in determining the zero component in the numerical calculation. Then it considers how to select the appropriate regular parameters to make the optimal solution reach the desired sparsity. Finally, based on the above theory, A sequential smooth gradient algorithm (SSG) is proposed to solve the LP norm canonical minimization model. Numerical experiments show that the SSG algorithm can effectively solve the LP norm canonical minimization model and obtain the sparse solution of the linear complementarity problem. In order to further improve the efficiency of sparse solution algorithm for linear complementarity problems, we transform complementary constraints into fixed point equations in projection form, and propose a projective constraint minimization model with F 1 norm regular term. Then, the threshold representation theorem of the solution of the subproblem of the regular problem is given, and a shrinkage threshold projection algorithm (STP) is designed. Finally, the algorithm is applied to solve the above l _ 1 regular projection minimization problem, and the convergence of the algorithm is given. Numerical experiments show that the STP algorithm can effectively solve the L _ 1 regular projection minimization model, and can obtain the high quality sparse solution of] LCPs. In order to better approximate the L _ 0 norm of vector, we propose a projective constrained minimization model with L _ 1 / 2 norm canonical term when solving sparse solution of linear complementarity problem. Then a semi-threshold projection algorithm (HTP) is designed and its convergence is established. Finally, numerical experiments show that the HTP algorithm can effectively solve the l / 2 regular projection minimization problem and output the high quality sparse solution of LCPs. For the sparse solution of nonlinear complementarity problem, a projective constrained minimization model with F 1 norm canonical term is proposed, and then the external gradient threshold algorithm (ETA) is designed and the convergence of the algorithm is analyzed. It is proved that any accumulation point of the sequence generated by the ETA algorithm is the solution of the NCP problem. Finally, numerical experiments show that the ETA algorithm can effectively solve the L 1 regular projection minimization model, and can output the high quality sparse solution of the complementary forced nonlinear complementarity problem. Finally, the main contributions of this paper are summarized, and the further possible research directions are prospected.
【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O221

【相似文献】