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

OPTIMIZATION OF DISCRETE-DISCRETE HYBRID DYNAMICAL SYSTEMS AND ITS APPLICATION TO PROBLEM SOLVING

CECILIA NAVA DE VILLEGAS, FERENC SZIGETI

Abstract. A hybrid dynamical system has continuous dynamics, described by differential equations, which interact with a discrete event dynamics [4]. One of the simplest discrete dynamics appears in the delay of a dynamic system. Delays can change in discrete times by discrete dynamics. This kind of interactions can show very complicated behavior. Some of the changes of delay can be described by jumps. The jumps can have proper dynamics, or can be considered as control in the framework of control systems. Technology development, problem solving [2, 3], and theorem proving have a common property: All new results became new tools for the development at the instant of their birth. That is, they become sources.

1. Results

The mathematical modelling of processes such as Technology development, problem solving , and theorem proving leads to discrete-discrete hybrid dynamical event systems, with jumps similar to the hybrid dynamical systems, and their continuous component is also a discrete dynamical system [2, 3]. We will use the process from problem solving as an example in this article.

The segments X(0) = a, b, c, … are given, as initial values. Selecting two of the given segments, let us draw a right triangle with the selected segments as its perpendicular sides. Then the hypotenuse of the obtained right triangle will be included to the initial segments. Then the obtained hypotenuse and one of the given segments (the hypotenuse is not excluded) will be selected as the perpendicular side of the following right triangle, etc. This controlled process can be described by a discrete-discrete hybrid dynamical system in sense of [4].

x(k + 1) = \sqrt{x(k)^{2} + x(j(k))^{2}}, j(k) ∈ \{0, 1, …, k\}  (1.1)
x(0) ∈ X(0)  (1.2)

If 0 < k and j(k) = 0 then x(j(k)) ∈ X(0) is not necessarily the same as the initial x(0). For example x(1) = \sqrt{a^{2} + b^{2}}, x(2) = \sqrt{x(1)^{2} + c^{2}} = y, x(3) = \sqrt{x(2)^{2} + b^{2}} = z. The general form of he process, supposing only two state variables, is

2000 Mathematics Subject Classification. 49N99.

Key words and phrases. Discrete-discrete hybrid dynamical systems; problem solving;

optimization.

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

Published May 30, 2005.

x(k + 1) = f_{k}(x(k), x(j(k)), u(k)),  (1.3)
x(0) ∈ X(0), j(k) ∈ {0, 1, …, k}  (1.4)

and for

1 ≤ k, j(k) = 0 ⇒ x(j(k)) ∈ X(0)  (1.5)

A cost function is also defined,

J(x, j, u) = G(x(K)) + ∑_{k=0}^{K−1} g_{k}(x(k), x(j(k)), u(k))  (1.6)

We can prove a minimum principle for the minimum cost of problem (1.3)-(1.6). The cost function may be vectorial equipped with a partial ordering with respect to a semi-group S, or a positive cone. Problem solving can be modelled in term of a decision process (1.3), with a particularly defined cost function. A minimization problem can be defined through cost function J(x, j, u). The cost function considered in (1.6) is equivalent to another one when all g_{k} = 0. The discrete process (x∗, u∗) is optimum (minimum) if J(x∗, u∗) ≤ J(x, u) is satisfied for any discrete process. Let (x∗, u∗) and (x, u) be two arbitraries optimization process of the first case, then the adjoint equation for the dual states p = (p(0), p(1), p(2), …, p(T)), p(t) ∈ Z^{kxn}, are defined by:

p(t) = p(t + 1)Rf(x ∗ (t); x(t), u(t))  (1.7)
p(T) = Rϕ(x ∗ (T); x(T));  (1.8)

that is,

\begin{matrix}ϕ(x(T)) − ϕ(x ∗ (T)) \\ = ∑_{t=o}^{T −1} p(t + 1)f(x ∗ (t), u(t)) − ∑_{t=0}^{T −1} p(t + 1)f(x ∗ (t), u ∗ (t)) \end{matrix}  (1.9)

