Stable Barrier-Projection and Barrier-Newton Methods for Linear and Nonlinear Programming

A space transformation technique is used for the reduction of constrained minimization problems to minimization problems without inequality constraints. The continuous and discrete versions of stable barrier-projection method and Newton’s method are applied for solving such reduced LP and NLP problems. The space transformation modifies these methods and introduces additional matrices which play the role of a multiplicative barrier, preventing the trajectories from crossing the boundary of the feasible set. The proposed algorithms are based on the numerical integration of systems of ordinary differential equations. These algorithms do not require feasibility of starting and current points, but they preserve feasibility. Some results about convergence rate analysis for continuous and discrete versions of the methods are presented. We describe primal barrier-projection methods, primal barrier-Newton methods and primal-dual barrier-Newton methods. For LP we develop dual barrier-projection and barrier-Newton methods.