Primal-dual relationship between Levenberg-Marquardt and central trajectories for linearly constrained convex optimization
type: Item
instance of: scholarly article
title: Primal-dual relationship between Levenberg-Marquardt and central trajectories for linearly constrained convex optimization
zbMATH Open document ID: 1311.90098
author: Roger Behling
author: Gabriel Haeser
author: C. C. Gonzaga
published in: Journal of Optimization Theory and Applications
publication date: 2014-10-23T00:00:00Z
review text: 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.
reviewed by: Rembert Reemtsen
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 90C51
Mathematics Subject Classification ID: 90C46
zbMATH DE Number: 6360644
zbMATH Keywords: convex programming
zbMATH Keywords: convex quadratic programming
zbMATH Keywords: primal-dual central path
zbMATH Keywords: Levenberg-Marquardt
zbMATH Keywords: interior points
zbMATH Keywords: path following method
zbMATH Keywords: initial point
zbMATH Keywords: trust region subproblem
MaRDI profile type: Publication
full work available at URL: s10957-013-0492-4
OpenAlex ID: W2057741860
cites work: Q3738934
cites work: A method for the solution of certain non-linear problems in least squares
cites work: An Algorithm for Least-Squares Estimation of Nonlinear Parameters
cites work: On well definedness of the central path
cites work: Examples of ill-behaved central paths in convex optimization
cites work: On the existence and convergence of the central path for convex programming and some duality results
cites work: Path-Following Methods for Linear Programming
cites work: Fast convergence of the simplified largest step path following algorithm
cites work: Interior path following primal-dual algorithms. II: Convex quadratic programming
cites work: Q5691079
cites work: On central-path proximity measures in interior-point methods
cites work: On the Implementation of a Primal-Dual Interior Point Method
cites work: Numerical Optimization
cites work: Interior point methods 25 years later
DOI: 10.1007/S10957-013-0492-4
description: scientific article; zbMATH DE number 6360644