# Central path

A differentiable curve where each point is the analytic center of a polyhedron associated with a linear program. Specifically, suppose we have the primal-dual pair:

$LaTeX: P: \; \max \left\{c^Tx : x \ge 0, \; Ax \le b \right\}.$
and
$LaTeX: \; D: \; \min \left\{ y^Tb : y \ge 0, \; A^Ty \ge c \right\}.$

Let $LaTeX: s = b - Ax$ be the primal slack. Then, the primal central path is:

$LaTeX: x^*(\mu) = \arg\max \left\{c^Tx + \mu \left(\sum_j \ln(x_j) + \sum_i \ln(s_i)\right) : x > 0, \; Ax + s = b, \; s > 0 \right\},$
for $LaTeX: u > 0$, where $LaTeX: \mu$ is the penalty parameter. Let $LaTeX: d = -(c - A^y)$ be the dual surplus. Then, the dual central path is:

$LaTeX: y^*(u) = \arg\min \left\{ y^Tb - \mu \left(\sum_j \ln(d_j) + \sum_i \ln(y_i)\right): y > 0, \; A^Ty - d = c, \; d > 0 \right\},$
for $LaTeX: u > 0$. A key fact is that if the LP optimality region is nonempty and bounded, then the central path converges to its analytic center as $LaTeX: \mu \downarrow 0$.