2003 Colloquium on Differential Equations and Applications, Maracaibo, Venezuela. Electronic Journal of Differential Equations, Conference 13, 2005, pp. 13–19. ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu ftp ejde.math.txstate.edu (login: ftp)

METHOD OF RELAXATION APPLIED TO OPTIMIZATION OF DISCRETE SYSTEMS

JEAN LOUIS CALVET, JUAN CARDILLO, JEAN CLAUDE HENNET, FERENC SZIGETI

Abstract. In this work, the relaxation method is presented and then applied to the optimization of a family of discrete systems. Thus, a condition for the relationship between the minimum of the original problem and of the relaxed problem is translated to an equivalent condition of minimum principle. Several examples illustrate this technique and the condition obtained.

1. Introduction

The relaxation technique can be describe in a simple way for the minimization of a function on a finite domain, f : {1, 2, …, n} → ℜ as follows: To each function on the domain Z_{n} = {1, 2, …, n}, associate another function on the set of probability measures as,

P̂ = {P = (p(i)) : 0 ≤ p(i) ∑_{i=1}^{n} p(i) = 1},  (1.1)

in the form:

i ↦ f(i) ⟺ P → E_{P} (f) = ∑_{i=1}^{n} p(i)f(i).  (1.2)

Also, P̂, the domain of the mathematical expectation, is a natural extension of the domain Z_{n}. Indeed, to each i ∈ Z_{n} we can be associated the probability measure

P_{i} = (0, …, 0, 1_{i}, 0 …, 0),  (1.3)

that is,

p_{i}(j) = \begin{cases}1, & j = i, \\ 0, & j ≠ i . \end{cases}  (1.4)

It is easy to see that the global minimum of the nonlinear problem min_{i∈Z_{n}} f(i) and the minimum of the lineaf function coincides in i_{0} → P_{i_{0}} .

The extension of a nonlinear function to a lineal function using the presented technique is called the relaxation method. For classic control systems, J. Warga and others used the relaxation technique since 1960’s. Surprisingly in the previous years the use of this technique has resurfaced, but in another context. Thus, instead of using of combinatorial optimization, we propose using relaxed problems, with the aim of diminishing the computational complexity. In [5, 6] is has been analyzed the equivalence between the original problem and the relaxed problem

2000 Mathematics Subject Classification. 93C65, 49M20, 74P20.

Key words and phrases. Discrete Systems; relaxation; optimization.

\begin{matrix}c \\ ◯ \end{matrix}2005 Texas State University - San Marcos.

Published May 30, 2005.

In this work, we outline the relaxation problem in the context of the optimization from a class of discrete events processes (discrete events systems) equipped with concave and convex cost functions. The first one, generically, always guarantees the equivalence between the original problem and the relaxed problem; moreover, the optimality criteria is given in the classical form of the minimum principle. While for the second problem, it is a consequence of the separation theorem for convex set. The equivalence between the original problem and the relaxed one, is also a classical minimum principle.

2. Discrete Event Process Optimization Problem (Discrete Event System)

Consider the optimization problem

x(k + 1) = A(u(k))x(k) + b(u(k)), x(0) = 0,  (2.1)

where A : {−1, 1}^{m} → ℝ^{n×n}, b : {−1, 1}^{m} → ℝ^{n}, are functions with finite domain, defined on the set {−1, 1}^{m} of the vertices of the hypercube of dimension m. The sequence u(0), u(1), …, u(K −1) is denominated control (decision). The trajectory associated to the control is the sequence x(0), x(1), …, x(K), calculated for (2.1). The cost function Φ : ℝ^{n} → ℝ is defined by J(x, u) = Φ(x(K)).

Now, the objective is to find a sequence u^{∗}(0), u^{∗}(1), …, u^{∗}(K − 1) , such that, for the corresponding trajectory x^{∗}(0), x^{∗}(1), …, x^{∗}(K),

J(x^{∗}, u^{∗}) = Φ(x^{∗}(K)) ≤ Φ(x(K)) = J(x, u),  (2.2)

be satisfied, for every u(0), u(1), …, u(K−1). The minimum principle is a necessary condition for the optimal control u^{∗}(0), u^{∗}(1), …, u^{∗}(K − 1).

To state our results, we need the concept of varied trajectory

x_{i,u}(0), x_{i,u}(1), …, x_{i,u}(K)

and the dual trajectory φ_{i,u}(i + 1), φ_{i,u}(i + 2), …, φ_{i,u}(K):

