Asymptotic analysis of the exponential penalty trajectory in linear programming (Q1341567): Difference between revisions

The practicable interior point methods for linear programming are all based on the logarithmic barrier function. The authors suggest an exponential penalty function for the same purpose in the following form: Primal problem (LP): \(\min_x \{c'x; Ax\leq b\}\), its unconstrained penalized version \((\text{P}_r)\): \(\min_x c'x+ r\sum \exp[(A_i x- b_i)/r]\). This problem has a unique solution \(x(r)\). The authors show that the trajectory \(x(r)\) is essentially a straight line directed towards the center of the optimal face of (LP) meaning that the error term tends to 0 exponentially fast as \(r\to 0\). A similar investigation is presented for the dual and the dual trajectory that show similar characteristics. The authors suggest that a path-following method could easily follow the optimal trajectory. Another advantageous feature of their approach is that, in contrast to the interior point methods, the exponential penalty function is defined everywhere. The paper discusses the theoretical aspects of the method, computational results are not reported.