Interior-point methods and the central path

Use the minimization form $\min c^Tx$ subject to $Ax=b$ and $x\ge0$. For a parameter $\mu>0$, replace nonnegativity by the logarithmic barrier objective $c^Tx-\mu\sum_i\log x_i$, defined only for $x_i>0$. The logarithm diverges near a zero coordinate, so a finite barrier minimizer remains inside that domain. Existence is not automatic: the equality set must admit positive points, and the barrier problem must actually attain a minimum. A convenient sufficient setting is strict primal and dual feasibility with full row rank of $A$; the following derivation assumes a barrier minimizer exists.

A dual vector $y$ for the equality constraints is unrestricted, and the minimization dual has slack $s=c-A^Ty\ge0$. Stationarity of the barrier problem gives $c-A^Ty=\mu X^{-1}\mathbf1$. Thus the selected primal and dual points are feasible and strictly positive in their inequality coordinates, with $x_is_i=\mu$ for every variable. This is perturbed complementary slackness. As the parameter shrinks, positive primal activity can coexist with a positive dual slack only through an increasingly small product. It is the product, rather than either coordinate alone, that is controlled.

For a feasible primal-dual pair in this minimization form, the gap is $c^Tx-b^Ty=x^Ts$. At an exact central point with $n$ nonnegative variables, it equals $n\mu$. Therefore the primal objective lies at most $n\mu$ above the optimal value whenever an optimum exists. This is an objective certificate, not a bound on Euclidean distance to a particular optimizer. If the optimal face contains many points, a small objective gap need not select one of them. Approximate centrality and residual errors require corresponding approximate rather than exact statements.

To move toward a smaller target parameter, linearize the primal equations, dual equations, and products simultaneously. The complementarity block is $S\Delta x+X\Delta s$, where $S$ is diagonal in the current dual slacks. Solve the resulting coupled linear system for a Newton direction and choose a step that preserves positivity. A full Newton step is not automatically safe. Practical predictor-corrector methods estimate and correct the effects of nonlinearity, while sparse factorization and careful scaling determine much of the computational cost. The smooth path does not eliminate the need for numerical linear algebra.

A short-step path-following analysis for an appropriate self-concordant barrier can bound Newton iterations by a quantity of order $\sqrt n\log(\text{initial gap}/\varepsilon)$ for target objective gap $\varepsilon$, under the algorithm's initialization and neighborhood assumptions. This is an iteration bound for a specified method, not a claim that each iteration costs constant time. Rational-input bit complexity additionally accounts for arithmetic precision, initialization, and data encoding. Polynomial-time LP algorithms are known, but a general strongly polynomial LP algorithm is still not known. One should not infer it from the attractive iteration count alone.

Lack of strict feasibility needs its own treatment, such as a suitable homogeneous embedding, a Phase I procedure, or reduction to a smaller face. It must not be handled by taking logarithms of forced zero coordinates. Infeasible-start primal-dual methods allow residuals during the search, but then the displayed gap alone does not certify a feasible answer. After convergence, check primal residuals, dual residuals, complementarity, and positivity tolerances together. A crossover procedure may produce a basis after an interior solution when a sparse vertex representation or basis sensitivity report is desired.