A LITTLE THEOREM OF THE BIG-MU IN INTERIOR-POINT ALGORITHMS

When we apply interior point algorithms to various problems including linear programs, convex quadratic programs, convex programs and comple mentarity problems, we often embed an original problem to be solved in an artificial problem having a known interior feasible solution from which we start the algorithm. The artificial problem involves a consta nt M (or constants) which we need to choose large enough to ensure the equivalence between the artificial problem and the original problem. Theoretically, we can always assign a positive number of the order O(2 L) to M in linear cases, where L denotes the input size of the problem . Practically, however, such a large number is impossible to implement on computers. If we choose too large M, we may have numerical instabi lity and/or computational inefficiency, while the artificial problem w ith M not large enough will never lead to any solution of the original problem. To solve this difficulty, this paper presents ''a little the orem of the big M'', which will enable us to find whether M is not lar ge enough, and to update M during the iterations of the algorithm even if we start with a smaller M. Applications of the theorem are given t o a polynomial-time potential reduction algorithm for positive semi-de finite linear complementarity problems, and to an artificial self-dual linear program which has a close relation with the primal-dual interi or point algorithm using Lustig's limiting feasible direction vector.