Parallel interior-point method for linear and quadratic programs with special structure (Q1608140)

The paper deals with the quadratic programming problems \(\min (1/2) x^T Q x+ c^T x\) subject to \(Ax \geq b\), \(x \geq 0\). Here \(x \in \mathbb{R}^n\) and \(A\) is an \(m \times n\)-matrix. The main step of the proposed method is the Newton iteration applied to suitably modified system of Karush-Kuhn-Tucker optimality conditions in the original problem. The global convergence of the proposed method is established. Numerical implementation of the method requires the solution of special linear system with an \(n \times n\)-matrix at each iteration. The authors suggest to solve the system by a preconditioned conjugate gradient method that is well studied for implementation on multiprocessor systems when matrix \(A\) exhibits a special structure. Applications to large-scale problems with block-angular constraint matrices are presented.