AN EFFICIENT NEWTON BARRIER METHOD FOR MINIMIZING A SUM OF EUCLIDEAN NORMS

A new Newton barrier method is proposed for minimizing a sum of Euclid ean norms (MSN), F(x) = Sigma(i=1)(kappa) parallel to A(i)(T) x b(i) p arallel to(2). MSN is a nonsmooth problem because F is not differentia ble 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 ha s the same optimal value as F. MSN is shown to have a dual problem wit h properties very similar to duality theory in linear programming. Thi s 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 implementati on of the algorithm is described for large sparse problems and numeric al results are presented for problems with more than 270,000 nonlinear variables. These problems arise from plastic collapse analysis.