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} a nd 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 pro gram and the error term eta(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectory lambda(r) whic h 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 tra jectory converges to an interior dual feasible solution.