S. Pougkakiotis and J. Gondzio
Abstract
In this paper we present a dynamic non-diagonal regularization
for interior point methods.
The non-diagonal aspect of this regularization is implicit since
all the off-diagonal elements of the regularization matrices are
cancelled out by some elements present in the Newton system
which do not contribute important information in the computation
of the Newton direction. Such a regularization has multiple goals.
The obvious one is to improve the spectral properties of the Newton
system solved at each iteration of the interior point method.
On the other hand, the regularization matrices introduce sparsity
to the aforementioned linear system, allowing for more efficient
factorizations. We also propose a rule for tuning the regularization
dynamically based on the properties of the problem, such that
sufficiently large eigenvalues of the non-regularized system are
perturbed insignicantly. This alleviates the need of finding
specific regularization values through experimentation, which
is the most common approach in literature. We provide perturbation
bounds for the eigenvalues of the non-regularized system matrix
and then discuss the spectral properties of the regularized
matrix. Finally, we demonstrate the efficiency of the method
through some numerical experiments.
Key words: Primal-dual regularization, Interior point methods.