Limiting behavior of weighted central paths in linear programming (Q1338144): Difference between revisions

Given the linear programming problem (P): \(\min c^T x\), s.t. \(Ax= b\), \(x\geq 0\), and its dual (D): \(\max b^T y\), s.t. \(A^T y+ s= c\), \(s\geq 0\), with \(A\in \mathbb{R}^{m\times n}\), \(b\in \mathbb{R}^m\) and \(c\in \mathbb{R}^n\), the paper discusses the solutions \((x(\mu), s(\mu))\) of the weighted penalized problems (P\('\)): \(\min c^T x- \mu \sum^n_{i= 1} \omega_i \ln(x_i)\) and (D\('\)): \(\min b^T y+ \mu \sum^n_{i= 1} \omega_i \ln(s_i)\), s.t. to the same restrictions, for \(\mu\in (0, \infty)\) and \(\omega> 0\). In particular, the limiting behaviour of the derivatives \((x^{(k)}(\mu), s^{(k)}(\mu))\), \(\mu> 0\), of the \(\omega\)-central path \((x(\mu), s(\mu))_{\mu> 0}\) is studied when \(\mu\) approaches zero and infinity. It is shown that the derivatives converge if \(\mu\) approaches zero and that the higher order derivatives vanish at infinity. The author concludes that these observations should be helpful in the construction of new locally fast interior-point algorithms.