where p = (p(0), p(1), …, p(T)); p(t) ∈ Z^{kxn} is the matrix solution of the adjoint equation (1.8).

The modified controls are defined by u = (u ∗ (0), u ∗ (1), …, u ∗ (i − 1), v, u ∗ (i + 1), …, u∗(T −1)) for each i = 0, 1, …, T −1 and v ∈ U. The process corresponding to u_{i,v} is (x_{i,v}, u_{i,v}) and the respective dual state is p_{i,v}. In that case the formula (1.9) reduces to

\begin{matrix}ϕ(x(T)) − ϕ(x ∗ (T)) \\ = ∑_{t=o}^{T −1} p_{i,v}(t + 1)f(x ∗ (t), u_{i,v}(t)) − ∑_{t=0}^{T −1} p_{i,v}(t + 1)f(x ∗ (t), u ∗ (t)) \\ = p_{i,v}(i + 1)f(x ∗ (i), v) − p(i + 1)f(x ∗ (i), u ∗ (i)) \end{matrix}  (1.10)

If (x∗, u∗) is an optimum (minimum) process for J(x, j, u) then

min_{v∈U} p_{i,v}(i + 1)(f(x ∗ (i), v) − f(x ∗ (i), u ∗ (i))) = 0  (1.11)

can also be expressed by another way, because p_{i,v}(i + 1)(f(x ∗ (i), v) − f(x ∗ (i), u ∗ (i))) ∈ S is a positive element of Z^{k}, for each i = 0, 1, …, T − 1 and v ∈ U. The Hamiltonian function is define as H : DxUxZ^{kxn} → Z^{k}, for H(x, u, p) = pf(x, u). Then

0 ≤ H(x ∗ (i), v, p_{i,v}(i + 1)) − H(x ∗ (i), u ∗ (i), p_{i,v}(i + 1))  (1.12)

When g_{k} ≠ 0 the Hamiltonian H is defined by H, for H(x, u, p) = pf(x, u) + g(x, u). Then the Pontryaguin minimum principle may be expressed in the same way as in (1.12). The Hamiltonian formalism is simply

\begin{matrix}x(t + 1) = R_{p}H(x(t), u(t), p(t + 1)) , \\ p(t) = R_{x}H(x(t), u(t), p(t + 1)) ; \end{matrix}  (1.13)

that is, the Taylor residue plays the same role as the gradient in the original formulation for the Pontryaguin minimum principle. The overall optimization can be reduced to a point wise optimization problem [1], that is, the minimum principle can be considered as a decomposition technique. However, instead of the classical optimization, The minimum principle is a discrete polynomial variation inequality.

Let us consider an alphabet of four letters denoted by A, A^{−1}, B, B^{−1}. The alphabet can be identified with the carthesian product U = {−1, 1} × {−1, 1}, by the correspondences

A ↔ (1, 1) A^{−1} ↔ (1, −1) B ↔ (−1, 1) B^{−1} ↔ (−1, −1)  (1.14)

The rules of simplification in the universal language generated by our alphabet are

AA = A, A^{−1}A^{−1} = A^{−1}, A^{−1}A = AA^{−1} = Θ  (1.15)

and the same rules for B,

BB = B, B^{−1}B^{−1} = B^{−1}, B^{−1}B = BB^{−1} = Θ  (1.16)

where Θ is the empty word. For example, the following identity holds in this language: BAB^{−1}B^{−1}AA^{−1} = BAB^{−1}.

Let X_{0} = {1, −1}, Θ = −1 the initial state space and the initial state, respectively, in the graded state space associated to this linguistic discrete event dynamical system. The first state space is X_{1} = {1, −1}^{3}, then the partially defined state transition f_{0} : X_{0} × U → X_{1} is defined by the application

