ABSTRACT
Discusses an extension of the arc-search interior-point algorithm developed in Chapter 9 to a more general problem, the so called linear complementary problem (LCP). It is explained why the convex quadratic programming problem is a special problem of linear complementary problem and how one can extend the arc-search interior-point algorithm developed in Chapter 9 to linear complementary problem. It is proved that the arc-search interior-point algorithm has the best polynomial bound that an interior-point algorithm can achieve for linear programming problem. The algorithm discussed in this chapter is also a feasible arc-search interior-point algorithm. For the reason we have mentioned many time, there is definitely a need to develop an infeasible arc-search interior-point algorithm for linear complementary problem.
