CENTRAL PATH
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:
- P: Max cx: x >= 0, Ax <= b.
- D: Min yb: y >= 0, yA >= c.
Let s = b - Ax (primal slack ). Then, the
primal central path is:
x*(u) = argmax(cx + u[Sum_j(ln(x_j)) + Sum_i(ln(s_i))]: x, s > 0) for u > 0,
where u is the penalty parameter. Let d = -(c - yA) (dual surplus ). Then, the
dual central path is:
y*(u) = argmin(yb - u[Sum_j(ln(d_j)) + Sum_i(ln(y_i))]: d, y > 0) for u > 0.
A key fact is that if the LP optimality region is nonempty and bounded, the central path converges to its analytic center as u–>0.
