Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization (Q2250064)

The authors investigate ways to efficiently deal with rank-degeneracy in linear optimization (that is, the dual problem has many more constraints than variables). Specifically, the first constraint-reduced primal-dual interior-point scheme proposed is based on a type of regularization of the Newton-KKT system, and the second on a new type of search direction called the ``kernel'' step, which can be viewed as a limiting case of the first. Both algorithms are analyzed and proved to converge globally and locally with quadratic rate under mild assumptions. Effectiveness of both algorithms is demonstrated by numerical experimentations, which suggest that, depending on the class of problems of interest, one or the other of these algorithms is superior.