Development of polynomial-time algorithms for solving non-monotone complementarity problems

互补问题是一个寻找满足等式约束y=f(X)和互补条件的非负向量(x，y)的问题。虽然已有一些关于单调映射f的伪多项式时间算法被提出，但众所周知，即使f是线性的，PO映射f也是NP完全的。然而，现实世界中出现的许多问题都被表述为PO互补问题。研究的目的是开发一些有效的算法来解决这些实用的非单调互补问题。为此，我们给出了一种适用于PO函数互补问题的齐次内点方法，推导了它的理论性质，并给出了一个实用的算法。我们认为，通过提供一个新的算法，我们已经达到了研究的目的，留下了关于它的收敛的一些理想的性质

The complementarity problem is a problem to find a non negative vectors (x, y) which satisfy the equality constraint y=f(x) and the complementarity condition. While some pseudo polynomial-time algorithms have been developed for monotone mappings f, it is known diet the problem with a PO mapping f is NP-complete even if f is linear. However, many problems arising from the real world have been formulated into PO complementarily problems. The aim of the research is to develop some efficient algorithms for solving these practical but non-monotone complementarity problems. To attain it, we provide a homogeneous, interior point method which can be applicable to the complementarity problems with PO functions, derive its theoretical properties and develop a practical algorithm. We consider that we have attained the aim of the research by providing a new algorithm leaving some desirable properties concerning its convergence