垂直线性互补问题的一种光滑算法

A SMOOTH ALGORITHM FOR VERTICAL LINEAR COMPLEMENTARITY PROBLEMS

文中给出了垂直线性互补问题的一个新的光滑价值函数,不同于光滑化方法中的价值函数,它不包含任何必须趋向零的参数,因此算法中不涉及参数调整步骤,而且具有良好的强制性.基此价值函数,提出了求解垂直线性互补问题的一种阻尼Newton类算法,并证明了该算法对竖块P_0+R_0矩阵的垂直线性互补问题具有全局收敛性;当解满足相当于BD-正则条件时,算法具有局部二次收敛性;在不增加额外校正步骤(算法的每个迭代步只求解一个Newton方程)的情形下,算法对竖块P-矩阵垂直线性互补问题(无须假设严格互补),具有有限步收敛性.数值实验结果令人满意.

A new smooth merit function was constructed for vertical linear complementarity problems（VLCPs）. The merit function has good coercive property, and differently from that used in the smoothing methods for VLCPs, there is no smoothing parameter in it. As a result, a damped Newton-type algorithm which based on the merit function was presented. The global convergence result was obtained for VLCPs with vertical block P0 ＋ R0 matrix, and the local quadratic convergence result was shown when the solution of VLCP is BD-regular. Furthermore, without using the hybrid switch technique or additional step as corrector Newton step as usual（only a system of linear equations was solved in each iteration）, and without assuming strict complementarity, the finite termination property was obtained for VLCPs with vertical block P matrix. Numerical results suggest that the method is promising.