Smoothing Newton method for minimizing the sum of \(p\) -norms (Q946175)

This paper considers the problem of minimizing the sum of \(p\)-norms, where \(p\) is a fixed real number in the interval \( [1,2]\). This nondifferentiable problem arises in many applications, including the very-large-scale-integration layout problem, the facilities location problem and the Steiner minimum tree problem under a given topology. The authors establish the optimality conditions, duality and uniqueness results for the problem, and then proposed a smoothing Newton method for the problem with \(p\in [1,2]\) based on the semismooth equations derived from the optimality conditions. The method is globally and superlinearly convergent, and furthemore it is quadratically convergent when \(p\in [1,3/2] \cup\{2\}\). In particular, the quadratic convergence for \(p\in [1,3/2] \cup\{2\}\) is proved without requiring strict complementarity. Numerical experiments confirm the good theoretical properties of the method.