Differential Algebraic Equations in Primal Dual Interior Point Optimization Methods

Abstract

Primal dual Interior Point Methods (IPMs) generate points that lie in the neighborhood of the central trajectory. The key ingredient of the primal dual IPMs is the parameterization of the central trajectory. A new approach to the parameterization of the central trajectory is presented. 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 for the barrier parameter of the primal dual IPMs is presented. The resulting ordinary differential equation combined with the first order Karush-Kuhn-Tucker (KKT) conditions, which are algebraic equations, are called differential algebraic equations (DAEs). By solving DAEs, we find an optimal solution to the given problem.