centralpath

Central path is a concept in interior-point optimization describing a smooth curve of primal-dual feasible points that interior-point algorithms follow as the barrier parameter decreases. It arises from solving a family of barrier-augmented optimization problems, which enforce strict feasibility by a logarithmic barrier at the boundary.

For a linear program in standard form: minimize c^T x subject to Ax = b, x >= 0. The barrier problem is minimize c^T x - mu sum_i log x_i subject to Ax = b, with mu > 0. The corresponding dual problem uses dual variables y and s with A^T y + s = c, s > 0. The central path consists of triples (x(mu), y(mu), s(mu)) that satisfy the barrier KKT conditions: Ax = b, A^T y + s = c, X S e = mu e, x > 0, s > 0, where X and S are diagonal matrices of x and s and e is the vector of ones.

Properties: The central path lies in the interior of the feasible region and is parameterized by mu; as mu decreases to zero, (x(mu), y(mu), s(mu)) converges to an optimal primal-dual solution of the original problem, assuming standard regularity conditions. The central path is typically unique for a given mu in convex problems with strict feasibility and is a smooth curve under mild assumptions.

Role in algorithms: Modern interior-point methods trace or approximately follow the central path by predictor-corrector steps, repeatedly solving Newton systems to move to a smaller mu while staying near the path. The distance to the path is controlled to ensure polynomial-time convergence in many cases.

Generalizations: The notion extends to conic and nonlinear programming with appropriate barrier terms; central path concepts underpin many path-following algorithms, including affine or primal-dual methods. Limitations include sensitivity to problem conditioning and the need for a strictly feasible starting point.