x_{i,u}(k) = x^{∗}(k), k ≤ i,
x_{i,u}(i + 1) = A(u)x^{∗}(i) + b(u),
x_{i,u}(k + 1) = A(u^{∗}(k))x_{i,u}(k) + b(u^{∗}(k)), k > i,
φ_{i,u}(k) = A(u^{∗}(k))^{T} φ_{i,u}(k + 1),
φ_{i,u}(K) = RΦ(x^{∗}(K); x_{i,u}(K)), k > i,

where

RΦ(x^{∗}(K); x(K)) = ∫_{0}^{1} grad Φ(x^{∗}(K) + t(x_{i,u}(k) − x^{∗}(K)).  (2.3)

Then the optimality criterion is the inequality:

⟨φ_{i,u}(i + 1), A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i))⟩ ≤ ⟨φ_{i,u}(i + 1), A(u(i))x^{∗}(i) + b(u(i))⟩ (2.4)

for everything i and u. (see minimum principle on finite domains [2]). Here the relaxation is defined using the dynamics for i, and the probability measure P = (p(u)), u ∈ {−1, 1}^{m}, as follows. The trajectory x_{i,P} (0), x_{i,P} (1), …, x_{i,P} (K), is defined by

x_{i,P} (k) = x^{∗}(k), k ≤ i,

x_{i,P} (i + 1) = ∑_{u} p(u)(A(u)x^{∗}(k) + b(u)),

x_{i,P} (k + 1) = A(u^{∗}(k))x_{i,P} (k) + b(u^{∗}(k)), k > i.

The relaxation problem consists on giving conditions such that

Φ(x^{∗}(K)) = min_{u(k)∈{−1,1}^{m}} Φ(x(K))_{∀k=0,1,...K} min_{P ∈P̂} Φ(x_{i,P} (K))_{∀i} .

3. Main Result

Let us observe that if P = P_{v}, this is

p_{v}(u) = \begin{cases}1, & u = v, \\ 0, & u ≠ v, \end{cases}

then x_{i,P} (k) = x_{i,u}(k). The corresponding dual trajectory, in this case, is defined as:

φ_{i,P} (k) = A(u^{∗}(k))^{T} φ_{i,P} (k + 1), φ_{i,P} (K) = RΦ(x^{∗}(K); x_{i,P} (K))

Lemma 3.1. If 0 ≤ ∑ c_{i}x(i), with ∑ x(i) = 1, for all x(i) ≥ 0, then 0 ≤ c_{i}.

Proof. Let x_{0}(i) = \begin{cases}1, & i = i_{0}, \\ 0, & i ≠ i_{0}, \end{cases}. Then 0 ≤ ∑ c_{i}x_{0}(i) = c_{i_{0}}. □

Lemma 3.2. If x_{i,P} (k) is the trajectory of the i-th relaxed problem for P = (p(u)) and x_{i,u}(k) is the solution of the problem perturbed in the step i by u, then

x_{i,P} (k) = ∑ p(u)x_{i,u}(k), k = i + 1, …, K  (3.1)

Proof. By definition x_{i,u}(i + 1) = A(u)x^{∗}(i) + b(u) and

x_{i,P} (i + 1) = ∑ p(u)(A(u)x^{∗}(i) + b(u)) = ∑ p(u)x_{i,u}(i + 1) .

Then (3.1) is true for i + 1. Using mathematical induction assume that (3.1) is valid for k. Then for k + 1, we have

x_{i,P} (k + 1) = A(u^{∗}(k))x_{P} (k) + b(u^{∗}(k)) =
= A(u^{∗}(k))(∑_{u} p(u)x_{i,v}(k)) + b(u^{∗}(k)) =

= ∑_{u} p(u)(A(u^{∗}(k))x_{i,v}(k) + b(u^{∗}(k))) = ∑_{u} p(u)x_{i,v}(k + 1).□

which completes the proof. □

Theorem 3.3. Assume that Φ is concave over a convex domain D ⊂ ℝ^{n}; i.e., for every λ, μ ≥ 0, with λ + μ = 1, and x, y ∈ D,

λΦ(x) + μΦ(y) ≤ Φ(λx + μy) .

Then the relaxed problem and the original problem have the same minimum. That is, u^{∗}(0), u^{∗}(1), …, u^{∗}(K − 1), is the optimal control, then, for each i fixed, the i-th relaxed problem min_{P ∈P̂} Φ(x_{i,P} (K)) has the minimum in P_{u^{∗}(i)}, defined by

p_{u^{∗}(i)}(u) = \begin{cases}1 & u = u^{∗}(i), \\ 0 & u ≠ u^{∗}(i). \end{cases}

Proof. First we will prove the equalities

Φ(x_{i,P} (K)) − Φ(x^{∗}(K))

