Minimizing a sum of norms subject to linear equality constraints

Numerical analysis of a class of nonlinear duality problems is presented. One side of the duality is to minimize a sum of Euclidean norms subject to linear equality constraints (the constrained MSN problem). The other side is to maximize a linear objective function subject to homogenous linear equality constraints and quadratic inequalities. Large sparse problems of this form result from the discretization of infinite dimensional duality problems in plastic collapse analysis. The solution method is based on the l1 penalty function approach to the constrained MSN problem. This can be formulated as an unconstrained MSN problem for which the first author has recently published an efficient Newton barrier method, and for which new methods are still being developed. Numerical results are presented for plastic collapse problems with up to 180 000 variables, 90 000 terms in the sum of norms and 90 000 linear constraints. The obtained accuracy is of order 10^-8 measured in feasibility and duality gap.