Primal-dual relationship between Levenberg-Marquardt and central trajectories for linearly constrained convex optimization (Q462993)

The authors consider the problem of minimizing a smooth convex function over a bounded polyhedron which is represented by linear equality constraints and non-negative variables and has a nonempty algebraic interior. For this problem they study primal-dual versions of the so-called Levenberg-Marquardt (LM) and the central trajectory where both trajectories start at the analytic center and are represented by the same parameter. The main theorem of the paper basically reveals that, for a sufficiently large parameter, the primal-dual LM trajectory is given by primal-dual feasible points for the problem and lies close to the primal-dual central path. This result motivates a path following procedure where, in a first phase, the primal-dual LM trajectory is traced until a point in a proper neighborhood of the central path is found and, in a second phase, this point is used as a starting point for a primal-dual interior point path following method. These results are relevant for quadratic programming and particularly for the solution of trust region subproblems in nonlinear programming since for quadratic programs points on the primal-dual LM trajectory can be easily calculated by the solution of systems of linear equations. The performed computational tests relate to box constrained trust region subproblems and indicate that the new initialization procedure can spare some iterations in a path-following method for their solution.