= ∑_{u} p(u)⟨φ_{i,P} (i + 1), (A(u)x^{∗}(i) + b(u)) − (A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i)))⟩

\begin{matrix}Φ(x_{i,P} (K)) − Φ(x^{∗}(K)) \\ = RΦ(x^{∗}(K); x_{i,P} (K))(x_{i,P} (K) − x^{∗}(K)) \\ = ⟨φ_{i,P} (K), x_{i,P} (K) − x^{∗}(K)⟩ \\ = ⟨φ_{i,P} (K), A(u^{∗}(K − 1))x_{i,P} (K − 1) + b(u^{∗}(K − 1)) \\ − A(u^{∗}(K − 1))x^{∗}(K − 1) − b(u^{∗}(K − 1))⟩ \\ = ⟨A(u^{∗}(K − 1))^{T} φ_{i,P} (K), x_{i,P} (K − 1) − x^{∗}(K − 1)⟩ \\ = ⟨φ_{i,P} (K − 1), x_{i,P} (K − 1) − x^{∗}(K − 1)⟩ = … \\ = ⟨φ_{i,P} (i + 1), x_{i,P} (i + 1) − x^{∗}(i + 1)⟩ \\ = ⟨φ_{i,P} (i + 1), ∑_{u} p(u)(A(u)x^{∗}(i) + b(u)) − (A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i)))⟩ \\ = ∑_{u} p(u)⟨φ_{i,P} (i + 1), (A(u)x^{∗}(i) + b(u)) − (A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i)))⟩ \end{matrix} (3.2)

Now suppose that i-th relaxed problem has optimum P_{u^{∗}(i)}. Then

0 ≤ Φ(x_{i,P} (K)) − Φ(x^{∗}(K)) .

By the formula demonstrated previously,

0 ≤ ∑_{u} p(u)⟨φ_{i,P} (i + 1), (A(u)x^{∗}(i) + b(u)) − (A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i)))⟩

for every P, as well as for P = P_{v} and φ_{P_{v},i}(i + 1) = φ_{i,v}(i + 1). By Lemma 3.1,

⟨φ_{i,v}(i + 1), A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i))⟩ ≤ ⟨φ_{i,v}(i + 1), A(u(i))x^{∗}(i) + b(u(i))⟩ (3.3)

This being the minimum principle, without necessity of concavity or convexity of Φ.

Now, let us suppose that the minimum principle is fulfilled. For a measure of probability P = (p(u)), multiply the inequality (3.3) by p(u) and add for everything v ∈ {−1, 1}^{m}. Then

0 ≤ ∑_{v} p(v)⟨φ_{i,v}(i + 1), (A(u)x^{∗}(i) + b(u)) − (A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i)))⟩

= ∑_{v} p(v)⟨φ_{i,v}(i + 1), x_{i,v}(i + 1) − x^{∗}(i + 1)⟩ = …

= ∑_{v} p(v)⟨φ_{i,v}(K), x_{i,v}(K) − x^{∗}(K)⟩ = ∑_{v} p(v)(Φ(x_{i,v}(K)) − Φ(x^{∗}(K)))

≤ Φ(∑_{v} p(v)x_{i,v}(K)) − ∑_{v} p(v)Φ(x^{∗}(K)) = Φ(x_{i,P} (K)) − Φ(x^{∗}(K)),

for what the minimum of the relaxed problem is reached in P_{u^{∗}(i)}. Hence the equivalence between the original problem and the relaxed problem is proven. □

4. Examples

Example 4.1. Consider the following system, linear in x(k),

x(k + 1) = A(u(k))x(k) + b(u(k)), x(0) = ξ  (4.1)

with the linear cost function

Φ(x(K)) = ⟨φ, x(K)⟩ .

The linear application ⟨φ, x(K)⟩ is concave (can also be convex) there fare the original problem and the relaxed problem have the same minimum by the previously theorem. The dual equations are also the same, since the initial condition φ(K) = φ is independent of the perturbation or of the relaxation. Hence in this case the minimum principle came be expressed in the classic form

⟨φ(i + 1), A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i))⟩ = min_{u}⟨φ(i + 1), A(u)x^{∗}(i) + b(u)⟩

or using the Hamiltonian form

H(x^{∗}(i), u^{∗}(i), φ(i + 1)) ≤ H(x^{∗}(i), u, φ(i + 1)).  (4.2)

Note that the Hamiltonian is defined as H(x, u, φ) = ⟨φ, A(u)x + b(u)⟩.

Example 4.2. Consider the same linear system with