f_{0}(Θ, u_{1}, u_{2}) = (u_{1}, u_{2}, −1) ∈ X_{1}  (1.17)

The general state space is X_{i} = {1, −1}^{2i+1}. Let us define the imbedding I_{i} : X_{i} → X_{i+1}, by

I_{i}(x_{1}, x_{2}, …, x_{2i+1}) = (x_{1}, x_{2}, …, x_{2i+1}, 1, 1) ∈ X_{i+1}  (1.18)

The correspondences (1.14) among letters and the elements of U = {−1, 1}×{−1, 1} can be extended for words of length i, without the possibility of simplification, the following way: If the word is L_{1}L_{2} … L_{i} and each letter L_{j} corresponds to the pair (u_{j}, v_{j}), then the extended correspondence is

L_{1}L_{2} … L_{i} → (u_{1}, v_{1}, u_{2}, v_{2}, …, u_{i}, v_{i}, −1)  (1.19)

that is, if x_{2j−1} = u_{j}, x_{2j} = v_{j}; j = 1, 2, …, i; x_{2i+1} = −1, then

L_{1}L_{2} … L_{i} → x = (x_{1}, x_{2}, …, x_{2i+1}) ∈ X_{i}  (1.20)

If a word L_{1}L_{2} … L_{i}, after the possible simplification, equals L̂_{1}L̂_{2} … L̂_{m}, which corresponds to the vector

x = (x_{1}, x_{2}, …, x_{2m}, −1) ∈ X_{m}

then I_{i−1}(I_{i−2}(… (I_{m−1}(x)) …)) ∈ X_{i} is considered as the corresponding representation of the unsimplified word L_{1}L_{2} … L_{i}, in X_{i}. Obviously the given extension is compatible with the immersions.

Now, the definition of the further graded dynamics is simple. Let us decompose the domain D(f_{i}) = D_{i} × U ⊂ X_{i} × U of the i-th dynamics in the union of the sets I_{i−1}(D_{i−1}) × U and {x : x = (x_{1}, x_{2}, …, x_{2i}, −1) ∈ X_{i}} × U. Then

f_{i}(x, u) = I_{i}(f_{i−1}(x_{1}, x_{2}, …, x_{2i−1}, u_{1}, u_{2})); (x, u) ∈ I_{i−1}(D_{i−1}) × U (1.21)

and

f_{i}(x, u) = \begin{cases}(x_{1}, x_{2}, …, x_{2i}, u_{1}, u_{2}, −1)^{T}; & x_{2i−1} ≠ u_{1}, \\ (x_{1}, x_{2}, …, x_{2i}, 1, 1, 1)^{T}; & x_{2i−1} = u_{1}, x_{2i} = u_{2}, \\ (x_{1}, x_{2}, …, x_{2(i−1)}, 1, 1, 1, 1, 1)^{T}; & x_{2i−1} = u_{1}, x_{2i} ≠ u_{2}, \end{cases} (1.22)

when x = (x_{1}, x_{2}, …, x_{2i}, −1). When x_{2i−1} ≠ u_{1}, the letters can not be cancelled. When x_{2i−1} = u_{1}, x_{2i} = u_{2}, there is a unique cancellation of type AA = A. When x_{2i−1} = u_{1}, there is a unique cancellation of type A^{−1}A = AA^{−1} = Θ.

Let us suppose that the control u^{∗}(0), u^{∗}(1), …, u^{∗}(T − 1) s a minimal value of the cost function u → Φ(x(T)), where x(0) = ξ, x(1), …, x(T) is the trajectory corresponding to the control and the dynamics (1.17), (1.21), (1.22). Moreover, let us suppose that there is no cancellation in the concatenation of the corresponding letters. Then the optimal dynamics is linear. Then if the variation of the optimal trajectory by

u = (u ∗ (0), u ∗ (1), …., u ∗ (i − 1), v, u ∗ (i + 1), …, u ∗ (T − 1))  (1.23)

