Solving linear systems involved in constrained optimization (Q1902118)

The interior point methods for large scale linear, quadratic and convex programming need \((n+ m)\times (n+ m)\) systems of linear equations to be solved in each iteration. The author proposes an inexpensive iterative method for solving those systems which guarantees exact solutions to the last \(m\) equations. Current implementations solve the systems by considering an equivalent system in each iteration and reducing the task to solving an \((m\times m)\) system which has to be solved exactly and therefore the iterative methods are avoided. The typical approach uses the Cholesky factorization in every iteration step which makes the computation costly and sometimes impractical. The new algorithm, proposed in this paper, uses only one Cholesky factorization at the initial step of the interior point algorithm. The description of the method and its convergence analysis are presented. Some implementation issues and the possibility to combine the proposed method with another iterative method such as the conjugate gradient method in order to have the advantages of both are discussed. Some preliminary numerical experiments, where the objective functions are widely used functions in economics, physics and engineering are shortly reported in the last section.