## An Efficient Primal-Dual Interior-Point Method
for Minimizing a Sum of Euclidean Norms

###
Knud D. Andersen, Edmund Christiansen, Andrew R. Conn and Michael L. Overton

The problem of minimizing a sum of Euclidean norms dates from the 17th
century and may be the earliest example of duality in the mathematical
programming literature. This nonsmooth optimization problem arises in
many different 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 and a perturbed
complementarity condition. The main work at each step consists of
solving a system of linear equations (the Schur complement equations).
This Schur complement matrix is not symmetric, unlike in linear
programming. We incorporate a Mehrotra-type predictor-corrector
scheme and present some experimental results comparing several
variations of the algorithm, including, as one option, explicit
symmetrization of the Schur complement with a skew corrector term. We
also present results obtained from a code implemented to solve large
sparse problems, using a symmetrized Schur complement. This has been
applied to problems arising in plastic collapse analysis, with
hundreds of thousands of variables and millions of nonzeros in the
constraint matrix. The algorithm typically finds accurate solutions in
less than 50 iterations and determines physically meaningful solutions
previously unobtainable.
August, 1998.

Contact: overton@cs.nyu.edu