satisfies that in the corresponding word there is no cancellation, then the obtained problem is linear. The general case is much more complicated; however, that also has a nice structure. Let us suppose that at the i-th step, we have a cancellation between the letters corresponding to u^{∗}(i − 1), u^{∗}(i). Then x^{∗}(i + 1) ∈ I_{i}(D_{i}), …, x^{∗}(T) ∈ I_{T −1}(D_{T −1}). Let us define the projection P_{im} : ℝ^{2i+1} → ℝ^{2m+1} by

P_{im}(x_{1}, x_{2}, …, x_{2i−1}, x_{2i}, x_{2i+1}) = (x_{1}, x_{2}, …, x_{2m}, x_{2m+1}),  (1.24)

where x_{2m+1} = −1, x_{2m+2} = x_{2m+3} = ⋯ = x_{2i+1} = 1; that is,

x = I_{i−1}(I_{i−2}(… (I_{m}(x_{1}, x_{2}, … x_{2m}, −1)) …)) .  (1.25)

Then the dynamics are defined by

f_{i}(x, u) = I_{i}(I_{i−1}(… (I_{m+1}(f_{m}(P_{im}(x), u))) …))  (1.26)

Hence, the i-th dynamics does not depend on the variables x_{2m+2}, x_{2m+3}, …, x_{2i+1}, and iteratively, the dynamics f_{j}(x, u); j > i does not depend on the variables x_{2m+j−i+2}, x_{2m+j−i+3}, …, x_{2j+1}. Hence the corresponding coordinates of the adjoint states vanish.

This fact simplifies the minimum principle too. The projections and the immersions are linear, the unsimplified dynamics are also linear, hence, this problem is linear, independently on the simplifications. The linear time depending dynamics and adjoint dynamics has the form

x(i + 1) = A_{i}x(i) + B_{i}u(i) + f_{i}ϕ(j) = A_{j}^{T} ϕ(j + 1); ϕ(T) = RΦ(x^{∗}(T); x_{i,v}(T)) . (1.27)

The minimum principle has the form

⟨φ(i + 1), B_{i}u^{∗}(i)⟩ ≤ ⟨φ(i + 1), B_{i}v⟩  (1.28)

If the cost function is linear, then its Taylor residual, that is, the initial dual state is constant, hence (1.28) is a classical minimum principle, minimizes the linear form in (1.28). For quadratic cost function, when Φ(x) = ⟨Cx, x⟩, then the Taylor residual is RΦ(x^{∗}(T); x_{i,v}(T)) = x^{∗}(T) + x_{i,v}(T), then the minimum principle is a variational inequality of form

⟨l, u^{∗}(i)⟩ + ⟨Lv, u^{∗}(i)⟩ ≤ ⟨l, v⟩ + ⟨Lv, v⟩  (1.29)

where u^{∗}(i) is the solution of the inequality, if (1.29) holds for all v ∈ {1, −1}^{2}. Let us assume that

l = (l_{1}, l_{2})^{T} , L = (\begin{matrix}L_{11} & L_{12} \\ L_{21} & L_{22} \end{matrix})  (1.30)

Then (1.29) is equivalent to the system of linear inequalities

\begin{matrix}(1, 1) → (l_{1} + L_{11} + L_{21})u_{1}^{∗}(i) + (l_{2} + L_{12} + L_{22})u_{2}^{∗}(i) \\ ≤ (l_{1} + L_{11} + L_{21}) + (l_{2} + L_{12} + L_{22}), \\ (1, −1) → (l_{1} + L_{11} − L_{21})u_{1}^{∗}(i) + (l_{2} + L_{12} − L_{22})u_{2}^{∗}(i) \\ ≤ (l_{1} + L_{11} − L_{21}) + (l_{2} + L_{12} − L_{22}), \\ (−1, 1) → (l_{1} − L_{11} + L_{21})u_{1}^{∗}(i) + (l_{2} − L_{12} + L_{22})u_{2}^{∗}(i) \\ ≤ (l_{1} − L_{11} + L_{21}) + (l_{2} − L_{12} + L_{22}), \\ (−1, −1) → (l_{1} − L_{11} − L_{21})u_{1}^{∗}(i) + (l_{2} − L_{12} − L_{22})u_{2}^{∗}(i) \\ ≤ (l_{1} − L_{11} − L_{21}) + (l_{2} − L_{12} − L_{22}). \end{matrix}  (1.31)

