\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}