Masakazu Kojima

The 1992 Frederick W. Lanchester Prize was awarded to a group of five authors who have worked collectively on a long-term research program aimed at establishing a theoretical foundation for primal-dual interior point methods for linear programming and its generalization to linear complementarity problems.

The authors Masakazu Kojima and Toshihito Noma of the Tokyo Institute of Technology, Nimrod Megiddo of the IBM Almaden Research Center in San Jose, Calif., Shinji Mizuno of Wuerzburg University in Germany, and Akiko Yoshise of the University of TsuLuba in Japan were recognized for a collection of 11 articles, including the monograph entitled A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, which appeared in Lecture Notes in Computer Science, published by Springer Verlag in 1991. The other papers were:

• N. Megiddo (1989) "Pathways to the Optimal Set in Linear Programming", in: N. Megiddo, ed., Progress in Mathematical Programming: Interior Point and Related Methods, Springer-Verlag, New York) 131-158.
• M. Kojima, S. Mizuno and A. Yoshise (1989) "A Primal-Dual Interior Point Algorithm for Linear Programming", in: N. Megiddo, ed., Progress in Mathematical Programming: Interior Point and Related Methods (Springer-Verlag, New York) 29-47.
• M. Kojima, S. Mizuno and A. Yoshise (1989) "A Polynomial-Time Algorithm for a Class of Linear Complementarity Problems", Mathematical Programming, Vol.44, 1-26.
• M. Kojima, S. Mizuno and A. Yoshise (1991) "An O(sqrt{n}) Iteration Potential Reduction Algorithm for Linear Complementarity Problems", Mathematical Programming, Vol. 50, 331-342.
• M. Kojima, N. Megiddo, T. Noma and A. Yoshise (1991) "A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems", Lecture Notes in Computer Science, Vol. 538, Springer-Verlag.
• M. Kojima, N. Megiddo and S. Mizuno (1993) "Theoretical Convergence of Large-Step Primal-Dual Interior Point Algorithms for Linear Programming", Mathematical Programming, Vol. 59, 1-22.
• M. Kojima, N. Megiddo and S. Mizuno (1993) "A Primal-Dual Infeasible-Interior-Point Algorithm for Linear Programming", Mathematical Programming, Vol. 61, 263-280.
• N. Megiddo (1991) "On Finding Primal- and Dual-Pptimal bases", ORSA Journal on Computing, Vol.3, 63-65.
• M. Kojima, S. Mizuno and T, Noma (1989) "A New Continuation Method for Complementarity Problems with Uniform P-Functions", Mathematical Programming, Vol.43, 107-113.
• M. Kojima, N. Megiddo and S. Mizuno (1993) "A General Framework of Continuation Methods for Complementarity Problems", Mathematics of Operations Research, Vol. 18, 945-963.
• M. Kojima, N. Megiddo and T. Noma (1991) "Homotopy Continuation Methods for onlinear Complementarity Problems", Mathematics of Operations Research, Vol. 16, 754-774.

The citation says, in part, that their "... research has been at the forefront of the very extensive literature on interior point algorithms, which originated with the method of Karmarkar. While their work is mostly theoretical and motivated by complexity issues, it applies to practical algorithms of great economic significance in the solution of a very large-scale LP problems.

"In particular, their monograph not only provides a unified treatment of several important algorithms for the LCP, but also introduces a new matrix class important for such problems. The work is a tour de force in both the generality and power of the results and covers a very wide range of algorithms and problems; in addition, the exposition is excellent."