Let us set up a problem solver as it has planned in the introductory example. Suppose that a problem is solved, if decision process, which starts form the initial values and taking the decisions (controls and jumps)

ξ_{1}, ξ_{2} ∈ X(0), u(i), j(i); i = 0, 1, …, T_{u} − 1,  (1.32)

is finishes at a terminal set x(T_{u}) ∈ X_{F inal}. Let the characteristic function of X_{Final} be ·.

Then J(x, j, u) = (1 − S_{F} (T_{u}, x(T_{u}))) is the cost function. Two costs are compared by the lexicographic order. Let us suppose that there exists solution for the problem, that is, the final set is accessible. Then the minimum, with respect to the lexicographic order is a pair of form (0, T_{Min}), where T_{Min} is the minimum of the length of the solution. This can be solved by the minimum principle, from the knowledge that a sequence of decisions and one of the jumps give a solution, that is, from the knowledge of the function S_{F}. An intelligent problem solving can be given at all step of the solution by the following way. Let us consider an intermediate step x(τ), obtained by a sequence of decisions

(u(0), j(0)), (u(1), j(1)), …, (u(τ − 1), j(τ − 1)),  (1.33)

and ask that some decision (u(τ), j(τ)), is better than other one (ū(τ), j̄(τ)). If X_{Final} is inaccessible from the initial states

x(τ + 1) = f_{τ} (x(τ), x(j(τ)), u(τ))  (1.34)

and

x(j(τ + 1)) ∈ X_{0} ∪ {x(1), …, x(τ), x(τ + 1)} = X_{τ+1}  (1.35)

then (u(τ), j(τ)) is inadmissible. If both decisions are admissible, then (u(τ), j(τ)) is better, if the minimal length of the solution of problem

x(t + 1) = f_{t}(x(t), x(j(t)), u(t)),  (1.36)

with initial values x(τ +1), x(j(τ +1)) is less then the minimal length of the solution of (1.36) with initial values

\begin{matrix}x̄(τ + 1), x̄(j̄(τ + 1)); \\ x̄(τ + 1) = f_{τ} (x(τ), x(j̄(τ)), ū(τ)), x̄(j̄(τ + 1)) ∈ X_{τ+1} \end{matrix}  (1.37)

Both computations require the solution of the optimal decision problem by the minimum principle and the knowledge of the function S_{F}. That is, an algorithm, based in an optimal decision problem, solves an intelligent decision problem.

References

[1] Cardillo A., Juan J.; Optimizacion de Sistemas a Eventos Discretos usando el Principio de Minimo de Pontrieguin. Tesis de Magister, Universida de los Andes, 1993.

[2] De Sarrazin, G. F. Szigeti and J. Cardillo; Computer aided problem solving via optimization, Risc-Linz Report Series, Hagenberg, Austria, N 99-13 May of 1999.

[3] De Sarrazin, G. J. Cardillo and F. Szigeti; Optimal solution of a computer task, Nonlinear Analysis 47 (2001) 1549-1560.

[4] Van der Schaft, A. and H. Schumacher; An Introduction to Hybrid Dynamical Systems, Lecture Notes in Control and Information Sciences N 251, 2000

Cecilia Nava de Villegas Departamento de Calculo, Escuela de Basica de Ingeniería, Universidad de Los Andes, Mérida, Venezuela

  E-mail address: villegasgc@intercable.net.ve

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

  E-mail address: fszigeti@intercable.net.ve