An efficient primal-dual interior-point method for minimizing a sum of Euclidean norms

The problem of minimizing a sum of Euclidean norms dates from the 17th cent ury and may be the earliest example of duality in the mathematical programm ing literature. This nonsmooth optimization problem arises in many differen t kinds of modern scientific applications. We derive a primal-dual interior -point algorithm for the problem, by applying Newton's method directly to a system of nonlinear equations characterizing primal and dual feasibility a nd a perturbed complementarity condition. The main work at each step consis ts of solving a system of linear equations (the Schur complement equations) . This Schur complement matrix is not symmetric, unlike in linear programmi ng. We incorporate a Mehrotra-type predictor-corrector scheme and present s ome experimental results comparing several variations of the algorithm, inc luding, as one option, explicit symmetrization of the Schur complement with a skew corrector term. We also present results obtained from a code implem ented to solve large sparse problems, using a symmetrized Schur complement. This has been applied to problems arising in plastic collapse analysis, wi th hundreds of thousands of variables and millions of nonzeros in the const raint matrix. The algorithm typically finds accurate solutions in less than 50 iterations and determines physically meaningful solutions previously un obtainable.