When the authors apply interior point algorithms to various problems including linear programs, convex quadratic programs, convex programs and complementarity problems, they often embed an origional problem to be solved in an artificial problem having a known interior feasible solution from which the authors start the algorithm. The artificial problem involves a constant ℳ (or constants) which they need to choose large enough to ensure the equivalence between the artificial problem and the original problem. Theoretically, the authors can always assign a positive number of the order O(2L) to ℳ 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 the authors choose too large ℳ, they may have numerical instability and/or computational inefficiency, while the artificial problem with ℳ not large enough will never lead to any solution of the original problem. To solve this difficulty, this paper presents ‘a little theorem of the big ℳ’, which will enable the authors to find whether ℳ is not large enough, and to update ℳ during the iterations of the algorithm even if they start with a smaller ℳ. Applications of the theorem are given to a polynomial-time potential reduction algorithm for positive semi-definite linear complementarity problems, and to an artificial self-dual linear program which has a close relation with the primal-dual interior point algorithm using Lustig’s limiting feasible direction vector.
