A symmetric Primal-Dual Newton method for minimizing sum of norms

Knud D. Andersen and Edmund Christiansen.

We present a symmetric Newton primal-dual method for minimizing a sum of norms (MSN) which is a convex non smooth problem. The method is develop using Newtons method at complementarity conditions subject to primal and dual feasibility. The first derivative of this non-linear system is non symmetric and the Newton steps is therefore explicitly symmetries. This means that the described method only are a pseudo Newton method, however in practice the number of iterations is similar to the number of iterations for primal-dual methods for linear programming. We furthermore describe how to use high-order and recentering in this method. The linear constraints are handled using an exact L1 penalty function as already described in an earlier paper, but we describe an improve method for increasing and decreasing the weight at the L1 penalty function. Numerical results are presented for large sparse problems arising in plastic collapse analysis. These results show that the new method is more efficient in measurement of iterations and time (up to over 3 times for large non-smooth problems) than a primal method. The method have been implemented in a portable C-code called GOPT (please note that GOPT is short for Global Optimizer and nothing else), for solution of large sparse MSN problems. Some implementation details will be given.