$P_*(\kappa)$线性互补问题的Mehrotra型预估-校正算法

Mehrotra-type predictor-corrector algorithm,as one of most efficient interior point methods,has become the backbones of most optimization packages.Salahi et al.proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice.We extend their algorithm to P_*（κ）linear complementarity problems.The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ο(（1+4κ）（17+19κ） √（1+2κn）^3/2log[（x⁰）^Ts⁰/ε] worst case iteration complexity bound.An numerical experiment verifies the feasibility of the new algorithm.     

求解P_*(κ)-阵线性互补问题的高阶仿射尺度内点算法

对P*(k)-阵线性互补问题提出了一种高阶内点算法.算法的每步迭代是基于线性规划原始-对偶仿射尺度算法的思想来确定迭代方向,再通过适当选取步长,得到算法的多项式复杂性.     

P*(κ)阵线性互补问题一种新的宽邻域预估-校正内点算法

基于邻近度量函数的最小值,对P*(κ)阵线性互补问题提出了一种新的宽邻域预估-校正算法,在较一般的条件下,证明了算法的迭代复杂性为O(κ+1)23n log(x0ε)Ts0.算法既可视为Miao的P*(κ)阵线性互补问题Mizuno-Todd-Ye预估-校正内点算法的一种变形,也可以视为最近Zhao提出的线性规划基于邻近度量函数最小值的宽邻域内点算法的推广.     

一类新的求解P_*(κ)阵线性互补问题的多项式内点算法

利用核函数及其性质,对P_*(k)阵线性互补问题提出了一种新的宽邻域不可行内点算法.对核函数作了一些适当的改进,所以是不同于Peng等人介绍的自正则障碍函数.最后证明了算法具有近似O((1+2k)n3/4log(nμ~0)/ε)多项式复杂性,是优于传统的基于对数障碍函数求解宽邻域内点算法的复杂性.     

非单调线性互补问题的高阶宽领域内点算法

本文研究了P(K)-阵线性互补问题宽邻域高阶内点算法.利用线性规划的原始-对偶仿射尺度算法来确定迭代方向,得到了算法的收敛性及迭代复杂性,其算法是有效可行的.     

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法：高阶Dikin型仿射尺度算法，算法的每步迭代．基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向，再适当选取步长，得到了算法的多项式复杂性。     

一个求解单调线性互补问题的高阶不可行内点算法

本文通过使用相同的矩阵因子，给出了一个求解单调线性互补问题的r-阶Mehrotra型宽城不可行内点算法，其中嵌入Wright的快速步与安全步算法．所给算法的迭代复杂性为O（n~((r 1)/r)L）．在考虑的问题有一个严格互补解的条件下，所给算法具有2阶Q-超线性收敛性．     

求解线性互补问题的一种新算法

包括数学规划、对策论、经济学和力学等应用领域中的某些问题,都可以转化成如下的线性互补问题:     

线性互补问题的宽邻域预估校正算法

对线性互补问题提出了一种新的宽邻域预估校正算法,算法是基于经典线性规划路径跟踪算法的思想,将Maziar Salahi关于线性规划预估校正算法推广到线性互补问题中,给出了算法的具体迭代步骤并讨论了算法迭代复杂性,最后证明了算法具有多项式复杂性为O(ηlog(X~0)~Ts~0/ε)。     

求解非线性互补问题的内点正算法

针对非线性互补问题,提出了与其等价的非光滑方程的内点正算法,并在一定条件下证明了该算法的收敛性定理。数值结果表明,该算法是十分有效的。     

An Asymptotical $O((k + 1)n^3L)$ Affine Scaling Algorithm for the $P_*(k)$-Matrix Linear Complementarity Problem

Based on the generalized Dikin-type direction proposed by Jansen et al in 1997, we give out in this paper a generalized Dinkin-type affine scaling algorithm for solving the $P_*(k)$-matrix linear complementarity problem (LCP). By using high-order correctors technique and rank-one updating, the iteration complexity and the total computational turn out asymptotically $O((\kappa+1)\sqrt{n}L)$ and $O((\kappa+1)n^3L)$ respectively.     

A Hybrid Smoothing-Nonsmooth Newton-Type Algorithm Yielding an Exact Solution of the $P_0$-LCP

We propose a hybrid smoothing-nonsmooth Newton-type algorithm for solving the P0 linear complementarity problem (P0-LCP) based on the techniques used in the non-smooth Newton method and smoothing Newton method. Under some assumptions, the proposed algorithm can find an exact solution of P0-LCP in finite steps. Preliminary numerical results indicate that the proposed algorithm is promising.     

Infeasible-interior-point algorithm for a class of nonmonotone complementarity problems and its computational complexity

This paper presents an infeasible-interior-point algorithm for a class of nonmonotone complementarity problems, and analyses its convergence and computational complexity. The results indicate that the proposed algorithm is a polynomial-time one.     

线性权互补问题的新全牛顿步可行内点算法

基于一个连续可微函数,通过等价变换中心路径,给出求解线性权互补问题的一个新全牛顿步可行内点算法.该算法每步迭代只需求解一个线性方程组,且不需要进行线搜索.通过适当选取参数,分析了迭代点的严格可行性,并证明算法具有线性优化最好的多项式时间迭代复杂度.数值结果验证了算法的有效性.     

水平线性互补问题的广义中心路径跟踪算法

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL).     

AN ASYMPTOTICAL O((k + 1)n~3L) AFFINE SCALING ALGORITHM FOR THE P_*(k)-MATRIX LINEAR COMPLEMENTRITY PROBLEM

1. IlltroductionAn LCP is normally for finding vectors x, s E Wu such that:where q E aam and M E Rrsxn. An LCP is called monotonic if M is positive semi-definite. Inthis paperg M is assumed to be a P*(K)--matrir[6][9] i.e. for a K 2 0, M satisfies:for any u E ac. Obviouslys positive semi-definite matrix is a p*(0)-matrix. It wajs proved in[10] that M is a P*(K)--matrix if f M is a sufficient[1].Based on Dikin's approach, Monteiro and Adler proposed in [81 an affine scaling algorith…     

A polynomial-time algorithm for a class of linear complementarity problems

Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x _i y _i = 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n ³ L) arithmetic operations by tracing the path of centers,{(x, y) S: x _i y _i = (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem.