On tridiagonal linear complementarity problems (Q1095609)

The author proposes an iterative algorithm for solving linear complementarity problems with symmetric positive definite tridiagonal matrices. Such problems are well known to be equivalent to strictly convex quadratic programs whose constraints consist exclusively of simple lower bounds on all the variables. The linear complementarity problems with such (Stieltjes) matrices have been studied earlier, but only in the (Minkowski) case where the off-diagonal entries are nonpositive. Problems of the kind considered in this paper can always be solved in principle by many existing methods. For large scale instances, iterative (indirect) methods are particularly attractive because they preserve sparsity which can definitely be lost when pivoting (direct) methods are applied. The author transforms the equivalent quadratic programming formulation into another quadratic program to which he applies conjugate duality theory to obtain an essentially unconstrained dual problem. The latter is then treated with Newton's method.