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.
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)