An efficient Newton barrier method for minimizing a sum of Euclidean norms

A new Newton barrier method is proposed for minimizing a sum of Euclidean norms (MSN), F(x) = Sigma(i=1)(kappa) parallel to A(i)(T) x b(i) parallel to(2). MSN is a nonsmooth problem because F is not differentiable at any point x where any of the norms is zero. The method used is based on approximating F with a smooth function, which in the limit has the same optimal value as F. MSN is shown to have a dual problem with properties very similar to duality theory in linear programming. This is used in the development of the method and to give a proof of when an optimal solution for the smooth approximation is epsilon-optimal (measured in the duality gap) for the original problem. An implementation of the algorithm is described for large sparse problems and numerical results are presented for problems with more than 270,000 nonlinear variables. These problems arise from plastic collapse analysis.