Journal of Convex Analysis Volume 2 (1995), No.1/2, 145–152

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

R. Cominetti^{1}

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

Received 30 May 1994 Revised manuscript received 6 February 1995

Dedicated to R. T. Rockafellar on his 60th Birthday

We study the asymptotic behavior of the integral curves of the differential equation

u̇(t) = −∇_{x}f(u(t), r(t)), u(t0) = u0

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) the solution u(t) is defined on the whole interval [t0, ∞) and, under suitable hypothesis on the rate of decrease of r(t), we establish the convergence of u(t) towards an optimal solution u_{∞} of the linear program. In particular we find sufficient conditions for u_{∞} to coincide with the limit of the unique minimizer x(r) of f(·, r).

Keywords : linear programming, exponential penalty, steepest descent, asymptotic behavior, nonlinear evolution equations.

1991 Mathematics Subject Classification: 90C05, 90C25, 90C31, 49M30.

1. Introduction

In this paper we study the asymptotic behavior of a non-autonomous nonlinear evolution equation of the form

(E) \{ \begin{matrix}u̇(t) & = −∇_{x}f(u(t), r(t)) \\ u(t_{0}) & = u_{0} \end{matrix}

where f(x, r) is convex and differentiable with respect to the x variable for every fixed r > 0, and r(t) is a positive real differentiable function decreasing to 0 as t → ∞. Our motivation for studying such type of evolution equations comes from the coupling of the steepest descent method with different approximation and/or regularization schemes for optimization problems. Namely, we interpret the function f(·, r) as a smooth convex

1 Partially supported by Fondecyt 93/1100.

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

146 R. Cominetti / Asymptotic convergence of the steepest descent method

approximation of a certain lower semicontinuous convex function f_{0} which we are willing to minimize. The approximation f(·, r) is assumed to converge to f_{0} when r ↓ 0, so that the evolution equation (E) corresponds to applying the steepest descent method to the approximating functions while simultaneously controlling the degree of approximation by means of a parameter function r(t). More precisely, in the present work we consider the specific case of the exponential penalty function

f(x, r) := c′x + r ∑_{i=1}^{m} exp[(A_{i}x − b_{i})/r]

which is a smooth approximation for the function

f_{0}(x) = \{ \begin{matrix}c′x & if Ax ≤ b \\ +∞ & otherwise \end{matrix}

associated with a linear program of the form

(P) min_{x} {c′x : Ax ≤ b}.

Our goal is to find conditions on the function r(t) to ensure that the integral curves of (E) converge as t → ∞ towards an optimal solution of (P). Evolution equations, specially in infinite dimensional spaces, have received a great deal of attention since many physical phenomena fall into such framework (see e.g. [2], [4], [7], [8]). For autonomous subdifferential inclusions of the form

(A) \{ \begin{matrix}u̇(t) ∈ −∂f_{0}(u(t)) \\ u(t_{0}) = u_{0} \end{matrix}

the asymptotic convergence of its integral curves towards a minimizer of f_{0} was established by Brézis [2] and Brück [3]. The asymptotic convergence for so-called semi-autonomous differential inclusions may also be found in [2], [7]. Fully non-autonomous evolution equations have been considered recently by Furuya, Miyashiba and Kenmochi [6]. Roughly speaking, they consider the case in which the approximating functions f(·, r(t)) approach the limit function f_{0} sufficiently fast, so that the asymptotic behavior of the non-autonomous system (E) is close to the one of the autonomous system (A). This approach leads to results requiring a fast convergence of r(t) towards 0. In this work we consider the specific setting of exponential penalties in linear programming [5], and we present two results on the asymptotic convergence of (E), which go in some sense in opposite directions in terms of assumptions. The first one is concerned with the case of a function r(t) converging to zero sufficiently fast, being close in spirit to the results in [6]. Nevertheless, the conditions we obtain are more explicit and seem to be weaker than the ones imposed by the abstract results in [6]. The second result considers the opposite situation: we show that asymptotic convergence will also be attained if the function r(t) goes to zero sufficiently slow. An advantage of this second approach is that the limit point of the integral curve may be identified and characterized in variational terms.

The paper is organized as follows. In section 2 we review the basic results concerning the exponential penalty trajectory in linear programming needed for the asymptotic convergence analysis of (E). The existence of global solutions for (E) as well as the asymptotic convergence towards an optimal solution of (P) are then presented in section 3.

2. Preliminaries

Let us consider the linear program

(P) min_{x} {c′x : Ax ≤ b}

where c ∈ IR^{n}, A is an m × n matrix of full rank n ≤ m, and b ∈ IR^{m}. We assume throughout that the optimal solution set of (P), which we denote by S, is nonempty and bounded. Equivalently, this amounts to suppose that the dual problem

(D) min_{λ} {b′λ : A′λ + c = 0, λ ≥ 0},

has a strictly positive feasible solution. Following [5], for each r > 0 we consider the unconstrained penalized problem

(P_{r}) min_{x} c′x + r ∑_{i∈I} exp[(A_{i}x − b_{i})/r]

where A_{i} denote the rows of A for i ∈ I := {1, …, m}. The dual problem of (P_{r}) is

(D_{r}) min_{λ} {b′λ + r ∑_{i∈I} λ_{i}(ln λ_{i} − 1) : A′λ + c = 0, λ ≥ 0} ,

which can be interpreted as a penalty method which introduces the positivity constraints of (D) into the objective function through the barrier term “r ∑ λ_{i}(ln λ_{i} − 1)”. From [5, Prop. 2.1] we know that both problems (P_{r}) and (D_{r}) have unique optimal solutions x(r) and λ(r) respectively, which are related as

λ_{i}(r) = exp[(A_{i}x(r) − b_{i})/r],

and are of class C^{∞} on the open interval (0, ∞). Moreover, according to [5, Thm. 5.8], when r tends to 0 the primal trajectory x(r) approaches (quite rapidly indeed) a straight line directed towards a center of the optimal face of (P). More precisely we have the asymptotic expansion

x(r) = x^{∗} + rd^{∗} + η(r)

where x^{∗} is an optimal solution of (P) which is called centroid, the directional derivative d^{∗} is completely characterized in variational terms, and the error η(r) goes to zero exponentially fast, that is, at the speed of exp(−μ/r) for some μ > 0. For the dual trajectory it turns out [5, Thm. 5.8] that λ(r) behaves asymptotically as a constant, that is

λ(r) = λ^{∗} + ν(r),

Figure 1. An example of primal (a) and dual (b) trajectories.

where λ^{∗} is a center of the optimal face of (D) and the error ν(r) goes to zero exponentially fast as r goes to 0. We recall a couple of additional properties which we shall use in section 3 (these may also be found in [5]). Firstly we remark that the centroid x^{∗} is a (relative) interior point of the optimal face S. Namely, denoting

I_{0} = {i ∈ I : A_{i}x = b_{i} for all x ∈ S}

the set of constraints which are binding at every optimal solution of (P), we have

A_{i}x^{∗} < b_{i} for all i ∉ I_{0}.  (2.1)

Secondly, the derivative of x(r) stays bounded as r goes to zero. In fact we have

\frac{dx}{dr}(r) = d^{∗} + ρ(r)

with ρ(r) converging exponentially fast towards 0.

3. The steepest descent method

In the sequel we denote by f(x, r) the exponential penalty function

f(x, r) = c′x + r ∑_{i∈I} exp[(A_{i}x − b_{i})/r].

In [5] it was suggested that the asymptotic straight line character of the primal trajectory x(r), should make it easy for a predictor-corrector method to trace this path approximately. However, instead of being forced to follow and stay close to a single trajectory, the task would be alleviated if we had a flow on IR^{n} whose integral curves converged towards the optimal set S. This leads us to consider the continuous steepest descent equation

(E) \{ \begin{matrix}u̇(t) = & − ∇_{x}f(u(t), r(t)) \\ u(t_{0}) = & u_{0} \end{matrix}

where r : [t_{0}, ∞) ⟶ IR_{+} is a given continuously differentiable decreasing function such that

lim_{t→∞} r(t) = 0.

Theorem 3.1. For each initial condition u_{0}, problem (E) has a unique solution u(t) which is defined on all of [t_{0}, ∞) and stays bounded as t → ∞.

Proof. Since the mapping (x, t) ⟶ ∇_{x}f(x, r(t)) is locally lipschitz we have local existence and uniqueness for (E), so that all we need is to establish an a priori bound for u(t). To this end let us consider the function

φ(t) = \frac{1}{2}∥u(t) − x(r(t))∥^{2}.

The optimality of x(r), the convexity of f(·, r) and equation (E) imply that

0 ≤ f(u(t), r(t)) − f(x(r(t)), r(t)) ≤ ⟨−u̇(t), u(t) − x(r(t))⟩.  (3.1)

Denoting Δ(t) := ⟨−u̇(t), u(t) − x(r(t))⟩, taking a constant M such that

∥\frac{dx}{dr}(r)∥ ≤ \sqrt{2}M for all r < r(t_{0}),

and observing that ṙ(t) ≤ 0, we obtain

0 ≤ Δ(t) = −φ̇(t) − ṙ(t)⟨\frac{dx}{dr}(r(t)), u(t) − x(r(t))⟩ ≤ −φ̇(t) − 2M\sqrt{φ(t)}ṙ(t). (3.2)

It follows that φ̇(t) ≤ −2M\sqrt{φ(t)}ṙ(t) from which one easily gets

\sqrt{φ(t)} ≤ \sqrt{φ(t_{0})} + M[r(t_{0}) − r(t)] ≤ \sqrt{φ(t_{0})} + Mr(t_{0}).  (3.3)

Since x(r(t)) stays bounded as t → ∞, we deduce that u(t) stays bounded as well.

We intend to prove that the solution u(t) of (E) converges, when t goes to infinity, towards an optimal solution u_{∞} of the linear program (P). To this end we need some assumptions on the rate of decrease of r(t) towards 0. We shall distinguish two cases:

Fast Decay: ∫_{t_{0}}^{∞} r(t) exp(−α/r(t))dt < ∞ for all α > 0,

Slow Decay: ∫_{t_{0}}^{∞} \frac{1}{r(t)} exp(−K/r(t))dt = ∞ for all K > 0.

Fast Decay holds for instance when r(t) = 1/t^{a} with a > 0, while Slow Decay holds in the case r(t) = 1/ ln(ln t). For r(t) = 1/ ln t neither Fast nor Slow Decay is satisfied.

Theorem 3.2. If r(t) satisfies the assumption of Fast Decay, then the solution u(t) of (E) converges towards a particular solution u_{∞} ∈ S.

Proof. We split the proof into 4 steps. Step 1: Existence of lim ∥u(t) − x(r(t))∥ = lim ∥u(t) − x^{∗}∥. Letting K = 2M[\sqrt{φ(t_{0})} + Mr(t_{0})] and using (3.2) and (3.3) we have φ̇(t) + Kṙ(t) ≤ 0. Then the function φ(t)+Kr(t) is positive and decreasing so that it has a finite limit when t → ∞. The convergence of φ(t) follows at once and, since x(r(t)) converges to x^{∗}, we conclude the existence of

lim_{t→∞} ∥u(t) − x(r(t))∥ = lim_{t→∞} ∥u(t) − x^{∗}∥.

Step 2: Δ(t) belongs to L^{1}(t_{0}, ∞). This follows from (3.2) taking into account that 2M\sqrt{φ(t)} ≤ K and

∫_{t_{0}}^{∞}[−φ̇(τ) − Kṙ(τ)]dτ ≤ φ(t_{0}) + Kr(t_{0}).

Step 3: Existence of lim ∥u(t) − ū∥ for all ū ∈ S. Let ū ∈ S. Since

∥u(t) − ū∥^{2} = ∥u(t) − x^{∗}∥^{2} + ∥x^{∗} − ū∥^{2} − 2⟨x^{∗}, x^{∗} − ū⟩ + 2⟨u(t), x^{∗} − ū⟩,

the existence of lim ∥u(t) − ū∥ is equivalent to the existence of

lim_{t→∞}⟨u(t), x^{∗} − ū⟩.

To prove this fact we shall establish that θ(t) := ⟨u̇(t), x^{∗} − ū⟩ belongs to L^{1}(t_{0}, ∞). Indeed, for ϵ ∈ IR let us set x_{ϵ}(t) := x(r(t)) + ϵ(ū − x^{∗}). The convexity of f(·, r) and (E) imply that

⟨−u̇(t), x_{ϵ}(t) − u(t)⟩ ≤ f(x_{ϵ}(t), r(t)) − f(u(t), r(t)),

so that using the optimality of x(r(t)) and the definitions of θ(t) and Δ(t) we deduce

ϵθ(t) = ϵ⟨u̇(t), x^{∗} − ū⟩ ≤ Δ(t) + f(x_{ϵ}(t), r(t)) − f(x(r(t)), r(t)).

Now, since x^{∗} and ū are optimal solutions for (P) we have

\begin{matrix}c′x(r(t)) = & c′x_{ϵ}(t) \\ A_{i}x(r(t)) = & A_{i}x_{ϵ}(t), i ∈ I_{0} \end{matrix}

and using the expression of f(·, r), we obtain the bound

ϵθ(t) ≤ Δ(t) + r(t) ∑_{i∉I_{0}} exp[(A_{i}x_{ϵ}(t) − b_{i})/r(t)].

We may then use (2.1) to find α > 0 such that for all ϵ close enough to 0 (either positive or negative) and all t sufficiently large

A_{i}x_{ϵ}(t) − b_{i} ≤ −α.

Then

ϵθ(t) ≤ Δ(t) + mr(t)e^{−α/r(t)}

so that the assumption of Fast Decay together with Step 2 imply that θ(t) belongs to L^{1}(t_{0}, ∞) as claimed. Step 4: Conclusion. By Step 2, the function Δ(t) belongs to L^{1}(t_{0}, ∞) so we may find a sequence t_{n} → ∞ such that Δ(t_{n}) → 0. By extracting a subsequence we may further assume that u(t_{n}) converges towards a certain u_{∞}. Using (3.1) and the results quoted from [5] in section 2, one may easily deduce that u_{∞} is a solution of (P). But then, using Step 3 we have the existence of

lim_{t→∞} ∥u(t) − u_{∞}∥ = lim_{n→∞} ∥u(t_{n}) − u_{∞}∥ = 0,

achieving the proof of our theorem.

Theorem 3.3. If r(t) satisfies the assumption of Slow Decay, then the solution u(t) of (E) converges to the centroid x^{∗} as t goes to infinity.

Proof. Since x(r) tends to x^{∗} as r → 0, it suffices to show that φ(t) tends to 0 as t goes to ∞. By contradiction assume that the limit of φ(t) is not 0 (see Step 1 in the previous proof). Using the expression of f(·, r) it is easy to see that for every R > 0, there exist constants K and L such that for all x, y ∈ B(0, R) and all r > 0 one has

⟨∇f(y, r) − ∇f(x, r), y − x⟩ ≥ \frac{L}{r} exp(−K/r)∥y − x∥^{2}.

Since u(t) and x(r(t)) stay bounded, we may find appropiate constants so that the previous inequality holds with x = x(r(t)), y = u(t) and r = r(t), to deduce

Δ(t) ≥ \frac{2L}{r(t)} exp(−K/r(t))φ(t).

Denoting β(t) = \frac{L}{r(t)} exp(−K/r(t)) we obtain

\begin{matrix}φ̇(t) = & − Δ(t) − ṙ(t)⟨\frac{dx}{dr}(r(t)), u(t) − x(r(t))⟩ \\ ≤ & − 2β(t)φ(t) − 2Mṙ(t)\sqrt{φ(t)}. \end{matrix}

Since φ(t) ≠ 0 for t large, we may divide by 2\sqrt{φ(t)} to deduce

\frac{1}{2\sqrt{φ(t)}}φ̇(t) + β(t)\sqrt{φ(t)} ≤ −Mṙ(t).

Let B(t) = ∫_{t_{0}}^{t} β(τ)dτ. Multiplying this inequality by exp(B(t)) we get

\frac{d}{dt}[exp(B(t))\sqrt{φ(t)}] ≤ −M exp(B(t))ṙ(t)

which integrated between s and t gives

\sqrt{φ(t)} ≤ exp(B(s) − B(t))\sqrt{φ(s)} − M ∫_{s}^{t} exp(B(τ) − B(t))ṙ(τ)dτ.

We recall that ṙ(t) ≤ 0, so that using the fact that B(·) is increasing we obtain the bound

\begin{matrix}\sqrt{φ(t)} ≤ & exp(B(s) − B(t))\sqrt{φ(s)} − M ∫_{s}^{t} ṙ(τ)dτ \\ = & exp(B(s) − B(t))\sqrt{φ(s)} + M[r(s) − r(t)]. \end{matrix}

The assumption of Slow Decay implies that B(t) tends to infinity as t → ∞. Thus, passing to the limit we deduce

lim_{t→∞} \sqrt{φ(t)} ≤ Mr(s).

It suffices now to let s approach infinity to conclude that φ(t) tends to 0, contradicting our assumption and proving the result.

Remark 3.4. The convergence analysis for the case of Slow Decay may be adapted to more general non-autonomous evolution equations. This will be the subject of the forthcoming paper [1].

References

[1] H. Attouch, R. Cominetti: A dynamical approach to convex minimization coupling approximation with the steepest descent method, submitted 1994.

[2] H. Brézis: Opérateurs maximaux monotones et semigroups de contractions dans les espaces de Hilbert, Mathematical Studies 5, North Holland 1973.

[3] R. Brück: Asymptotic convergence of nonlinear contraction semigroups in Hilbert space, Journal of Functional Analysis 18 1975, 15–26.

[4] T. Cazenave, A. Haraux: Introduction aux problèmes d’évolution semi-linéaires, Mathématiques & Applications 1, Ellipses 1993.

[5] R. Cominetti, J. San Martín: Asymptotic behavior of the exponential penalty trajectory in linear programming, Mathematical Programming 67 1994, pp. 169–187.

[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.

[7] A. Haraux: Nonlinear Evolution Equations: Global Behavior of Solutions, Lecture Notes in Mathematics 841, Springer-Verlag 1981.

[8] A. Pazy: Semigroups of linear operators and applications to partial differential equations, Springer-Verlag, New York 1983.