Second-order cone programming for frictional contact mechanics using interior point algorithm

We report experiments of an implementation of a primal-dual interior point algorithm for solving mechanical models of one-sided contact problems with Coulomb friction. The objective is to recover an optimal solution with high accuracy and as quickly as possible. These developments are part of the design of Siconos, an open-source software for modelling and simulating non-smooth dynamical systems. Currently, Siconos uses mainly first-order methods for the numerical solution of these systems. These methods are very robust, but suffer from a linear rate of convergence and are therefore too slow to find accurate solutions in a reasonable time. Our main objective is to apply second-order methods to speed up convergence. In this paper, we focus on solving a relaxed formulation of the initial mechanical model, corresponding to the optimality conditions of a convex quadratic minimization problem with second-order cone constraints. We will present in detail a primal-dual interior point algorithm for solving this type of problem. The main difficulty in implementing this algorithm arises from the fact that at each iteration of the algorithm, a change of variable, called a scaling, has to be performed in order to guarantee the non-singularity of the linear system to be solved, as well as to recover a symmetric system. Although this scaling strategy is very nice from a theoretical point of view, it leads to an enormous deterioration of the conditioning of the linear system when approaching the optimal solution and therefore to all the numerical difficulties that result from it. We will describe in detail the numerical algebra that we have developed in our implementation, in order to overcome these problems of numerical instability. We will also present the solution of the models resulting from the problems of rolling friction, for which the cone of constraints is no longer self-dual like the Lorentz cone.