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

DOI10.1007/S10957-013-0492-4MaRDI QIDQ462993zbMATH OpenOpenAlexFDO

Authors Roger Behling, Gabriel Haeser, C. C. Gonzaga

Publication date 23 October 2014

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10957-013-0492-4

zbMATH Keywords

convex programmingconvex quadratic programminginitial pointinterior pointsLevenberg-Marquardtpath following methodprimal-dual central pathtrust region subproblem

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Nonlinear programming (90C30) Optimality conditions and duality in mathematical programming (90C46) Interior-point methods (90C51)

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.

Recommendations

• On the Resolution of Linearly Constrained Convex Minimization Problems
• On the Levenberg-Marquardt methods for convex constrained nonlinear equations
• Infeasible primal-dual algorithm for minimizing convex quadratic problems
• A new primal-dual path-following interior-point algorithm for linearly constrained convex optimization
• scientific article; zbMATH DE number 269555

Cites work

• A method for the solution of certain non-linear problems in least squares
• An Algorithm for Least-Squares Estimation of Nonlinear Parameters
• Examples of ill-behaved central paths in convex optimization
• Fast convergence of the simplified largest step path following algorithm
• scientific article; zbMATH DE number 3972641 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• Interior point methods 25 years later
• Numerical Optimization
• On central-path proximity measures in interior-point methods
• On the existence and convergence of the central path for convex programming and some duality results
• On the Implementation of a Primal-Dual Interior Point Method
• On well definedness of the central path
• Path-Following Methods for Linear Programming

Cited in

(1)

• A primal-dual interior-point method based on various selections of displacement step for symmetric optimization

This page was built for publication: Primal-dual relationship between Levenberg-Marquardt and central trajectories for linearly constrained convex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462993)