The convergent generalized central paths for linearly constrained convex programming

Xun Qian, Lizhi LIAO, Jie Sun, Hong Zhu

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

The convergence of central paths has been a focal point of research on interior point methods. Quite detailed analyses have been made for the linear case. However, when it comes to the convex case, even if the constraints remain linear, the problem is unsettled. In [Math. Program., 103 (2005), pp. 63–94], Gilbert, Gonzaga, and Karas presented some examples in convex optimization, where the central path fails to converge. In this paper, we aim at finding some continuous trajectories which can converge for all linearly constrained convex optimization problems under some mild assumptions. We design and analyze a class of continuous trajectories, which are the solutions of certain ordinary differential equation (ODE) systems for solving linearly constrained smooth convex programming. The solutions of these ODE systems are named generalized central paths. By only assuming the existence of a finite optimal solution, we are able to show that, starting from any interior feasible point, (i) all of the generalized central paths are convergent, and (ii) the limit point(s) are indeed the optimal solution(s) of the original optimization problem. Furthermore, we illustrate that for the key example of Gilbert, Gonzaga, and Karas, our generalized central paths converge to the optimal solutions.

Original languageEnglish
Pages (from-to)1183-1204
Number of pages22
JournalSIAM Journal on Optimization
Volume28
Issue number2
DOIs
Publication statusPublished - 2018

Scopus Subject Areas

  • Software
  • Theoretical Computer Science

User-Defined Keywords

  • Continuous trajectory
  • Convex programming
  • Interior point method
  • Ordinary differential equation

Fingerprint

Dive into the research topics of 'The convergent generalized central paths for linearly constrained convex programming<sup>∗</sup>'. Together they form a unique fingerprint.

Cite this