ASYMPTOTIC ANALYSIS OF THE EXPONENTIAL PENALTY TRAJECTORY IN LINEAR-PROGRAMMING

We consider the linear program min {c'x: Ax less than or equal to b} and the associated exponential penalty function f(r)(x) = c'x + r Sigma exp[(A(i)x - b(i))/r]. For r close to 0, the unconstrained minimizer x(r) of f(r) admits an asymptotic expansion of the form x(r) = x* + rd* + eta(r) where x* is a particular optimal solution of the linear program and the error term eta(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectory lambda(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis when r tends to infinity: the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.