x(k + 1) = A(u(k))x(k) + b(u(k)), x(0) = ξ

with positive semi definite quadratic cost function

Φ(x(K)) = ⟨Qx(K), x(K)⟩

and the same considerations for the perturbed system and for the relaxed system. Then

Φ(x_{i,P} (K)) − Φ(x^{∗}(K))

= ∑_{u} p(u)⟨φ_{i,P} (i + 1), A(u)x^{∗}(i) + b(u) − A(u^{∗}(i))x^{∗}(i) + b(u^{∗}(i))⟩

Suppose that v is such that

p_{i,v}(u) = \begin{cases}1, & u = v, \\ 0, & u ≠ v . \end{cases}

If 0 ≤ Φ(x_{i,v}(K)) − Φ(x^{∗}(K)), (minimum), Φ is smooth in x^{∗}(K) and it is convex, then the tangent hyperplane that separates the convex body {x : Φ(x) ≤ Φ(x^{∗}(K))} at x^{∗}(K) containing the points x_{i.v}(K), also separates the convex hull of the points {x^{∗}(K), x_{i,v}(K), v ∈ {−1, 1}^{m}}; thats is the points x_{i,P} (K) = ∑_{u} p(u)x_{i,v}(K).

Hence why, Φ(x_{i,P} (K)) ≥ Φ(x^{∗}(K)). Thus

0 ≤ Φ(x_{i,P} (K)) − Φ(x^{∗}(K)) = Φ(∑_{v} p(v)x_{i,v}(K)) − Φ(x^{∗}(K))

and the two problems are equivalent. The previous idea is illustrated in Figure 1.

[figure: x^{∗}(K); x_{P} (K); x_{P_{v}}(K)]

Figure 1. A geometric interpretatoion of ⟨Qx, x⟩ ≤ ⟨Qx^{∗}(K), x^{∗}(K)⟩

Conclusions. Most of the discrete optimization problems, do not escape from the use of combinatorial optimization, hence these problem, are sensitive to the computational complexity. Thus, in this work we recapture the idea of the use of the method relaxation over finite domains. This leads to the transformation of the discrete problems in a classic formulation, which provides a way to solve the optimization problem. Here, a family peculiar of discrete processes are considered, linear in the state, equipped with concave or convex cost functions. We obtain equivalence between the relaxed optimum and the optimum of the original problem, in the form of minimum principle. For linear cost function, the obtained condition is a classical minimum principle.

References

[1] Amir Beck and Marc Teboulle; Global Optimality Condition for Quadratic Optimization Problem with Binari Constraints, SIAM Journal Optimization, vol. 11, n 1, pp. 179-188, 2000.

[2] Juan Cardillo; Optimizacin de Sistemas a Eventos Discretos, Tesis de Doctorado, 2003.

[3] J. B. Lasserre; An explicit exact SDP relaxation for nonlinear 0-1 programs, Rapport LAAS No00475 8th International Conference on Integer Programming and Combinatorial Optimization (IPCO’VIII), Utrecht (Pays-Bas), 13-15 Juin 2001, Lecture Notes in Computer Sciences 2081, Eds. K.Aardal, B.Gerards, 2001, Springer, ISBN 3-540-42225-0, pp. 293-303

[4] J. B. Lasserre , T. Prieto; Rumeau SDP Vs. LP Relaxations for the moment approach in some performance evaluation problems, Rapport LAAS N03125, Mars 2003, 16p.

[5] J. Warga; Relaxed Variational Problem, Journal o Mathematical Analysis and Applications, 4, 111-128, 1962.

[6] J. Warga; Necessary Condition for Minimum in Relaxed Variational Problem, Journal of Mathematical Analysis and Applications 4, 129-145, 1962.

[7] J. Warga; Optimal Control of Differential and Functional Equations, Academic Press 1972, Card Number 72-87229.

Jean Louis Calvet Laboratoire d’Analyse et d’Architecture de Systémes (LAAS) du CNRS, Toulouse, France, LAAS-CNRS

E-mail address: calvet@laas.fr

Juan Cardillo Departamento de Sistemas de Control, Escuela de Ingeniería de Sistemas, Universidad de Los Andes, Mérida, Venezuela

E-mail address: ijuan@ula.ve

Jean Claude Hennet Laboratoire d’Analyse et d’Architecture de Systémes (LAAS) du CNRS, Toulouse, France, LAAS-CNRS

E-mail address: hennet@laas.fr

Ferenc Szigeti Departamento de Sistemas de Control, Escuela de Ingeniería de Sistemas, Universidad de Los Andes, Mérida, Venezuela

E-mail address: fszigeti@icnet.com.ve