Central path

From Glossary

Jump to: navigation, search

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.


Views
Personal tools