Asymptotic Convergence of the Steepest Descent Method for the Exponential Penalty in Linear Programming

We study the asymptotic behavior of the integral curves of the differential equation u̇(t) = −∇ₓf(u(t), r(t)),

where f(x, r) is the exponential penalty function associated with the linear program min{c'x : Ax ≤ b}, and r(t) decreases to 0 as t goes to ∞. We show that for each initial condition

(t_0, u_0) ( t 0 , u 0 )

the solution u(t) is defined on the whole interval

[t_0, \infty) [ t 0 , ∞ )

and, under suitable hypothesis on the rate of decrease of r(t), we establish the convergence of u(t) towards an optimal solution

u_\infty u ∞

of the linear program. In particular we find sufficient conditions for

u_\infty u ∞

to coincide with the limit of the unique minimizer x(r) of f(·, r).