Differential-algebraic equations in primal dual interior point optimization methods: A new approach to the parameterization of the central trajectory.

Abstract

Interior Point Methods (IPMs) are iterative algorithms for mathematical optimization problems that can be interpreted as path-following procedures. Given a starting solution, the iterative scheme generates a sequence of points that converge to the optimal solution of the problem. The points specified by the iterative scheme lie on the central trajectory. The central trajectory is a smooth analytical curve in the interior of the feasible region of the problem. It starts from an interior point and ends at the optimal solution of the problem. Primal dual IPMs generate points that lie in the neighborhood of the central trajectory. The key ingredient of primal dual IPMs is the parameterization of the central trajectory. The duality gap depends linearly on the barrier parameter for the points in the central trajectory. In this research, a new approach to the parameterization of the central trajectory for primal dual IPMs is proposed. A continuous dynamical system that describes the rate of the change of the barrier parameter at the central trajectory is considered. Instead of parameterizing the central trajectory by the barrier parameter, it is parameterized by the time by describing a continuous dynamical system. Specifically, a new update rule based on the solution of an ordinary differential equation (ODE) for the barrier parameter of the primal dual IPMs is presented. The resulting ordinary differential equation combined with the first order Karush-Kuhn-Tucker conditions, which are algebraic equations, are called differential algebraic equations (DAEs). By solving DAEs, we follow approximately the central trajectory of the primal dual IPMs. By doing so, we find an optimal solution to the given problem.

The proposed parameterization of the central trajectory for primal dual IPMs is investigated both for linear and convex quadratic optimization problems and primal dual IPMs are modified by using new parameterization. In addition, convergence, implementation, computational complexity and stability issues of the proposed parameterization of the central trajectory are also investigated. Some computational results for the proposed parameterization of the central trajectory for linear and convex quadratic optimization problems and applications to support vector machines (SVMs) for the classification problem are presented.