Solving linear systems involved in constrained optimization Original Research Article

Many interior point methods for large scale linear programming, quadratic programming, the convex programming solve an (n + m) × (n + m) linear system in each iteration. The last m equations require exact solutions in order to maintain the feasibility. Current implementations reduce that step to solving an m × m linear system. The solution must be exact, because otherwise the error would be entirely passed on to the last m equations of the original system. This makes the computation costly and sometimes impractical. In this paper, we propose an inexpensive iterative method for solving that (n + m) × (n + m) system. It guarantees exact solutions to the last m equations. The convergence is proved, and the implementational issues are discussed. Some preliminary numerical results are also reported.