\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
\begin{equation}
\ve x_{i+1} = E \ve x_i + F \ve u_i   \ \ \ \ i=0,1,...,k-1
\label{1}
\end{equation}
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
\begin{equation}
G_0 \ve x_{0} = \ve c_0  \ \ \ \ \ \ G_k \ve x_{k} = \ve c_k
\label{2}
\end{equation}
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
\begin{equation}
\frac{1}{2} \ve x^T Q_x \ve x + \ve u^T Q_u \ve u
\label{3}
\end{equation}
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}