\documentstyle{article} \setlength{\headsep}{-0.9cm} \setlength{\textheight}{21.5cm} \setlength{\textwidth}{14.5cm} %\setlength{\baselineskip}{12pt} \setlength{\evensidemargin}{1.0cm} \setlength{\oddsidemargin}{1.0cm} \title{ \centerline{Numerical Solution of Discrete Quadratic} \centerline{Optimal Control Problems} } \author{Carla Durazzi$^1$ and Emanuele Galligani$^2$ \\ $^1$Department of Mathematics, University of Padova, Padova, Italy \\ $^2$Department of Mathematics, University of Modena, Modena, Italy } \date{} \pagestyle{empty} \newcommand{\ve}[1]{\mbox{\boldmath $#1$}} \begin{document} \maketitle Consider a dynamical system described by the linear difference equation $$\ve x_{i+1} = E \ve x_i + F \ve u_i \ \ \ \ i=0,1,...,k-1 \label{1}$$ where $\ve x_i \in R^n$ is the system state at time $i$, $\ve u_i \in R^m$ is the system control (or input) at time $i$, $E$ is an ${n\times n}$ matrix and $F$ is an ${n\times m}$ matrix. \noindent In conjuction with the system equation (\ref{1}), the initial and terminal constraints are given $$G_0 \ve x_{0} = \ve c_0 \ \ \ \ \ \ G_k \ve x_{k} = \ve c_k \label{2}$$ where $G_0$ is an $l_0\times n$ matrix of rank $l_0$ and $G_k$ is an $l_k\times n$ matrix of rank $l_k$; $\ve c_0 \in R^{l_0}$ and $\ve c_k \in R^{l_k}$ are fixed vectors. The formulation of discrete optimal control problem with quadratic cost is to find a control vector $\ve u^* = ({\ve u_0^*}^T, {\ve u_1^*}^T, ..., {\ve u_{k-1}^*}^T)^T$ and a corresponding trajectory $\ve x^* = ({\ve x_0^*}^T, {\ve x_1^*}^T, ..., {\ve x_{k}^*}^T)^T$, determined by (\ref{1}), which minimize the quadratic function $$\frac{1}{2} \ve x^T Q_x \ve x + \ve u^T Q_u \ve u \label{3}$$ where $Q_x$ is a $(k+1)\cdot n \times (k+1)\cdot n$ symmetric positive semidefinite block diagonal matrix and $Q_u$ is a $k\cdot m \times k \cdot m$ symmetric positive definite block diagonal matrix. \noindent Often it is useful to write the function (\ref{3}) in the form $\frac{1}{2} \ve z^T Q \ve z$ where $$\ve z=({\ve x}^T, {\ve u}^T)^T= (\ve x_0^T, \ve x_1^T, ..., \ve x_{k}^T, \ve u_0^T, \ve u_1^T, ..., \ve u_{k-1}^T)^T$$ and the $((k+1)\cdot n +k\cdot m) \times ((k+1)\cdot n+ k\cdot m)$ matrix $$Q=\left[ \matrix{Q_x & 0 \cr 0 & Q_u} \right]$$ is symmetric positive semidefinite block diagonal. \noindent It is well known that discrete optimal control problems can be viewed as nonlinear programming problems with a special structure and, usually, large dimensions. \noindent This paper is concerned with the development of two different transcriptions of problem (\ref{1})--(\ref{3}) into a quadratic programming problem which is solved with the {\it Hestenes' method of multipliers} combined with the {\it conjugate gradient algorithm}. \noindent This method is well suitable for parallel implementation on vector--parallel computers. \noindent Conditions for the convergence of the method are established and results of some computational experiments, which are aimed at evaluating the {\it effectiveness} of the method, are reported. \end{document} 