求解线性互补问题的同伦方法

It is well known that a linear complementarity problem (LCP) can be formulated as a system of nonsmooth equations F(x) = 0, where F is a map from Rninto itself. Using the aggregate function, we construct a smooth Newton homotopy H(x,t) = 0. Under certain assumptions, we prove the existence of a smooth path defined by the Newton homotopy which leads to a solution of the original problem, and study limiting properties of the homotopy path.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Superlinear Noninterior One-Step Continuation Method for Monotone LCP in the Absence of Strict Complementarity

We propose a noninterior continuation method for the monotone linear complementarity problem (LCP) by modifying the Burke–Xu framework of the noninterior predictor-corrector path-following method (Refs. 1–2). The new method solves one system of linear equations and carries out only one line search at each iteration. It is shown to converge to the LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution. Our analysis of the continuation method is based on a broader class of the smooth functions introduced by Chen and Mangasarian (Ref. 3).     

线性互补问题的一类新的带参数价值函数的阻尼牛顿法

本文给出了线性互补问题LCP(q ,M)的一类新的带参数光滑价值函数 ,基此价值函数提出了一种阻尼牛顿类算法 ,并证明了当M为P 矩阵时 ,该算法全局收敛且有限步终止 .通过数值实验说明了该算法高效可靠 .与互补问题的磨光方程组中所采用的带参数价值函数不同 ,这里的参数最终并不趋向于零 ,而是趋向于被称作解的乘子向量 (与凸非线性极小极大问题的Lagrange乘子完全一致 ) ,这一思想是本文作者首次提出来的 ,同时本文中所采用的阻尼牛顿类方法也有其独到之处 ,在互补问题的研究中有进一步发展的潜力     

A Non-Interior Continuation Algorithm for the P0 or P* LCP with Strong Global and Local Convergence Properties

We propose a non-interior continuation algorithm for the solution of the linear complementarity problem (LCP) with a P₀ matrix. The proposed algorithm differentiates itself from the current continuation algorithms by combining good global convergence properties with good local convergence properties under unified conditions. Specifically, it is shown that the proposed algorithm is globally convergent under an assumption which may be satisfied even if the solution set of the LCP is unbounded. Moreover, the algorithm is globally linearly and locally superlinearly convergent under a nonsingularity assumption. If the matrix in the LCP is a P_* matrix, then the above results can be strengthened to include global linear and local quadratic convergence under a strict complementary condition without the nonsingularity assumption.     

基于凝聚函数的互补问题的光滑化算法

对于不可微的"极大值"形式的函数,可以利用凝聚函数对其进行光滑逼近.借助这个技术,给出了求解线性互补问题的光滑方程组算法.首先是将互补问题转化为等价的非光滑方程组,再利用凝聚函数进行光滑逼近,从而转化为光滑方程组的求解问题.通过一些考题对这个算法进行了数值试验,结果显示了该算法的有效性和稳定性.     

线性互补问题模系多重网格方法的AMSOR光滑算子

为了改进求解大型稀疏线性互补问题模系多重网格方法的收敛速度和计算时间,本文采用加速模系超松弛(AMSOR)迭代方法作为光滑算子.局部傅里叶分析和数值结果表明此光滑算子能有效地改进模系多重网格方法的收敛因子、迭代次数和计算时间.     

基于凝聚函数的互补问题的自调节内点算法

对于不可微的"极大值"形式的函数,可以利用凝聚函数对其进行光滑逼近.借助这个技术,给出了求解线性互补问题的一个具有自调节功能的内点算法.基于邻近度量和线性互补问题的标准中心化方程的关系,定义了一个新的邻近度量函数,并以极小化这个函数的最优性条件代替了该中心化方程.以此在摄动方程本身建立一种自调节的机制,从而使牛顿方向能够根据上次迭代点的信息做出自适应的调整.基于改造后的摄动方程组,建立了一个具有自调节功能的内点算法.通过一些考题对这个算法进行了数值试验,结果显示了算法的有效性和稳定性.     

单调线性互补问题的Mehrotra型预估-校正算法的迭代复杂性

Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(n log((x0)T s0/ε)),同时,初步的数值实验证明了新算法是有效的.