The Linear Complementarity Problem
The Linear Complementarity Problem
复制标题
DOI：
10.1007/978-94-015-8330-5_3
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
P. Pardalos
中科院分区：
文献类型：
--
作者：
P. Pardalos
本文讨论了从正在进行的求解非凸线性互补问题（LCP）的更有效算法的研究中得出的一些观察结果和结论。我们将内点方法和划分技术应用于可以有效解决的问题类别。利用势约简算法，我们描述了一些可以在多项式时间内解决的问题。同样的算法也用于求解具有行充分矩阵的问题。该算法在全多项式近似时间内生成LCP的平稳点。当问题数据没有结构时，我们证明了混合整数规划问题与线性互补问题的等价性。
This paper discusses a number of observations and conclusions drawn from ongoing research into more efficient algorithms for solving nonconvex linear complementarity problems (LCP). We apply interior point approaches and partitioning techniques to classes of problems that can be solved efficiently. Using the potential reduction algorithm, we characterize some classes of problems that can be solved in polynomial time. The same algorithm is used for the solution of problems with a row-sufficient matrix. The algorithm also generates a stationary point for the LCP in fully polynomial approximation time. When the problem data has no structure, we show equivalence of mixed integer programming problems and the linear complementarity problems.