\documentclass[reqno]{amsart} \usepackage{epic} \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. 13--19.\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}{13} \begin{document} \title[\hfilneg EJDE/Conf/13 \hfil Method of relaxation] {Method of relaxation applied to optimization of discrete systems} \author[J. L. Calvet, J. Cardillo, J. C. Hennet, F. Szigeti \hfil EJDE/Conf/13 \hfilneg] {Jean Louis Calvet, Juan Cardillo, \\ Jean Claude Hennet, Ferenc Szigeti} % in alphabetical order \address{Jean Louis Calvet \hfill\break Laboratoire d'Analyse et d'Architecture de Syst\'emes (LAAS) du CNRS, Toulouse, France, LAAS-CNRS} \email{calvet@laas.fr} \address{Juan Cardillo \hfill\break Departamento de Sistemas de Control, Escuela de Ingenier\'{\i}a de Sistemas, Universidad de Los Andes, M\'erida, Venezuela} \email{ijuan@ula.ve} \address{Jean Claude Hennet \hfill\break Laboratoire d'Analyse et d'Architecture de Syst\'emes (LAAS) du CNRS, Toulouse, France, LAAS-CNRS} \email{hennet@laas.fr} \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@icnet.com.ve} \date{} \thanks{Published May 30, 2005.} \subjclass[2000]{93C65, 49M20, 74P20} \keywords{Discrete Systems; relaxation; optimization} \begin{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. \end{abstract} \maketitle \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \section{Introduction} The relaxation technique can be describe in a simple way for the minimization of a function on a finite domain, $f:\{ {1,2, \dots ,n} \} \to \Re $ as follows: To each function on the domain $Z_n=\{1,2,\dots,n \}$, associate another function on the set of probability measures as, \begin{equation} %1.1 \hat P = \{ {P = ( {p( i )} ):0 \le p( i )\;\sum_{i = 1}^n {p( i )} = 1} \}, \end{equation} in the form: \begin{equation} %1.2 i \mapsto f( i ) \Longleftrightarrow P \to E_P ( f ) = \sum_{i = 1}^n {p( i )f( i)}. \end{equation} Also, $\hat P$, the domain of the mathematical expectation, is a natural extension of the domain $Z_n$. Indeed, to each $i\in Z_n$ we can be associated the probability measure \begin{equation} %1.3 P_i = ( {0, \dots ,0,\mathop 1_i ,0 \dots ,0}), \end{equation} that is, \begin{equation} %1.4 p_i ( j ) = \begin{cases} 1, &j = i, \\ 0, &j\ne i\,. \end{cases} \end{equation} It is easy to see that the global minimum of the nonlinear problem $\min_{i\in Z_n} f(i)$ and the minimum of the lineaf function coincides in $i_0 \to 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 \cite{JW62,JW162} is has been analyzed the equivalence between the original problem and the relaxed problem 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. \section{Discrete Event Process Optimization Problem (Discrete Event System)} Consider the optimization problem \begin{equation} \label{ec21} x(k+1)=A(u(k))x(k)+b(u(k)), x(0)=0, \end{equation} where $A:\{-1,1\}^m\to \mathbb{R}^{n\times n}$, $b:\{-1,1\}^m \to \mathbb{R}^{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),\dots,u(K-1)$ is denominated control (decision). The trajectory associated to the control is the sequence $x(0), x(1),\dots,x(K)$, calculated for (\ref{ec21}). The cost function $\Phi:\mathbb{R}^n\to \mathbb{R}$ is defined by $J(x,u)=\Phi(x(K))$. Now, the objective is to find a sequence $u^*(0), u^*(1),\dots,u^*(K-1)$ , such that, for the corresponding trajectory $x^*(0), x^*(1),\dots,x^*(K)$, \begin{equation} J(x^*,u^*)=\Phi(x^*(K))\leq \Phi(x(K))=J(x,u), \end{equation} be satisfied, for every $u(0), u(1),\dots,u(K-1)$. The minimum principle is a necessary condition for the optimal control $u^*(0), u^*(1),\dots,u^*(K-1)$. To state our results, we need the concept of varied trajectory \[ x_{i,u}(0), x_{i,u}(1),\dots, x_{i,u}(K) \] and the dual trajectory $\varphi_{i,u}(i+1),\varphi_{i,u}(i+2),\dots, \varphi_{i,u}(K)$: \begin{gather*} x_{i,u} ( k ) = x^* ( k), k \le 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, \\ \varphi _{i,u} ( k ) = A( {u^* ( k )})^T \varphi _{i,u} ( {k + 1} ),\\ \varphi_{i,u} ( K ) = R\Phi ( {x^* ( K);x_{i,u} ( K )} ),\quad k > i, \end{gather*} where \begin{equation} %2.3 R\Phi(x^*(K);x(K))=\int_{0}^{1} \mathop{\rm grad}\Phi(x^*(K)+t(x_{i,u}(k)-x^*(K)). \end{equation} Then the optimality criterion is the inequality: \begin{equation} %2.4 \langle\varphi_{i,u}(i+1),A(u^*(i))x^*(i)+b(u^*(i))\rangle\leq \langle\varphi_{i,u}(i+1),A(u(i))x^*(i)+b(u(i))\rangle\ \end{equation} for everything $i$ and $u$. (see minimum principle on finite domains \cite{JC03}). Here the relaxation is defined using the dynamics for $i$, and the probability measure $P=(p(u))$, $u\in\{-1,1\}^{m}$, as follows. The trajectory $x_{i,P} ( 0 ),x_{i,P} ( 1), \dots ,x_{i,P} ( K )$, is defined by \begin{gather*} x_{i,P} ( k ) = x^* ( k ),{\rm{ k}} \le i,\\ x_{i,P} ( {i + 1} ) = \sum_u^{} {p( u)} ( {A( u )x^* ( k ) + b( u)} ),\\ x_{i,P} ( {k + 1} ) = A( {u^* ( k )})x_{i,P} ( k ) + b( {u^* ( k )}), \quad k > i. \end{gather*} The relaxation problem consists on giving conditions such that \[ \Phi ( {x^* ( K )} ) = \min_{u( k ) \in \{ { - 1,1} \}^m } \Phi( {x( K )} )_{\forall k = 0,1, \dots K} \min_{P \in \hat P} \Phi ( {x_{i,P} (K )} )_{\forall i}\,. \] \section{Main Result} Let us observe that if $P = P_v $, this is \[ p_v ( u ) = \begin{cases} 1, & u = v, \\ 0, & u \ne v, \end{cases} \] then $x_{i,P} ( k ) = x_{i,u} ( k )$. The corresponding dual trajectory, in this case, is defined as: \[ \varphi _{i,P} ( k ) = A( {u^* ( k )} )^T \varphi _{i,P} ( {k + 1} ), \varphi _{i,P} ( K ) = R\Phi ( {x^* ( K);x_{i,P} ( K )} ) \] \begin{lemma} \label{lem1} If $0\leq\sum{c_i x(i)}$, with $\sum{x(i)}=1$, for all $x(i)\geq0$, then $0\leq c_i$. \end{lemma} \begin{proof} Let $ x_0 ( i ) = \begin{cases} 1, & i = i_0, \\ 0, & i \ne i_0, \end{cases}$. Then $0 \le \sum {c_i x_0 ( i )} = c_{i_0 }$. \end{proof} \begin{lemma} \label{lem2} 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 \begin{equation}\label{ec31} x_{i,P} ( k ) = \sum {p( u )} x_{i,u} ( k ),\quad k = i + 1,\dots ,K \end{equation} \end{lemma} \begin{proof} By definition $x_{i,u} ( i+1 ) =A(u) x^* ( i)+ b(u)$ and \[ x_{i,P} ( {i + 1} ) = \sum {p( u ) } ( {A( u )x^* ( i ) + b( u )} ) = \sum {p( u ) } x_{i,u} ( {i + 1})\,. \] Then (\ref{ec31}) is true for $i+1$. Using mathematical induction assume that (\ref{ec31}) is valid for $k$. Then for $k+1$, we have \[ \begin{array}{ll} x_{i,P} ( {k + 1} )& = A( {u^* ( k )} )x_P^{} ( k ) + b( {u^* ( k )} ) = \\ & = A( {u^* ( k )} )( {\sum_u^{} {p( u )x_{i,v}^{} ( k )} } ) + b( {u^* ( k )} ) = \\ & = \sum_u^{} {p( u )} ( {A( {u^* ( k )} )x_{i,v}^{} ( k ) + b( {u^* ( k )} )} ) = \sum_u^{} {p( u )} x_{i,v}^{} ( {k + 1} ).\square \end{array} \] which completes the proof. \end{proof} \begin{theorem} \label{thm1} Assume that $\Phi $ is concave over a convex domain $D \subset \mathbb{R} ^n $; i.e., for every $\lambda,\mu\geq0$, with $\lambda+\mu=1$, and $x,y \in D$, \[ \lambda\Phi(x)+\mu\Phi(y)\leq\Phi(\lambda x+\mu y)\,. \] Then the relaxed problem and the original problem have the same minimum. That is, $u^*(0), u^*(1),\dots,u^*(K-1)$, is the optimal control, then, for each $i$ fixed, the $i$-th relaxed problem $\mathop {\min }_{P \in \hat P} \Phi ( {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 \ne u^* ( i ). \end{cases} \] \end{theorem} \begin{proof} First we will prove the equalities \begin{align*} &\Phi ( {x_{i,P} ( K )} ) - \Phi ( {x^*( K )} )\\ & = \sum_u^{} {p( u )}\langle {\varphi _{i,P} ( {i + 1} ),( {A( u )x^* ( i ) + b( u )}) - ( {A( {u^* ( i )} )x^* ( i ) + b( {u^* ( i )})} )}\rangle \end{align*} \begin{equation}\label{ec32} \begin{aligned} &\Phi ( {x_{i,P} ( K )} ) - \Phi ( {x^*( K )} )\\ & = R\Phi ( {x^* ( K);x_{i,P} ( K )} )( {x_{i,P} ( K) - x^* ( K )} )\\ & = \langle {\varphi _{i,P} ( K ),x_{i,P} ( K ) - x^*( K )} \rangle\\ &= \langle \varphi _{i,P} ( K ),A( {u^* ( {K - 1} )} )x_{i,P} ( {K - 1} ) + b( {u^* ( {K - 1} )} ) \\ &\quad - A( {u^* ( {K - 1} )} )x^* ( {K - 1} ) - b( {u^* ( {K - 1} )} ) \rangle \\ &= \langle {A( {u^* ( {K - 1} )} )^T \varphi _{i,P} ( K ),x_{i,P} ( {K - 1} ) - x^* ( {K - 1} )} \rangle \\ &= \langle {\varphi _{i,P} ( {K - 1} ),x_{i,P} ( {K - 1} ) - x^* ( {K - 1} )} \rangle = \dots \\ & = \langle {\varphi _{i,P} ( {i + 1} ),x_{i,P} ( {i + 1} ) - x^* ( {i + 1} )} \rangle \\ & = \langle {\varphi _{i,P} ( {i + 1} ),\sum_u^{} {p( u )} ( {A( u )x^* ( i ) + b( u )} ) - ( {A( {u^* ( i )} )x^* ( i ) + b( {u^* ( i )} )} )} \rangle \\ &= \sum_u^{} {p( u )} \langle {\varphi _{i,P} ( {i + 1} ),( {A( u )x^* ( i ) + b( u )} ) - ( {A( {u^* ( i )} )x^* ( i ) + b( {u^* ( i )} )} )} \rangle \end{aligned} \end{equation} Now suppose that $i$-th relaxed problem has optimum $P_{u^*( i )} $. Then \[ 0 \le \Phi ( {x_{i,P} ( K )} ) - \Phi ({x^* ( K )} )\,. \] By the formula demonstrated previously, \[ 0 \le \sum_u^{} {p( u )} \langle {\varphi _{i,P} ( {i + 1} ),( {A( u )x^* ( i ) + b( u )} ) - ( {A( {u^* ( i )} )x^* ( i ) + b( {u^* ( i )} )} )} \rangle \] for every $P$, as well as for $P = P_v $ and $\varphi _{P_v ,i} ( {i + 1} ) = \varphi _{i,v} ( {i + 1} ) $. By Lemma \ref{lem1}, \begin{equation}\label{ec33} \langle {\varphi _{i,v} ( {i + 1} ),A( u^*(i) )x^* ( i ) + b( u^*(i) )} \rangle \leq \langle {\varphi _{i,v} ( {i + 1} ),A( u(i) )x^* ( i ) + b( {u ( i )} )} \rangle \end{equation} This being the minimum principle, without necessity of concavity or convexity of $\Phi$. Now, let us suppose that the minimum principle is fulfilled. For a measure of probability $P = ( {p( u )})$, multiply the inequality (\ref{ec33}) by $p(u)$ and add for everything $v \in \{ { - 1,1} \}^m $. Then \begin{align*} 0 &\le \sum_v^{} {p( v )} \langle {\varphi _{i,v} ( {i + 1} ),( {A( u )x^* ( i ) + b( u )} ) - ( {A( {u^* ( i )} )x^* ( i ) + b( {u^* ( i )} )} )} \rangle \\ &= \sum_v^{} {p( v )} \langle {\varphi _{i,v} ( {i + 1} ),x_{i,v} ( {i + 1} ) - x^* ( {i + 1} )} \rangle = \dots \\ &= \sum_v^{} {p( v )} \langle {\varphi _{i,v} ( K ),x_{i,v} ( K ) - x^* ( K )} \rangle = \sum_v^{} {p( v )} ( {\Phi ( {x_{i,v} ( K )} ) - \Phi ( {x^* ( K )} )} ) \\ & \le \Phi ( {\sum_v^{} {p( v )} x_{i,v} ( K )} ) - \sum_v^{} {p( v )} \Phi ( {x^* ( K )} ) = \Phi ( {x_{i,P} ( K )} ) - \Phi ( {x^* ( K )} ), \end{align*} 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. \end{proof} \section{Examples} \subsection*{Example 4.1} Consider the following system, linear in $x( k )$, \begin{equation} %4.1 x(k+1)=A(u(k))x(k)+b(u(k)), x(0)=\xi \end{equation} with the linear cost function \[ \Phi ( {x( K )} ) = \langle {\varphi ,x( K )} \rangle\,. \] The linear application $\langle {\varphi ,x( K )} \rangle $ 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 $\varphi ( K ) = \varphi $ is independent of the perturbation or of the relaxation. Hence in this case the minimum principle came be expressed in the classic form \[ \langle {\varphi ( {i + 1} ),A( {u^* ( i )} )x^* ( i ) + b( {u^* ( i )} )} \rangle = \mathop {\min }_u \langle {\varphi ( {i + 1} ),A( u )x^* ( i ) + b( u )} \rangle \] or using the Hamiltonian form \begin{equation} H(x^*(i),u^*(i),\varphi(i+1))\leq H(x^*(i),u,\varphi(i+1)). \end{equation} Note that the Hamiltonian is defined as $H( {x,u,\varphi }) = \langle {\varphi ,A( u )x + b( u)} \rangle $. \subsection*{Example 4.2} Consider the same linear system with \[ x( {k + 1} ) = A( {u( k )} )x( k ) + b( {u( k )}),x (0) = \xi \] with positive semi definite quadratic cost function \[ \Phi ( {x( K )} ) = \langle {Qx( K ),x( K )} \rangle \] and the same considerations for the perturbed system and for the relaxed system. Then \begin{align*} &\Phi ( {x_{i,P} ( K )} ) - \Phi ( {x^*( K )} ) \\ &= \sum_u {p( u )}\langle {\varphi _{i,P} ( {i + 1} ),A( u )x^* ( i ) + b( u ) - A( {u^*( i )} )x^* ( i ) + b( {u^* ( i )} )} \rangle \end{align*} Suppose that $v$ is such that \[ p_{i,v} ( u ) = \begin{cases} 1, & u = v, \\ 0, & u \ne v\,. \end{cases} \] If $ 0 \le \Phi ( {x_{i,v} ( K )} ) - \Phi( {x^* ( K )} )$, (minimum), $\Phi $ is smooth in $ x^* ( K )$ and it is convex, then the tangent hyperplane that separates the convex body $\{ {x:\Phi ( x ) \le \Phi ( {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 \in \{ { - 1,1}\}^m } \}$; thats is the points $x_{i,P} ( K) = \sum_u {p( u )} x_{i,v} (K )$. Hence why, $ \Phi ( {x_{i,P} ( K )} ) \ge\Phi ( {x^* ( K )} )$. Thus \[ 0 \le \Phi ( {x_{i,P} ( K )} ) - \Phi ( {x^* ( K )} ) = \Phi ( {\sum_v^{} {p( v )} x_{i,v} ( K )} ) - \Phi ( {x^* ( K )} ) \] and the two problems are equivalent. The previous idea is illustrated in Figure 1. \begin{figure}[ht] \label{fig1} \begin{center} \setlength{\unitlength}{.8mm} \begin{picture}(102,80)(8,20) \qbezier(30,54)(19,48)(8,36) \qbezier(8,36)(25,38)(32,20) \qbezier(32,20)(67,50)(104,30) \qbezier(104,30)(106,38)(110,40) \qbezier(110,40)(101,53)(84,60) \drawline(23,60)(50,38)(90,64)(68,78)(23,60) \put(45,48){$x^*(K)$} \drawline(60,60)(97,80) \drawline(95,80.5)(97,80)(96.2,78.2) \put(97,76){$x_P(K)$} \drawline(60,60)(30,82) \drawline(30.7,80.2)(30,82)(32,82) \put(20,76){$x_{P_v}(K)$} \drawline(60,60)(60,100) \drawline(59,98)(60,100)(61,98) \end{picture} \end{center} \caption{A geometric interpretatoion of $\langle Qx,x\rangle\leq \langle Qx^*(K),x^*(K)\rangle$} \end{figure} \subsection*{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. \begin{thebibliography}{99} \bibitem{AB00} 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. \bibitem {JC03} Juan Cardillo; Optimización de Sistemas a Eventos Discretos, Tesis de Doctorado, 2003. \bibitem {JL01} 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 \bibitem {JL03} J. B. Lasserre , T. Prieto; Rumeau SDP Vs. LP Relaxations for the moment approach in some performance evaluation problems, Rapport LAAS N°03125, Mars 2003, 16p. \bibitem {JW62} J. Warga; Relaxed Variational Problem, Journal o Mathematical Analysis and Applications, 4, 111-128, 1962. \bibitem {JW162} J. Warga; Necessary Condition for Minimum in Relaxed Variational Problem, Journal of Mathematical Analysis and Applications 4, 129-145, 1962. \bibitem {JW72} J. Warga; Optimal Control of Differential and Functional Equations, Academic Press 1972, Card Number 72-87229. \end{thebibliography} \end{document}