\documentclass[reqno]{amsart}
\usepackage{hyperref}
\AtBeginDocument{{\noindent\small
2003 Colloquium on Differential Equations and Applications, Maracaibo, Venezuela.\newline
{\em Electronic Journal of Differential Equations},
Conference 13, 2005, pp. 89--94.\newline
ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or
http://ejde.math.unt.edu
\newline ftp ejde.math.txstate.edu (login: ftp)}
\thanks{\copyright 2005 Texas State University - San Marcos.}
\vspace{9mm}}
\setcounter{page}{89}
\begin{document}
\title[\hfilneg EJDE/Conf/13 \hfil Optimization of hybrid dynamical systems]
{Optimization of discrete-discrete hybrid dynamical systems
and its application to problem solving}
\author[C. Nava, F. Szigeti \hfil EJDE/Conf/13 \hfilneg]
{Cecilia Nava de Villegas, Ferenc Szigeti} % in alphabetical order
\address{Cecilia Nava de Villegas \hfill\break
Departamento de Calculo\\
Escuela de Basica de Ingenier\'{\i}a\\
Universidad de Los Andes, M\'erida, Venezuela}
\email{villegasgc@intercable.net.ve}
\address{Ferenc Szigeti \hfill\break
Departamento de Sistemas de Control\\
Escuela de Ingenier\'{\i}a de Sistemas \\
Universidad de Los Andes, M\'erida, Venezuela}
\email{fszigeti@intercable.net.ve}
\date{}
\thanks{Published May 30, 2005.}
\subjclass[2000]{49N99}
\keywords{Discrete-discrete hybrid dynamical systems; problem solving;
\hfill\break\indent optimization}
\begin{abstract}
A hybrid dynamical system has continuous dynamics,
described by differential equations, which interact with a
discrete event dynamics \cite{v1}. 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
\cite{d1,d2}, 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.
\end{abstract}
\maketitle
\numberwithin{equation}{section}
\section{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
\cite{d1,d2}. We will use the process from problem solving as an
example in this article.
The segments $X(0)={ a,b,c,\dots }$ 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 \cite{v1}.
\begin{gather} % 1, 2
x(k + 1) = \sqrt {x(k)^2 + x(j(k))^2 } ,\quad j(k) \in \{0,1,\dots ,k \}\\
x(0) \in X(0)
\end{gather}
If $ 0 < k$ and $ j(k) = 0 $ then $ x(j(k)) \in 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
\begin{gather}\label{ec1}
x(k + 1) = f_k (x(k),x(j(k)),u(k)), \\
x(0) \in X(0),\quad j(k) \in \{0,1,\dots ,k \}
\end{gather}
and for
\begin{equation} %e5
1 \le k,\quad j(k) = 0 \Rightarrow x(j(k)) \in X(0)
\end{equation}
A cost function is also defined,
\begin{equation}\label{ec2}
J(x,j,u) = G(x(K)) + \sum_{k = 0}^{K - 1} {g_k
(x(k),x(j(k)),u(k))}
\end{equation}
We can prove a minimum principle for the minimum cost of problem
(\ref{ec1})-(\ref{ec2}). 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 (\ref{ec1}), with a particularly defined
cost function. A minimization problem can be defined through cost
function $ J(x,j,u)$. The cost function considered in (\ref{ec2})
is equivalent to another one when all $ g_k = 0$. The discrete
process $(x*,u*)$ is optimum (minimum)
if $ J(x*,u*) \le 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),\dots,p(T)),p(t) \in Z^{kxn}$, are
defined by:
\begin{equation}
p(t) = p(t + 1)Rf(x*(t);x(t),u(t))
\end{equation}
\begin{equation}\label{ec3}
p(T) = R\phi (x*(T);x(T));
\end{equation}
that is,
\begin{equation}\label{ec4}
\begin{aligned}
&\phi (x(T)) - \phi (x*(T))\\
&= \sum_{t = o}^{T - 1} {p(t +1)f(x*(t),u(t))
- \sum_{t = 0}^{T - 1} {p(t +1)f(x*(t),u*(t))} }
\end{aligned}
\end{equation}
where $ p = (p(0),p(1),\dots ,p(T))$; $p(t) \in Z^{kxn}$ is the matrix
solution of the adjoint equation (\ref{ec3}).
The modified controls are defined by
$ u = (u*(0),u*(1),\dots ,u*(i- 1),v,u*(i + 1),\dots ,u*(T - 1)) $
for each $ i = 0,1,\dots ,T - 1$
and $ v \in 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 (\ref{ec4}) reduces to
\begin{equation}
\begin{aligned}
&\phi (x(T)) - \phi (x*(T)) \\
&= \sum_{t = o}^{T - 1} {p_{i,v}
(t + 1)f(x*(t),u_{i,v} (t)) -
\sum_{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{aligned}
\end{equation}
If $(x*,u*)$ is an optimum (minimum) process for $J(x,j,u)$ then
\begin{equation}\label{ec5}
\mathop {\min }_{v \in U} p_{i,v} (i + 1)(f(x*(i),v) -
f(x*(i),u*(i))) = 0
\end{equation}
can also be expressed by another way, because
$p_{i,v} (i +1)(f(x*(i),v) - f(x*(i),u*(i))) \in S$ is a positive element of
$Z^k$, for each $ i = 0,1,\dots ,T - 1$ and $v \in U$. The
Hamiltonian function is define as $H:DxUxZ^{kxn} \to Z^k$, for
$H(x,u,p) = pf(x,u)$. Then
\begin{equation}\label{ec6}
0 \le H(x*(i),v,p_{i,v} (i + 1)) - H(x*(i),u*(i),p_{i,v} (i + 1))
\end{equation}
When $g_k \ne 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 (\ref{ec6}).
The Hamiltonian formalism is simply
\begin{equation}\label{ec7}
\begin{gathered}
x(t + 1) = R_p H(x(t),u(t),p(t + 1))\,, \\
p(t) = R_xH(x(t),u(t),p(t + 1))\,;
\end{gathered}
\end{equation}
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 \cite{c1}, 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} \} \times \{{ - 1,1} \}$, by
the correspondences
\begin{equation}\label{ec8}
A \leftrightarrow (1,1) \quad
A^{ - 1} \leftrightarrow (1, - 1) \quad
B \leftrightarrow (- 1,1) \quad
B^{-1} \leftrightarrow (- 1,- 1)
\end{equation}
The rules of simplification in the universal language generated
by our alphabet are
\begin{equation}
AA = A,\quad A^{ - 1} A^{ - 1} = A^{ - 1} ,\quad
A^{ - 1}A = AA^{ - 1} = \Theta
\end{equation}
and the same rules for $B$,
\begin{equation}
BB = B,\quad B^{ - 1} B^{ - 1} = B^{ - 1} , \quad
B^{ - 1}B = BB^{ - 1} = \Theta
\end{equation}
where $ \Theta$ 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}\}$, $\Theta = - 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 \times U \to X_1$ is defined by the
application
\begin{equation}\label{ec9}
f_0 (\Theta ,u_1 ,u_2 ) = (u_1 ,u_2 , - 1) \in X_1
\end{equation}
The general state space is $ X_i = \{ {1, - 1} \}^{2i+ 1}$.
Let us define the imbedding $ I_i :X_i \to X_{i + 1}$, by
\begin{equation}
I_i (x_1 ,x_2 ,\dots ,x_{2i + 1} ) = (x_1 ,x_2 ,\dots ,x_{2i + 1} ,1,1)
\in X_{i + 1}
\end{equation}
The correspondences (\ref{ec8}) among letters and the elements of
$ U = \{ { - 1,1} \} \times \{ { - 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
\dots L_i$ and each letter $ L_j$ corresponds to the pair
$ (u_j ,v_j )$, then the extended correspondence is
\begin{equation}
L_1 L_2 \dots L_i \to (u_1 ,v_1 ,u_2 ,v_2 ,\dots ,u_i ,v_i , - 1)
\end{equation}
that is, if $ x_{2j - 1} = u_j$, $x_{2j} = v_j$;
$j = 1,2,\dots ,i$; $x_{2i + 1} = - 1$, then
\begin{equation}
L_1 L_2 \dots L_i \; \to \; x = (x_1 ,x_2 ,\dots ,x_{2i + 1})
\quad \in {\rm{ }}X_i
\end{equation}
If a word $ L_1 L_2 \dots L_i$, after the possible simplification,
equals $ \hat L_1 \hat L_2 \dots \hat L_m $, which corresponds to
the vector
\[
x = (x_1 ,x_2 ,\dots ,x_{2m} , - 1) \in X_m
\]
then $ I_{i - 1} (I_{i - 2} (\dots (I_{m - 1}(x))\dots )) \in X_i$
is considered as the corresponding representation of the unsimplified
word $ L_1 L_2 \dots 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 \times U \subset X_i
\times U$ of the $ i$-th dynamics in the union of the sets $ I_{i
- 1} (D_{i - 1} ) \times U$ and $ \{ {x:x = (x_1 ,x_2
,\dots ,x_{2i} , - 1) \in X_i } \} \times U$. Then
\begin{equation}\label{ec10}
f_i (x,u) = I_i (f_{i - 1} (x_1 ,x_2 ,\dots ,x_{2i - 1} ,u_1 ,u_2
));\quad (x,u) \in I_{i - 1} (D_{i - 1} ) \times U
\end{equation}
and
\begin{equation}\label{ec11}
f_i (x,u) = \begin{cases}
(x_1 ,x_2 ,\dots,x_{2i} ,u_1 ,u_2 , - 1)^T ;& x_{2i - 1} \ne u_1 , \\
(x_1 ,x_2 ,\dots,x_{2i} ,1,1,1 )^T ; & x_{2i - 1} = u_1 ,\;
x_{2i} = u_2 , \\
(x_1 ,x_2 ,\dots,x_{2( {i - 1} )} ,1,1,1,1,1 )^T ;
&x_{2i - 1} = u_1 ,\; x_{2i} \ne u_2 ,
\end{cases}
\end{equation}
when $ x = (x_1 ,x_2 ,\dots ,x_{2i} , - 1)$. When
$x_{2i - 1} \ne u_1$, the letters can not be cancelled.
When $x_{2i - 1} = u_1 ,{\rm{ }}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} =\Theta$.
Let us suppose that the control
$ u^* (0),u^* (1),\dots ,u^* (T -1)$ s a minimal value of the cost function
$ u \to \Phi (x(T))$, where $ x(0) = \xi ,x(1),\dots ,x(T)$ is the trajectory
corresponding to the control and the dynamics
(\ref{ec9}), (\ref{ec10}), (\ref{ec11}). 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
\begin{equation}
u = (u*(0),u*(1),\dots .,u*(i - 1),v,u*(i + 1),\dots ,u*(T - 1))
\end{equation}
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) \in I_i (D_i ),\dots ,x^*(T) \in I_{T - 1} (D_{T - 1} )$.
Let us define the projection
$P_{im} :\mathbb{Re} ^{2i + 1} \to \mathbb{Re} ^{2m + 1}$ by
\begin{equation}
P_{im} (x_1 ,x_2 ,\dots ,x_{2i - 1} ,x_{2i} ,x_{2i + 1} )
= (x_1 ,x_2 ,\dots ,x_{2m} ,x_{2m + 1} ),
\end{equation}
where $ x_{2m + 1} = - 1$, $ x_{2m + 2} = x_{2m + 3} = \dots =
x_{2i + 1} = 1$; that is,
\begin{equation}
x = I_{i - 1} (I_{i - 2} (\dots (I_m (x_1 ,x_2 ,\dots x_{2m} , -
1))\dots ))\,.
\end{equation}
Then the dynamics are defined by
\begin{equation}
f_i (x,u) = I_i (I_{i - 1} (\dots (I_{m + 1} (f_m (P_{im}
(x),u)))\dots ))
\end{equation}
Hence, the $i$-th dynamics does not depend on the variables
$x_{2m + 2},x_{2m + 3},\dots ,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} ,\dots ,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
\begin{equation}
x( {i + 1} ) = A_i x( i ) + B_i u( i
) + f_i \phi (j) = A_j^T \phi (j + 1);\phi (T)
= R\Phi(x^* (T);x_{i,v} (T))\,.
\end{equation}
The minimum principle has the form
\begin{equation}\label{ec12}
\langle {\varphi ( {i + 1}),B_i u^* ( i)}\rangle
\le \langle {\varphi ( {i + 1}),B_i v} \rangle
\end{equation}
If the cost function is linear, then its Taylor residual, that
is, the initial dual state is constant, hence (\ref{ec12}) is a
classical minimum principle, minimizes the linear form in
(\ref{ec12}). For quadratic cost function, when $ \Phi (x) =
\langle {Cx,x} \rangle$, then the Taylor residual is $
R\Phi (x^* (T);x_{i,v} (T)) = x^* (T) + x_{i,v} (T)$, then the
minimum principle is a variational inequality of form
\begin{equation}\label{ec13}
\langle {l,u^* ( i )} \rangle +
\langle {Lv,u^* ( i )} \rangle \le
\langle {l,v} \rangle + \langle {Lv,v}
\rangle
\end{equation}
where $ u^* (i)$ is the solution of the inequality, if (\ref{ec13})
holds for all $ v \in \{ {1, - 1} \}^2$. Let us assume
that
\begin{equation}
l = (l_1 ,l_2 )^T ,\quad L = \begin{pmatrix}
{L_{11} } & {L_{12} } \\
{L_{21} } & {L_{22} } \end{pmatrix}
\end{equation}
Then (\ref{ec13}) is equivalent to the system of linear
inequalities
\begin{equation}
\begin{aligned}
&( {1,1} ) \to ( {l_1 + L_{11} + L_{21} } )u_1^* (i) + ( {l_2 + L_{12}
+ L_{22} } )u_2^* (i)\\
&\le ( {l_1 + L_{11} + L_{21} } ) + ( {l_2 + L_{12} + L_{22} } ), \\
&( {1, - 1} ) \to ( {l_1 + L_{11} - L_{21} } )u_1^* (i) + ( {l_2
+ L_{12} - L_{22} } )u_2^* (i)\\
&\le ( {l_1 + L_{11} - L_{21} } ) + ( {l_2 + L_{12} - L_{22} } ), \\
&( { - 1,1} ) \to ( {l_1 - L_{11} + L_{21} } )u_1^* (i)
+ ( {l_2 - L_{12} + L_{22} } )u_2^* (i)\\
&\le ( {l_1 - L_{11} + L_{21} } ) + ( {l_2 - L_{12} + L_{22} } ), \\
&( { - 1, - 1} ) \to ( {l_1 - L_{11} - L_{21} } )u_1^* (i)
+ ( {l_2 - L_{12} - L_{22} } )u_2^* (i)\\
&\le ( {l_1 - L_{11} - L_{21} } ) + ( {l_2 - L_{12} - L_{22} } ).
\end{aligned}
\end{equation}
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)
\begin{equation}
\xi _1 ,\xi _2 \in X(0),\quad u(i),\quad j(i);\quad i =
0,1,\dots ,T_u - 1,
\end{equation}
is finishes at a terminal set $ x(T_u ) \in X_{Final}$. Let the
characteristic function of $ X_{\rm Final}$ be $\cdot$.
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(\tau )$,
obtained by a sequence of decisions
\begin{equation}
( {u(0),j(0)} ),( {u(1),j(1)} ),\dots ,({u(\tau - 1),j(\tau - 1)} ),
\end{equation}
and ask that some decision $ ( {u(\tau ),j(\tau )})$, is better
than other one $ ( {\bar u(\tau ),\bar j(\tau )} )$.
If $ X_{\rm Final}$ is inaccessible from the initial states
\begin{equation}
x(\tau + 1) = f_\tau ( {x(\tau ),x(j(\tau )),u(\tau )})
\end{equation}
and
\begin{equation}
x(j(\tau + 1)) \in X_0 \cup \{ {x(1),\dots ,x(\tau ),x(\tau +
1)} \} = X_{\tau + 1}
\end{equation}
then $ ( {u(\tau ),j(\tau )} )$ is inadmissible. If
both decisions are admissible, then $ ( {u(\tau ),j(\tau )})$ is better,
if the minimal length of the solution of problem
\begin{equation}\label{ec14}
x(t + 1) = f_t (x(t),x(j(t)),u(t)),
\end{equation}
with initial values $ x(\tau + 1),x(j(\tau + 1))$ is less then
the minimal length of the solution of (\ref{ec14}) with initial
values
\begin{equation}
\begin{gathered}
\bar x(\tau + 1),\quad
\bar x(\bar j(\tau + 1)); \\
\bar x(\tau + 1) =
f_\tau ( {x(\tau ),x(\bar j(\tau )),\bar u(\tau )}),\quad
\bar x(\bar j(\tau + 1)) \in X_{\tau + 1}
\end{gathered}
\end{equation}
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.
\begin{thebibliography}{99}
\bibitem {c1}
Cardillo A., Juan J.; \emph{Optimizacion de Sistemas a Eventos Discretos
usando el Principio de Minimo de Pontrieguin}. Tesis de Magister,
Universida de los Andes, 1993.
\bibitem {d1}
De Sarrazin, G. F. Szigeti and J. Cardillo;
\emph{Computer aided problem solving via optimization},
Risc-Linz Report Series,
Hagenberg, Austria, Nš 99-13 May of 1999.
\bibitem {d2}
De Sarrazin, G. J. Cardillo and F. Szigeti;
\emph{Optimal solution of a computer task},
Nonlinear Analysis 47 (2001) 1549-1560.
\bibitem {v1}
Van der Schaft, A. and H. Schumacher;
\emph{An Introduction to Hybrid Dynamical Systems},
Lecture Notes in Control and Information
Sciences Nš 251, 2000
\end{thebibliography}
\end{document}