##
A truncated Newton interior-point algorithm for the solution
of a multicommodity spatial equilibrium model

###
L. Portugal, J. Judice, and L. Fernandez

In this paper we introduce a Truncated Newton (TN)
interior-point algorithm for solving monotone linear
complementarity problems.
Contrary to the usual Newton interior-point
methods that use exact Newton directions,
this algorithm computes at each iteration an approximate
Newton direction
by employing appropriate preconditioned
iterative linear system solvers.
The stopping criterion used in these iterative procedures is
defined in terms of the norm of the residual vector associated
to the linear constraints and guarantes global
convergence for the TN interior-point algorithm.
We describe an efficient implementation of this algorithm
for solving the Linear Complementarity Problem (LCP)
associated to the symmetric and nonsymmetric
multicommodity spatial equilibrium problems.
The Preconditioned Conjugate Gradient (PCG) or
the Preconditioned
Quasi Minimal Residual (PQMR) algorithms are incorporated
in the implementation depending on the matrix of the LCP
to be symmetric or nonsymmetric.
We also describe an incomplete QR factorization
preconditioning technique which greatly
improves the convergence properties of the PCG and
PQMR algorithms.
Finally, the stopping criterion of the TN algorithm
exploits the stucture of the network model
and leads to
an exact solution for the LCP.
We report extensive computational experience
that shows the great efficiency of the approach
discussed in this paper.