A convergence result for non-autonomous subgradient evolution equations and its application to the
steepest descent exponential penalty trajectory in linear programming
Jean-Bernard Baillon,
CERMSEM
Roberto Cominetti*,
Universidad de Chile
Résumé.
On présente un nouveau résultat concernant le comportement asymptotique des équations d'évolution
non-autonome de la forme u(t) appartient à d jt (u(t))
où jt est le sous-différentiel des fonctions convexes
s.c.i. propre jt paramétrées par t. Le résultat
est utilisé pour étudier les trajectoires engendrées par jt(x) = f(x,r(t)) où f(x,r) := cTx + r S
exp [(Aix - bi)/r] est la pénalité exponentielle du problème de
programmation linéaire min{c Tx : Ax £ b} avec r(t) une fonction
positive tendant vers 0 quand t tend vers l'infini. On prouve que la trajectoire u(t) converges vers une
solution optimale u infini du problème de programmation linéaire. On donne des conditions pour
que la trajectoire du problème dual associé mi(t) :
exp[(Ai u(t) - bi)/ r(t)] converge vers une solution optimale du problème de
programmation linéaire dual.
Mots clés :
Equations d'évolutions, pénalité exponentielle, programmation linéaire.
Abstract.
We present a new result on the asymptotic behavior of non-autonomous subgradient evolution equations
of the form u(t) appartient à d jt, where {jt : t greater than or equal to 0} is a family of closed proper convex functions.
The result is used to study the flow generated by the family jt(x) = f(x,r(t)) where f(x,r) := cTx + r Sexp [(Aix - bi)/r] is the exponential penalty approximation of the
linear program min{c Tx : Ax £b}, and r(t) is a positive function
tending to 0 when t tend vers l'infini. We prove that the trajectory u(t) converges to an optimal solution u
infini of the linear program, and we give conditions for the convergence of the associated dual trajectory
mi(t) : exp[(Ai u(t) - bi)/ r(t)] towards an
optimal solution of the dual program.
Keywords :
Evolution equations, exponential penalty, linear programming.
AMS Classification :
34C35, 34D05, 49M10, 49M30, 90C25.
*Universidad de Chile, Casilla 170/3, Correo 3, Santiago, Chile.
