Dynamical system characterization of the central path and its variants-a revisit

Moody T. Chu, Matthew M. Lin

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

The notion of central path plays a fundamental role in the development of interior point methods which, in turn, have become important tools for solving various optimization problems. The central path equation is algebraic in nature and is derived from the KKT optimality conditions of a certain logarithmic barrier problem; meanwhile, the primal variable portion of the very same central path can also be cast precisely as the integral curve, known as the affine scaling trajectory, of a certain gradient-type dynamical system. The justification is easy to establish in the context of linear programming. Though expected, the generalization of such a concept to semidefinite programming is not quite as obvious due to the difficulty of addressing noncommutativity in matrix multiplication. This paper revisits the dynamical system characterization of these flows and addresses the needed details for extension to semidefinite programming by means of a simple notion of operators and a specially defined inner product. From a dynamical systems point of view, numerical ODE techniques might help us to develop some novel interior point methods.

Original languageEnglish
Pages (from-to)887-905
Number of pages19
JournalSIAM Journal on Applied Dynamical Systems
Volume10
Issue number3
DOIs
Publication statusPublished - 2011 Nov 1

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Analysis
  • Modelling and Simulation

Cite this