| Complementary problem has wide applications in many fields such as economics, game theory. The research on nonlinear science and compute science is always active, and we got many good conclusions on the algorithms to solve the complementary problem. In these algorithms, interior point algorithm is especially active in mathematical programming. For interior point algorithm has a good polynomial complexity, especially for large-scale problems in practice.Thanks to these merits, we hope interior point algorithm can solve common complement ary problem not only in the Euclidean space but also in matrices. After much research, M Koji ma and S Shidoh and S Hara gave the definition of the semi-definite linear complementary problem in matrices.This problem enjoys a close analogy with the LCP in the Euclidean space. In particular, the central trajectory leading to a solution of the problem exists under the non emptyness of the interior of the feasible region and a monotonicity assumption on the affine subspace.In this paper, based on the theory of the monotone semi-definite linear complementary problem in symmetric matrices by M Kojima, we construct a new interior-point algorithm with the use of the Nesterov-Todd equation to solve the complementary problem. Nesterov-Todd equations are better than Newton directions, because the matrices in them are always symmetric in iterations.Respectively, we construct path-following algorithm and potential-reduction algorithm. In the path-following algorithm, we modify step size parameter equal to 1 and use a narrow neighborhood of the central trajectory. Then we discuss the feasibility and the convergence. In the potential-reduction algorithm, we choose initial point, which can be infeasible, and then we make use of linear detection to choose step size. And we prove its feasibility and compute the least reduction. In the end, due to the restrictions of monotonicity, we extend the result to p (Ï„) arithmetic operator in the path-following algorithm.
|
PDF Full Text Request