Applying a Newton method to strictly convex separable network quadratic programs

Abstract

By introducing quadratic penalty terms, a strictly convex separable network quadratic program can be reduced to an unconstrained optimization problem whose objective is a continuously differentiable piecewise quadratic function. A recently developed nonsmooth version of Newton's method is applied to the reduced problem. The generalized Newton direction is computed by an iterative procedure which exploits the special network data structures that originated from the network simplex method. New features of the algorithm include the use of min-max bases and a dynamic strategy in computation of the Newton directions. Some preliminary computational results are presented. The results suggest the use of "warm start" instead of "cold start.".