Abstract

We study the asymptotic behavior of the integral curves of the differential equation u̇(t) = −∇ₓf(u(t), r(t)), u(t0)=u0u(t_0) = u_0 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 (t0,u0)(t_0, u_0) the solution u(t) is defined on the whole interval [t0,∞)[t_0, \infty) and, under suitable hypothesis on the rate of decrease of r(t), we establish the convergence of u(t) towards an optimal solution u∞u_\infty of the linear program. In particular we find sufficient conditions for u∞u_\infty to coincide with the limit of the unique minimizer x(r) of f(·, r).

Author information

Contact details are reproduced from the original publication and may be historical.

R. Cominetti

Universidad de Chile, Casilla 170/3 Correo 3, Santiago, Chile.

Keywords

  • linear programming
  • exponential penalty
  • steepest descent
  • asymptotic behavior
  • nonlinear evolution equations

References

  1. H. Attouch, R. Cominetti: A dynamical approach to convex minimization coupling approximation with the steepest descent method, submitted 1994.Google Scholar
  2. H. Brézis: Opérateurs maximaux monotones et semigroups de contractions dans les espaces de Hilbert, Mathematical Studies 5, North Holland 1973.Google Scholar
  3. R. Brück: Asymptotic convergence of nonlinear contraction semigroups in Hilbert space, Journal of Functional Analysis 18 1975, 15–26.https://doi.org/10.1016/0022-1236(75)90027-0Google Scholar
  4. T. Cazenave, A. Haraux: Introduction aux problèmes d’évolution semi-linéaires, Mathématiques & Applications 1, Ellipses 1993.Google Scholar
  5. R. Cominetti, J. San Martín: Asymptotic behavior of the exponential penalty trajectory in linear programming, Mathematical Programming 67 1994, pp. 169–187.https://doi.org/10.1007/BF01582220Google Scholar
  6. H. Furuya, K. Miyashiba, N. Kenmochi: Asymptotic behavior of solutions to a class of nonlinear evolution equations, Journal of Differential Equations 62 1986, 73–94.https://doi.org/10.1016/0022-0396(86)90106-3Google Scholar
  7. A. Haraux: Nonlinear Evolution Equations: Global Behavior of Solutions, Lecture Notes in Mathematics 841, Springer-Verlag 1981.https://doi.org/10.1007/BFb0089606Google Scholar
  8. A. Pazy: Semigroups of linear operators and applications to partial differential equations, Springer-Verlag, New York 1983.https://doi.org/10.1007/978-1-4612-5561-1Google Scholar

Suggested citation

R. Cominetti. “Asymptotic Convergence of the Steepest Descent Method for the Exponential Penalty in Linear Programming.” Journal of Convex Analysis 2 (1995), No. 1&2, 145–152. https://doi.org/10.68381/jca02009

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 1995. Rights now held by Banach Press LLC.