text:
\begin{document}

\title{\large Asymptotic Exponential Arbitrage\\ and Utility-based Asymptotic Arbitrage in\\ Markovian Models of Financial
Markets\thanks{The authors thank the referee and the associate editor for extremely constructive and
helpful reports.}}

\author{Martin Le Doux Mbele Bidima\thanks{University of Yaound\'e I, Cameroon, e-mail: mbelebidima@gmail.com} \and Mikl\'os R\'asonyi
\thanks{MTA Alfr\'ed R\'enyi Institute of Mathematics, Budapest, Hungary and University of Edinburgh, U.K., e-mail: rasonyi@renyi.mta.hu
}}

\date{\today}

\maketitle

\begin{abstract}

Consider a discrete-time infinite horizon financial market model in which the logarithm of
the stock price is a time discretization of a stochastic differential equation. Under conditions different from those given in \cite{MR}, we prove
the existence of investment opportunities producing an exponentially growing profit with probability tending to $1$
geometrically fast. This is achieved using ergodic results on Markov chains and tools of large deviations theory.

Furthermore, we discuss asymptotic arbitrage in the expected utility sense and its
relationship to the first part of the paper.

\end{abstract}

\noindent{\bf Keywords:} Asymptotic exponential arbitrage, Markov chains, large deviations, expected utility.

\section{Introduction}

In the classical theory of financial markets,  absence of arbitrage (riskless profit)
is characterized by the existence of suitable ``pricing rules'': risk-neutral (i.e. equivalent martingale) measures for the discounted price process of the
risky asset. This result is often referred to as ``the fundamental theorem of asset pricing''.

Further developments of arbitrage theory encompass the so-called ``large financial markets'' (see \cite{KK2}, \cite{FSr} and the references therein).
In these papers the following common feature of numerous models is highlighted: on each finite time horizon $T>0$, there is no arbitrage opportunity but when $T$ tends to infinity, one may realize riskless profit in the long
run. Such trading opportunities
are referred to as ``asymptotic arbitrage''.

An important tool that can be used for the study of asymptotic arbitrage is the theory of large deviations (see  \cite{DZ}), as proposed in
\cite{FSr}. More recently, in \cite{MR} we presented  the discrete-time versions of some results in \cite{FSr} about asymptotic arbitrage and, in this framework, we extended
them by studying ``asymptotic exponential arbitrage with geometrically decaying probability of failure'', i.e. we discussed the possibility for investors to realize an exponentially growing profit on their long-term investments while controlling (at a geometrically decaying rate) the probability of failing to achieve such a profit.
Some of these results were subsequently proved for continuous-time models in \cite{KN}. In the present paper
we prove results similar to Theorem 5 of \cite{MR} using different arguments and technical tools (the large deviation results of \cite{KM2} instead of those in \cite{KM1}). In this way we manage
to cover some well-known models for asset prices which were untractable in the
setting of \cite{MR}, see Examples \ref{ex2.16}, \ref{exnew} below.
We recall now the setting of \cite{MR}.

Consider a financial market in which two assets are traded: a riskless asset (a bank account or a risk-free bond) with interest rate set to $0$, i.e. with price normalized to $B_t:=1$ at all times $t\in\mathbb{N}$; and a single risky asset (such as stock) whose (discounted) price is assumed to evolve as
\be\label{eq1}
S_t:=\exp(X_t),\quad t\in\mathbb{N},
\e
where the logarithm of the stock price, $X_t$, is an $\mathbb{R}$-valued stochastic process governed by the discrete time difference equation
\be\label{eq2}
X_t-X_{t-1}=\mu(X_{t-1})+\sigma(X_{t-1})\varepsilon_t,\quad t\geq 1,
\e
starting from a constant $X_0\in\mathbb{R}$. Here $\mu,\,\sigma:\mathbb{R}\to\mathbb{R}$ are measurable functions
(determining the drift and volatility of the stock) and $(\varepsilon_t)_{t\in\mathbb{N}}$ is an $\mathbb{R}$-valued sequence of i.i.d. random variables representing the random driving process of the stock price evolution.

Note that the log-price process $X_t$ is clearly a (discrete-time) Markov chain in the (uncountable) state space $\mathbb{R}$ (see pp. 211--228 in \cite{BW}). We suppose that its evolution is modelled on a filtered probability space $(\Omega,\mathcal{F},\mathbb{F},\mathbb{P})$, where $\mathbb{F}:=(\mathcal{F}_t)_{t\in\mathbb{N}}$ and $\mathcal{F}_t:=\sigma(X_s,0\le s\le t)$, is the natural filtration of the log-price process $X_t$ of the stock. In the sequel $\mathbb{E}$ denotes expectation with respect to the probability $\mathbb{P}$.

Trading strategies in this market are assumed $\mathbb{F}$-predictable $[0,1]$-valued processes $(\pi_t)_{t\geq 1}$ (i.e. $\pi_t$ is assumed $\mathcal{F}_{t-1}$-measurable) and no short-selling or borrowing are allowed. This means that, at each time $t$, investors allocate a proportion $\pi_t\in [0, 1]$ of their overall wealth to the
stock while the rest remains in the bank account. Hence, given any such strategy, the corresponding wealth process $V_t^{\pi}$ of an investor  obeys the dynamics
\be\label{eq3}
 \frac{V_t^{\pi}}{V_{t-1}^{\pi}}=(1-\pi_t)+\pi_t\frac{S_t}{S_{t-1}},\quad \mbox{for all }t\ge 1,
\e
where $V_0^{\pi}:=V_0>0$ is the investor's initial capital.

\begin{definition}\label{d1}\emph{(Definitions 3 and 4 of \cite{MR})} Let $\pi_t$ be a trading strategy.

 $i)$ We say that $\pi_t$ is an asymptotic exponential arbitrage ($AEA$) in the wealth model \eqref{eq3} if there is a constant $b>0$ such that, for all $\epsilon>0$, there is a time $t_{\epsilon}\in\mathbb{N}$ satisfying
\be\label{ineq1}
\mathbb{P}(V_t^{\pi}\geq e^{bt})\geq 1-\epsilon,\mbox{ for all time}\,\,t\geq t_{\epsilon}.
\e

 $ii)$ We say that $\pi_t$ generates an asymptotic exponential arbitrage ($AEA$) with geometrically decaying probability  of failure $(GDPF)$ if there are constants $b>0$, and $c>0$ such that,
\begin{equation}\label{ineq2}
\mathbb{P}(V_t^{\pi}\geq e^{bt})\geq 1- e^{-ct}\mbox{ for all large enough }t\geq 1.
\end{equation}
\end{definition}

Clearly, $AEA$ with $GDPF$ implies $AEA$. The second kind of asymptotic arbitrage above is much  more stringent than the first one. Indeed, in \eqref{ineq1} above, there is no visible relationship between the tolerance level $\epsilon$ and the elapsed time $t_{\epsilon}$ from which the investor starts realizing exponentially growing profit; one may need to wait for a
very long time to achieve a desired tolerance level. The concept of $AEA$ with $GDPF$  removes this drawback  by allowing investors to control, at a geometrically decaying rate, the probability of failing to achieve an exponentially growing profit in the long term.

We recall the main results of \cite{MR} here. Under the following main assumptions: boundedness of the drift and volatility functions $\mu$ and $\sigma$; $\sigma$ being
bounded away from $0$ on compacts and exponential integrability of the $\varepsilon_t$s, we proved Theorem 2 (resp. Theorem 4) of \cite{MR} on the existence of $AEA$ (resp. $AEA$ with $GDPF$) in the wealth model \eqref{eq3}.

Theorem 5 of \cite{MR} provided ergodicity-related conditions on $X_t$
which ensured AEA with GDPF.

 In sections 2 and 3 below we continue to consider the same models as in \eqref{eq1}, \eqref{eq2}, \eqref{eq3}. Under a new set of conditions on $\mu$, $\sigma$ and $(\varepsilon_t)_{t\in\mathbb{N}}$ (see $(A_1),(A_2),(A_3),(A_4)$ below), which are neither stronger nor weaker than the corresponding conditions in \cite{MR} recalled above, we show again the existence of $AEA$ with $GDPF$ (see Theorem \ref{t2.15} below), using  classical large deviations techniques from \cite{DZ}, Markov chains tools from \cite{MT} and ergodicity results on Markov chains from \cite{KM2}. Moreover, the trading strategies generating those arbitrage
opportunities will be explicitly constructed; a contribution we already obtained in \cite{MR} under different conditions, but it was absent from the inspiring continuous-time work \cite{FSr}. To get those explicit arbitrage opportunities we will be considering only stationary Markovian strategies, that is; strategies $(\pi_t)_{t\geq 1}$ where $\pi_t=\pi(X_{t-1})$, $t\ge 1$, for some fixed measurable function $\pi:\mathbb{R}\to [0,1]$.

In section 4, we will discuss the concept of ``utility-based'' asymptotic arbitrage, that is,
asymptotic arbitrage linked to von Neumann-Morgenstern expected utilities (see Chapter 2 of \cite{FSd}). An optimal investment for
an economic agent with utility function $U$ and time horizon $T$ is $\pi_t$ with final portfolio value $V_T^{\pi}$ for
which the expected utility $\mathbb{E}U(V_T^{\pi})$ is maximal. We do not focus on the construction of
optimal strategies but rather on ones that provide (rapidly) increasing expected utilities for the agent as the time horizon tends to infinity.

More precisely,
we wish to treat questions like: for power utilities $U$, and given an $AEA$ strategy $\pi_t$ as in \eqref{ineq1},
will the investor's expected utility $\mathbb{E}U(V_t^{\pi})$ tend to the highest available utility $U(\infty)$? If so, how fast such a convergence will take place? Conversely, if an agent pursues a trading strategy $\pi_t$  such that her/his expected utility has a convergence rate estimate, will $\pi_t$ generate $AEA$ (with $GDPF$)? We provide partial answers to these questions in Proposition \ref{p3.1}, Theorem \ref{p3.3} and Theorem \ref{t3.5} below.

\section{Main theorem on AEA with GDPF}

We denote by $\lambda$ the Lebesgue measure on $\mathcal{B}(\mathbb{R})$.
We assume throughout this paper that the Markov chain $X_t$ satisfies the following conditions:

 $(A_1)$ The random variables $\varepsilon_t$s have a (common) density $\gamma$ with respect to $\lambda$, and this density is bounded and bounded
away from $0$ on each compact in $\mathbb{R}$.

 $(A_2)$ The drift $\mu$ is locally bounded. The volatility $\sigma$ is positive, bounded away from zero on each compact and it is (globally) bounded.

  $(A_3)$  We impose the mean-reverting drift condition
\be\label{a1}
\limsup_{|x|\to\infty}\frac{|x+\mu(x)|}{|x|}<1. \nonumber
\e

 $(A_4)$ We assume the following integrability property for the law of the
$\varepsilon_t$s:
\be\label{a2}
 \,\exists\, \kappa>0\mbox{ such that }\mathbb{E}\big(e^{\kappa\varepsilon_1^2}\big)=:I<\infty,
\e

and $\mathbb{E}\varepsilon_1=0$ holds\footnote{This is not a restriction
of generality.
If we had $\mathbb{E}\varepsilon_1=m$, we could replace $\mu(x)$ by $\mu'(x):=\mu(x)+\sigma(x)m$
and $\varepsilon_t$ by $\varepsilon_t':=\varepsilon_t-m$ and in this way
get back to the case $\mathbb{E}\varepsilon_1=0$.}.

\begin{remark} {\rm These conditions are similar to those of \cite{MR}. The main difference
is that $\mu$ was assumed to be a bounded function in \cite{MR} while it may
be unbounded in the present paper. In this way we accomodate e.g. autoregressive processes (see Examples \ref{ex2.16} and \ref{exnew} below), which did not fit the setting
of \cite{MR}. While we relax boundedness of $\mu$, we need the integrability condition $(A_4)$ on $\varepsilon_t$, which is more stringent than the ones in \cite{MR}. Furthermore, $(A_3)$
is a much stronger ergodicity condition on the Markov chain $X_t$ than that
of Theorem 5 in \cite{MR}. Hence our main result (Theorem \ref{t2.15}) does not generalize \cite{MR} but rather complements it.}
\end{remark}

\begin{remark}
{\rm Analogously to \cite{FSr}, where the exponential of an Ornstein-Uhlenbeck process
was considered, our conditions imply that the log-price $X_t$ is ergodic
(in a strong sense). It may be argued on ecomonetric grounds that the price increments $X_t/X_{t-1}$ rather than $X_t$ should be assumed ergodic.
Just like in \cite{MR}, we opted for the present setting in order to be consistent
with \cite{FSr}. Very similar arguments could be used to prove analogous
results for the case where $X_t/X_{t-1}$ is assumed to be an ergodic Markov chain. We do not pursue this
route here.}
\end{remark}

Consider the following condition:
\be\label{rc+}
\mbox{$(RC_+)$ \,\,\,\,The set}\,\,R^+:=\{x\in\mathbb{R}\mid \mu(x)> 0\}\,\,\mbox{ satisfies }\lambda(R^+)>0.
\e

 We interpret $R^+$ as representing all states of the stock $\log$-prices $X_t$ whose
``drift'' is positive. Thus $(RC_+)$ means that the set of states $x$ from which there is a ``bright future''
(i.e. there is an upward trend for the stock price) has positive Lebesgue measure. This is rather natural: note that
short-selling is prohibited in our model hence negative market trends
cannot be taken advantage of. We now state the main result of the present article.

\begin{theorem}\label{t2.15} Assume that $(A_1)-(A_4)$ and $(RC_+)$ hold. Then the Markovian strategy
$\pi_t^+:=\mathbf{1}_{R^+}(X_{t-1})$ produces an $AEA$ with $GDPF$.
\end{theorem}

The proof will be presented at the end of the next section, after appropriate
preparations.

\section{Large deviation estimates}

Consider the $\mathbb{R}^2$-valued auxiliary process $\Phi_t:=(X_{t-1},X_t)$, $t\ge 0$, consisting of two consecutive values of the log-price process $X_t$, where $X_{-1}$ is an arbitrarily chosen constant. We
present below a set of preliminary results.

\begin{proposition}\label{p2.1} The process $\Phi_t$ is a Markov chain with state space $\mathbb{R}^2$.
\end{proposition}

 {\bf Proof.} We derive this from \cite{BW} pp. 211-228, where the Markov property of any (discrete-time)
 process $Y_t$ in a Polish state space $S$ is proved when  $Y_{t+1}=m(Y_t, \xi_{t+1})$ with
 $(\xi_t)_t$ a sequence of i.i.d. random variables independent of $Y_0$ and valued in some measurable space $S'$ and
 $m:S\times S'\to S$ a measurable function. Clearly, $X_{t+1}=m(X_t,\varepsilon_{t+1})$ for $t\in\mathbb{N}$
 with $m(x,y):=x+\mu(x)+\sigma(x)y$, $x,y\in\mathbb{R}$. It follows that we have
 $\Phi_{t+1} = (X_t,X_{t+1})=(X_t,m(X_t,\varepsilon_{t+1}))=F(\Phi_t,\xi_{t+1})$, where
 $\xi_t:=(0,\varepsilon_t)$ and $F$ is the measurable function defined on $S\times S':=\mathbb{R}^2\times\mathbb{R}^2$ by
 $F((x,y),(a,b)):=(y,m(y,b))$. Since the $\varepsilon_t$s are i.i.d. and independent of $X_0$,
 the $\xi_t$s are also i.i.d. and independent from $\Phi_0$, showing the result. \hfill $_{\blacksquare}$

Notice that
$$
P(x,A):=P(X_1\in A|X_0=x)=\int_{A} p(x,y)dy,\ x\in\mathbb{R},\ A\in\mathcal{B}(\mathbb{R}),
$$
where
$$
p(x,y):=\frac{1}{\sigma(x)}\gamma\left(\frac{y-\mu(x)-x}{\sigma(x)}\right),
$$
and this function is bounded away from $0$ on each compact in $\mathbb{R}^2$,
by $(A_1)$ and $(A_2)$.

For $z\in\mathbb{R}^2$ and $A\in\mathcal{B}(\mathbb{R}^2)$,
let $Q^t(z,A):=P(\Phi_t\in A|\Phi_0=z)$ be the $t$-step transition kernel of
the chain $\Phi_t$.

We note that, for $t\geq 2$ and $A\in\mathcal{B}(\mathbb{R}^2)$,
\begin{equation}\label{mkkk}
Q^t((u,v),A)=\int_{\mathbb{R}^{t}} 1_A(a_{t-1},a_{t})p(v,a_1)p(a_1,a_2)\ldots p(a_{t-1},a_t)da_1\ldots
da_{t},\ u,v\in\mathbb{R}.
\end{equation}

Let $\lambda_2$ denote the Lebesgue measure on $\mathcal{B}(\mathbb{R}^2)$.

\begin{proposition}\label{p2.2} The Markov chain $\Phi_t$ is $\psi$-irreducible, i.e. there is a non-trivial measure $\psi$ such that $\psi(A)>0$ implies that for all $z$, $Q^t(z,A)>0$ for some $t$.
\end{proposition}

 {\bf Proof.} It suffices to check that $\lambda_2$ is such a measure. If $\lambda_2(A)>0$ then for $t=2$ we
get from \eqref{mkkk} that
$$
Q^2((u,v),A)=\int_{\mathbb{R}^{2}} 1_A(a_1,a_2)p(v,a_1)p(a_1,a_2)da_1\,da_2>0
$$
since $p(v,a_1)p(a_1,a_2)$ is (everywhere) positive.
\hfill $_{\blacksquare}$

We recall two definitions from Chapter 5 of \cite{MT} in our specific setting.
A set $C_2\subset \mathbb{R}^2$ is called \emph{small} if
$$
Q^t(x,A)\ge\mu(A)\,\,\mbox{for all}\,\, x\in C_2,\,A\in\mathcal{B}(\mathbb{R}^2)
$$
with some non-trivial measure $\mu$. The chain $\Phi_t$ is \emph{aperiodic} if,
for some small set $C_2$ and corresponding measure $\mu$, the greatest common
divisor of the set
\[
E_{C_2}:=\{n\ge 1: \mbox{for all }x\in C_2,\ Q^n(x,A)\ge\delta_n\mu(A)\mbox{ for some $\delta_n>0$}\},
\]
is $1$.

\begin{proposition}\label{p2.3}
If $C$ is a compact interval in $\mathbb{R}$ then $C_2:=\mathbb{R}\times C$ is a
small set for the Markov chain $\Phi_t$, and this chain is aperiodic.
\end{proposition}

{\bf Proof.} It suffices to show that for all $u\in\mathbb{R}$ and $v\in C$,
$$
Q^i((u,v),A)\geq c_i\lambda_2(A\cap (C\times C))
$$
for $i=2,3$ and appropriate constants $c_2,c_3>0$ since this implies $2,3\in E_{C_2}$.
This is true by \eqref{mkkk} with
$$
c_2=\inf_{v, a_1\in C}p(v,a_1)\inf_{a_1,a_2\in C}p(a_1,a_2),\quad
c_3=\inf_{a_2,a_3\in C}p(a_2,a_3) \inf_{v,a_1\in C}p(v,a_1)
\inf_{a_1,a_2\in C}p(a_1,a_2)\lambda(C).
$$
\hfill $_{\blacksquare}$

Now we need certain moment estimates.
\begin{lemma}\label{l2.4} The random variable $\varepsilon_1$ in \eqref{a2} of Assumption $(A_4)$ satisfies the following property: there is $c>0$ such that for every real number $a\geq 1$ we have
\begin{equation}\label{csillagok}
\mathbb{E}\big(e^{a|\varepsilon|}\big)\le e^{ca^2}.
\end{equation}
\end{lemma}

{\bf Proof.} Set $\xi:=|\varepsilon_1|$. Then we have
 \be
 \begin{array}{lll}
  \mathbb{P}\big(e^{a\xi}>x\big) &=& \mathbb{P}\Big(\exp\Big(\kappa\Big[\frac{\log(e^{a\xi})}{a}\Big]^2\Big)>\exp\Big(\kappa\Big[\frac{\log x}{a}\Big]^2\Big)\Big)\\ \nonumber

                           &\le& I\exp\Big(-\kappa\big(\log(x)/a\big)^2\Big)\,\,\mbox{by Markov's inequality} \\ \nonumber
                           &=& I(\frac{1}{x})^{(\kappa/a^2)\log x},
\end{array}
\e
see \eqref{a2} for the definition of $I$.
 Since the exponent $(\kappa/a^2)\log x > 2$ provided that $x>e^{2a^2/\kappa}$, we have $\mathbb{E}\big(e^{a\xi}\big)=\int_0^{\infty}\mathbb{P}\big(e^{a\xi}>x\big)dx\le e^{2a^2/\kappa}+I\int_{\exp(2a^2/\kappa)}^{\infty}1/x^2dx$. The last integral is less than $\int_1^{\infty}1/x^2dx$, which is finite, thus we conclude the proof of
\eqref{csillagok} by taking $c=c_1+(2/\kappa)$ with $c_1>0$ large enough. \hfill $_{\blacksquare}$

The proof of Theorem \ref{t2.15} will be based  on results from \cite{KM2}. In order to apply
the results of that paper we will need to verify that the Markov chain $\Phi_t$ satisfies condition $(DV3+)$
below. We formulate this condition only in the case where the state space is $\mathbb{R}^d$.

We say that a $\psi$-irreducible and aperiodic Markov chain $Z_t$ with transition law
$R=R(x,A)$ satisfies condition $(DV3+)$ if
\begin{enumerate}

\item[(i)] There are measurable functions $V,W:\mathbb{R}^d\to [1,\infty)$ and a small
set $C$ such that for all $x\in\mathbb{R}^d$,
\begin{equation}\label{cry}
\log (e^{-V}Re^V)(x)\leq -\delta W(x) + b\mathbf{1}_C(x)
\end{equation}
for some $\delta,b>0$.

\item[(ii)] There exists $t_0>0$ such that, for each $r<\Vert W\Vert_{\infty}$, there is
a measure $\beta_r$ with $\beta_r(e^V)<\infty$ and
\begin{equation}\label{ad}
\mathbb{P}_x(Z_{t_0}\in A\mbox{ and }Z_t\mbox{ has not quitted }C_W(r)\mbox{ before }t_0+1)\leq
\beta_r(A)
\end{equation}
for all $x\in C_W(r)$ and $A\in\mathcal{B}(\mathbb{R}^d)$,
where $C_W(r)=\{y\in\mathbb{R}^d:\ W(y)\leq r\}$.
\end{enumerate}

We now recall the results of \cite{KM2} which we will need in the sequel. Let $W_0:\mathbb{R}^d\to [1,\infty)$
such that
\be\label{eq18}
\lim_{r\to\infty}\sup_{x\in\mathbb{R}^d}\Big(\frac{W_0(x)}{W(x)}{\bf 1}_{\{W(x)>r\}}\Big)=0.
\e
Next, consider the Banach space $L_{\infty}^{W_0}:=\{g:\mathbb{R}^d\to\mathbb{C}:\sup_{x}\frac{|g(x)|}{W_0(x)}<\infty\}$,
equipped with the norm $\|g\|_{W_0}:=\sup_{x}|g(x)|/W_0(x)$.

\begin{theorem}\label{alap} Let $Z_t$ satisfy $(DV3+)$ with unbounded $W$. Then
$Z_t$ admits an invariant probability measure $\nu$, the limit
$$
\Lambda(g):=\lim_{t\to\infty} \frac{1}{t}\ln \mathbb{E}_z [\exp(\sum_{n=1}^t g(Z_n))]
$$
exists and it is finite for all $g\in L_{\infty}^{W_0}$ and for all initial values $Z_0=z$ (and it is independent of $z$). Fix $g_0\in L_{\infty}^{W_0}$.
The function
$\theta\to \Lambda(g_0+\theta g)$ is analytic in $\theta$ with Taylor-expansion
$$
\Lambda(g_0+\theta g)=\Lambda(g_0)+\theta \nu(g)+\frac{1}{2}\theta^2 \sigma^2(g)+O(\theta^3),
$$
where $\sigma^2(g):=\lim_{t\to\infty}(1/t)\mathrm{var}(g(Z_0)+\ldots+g(Z_{t-1}))$.
\end{theorem}
\begin{proof}
This follows from Theorems 1.2 and 4.3 of \cite{KM2}.
\end{proof}

Let us define $\Lambda_g(\theta):=\Lambda (\theta g)$ for $\theta\in\mathbb{R}$. Denote
$$
\Lambda_g^*(x):=\sup_{\theta\in\mathbb{R}}(\theta x-\Lambda_g(\theta)),\quad x\in\mathbb{R},
$$
the Fenchel-Legendre conjugate of $\Lambda_g(\cdot)$.
\begin{corollary}\label{kp}
Under the conditions of the previous Theorem, if $\sigma^2(g)>0$ then
$\Lambda_g^*(x)>0$ for all $x\neq \nu(g)$.
\end{corollary}

{\bf Proof.} $\Lambda_g$ is analytic, a fortiori, it is differentiable. $\Lambda_g(0)=0$ by the definition of $\Lambda$.
From the Taylor expansion of the preceding Theorem,
$\Lambda_g'(0)=\nu(g)$ and $\Lambda_g''(0)=\sigma^2(g)>0$ so we get that $\Lambda_g^*(\nu(g))=\nu(g)\times 0-\Lambda_g(0)=0$. By the definition of a conjugate function we always have
$\Lambda_g^*(x)\ge 0\times x-\Lambda_g(0)=0$ for all $x\in\mathbb{R}$. It follows that $\nu(g)$ is a global minimiser for $\Lambda_g^*$.
By the differentiability of $\Lambda_g$, $\Lambda_g^*$ is strictly convex on its effective domain. This implies that the global minimiser
$\nu(g)$ for $\Lambda_g^*$ is unique. This uniqueness implies that $\Lambda_g^*(x)>0$ for all $x\ne\nu(g)$.
\hfill $_{\blacksquare}$

In order to apply these results to our long-term investment problems we need to establish that $\Phi_t$ satisfies $(DV3+)$.
First we prove a related statement about $X_t$.

\begin{proposition}\label{p2.5} The Markov chain $X_t$ satisfies the ``drift condition'' \eqref{cry} for $d=1$,
$R(x,A)=P(x,A)$ with a suitable compact interval $C\subset \mathbb{R}$ and $V(x)=W(x)=1+qx^2$ with a suitable $q>0$.
\end{proposition}

 {\bf Proof.} Recall that $R\,e^V(x):=\int e^{V(y)}R(x,dy)$, for all $x\in\mathbb{R}$.
We have to show
\be\label{ineq10}
 P\,e^V(x)\le e^{V(x)-\delta W(x) + b{\bf 1}_C(x)}\,\,\mbox{for all}\,\, x\in\mathbb{R}
\e
for suitably small $q>0$ and $C=[-K,K]$ with $K$ suitably large.

 Since $Pe^V(x)=\mathbb{E}\big(e^{V(X_1)}\mid X_0=x\big)=\mathbb{E}\big(e^{V(x+\mu(x)+\sigma(x)\varepsilon_1)}\big)$, it follows from \eqref{ineq10} that we need to show,
\be\label{ineq11}
 \mathbb{E}\big(e^{1+q(x+\mu(x))^2+2q(x+\mu(x))\sigma(x)\varepsilon_1+q\sigma^2(x)\varepsilon_1^2}\big)\le e^{(1-\delta)V(x)+b{\bf 1}_C(x)}\,\,\mbox{for all}\,\,x\in\mathbb{R}.
\e

 To get this, it is sufficient to prove the two claims below:

 {\bf Claim 1:} For all $x$ with $|x|>K$ with $K$ large enough we have
\be\label{e8}
 \mathbb{E}\big(e^{1+q(x+\mu(x))^2+2q(x+\mu(x))\sigma(x)\varepsilon_1+q\sigma^2(x)\varepsilon_1^2}\big)\le e^{(1-\delta)(1+qx^2)}
\e

 {\bf Claim 2:} For ``small'' $x$ (i.e. $|x|\leq K$ we have
\be\label{e9}
 \sup_{x\in C}\mathbb{E}\big(e^{1+q(x+\mu(x))^2+2q(x+\mu(x))\sigma(x)\varepsilon_1+q\sigma^2(x)\varepsilon_1^2}\big)<G(K),
\e
for some positive constant $G(K)$.

 {\bf Proof of Claim 1.} Using Assumption $(A_3)$, for $|x|$ large enough, there is a small $\delta>0$ such
 that $(x+\mu(x))^2\le (1-4\delta)x^2$. Since $1\le\delta(1+qx^2)$ for $|x|$ large enough, it follows that
 $e^{1+q(x+\mu(x))^2}\le e^{(1-3\delta)(1+qx^2)}$.

By $(A_2)$ there is $M>0$ such that, for all $x$, $\sigma(x)\leq M$.
If we choose $q$ such that $q M^2<\kappa/2$  then it is enough to show that
$
 \mathbb{E}\big(e^{2q|x+\mu(x)|M|\varepsilon_1|+(\kappa/2)\varepsilon_1^2}\big)\le e^{2\delta qx^2}
$.
By the Cauchy-Schwarz inequality, it suffices to prove
\be\label{e10}
 \sqrt{\mathbb{E}\big(e^{4q|x+\mu(x)|M|\varepsilon_1|}\big)}\sqrt{\mathbb{E}\big(e^{\kappa\varepsilon_1^2}\big)}\le e^{2\delta qx^2}
\e

 By \eqref{a2}, the second term on the left-hand side of \eqref{e10} is the constant $\sqrt{I}$. This is smaller than $e^{\delta qx^2}$ for large enough $|x|$. So, since again by $(A_3)$, $4q|x+\mu(x)|M\le 4qM|x|$ for $|x|$ large enough, it remains to show
$
 \sqrt{\mathbb{E}\big(e^{4qM|x||\varepsilon_1|}\big)}\le e^{\delta qx^2}\,\,\mbox{for large}\,\,|x|
$, or, equivalently,
\be\label{e11}
 \mathbb{E}\big(e^{4qM|x||\varepsilon_1|}\big)\le e^{2\delta qx^2}\,\,\mbox{for large}\,\,|x|.
\e
Applying Lemma \ref{l2.4}, the left-hand side of \eqref{e11} is smaller than $e^{16cq^2M^2|x|^2}$ for some fixed constant $c>0$. Hence, if one chooses $q$ small enough such that $16q^2M^2c<2\delta q$ and $qM^2<\kappa/2$ then \eqref{e11} holds, showing Claim 1.

 {\bf Proof of Claim 2.} By Assumption $(A_2)$, $\mu$ is bounded above on any compact
 $C=[-K,K]$ by some positive constant $A=A(K)$ and the function
 $x\mapsto (x+\mu(x))^2$ is also bounded on $C$ by some positive constant $B=B(K)$.

 Applying Cauchy-Schwarz Inequality and \eqref{a2},
\[
 \begin{array}{lll}
 \mathbb{E}\big(e^{1+q(x+\mu(x))^2+2q(x+\mu(x))\sigma(x)\varepsilon_1+q\sigma^2(x)\varepsilon_1^2}\big) &\le&
 \mathbb{E}\big(e^{1+qB+2q(K+A)M|\varepsilon_1| +(\kappa/2)\varepsilon_1^2}\big)\\
       &\le& e^{(1+qB)}\sqrt{\mathbb{E}\big(e^{4q(K+A)M|\varepsilon_1|}\big)}\sqrt{\mathbb{E}\big(e^{\kappa\varepsilon_1^2}\big)}\\
       &=& e^{(1+qB)}\sqrt{I}\sqrt{\mathbb{E}\big(e^{4q(K+A)M|\varepsilon_1|}\big)}
\end{array}
\]

 We then choose $K$ large enough such that $4q(K+A)M\geq 1$ and we get, by Lemma \ref{l2.4}, that for all $x\in C=[-K,K]$,
 \[
\mathbb{E}\big(e^{1+q(x+\mu(x))^2+2q(x+\mu(x))\sigma(x)\varepsilon+q\sigma^2(x)\varepsilon^2}\big)\le e^{(1+qB)}\sqrt{I}\sqrt{e^{16c'q^2(K+A)^2M^2}},
\]
for a fixed constant $c'>0$. This holds for all $x\in C$, hence \eqref{e9} holds true when taking the supremum over $C$ of the left-hand side of this latter inequality.
\hfill $_{\blacksquare}$

\begin{proposition}\label{p2.555} The Markov chain $\Phi_t$ satisfies $(DV3+)\,(i)$.
\end{proposition}

{\bf Proof.} We follow Proposition 4.1 of \cite{KM2} and deduce this statement from
Proposition \ref{p2.5} above.  Recall
$V(x)=W(x)=1+qx^2$, $C$ and $\delta>0$ from that Proposition.
Take $C_2:=\mathbb{R}\times C$. For $x,y\in\mathbb{R}$
define $V_2(x,y):=V(y)+(\delta/2) W(x)$ and $W_2(x,y):=(1/2)(W(x)+W(y))$.
Then
\begin{eqnarray*}
\log e^{-V_2}Qe^{V_2}(x,y)&=&-V(y)-(\delta/2) W(x) +\log \int_{\mathbb{R}}e^{\frac{\delta}{2}W(y)
+V(z)} P(y,dz)\\ &\leq& -V(y)-(\delta/2) W(x) +(\delta/2) W(y) + [V(y)-\delta W(y)+
b 1_C (y)]\\ &\leq& -\delta W_2(x,y) + b 1_{C_2}(x,y),
\end{eqnarray*}
showing that \eqref{cry} is true with $V_2,W_2$. As $C_2$ has been shown to be small in Proposition \ref{p2.3},
we conclude.
\hfill $_{\blacksquare}$

\begin{proposition}\label{p2.9} The chain $\Phi_t$ satisfies condition $(DV3+)\,(ii)$ as well.
\end{proposition}

 {\bf Proof.}  Consider $V_2(x,y),W_2(x,y)$, defined in the previous
Proposition. We choose $t_0:=2$, and let $r<\|W\|_{\infty}=\infty$.

It suffices to prove existence of a measure $\beta_r$ on $\mathcal{B}(\mathbb{R}^2)$ such that,
\be\label{e26}
 \beta_r(e^{V_2})<\infty\,\,\mbox{and}\,\,Q^2\big((x,y), D\cap C_W(r) \big)\le\beta_r(D),
\e
for all $(x,y)\in C_W(r)$ and all $D\in\mathcal{B}(\mathbb{R}^2)$.

Let $H$ denote the projection of $C_W(r)$ on the first coordinate (which is the same as its projection on
the second coordinate). By $(A_1)$ and $(A_2)$, the function $p(x,y)$ is bounded on $H\times H$ by a constant $J$.
Hence
$$
Q^2\big((x,y), D\cap C_W(r) \big)\le \int_{D\cap C_W(r)} p(y,a_1)p(a_1,a_2)da_1 da_2\leq J^2\lambda_2(D\cap C_W(r))=:
\beta_r(D).
$$
Finally, it is clear that $\beta_r(e^{V_2})<\infty$ as it
is the Lebesgue-integral of a continuous function on a compact of $\mathbb{R}^2$.
\hfill $_{\blacksquare}$

\begin{corollary}\label{c2.7} The Markov chain $\Phi_t$ has an invariant probability measure $\nu$ equivalent to $\lambda_2$.
\end{corollary}

 {\bf Proof.} Theorem \ref{alap} implies that $\Phi_t$ has an invariant probability measure, say, $\nu$.

 Furthermore, from \eqref{mkkk}, $\mathbb{P}(\Phi_2\in\cdot\vert \Phi_0=(x,y))$ is $\lambda_2$-absolutely continuous
 for each $(x,y)\in\mathbb{R}^2$, hence we get $\nu \ll \lambda_2$. On the other hand,
 from the definitions of recurrent and positive chains on pages 186 and 235 of \cite{MT},
 it follows by Proposition 10.1.1 and Theorem 10.4.9 of the same reference that $\nu\sim\psi$,
 where $\psi$ is a maximal irreducibility measure. Hence $\psi \gg \lambda_2$ by Proposition 4.2.2 $(ii)$ in \cite{MT}, so
 we get $\nu \gg \lambda_2$. It follows that $\nu\sim\lambda_2$, as required. \hfill\  $_{\blacksquare}$

 We now proceed to a proper investigation of asymptotic arbitrage exponential opportunities in the wealth model \eqref{eq3}. Inspecting again the dynamics of the investor's wealth process $V_t^{\pi}$ in this model, for any Markovian strategy $\pi_t$, we may express it in the form
\be\label{e32}
  V_t^{\pi} = V_0\exp\big(\sum_{n=1}^tf(\Phi_n)\big) = V_0\exp\Big(t\frac{\sum_{n=1}^tf(\Phi_n)}{t}\Big),\,\,\mbox{for all}\,\,t\ge 1,
\e
where the function $f$ is defined by
\begin{equation}\label{suttog}
f(x,y):= \log\big((1-\pi(x))+\pi(x)\exp(y-x)\big),\quad x,y\in\mathbb{R},
\end{equation}
and $\Phi_t=(X_{t-1},X_t)$, $t\in\mathbb{N}$, is the Markov chain
in consideration. We will need to insure that, for any Markovian strategy $\pi_t$, the sequence of random variables $\log(V_t^{\pi}/V_0)=\sum_{n=1}^tf(\Phi_n)$ satisfies a large deviation principle ($LDP$) hypotheses. That is, we will need that the limit $\Lambda_f(\theta):=\lim_{t\to\infty}\frac{1}{t}\log\mathbb{E}(e^{\theta\sum_{n=1}^t f(\Phi_n)})$ exists, for each $\theta\in\mathbb{R}$, with $\Lambda_f$ satisfying the remaining conditions in G\"artner-Ellis Theorem as stated in Theorem 2.3.6 in \cite{DZ}.

Define the function $W_0:\mathbb{R}^2\to [1,\infty)$
by $W_0(x,y):=1+|x|+|y|$, for all $x,y\in\mathbb{R}$. Clearly, $W_0$ satisfies \eqref{eq18} with $d=2$ and $W=W_2$.

\begin{lemma}\label{l2.10} The function $f$ belongs to the space $L_{\infty}^{W_0}$.
\end{lemma}

 {\bf Proof.} For all $x,y\in\mathbb{R}$, since $\pi(x)\in\ [0,1]$, we have $1-\pi(x)+\pi(x)\exp(y-x)\leq 1+\exp(y-x)$. It follows that $f(x,y)\leq \vert x\vert+\vert y\vert +1$.

 On the other hand, for $0\leq a\leq 1/2$, we have $1-a+a \exp(y-x)\geq 1/2$. And for $a>1/2$, we have $1-a+a \exp(y-x)\geq (1/2)\exp(y-x)$. To sum up, we obtain that $f(x,y)\geq \log (1/2)-\vert x\vert -\vert y\vert$ for all $x,y\in\mathbb{R}$.

 Hence $\vert f(x,y)\vert\leq c(1 +\vert x\vert +\vert y\vert)$, for some constant $c>0$, and the claim follows. \hfill $_{\blacksquare}$

\begin{proposition}\label{p2.11} Let $\pi_t$ be any Markovian strategy in the wealth model \eqref{eq3}. Then
$\Lambda_f(\theta):=\lim_{t\to\infty}\frac{1}{t}\log\mathbb{E}_{(X_{-1},X_0)}\big(e^{\theta\sum_{n=1}^tf(\Phi_n)}\big)$, $\theta\in\mathbb{R}$ is a well-defined analytic function so the averages $\frac{1}{t}\log(V_t^{\pi}/V_0)=\frac{1}{t}\sum_{n=1}^tf(\Phi_n)$ satisfy a large deviations estimate with good rate function $\Lambda_f^*$ (the convex conjugate of $\Lambda_f$).
\end{proposition}

 {\bf Proof.} By Theorem \ref{alap}, $\Lambda_f$ verifies the conditions of the G\"artner-Ellis Theorem 2.3.6 in \cite{DZ}
 (analyticity implies essential smoothness). Applying this theorem we conclude.
\hfill $_{\blacksquare}$

\begin{lemma}\label{l2.14} If $(RC_+)$ is satisfied then the Markovian strategy $\pi^+(x):=\mathbf{1}_{R^+}(x)$
is such that
\be
\nu(f)=\mathbb{E}\Big(\log\big((1-\pi^+(\tilde{X_0}))+\pi^+(\tilde{X_0})\exp(\tilde{X_1}-\tilde{X_0})\big)\Big)>0,
\e
where the pair of random variables $(\tilde{X_0},\tilde{X_1})$ has distribution $\nu$.
\end{lemma}

 {\bf Proof.} Since $\nu$ is a probability measure on $\mathcal{B}(\mathbb{R}^2)$ and is invariant for the chain $\Phi_t=(X_t,X_{t+1})$, there is a pair of $\mathbb{R}$-valued random variables $(\tilde{X_0},\varepsilon_1)$ such that $\varepsilon_1$ is independent of $\tilde{X_0}$ and, defining
 $\tilde{X_1}=\tilde{X_0}+\mu(\tilde{X_0})+\sigma(\tilde{X_0})\varepsilon_1$, the pair $(\tilde{X_0},\tilde{X_1})$ has distribution $\nu$. For all $x\in\mathbb{R}$,
\be
 \begin{array}{lllll}
 \mathbb{E}\big(\tilde{X_1}\mid \tilde{X_0}=x\big) &=& \mathbb{E}\big(x+\mu(x)+\sigma(x)\varepsilon_1\mid \tilde{X_0}=x\big)\\
                                  &=& x+\mu(x)+\sigma(x)\mathbb{E}(\varepsilon_1\mid \tilde{X_0}=x)\\
                                   &=& x+\mu(x)+\sigma(x)\mathbb{E}(\varepsilon_1)\\
                                  &=& x+\mu(x), \nonumber\\

\end{array}
\e
since $\varepsilon_1$ independent of $\tilde{X}_0$. It follows that if $x\in R_+$ then we have
\begin{equation}\label{mkk}
\mathbb{E}(\tilde{X_1}\mid \tilde{X_0}=x)>x.
\end{equation}

 Consider now the explicitly defined Markovian strategy $\pi^+(x):={\bf 1}_{R^+}(x)$ for $x\in\mathbb{R}$, which is constructed as follows: at each time $t>0$, we invest all the current wealth in the stock if the $\log$-market price of risk is above $0$, and we put everything in the bank account otherwise. Given this strategy, consider the corresponding $f(x,y)= \log\big((1-\pi^+(x))+\pi^+(x)\exp(y-x)\big)$, $(x,y)\in\mathbb{R}^2$. Since by definition $\nu(f)=\int_{\mathbb{R}^2}f(x,y)\nu(dx,dy)$, we have $\nu(f)=\mathbb{E}\Big(\log\big((1-\pi^+(\tilde{X_0}))+\pi^+(\tilde{X_0})\exp(\tilde{X_1}-\tilde{X_0})\big)\Big)$. Next, by Corollary \ref{c2.7}, $\nu$ has a $\lambda_2$-a.e. positive density with respect to $\lambda_2$, hence its $\tilde{X}_0$-marginal, denoted by $\eta$, has a $\lambda$-a.e. positive density $\ell(x)$. Therefore we obtain that
\[
\begin{array}{llll}
 \nu(f) &=& \int_{\mathbb{R}}\mathbb{E}\big(\log((1-\pi^+(x))+\pi^+(x)\exp(\tilde{X_1}-x))\mid \tilde{X_0}=x\big)\eta(dx) \\
        &\ge& \int_{{R}^+}\mathbb{E}\big(\log\exp(\tilde{X_1}-x)\mid \tilde{X_0}=x\big)\eta(dx) \\
        &=& \int_{{R}^+}\mathbb{E}\big(\tilde{X_1}-x\mid \tilde{X_0}=x\big)\ell(x)\lambda(dx)\\
        &>& 0,
\end{array}
\]
by \eqref{mkk}, showing the lemma. \hfill $_{\blacksquare}$

 {\bf Proof of Theorem \ref{t2.15}.} If $f$ is $\nu$-a.s. constant then the statement is trivial. If not, then $\sigma^2(f)>0$
by the argument of  Theorem 5 in \cite{MR}. Proposition \ref{p2.11} says that $\frac{1}{t}\log(V_t^{\pi^+}/V_0)$ satisfies
a large deviations principle with good rate function $\Lambda_f^*$.
In particular,
applying the upper large deviations inequality $(2.3.7)$ of Theorem 2.3.6 in \cite{DZ} we get
\be\label{ineq25}
 \limsup_{t\to\infty}\frac{1}{t}\log\mathbb{P}\Big(\frac{1}{t}\log(V_t^{\pi^+}/V_0)<\nu(f)/2\Big)\le
 -\inf_{x\in (-\infty,\nu(f)/2]}\Lambda_f^*(x),
\e
where $\nu(f)>0$ by Lemma \ref{l2.14}. By Corollary \ref{kp}, $\Lambda_f^*(\nu(f)/2)>0$ and $\nu(f)$ is the unique minimiser of $\Lambda_f^*$. By strict convexity, $\Lambda_f^*$ is decreasing on $(-\infty,\nu(f)]$. These imply that the right hand side of \eqref{ineq25} is equal to $-\Lambda_f^*(\nu(f)/2)$. Hence
\be\label{e38}
 \mathbb{P}\big(V_t^{\pi^+}\ge e^{\log(V_0)+\nu(f)t/2}\big)\ge 1-e^{-t\Lambda_f^*(\nu(f)/2)}\,\,\mbox{for large}\,\,t,
\e
and the result follows. \hfill $_{\blacksquare}$

The following two examples fall outside the scope of \cite{MR} but can be treated using Theorem \ref{t2.15} above.

\begin{example}\label{ex2.16} \textrm{\bf Stable autoregressive process.}\hfill

 \emph{Consider the model $S_t:=e^{X_t}$ where $X_t$ is a stable
autoregressive process (that is, the  discrete-time version of the Ornstein-Uhlenbeck process):
\be\label{e2.40}
X_{t+1}=\alpha X_t+\varepsilon_{t+1},\,\,\mbox{for all}\,\,t\ge 1,
\e
where $0<\vert \alpha\vert <1$, $X_0$ is constant and the $\varepsilon_t$ are i.i.d. $\mathcal{N}(0,1)$.}

 \emph{In this typical example, the drift and volatility functions are identified as $\mu(x)=(\alpha-1)x$ and $\sigma(x)=1$, for all $x\in\mathbb{R}$. All the assumptions $(A_1)-(A_4)$ on $\mu$, $\sigma$ and on the $\varepsilon_t$s trivially hold.}

 \emph{Next, $R^+=(-\infty,0)$. Obviously, $(RC_+)$ holds.
 It follows that the trading opportunity $\pi_t^+=\pi^+(X_{t-1})$, with $\pi^+:={\bf 1}_{R^+}$ realizes an $AEA$ with $GDPF$, by Theorem \ref{t2.15}.} \hfill $_{\blacksquare}$
\end{example}

\begin{example}\label{exnew} \emph{\bf A Cox-Ingersoll-Ross--type process.}\hfill

{\rm In mathematical finance the process $H_t$ described by the stochastic
differential equation
\begin{equation}\label{cir}
dH_t=-\beta H_t dt+ \sigma\sqrt{|H_t|}dW_t
\end{equation}
is often used to model stochastic volatility or the short rate in bond markets,
here $W_t$ is a Brownian motion.
We present here a slight modification of the discretization of this model.
The modifications are necessary, since the volatility of $H_t$ is neither
bounded above nor bounded away from $0$.

Let us define the log-price process by
$$
X_{t+1}=\alpha X_t +\sigma \min\{\max\{\sqrt{|X_t|},c_1\},c_2\}\varepsilon_t,
\quad t\geq 1,
$$
where $|\alpha|<1$, $\sigma>0$, $0<c_1<c_2$ are given constants and $\varepsilon_t$
is $\mathcal{N}(0,1)$. It is easy to check that this process
also satisfies the conditions of Theorem \ref{t2.15}.}

\end{example}

\section{Utility-based Asymptotic Arbitrage}

 We consider risk-averse investors with initial capital $V_0=x\in (0,\infty)$ who express their preferences

in terms of a utility function $U:(0,\infty)\to\mathbb{R}$, where $U$ belongs to the subclass of Hyperbolic Absolute Risk Aversion ($HARA$)
utility functions $U(x)=x^{\alpha}$, with $0<\alpha< 1$, or $U(x)=-x^{\alpha}$, with $\alpha< 0$, for all $x\in (0,\infty)$.
The parameter $\alpha$ is related to risk-aversion: the larger $-\alpha$ is, the more afraid investors become of losses, see \cite{FSd}.

 As mentioned in the introductory section, in this paper we do not intend to solve the finite horizon utility maximization problem which is well-discussed in the
 literature  and which consists in finding the maximal expected utility $u(x):=\sup_{\pi}\mathbb{E}U(V_T^{\pi})$ together with an optimal strategy $(\pi^*_t)_{1\le t\le T}$ verifying $u(x)=\mathbb{E}U(V_T^{\pi^*})$. Instead, we focus on trading opportunities that provide (rapidly) increasing expected utilities for the agents as the time horizon tends to infinity, in the
spirit of \cite{Dk} and \cite{FSr}.

Consider first the subclass of power utility functions $U(x):=x^{\alpha}$, with $0<\alpha<1$, for $x\in (0,\infty)$.

\begin{proposition}\label{p3.1} If a trading strategy $\pi_t$ realizes an $AEA$  then there is a constant $b>0$ such that
\be
 \mathbb{E}U(V_t^{\pi})\ge e^{\alpha bt},\,\,\mbox{for all large enough }\,\, t.
\e
\end{proposition}

 {\bf Proof.} By definition of $AEA$, there are a constant $b>0$ and a time $t_{1/2}$ such that
$\mathbb{P}(V_t^{\pi}\ge e^{bt})\ge 1/2$ for all time $t\geq t_{1/2}$. It follows that
$\mathbb{E}U(V_t^{\pi})\ge\mathbb{E}U(e^{bt}){\bf 1}_{\{V_t^{\pi}\ge e^{bt}\}}\ge (1/2)e^{\alpha bt}\ge e^{\alpha b't}$ for any $b'<b$ and for all $t$ large enough, as required. \hfill $_{\blacksquare}$

Next, suppose that investors choose from the second subclass of power utility functions $U(x):=-x^{\alpha}$, with $\alpha<0$, for all $x\in (0,\infty)$. These functions express larger risk-aversion and are thought to be more realistic. We derive the key result of this section below. We remark that, despite the short proof, the following theorem relies on all the heavy machinery of the paper \cite{KM2} as well as on our preliminary results established in Section 2 and it is, in fact, highly non-trivial.

\begin{theorem}\label{p3.3} Assume that the log-price $X_t$ satisfies $(A_1)-(A_4)$ as well as $(RC_+)$. Let $\pi^+_t$ be the strategy defined in
Theorem \ref{t2.15}. Then there is $\alpha_0<0$ such that for any risk-aversion coefficient $0>\alpha>\alpha_0$, the expected utility of the corresponding investor's wealth converges to $0$ at an exponential rate. That is, with the power utility $U(x):=-x^{\alpha}$, $x\in (0,\infty)$, we have,
\be\label{e4.4}
|\mathbb{E}U(V_t^{\pi^+})|\le  K e^{-ct},\,\,\mbox{for all large enough}\,\, t,
\e
for some constants $K=K(\alpha),c=c(\alpha)>0$.
\end{theorem}

 {\bf Proof.} Recall section 2, in particular, Corollary \ref{c2.7}, Proposition \ref{p2.11} and \eqref{suttog}. When $f$ is constant $\nu$-a.s., the statement is trivial. Otherwise we may assume $\sigma^2(f)>0$
(see the proof of Theorem \ref{t2.15}). In section 2 we obtained  that $\Lambda_f(0)=0$, $\Lambda_f'(0)=\nu(f)>0$. Since by analyticity of $\Lambda_f$, $\Lambda_f'$ is continuous, there exists $\alpha_0<0$ such that $\Lambda_f(\alpha)<0$ for $\alpha\in (\alpha_0,0)$. Theorem 3.1 of \cite{KM2} implies that for some constant $d_{\alpha}$, we have
\be\label{pope}
\frac{-\mathbb{E}e^{\alpha (f(\Phi_1)+\ldots+f(\Phi_n))}}{e^{n\Lambda_f(\alpha)}}=
\frac{ \mathbb{E} U(V^{\pi}_n)/V_0^{\alpha}}
{e^{n\Lambda_f(\alpha)}}
\to d_{\alpha},\ n\to\infty,
\e
showing the statement. \hfill $_{\blacksquare}$

 It seems that, in general, we should not expect more than this result (i.e. we cannot get such a
theorem for all $\alpha<0$). To illustrate this, we now construct an example where there is
$AEA$ with $GDPF$ but, for some $\alpha<0$, we have $\mathbb{E}(V_t^{\pi})^{\alpha}\to -\infty$ as $t\to\infty$.

\begin{example}\label{ex3.4} \emph{Consider the $\log$-price $X_t$ governed by the equation $X_{t+1}=X_t+\varepsilon_{t+1}$, $t\in\mathbb{N}$, with $X_0=0$, where $\varepsilon_t$ are i.i.d. random variables in $\mathbb{R}$ with common distribution chosen such that $\mathbb{E}e^{-\varepsilon_1}>1$ and $\mathbb{E}\varepsilon_1 >0$. For example $\varepsilon_1\sim\mathcal{N}(1/4,1)$
will do. We identify the drift and volatility as $\mu\equiv 0$ and $\sigma\equiv 1$.}

 \emph{Choose the trading strategy $\pi_t\equiv 1$ for all $t$ and let $V_0=1$. Then we have $V_t:=\exp(\varepsilon_1+\cdots +\varepsilon_t)$ for all $t\ge 1$. Since $1/5<1/4=\mathbb{E}\varepsilon_1$, by Cram\'er's theorem (see e.g. \cite{DZ}), there are a constant $c>0$ and $t_0>0$ such that for all $t\ge t_0$, we have $\mathbb{P}(V_t\ge e^{t/5})\ge 1-e^{-ct}$. Hence there is $AEA$ with $GDPF$.}

 \emph{However, for $\alpha=-1$, we have, by independence,
$$
\mathbb{E}U(V_t)=\mathbb{E}(-V_t^{-1})=-\mathbb{E}\exp\{-(\varepsilon_1+\cdots +\varepsilon_t)\}=
-(\mathbb{E}e^{-\varepsilon_1})^t\to -\infty
$$ as $t\to\infty$.} \hfill $_{\blacksquare}$
\end{example}

 Finally we investigate what happens if a risk-averse agent produces expected utility tending to $0=U(\infty)$ exponentially fast as $t\to\infty$. It turns out that his/her strategy produces $AEA$ with $GDPF$. Indeed, following the footsteps of
Proposition 2.2 in \cite{FSr} we get the following result.

\begin{theorem}\label{t3.5} Consider the power utility $U(x)=-x^{\alpha}$ for some $\alpha<0$.
Let $\pi_t$ be such that $|\mathbb{E}U(V_t^{\pi})|\le Ke^{-ct}$ for all large enough $t$, for some constants $c,K>0$. Then $\pi_t$ provides an $AEA$ with $GDPF$.
\end{theorem}

 {\bf Proof.} We may and will assume $K=1$. We need to find constants $b>0$, $c'>0$ such that
 $\mathbb{P}(V_t^{\pi}\ge e^{bt})\ge 1-e^{-c't}$ for all large enough $t$. Choose $b>0$ such that $c+\alpha b>0$, then we have
\be\begin{array}{lll}
\mathbb{P}(V_t^{\pi}<e^{bt}) &=& \mathbb{P}\big(|U(V_t^{\pi})|> |U(e^{bt})|\big)\\
    &\le& \frac{\mathbb{E}|U(V_t^{\pi})|}{|U(e^{bt})|}\,\,\mbox{by Markov's inequality}.
\end{array}
\e

 But $\mathbb{E}|U(V_t^{\pi})|=|\mathbb{E}U(V_t^{\pi})|\le e^{-ct}$ and $|U(e^{bt})|=e^{\alpha bt}$ imply $\mathbb{P}(V_t^{\pi}<e^{bt})\le e^{-(c+\alpha b)t}$ for all $t$.

Hence the result follows taking $c':=c+\alpha b$. \hfill $_{\blacksquare}$

 To conclude, if an economic agent with $HARA$ utility risk-aversion coefficient $\alpha<0$ achieves an expected utility that converges exponentially fast to $0$, then his/her strategy provides $AEA$ with $GDPF$, too. Conversely, under the stringent conditions of Section 2, one is able to construct strategies producing $AEA$ with $GDPF$ which also provide expected utilities tending to $0$
 exponentially fast {for $\alpha$ not
too negative} (i.e. for not too risk-averse investors).


text:
\section{First approach: Reduction to solving multivariate systems}\label{sec:first}

In this section and the next,
we present two approaches to solving the problem of enumerating superspecial Howe curves.
As we mentioned in Section~\ref{sec:intro},
the first approach, described in this section, enumerates pairs of supersingular elliptic curves $E_1\colon w^2 = f_1$ and $E_2\colon z^2 = f_2$ such that $C\colon y^2=f_1f_2$ is superspecial.
For this, we shall apply a construction of Howe curves given in \cite{KHS20}.
While this construction is different from the original one of \cite{Howe}, it can easily reduce our problem to finding roots of polynomial systems.

\subsection{Reduction to solving multivariate systems over finite fields}\label{subsec:red}

Let $K$ be an algebraically closed field in characteristic $p > 3$.
In \cite{KHS20}, the authors parametrize the space of all Howe curves by the projective plane $\bbP^2$.
We here briefly recall the parametrization; see \cite[\S2]{KHS20} for more details.
Let $y^2 = x^3 + A_i x + B_i$ ($i=1,2$) be two (nonsingular) elliptic curves, where $A_1,B_1,A_2,B_2\in K$.
Let $\lambda, \mu, \nu$ be elements of $K$ such that (i) $\mu \ne 0$ and $\nu \neq 0$, and (ii) $f_1$ and $f_2$ are coprime, where
\begin{align}
f_1(x) &= x^3 + A_1 \mu^2 x + B_1\mu^3,\label{f1}\\
f_2(x) &= (x-\lambda)^3 + A_2 \nu^2(x-\lambda) + B_2 \nu^3.\label{f2}
\end{align}
A point $(\lambda : \mu : \nu) \in \bbP^2 (K)$ satisfying (i) and (ii) is said to be \emph{of Howe type} in \cite{KHS20}.
Note that the isomorphism classes of $E_1$ and $E_2$ are independent of the choice of $(\lambda,\mu,\nu)$ provided $\mu\ne 0$ and $\nu\ne 0$.
Then the desingularization $H$ of the fiber product $E_1\times_{{\bbP}^1}E_2$ is a Howe curve, and vice versa.

This parametrization, together with the criterion of superspeciality in Section~\ref{sec:Howe}, enables us to reduce the search for superspecial Howe curves into solving multivariate systems over $K$; it suffices to compute the solutions $(\lambda : \mu : \nu) \in \bbP^2(K)$ (of Howe type) to $a = b = c = d = 0$, where $a$, $b$, $c$ and $d$ are the entries of the Cartier--Manin matrix of the hyperelliptic curve $C\colon y^2 = f_1 f_2$.
Note that $a$, $b$, $c$ and $d$ are homogeneous as polynomials in $\lambda$, $\mu$ and $\nu$, and that $\ord_*(-)=O(p)$ for $*=\lambda,\mu,\nu$ and for $-=a,b,c,d$.

Note that the multivariate systems above are zero-dimensional, since
there are only finitely many points $(\lambda : \mu : \nu)$ parameterizing supersingular Howe curves (cf.\;\cite{KHS20}), whence the same thing holds for superspecial cases.
In fact, we may assume that the coordinates $A_1$, $B_1$, $A_2$, $B_2$, $\lambda$, $\mu$ and $\nu$ belong to $\bbF_{p^2}$:

\begin{proposition}\label{prop:field_of_def}
Any superspecial Howe curve is $K$-isomorphic to $H$ obtained as above for $A_1$, $B_1$, $A_2$, $B_2$, $\mu$, $\nu$ and $\lambda$ belonging to $\bbF_{p^2}$.
\end{proposition}
\begin{proof}
It suffices to consider the case of $K=\overline{\bbF}_{p^2}$,
since every supersingular elliptic curve can be defined over $\bbF_{p^2}$
and $(\lambda,\mu,\nu)$ is a solution of $a=b=c=d=0$.
Let $H'$ be a superspecial Howe curve over $K=\overline{\bbF}_{p^2}$.
Choose $E'_1$ and $E'_2$ over $K$ so that $H'$ is the normalization of
$E'_1\times_{\bbP^1} E'_2$.
It is well-known that $H'$ descends to a curve $H$ over $\bbF_{p^2}$
such that the Frobenius map $F$ (the $p^2$-power map) on $\Jac(H)$ is $p$ or $-p$ and all automorphisms of $H$ are defined over $\bbF_{p^2}$ (cf.\;the proof of \cite[Theorem~1.1]{Ekedahl}). Let $E_1$ and $E_2$ be the quotients of $H$ corresponding to $E'_1$ and $E'_2$. The quotient $E_i$ of $H$ is obtained by an involution $\iota_i \in\Aut(H)$, and therefore is defined over $\bbF_{p^2}$.
The quotient of $H$ by the group generated by $\iota_1$ and $\iota_2$
is isomorphic to $\bbP^1$ over ${\bbF_{p^2}}$.
Let $S_i$ be the set of the ramified points of $E_i \to \bbP^1$.
Since $S_1\cap S_2$ consists of a single point, this point is invariant under the action of the absolute Galois group of $\bbF_{p^2}$ and therefore is an $\bbF_{p^2}$-rational point. An element of $\PGL_2(\bbF_{p^2})$ sends this point to the infinite point of~$\bbP^1$.
Since the Frobenius map $F$ on $E_i$ is also $\pm p$,
the other elements $P$ of $S_i$ (which are $2$-torsion points on $E_i$)
are also $\bbF_{p^2}$-rational by $F(P)=\pm p P = P$.
This implies the desired result.
\end{proof}

\subsection{Concrete algorithm}\label{subsec:alg1}

Based on the reduction described in the previous subsection, we present a concrete algorithm (Algorithm \ref{alg:main1} below).
\begin{algorithm}\label{alg:main1}
\
\begin{description}
\item[Input] A rational prime $p > 3$.
\item[Output] A list $\calH(p)$ of superspecial Howe curves, each of which is represented by a pair $(f_1, f_2)$ of polynomials $f_1, f_2 \in \bbF_{p^2}[x]$.
\end{description}
\begin{enumerate}
\item Compute the set $\calS(p)$ of representatives of the $\overline{\bbF}_{p}$-isomorphism classes of supersingular elliptic curves in characteristic $p$ so that each representative is given in Weierstrass form $E_{A,B}\colon y^2 = f_{A,B}(x) \coloneqq x^3 + A x + B$ by a pair $(A, B)$ of elements in $\bbF_{p^2}$.
\item Set $\calH_0(p)$ $\leftarrow$ $\emptyset$.
For each pair of $E_{A_1,B_1}$ and $E_{A_2, B_2}$ in $\calS(p)$, possibly choosing $(A_1,B_1) = (A_2,B_2)$, conduct the following (2-1)-(2-3) to compute all $(\lambda , \mu, \nu ) \in (\bbF_{p^2})^3$ of Howe type such that the desingularization $H$ of $E_1 \times_{\bbP^1} E_2$ is superspecial, where $E_1\colon w^2 = f_1$ (resp.\ $E_2\colon z^2 = f_2$) is an elliptic curve $\bbF_{p^2}$-isomorphic to $E_{A_1,B_1}$ (resp.\ $E_{A_2,B_2}$).
\begin{enumerate}
\item[(2-1)] Compute the Cartier--Manin matrix $M$ given in \eqref{Cartier-Manin matrix}.
\item[(2-2)] Compute the set $\calV(A_1,B_1,A_2,B_2)$ of elements $(\lambda, \mu, \nu) \in (\bbF_{p^2})^3$ (with $\nu = 1$) such that $M=0$.
\item[(2-3)] For each $(\lambda, \mu, \nu) \in \calV(A_1,B_1,A_2,B_2)$:
If $\mu \neq 0$ and $\nu \neq 0$, set $\calH_0(p)$ $\leftarrow$ $\calH_0(p) \cup \{ (f_1, f_2) \}$, where $f_1$ and $f_2$ are as in \eqref{f1} and \eqref{f2}.
\end{enumerate}
{\bf Note:} By Lemma 4.4 and  Proposition 4.6 of \cite{KHS20}, for each root $(\lambda, \mu , \nu)$ computed in Step (2-2), the cubics $f_1$ and $f_2$ are coprime if $\mu \neq 0$ and $\nu \neq 0$.
Moreover, it suffices to compute elements $(\lambda, \mu, \nu)$ with $\nu = 1$; see Remark 4.2 of \cite{KH20} for more details.
\item Set $\calH(p)$ $\leftarrow$ $\emptyset$.
For each $(f_1, f_2) \in \calH_0(p)$:
If the Howe curve $H$ represented by $(f_1, f_2)$ is not isomorphic to any Howe curve of $\calH(p)$, set $\calH(p)$ $\leftarrow$ $\calH(p) \cup \{ H \}$.
\end{enumerate}
\end{algorithm}

The complexity of this algorithm is estimated as $\tilde{O}(p^6)$, as long as $\# \calH_0 (p) = O(p^3)$; see Subsection \ref{subsec:alg1comp} below for more details.

\begin{remark}
If one would search for a single example of a superspecial Howe curve (or determine the non-existence of such a curve), it suffices to decide the (non)-existence of a root in Step (2-2).
In this case, it will be estimated in the next subsection that the complexity is $\tilde{O} (p^5)$.
\end{remark}

\subsection{Complexity of the first approach}\label{subsec:alg1comp}

We here briefly discuss the complexity of Algorithm \ref{alg:main1} together with several variants of computing the roots of a multivariate system in Step (2-2).
For reasons of space, we give only a summary of the estimation of the complexity, and refer to \cite[\S5.1]{KH20} for most of details.
In the following, all time complexity bounds refer to arithmetic complexity, which is the number of operations in $\bbF_{p^2}$.
We denote by $\mathsf{M}(n)$ the time to multiply two univariate polynomials over $\bbF_{p^2}$ of degree $n$.

For Step (1), one can check that its complexity is dominated by the cost of computing all supersingular $j$-invariants in characteristic $p$.
This cost is bounded by $O ({\log}^{2} (p) \mathsf{M}(p) ) = \tilde{O}(p)$, see \cite[\S5.1.1]{KH20} for details.

For Step (2), clearly the complexities of Steps (2-1) and (2-2) are larger than that of Step (2-3).
In Step (2-1), we compute the Cartier--Manin matrix $M$ from $f\coloneqq f_1 f_2$ \emph{with indeterminates} $\lambda$ and $\mu.$
The cost of computing $M$ is bounded by $\tilde{O}(p^3)$, see Remark \ref{rem:compHW} below.
In Step (2-2), there are three variants (i)-(iii) to compute all $(\lambda, \mu, \nu) \in (\bbF_{p^2})^3$ with $\nu = 1$ such that $M=0$, where $M$ is the Cartier--Manin matrix as in \eqref{Cartier-Manin matrix} with entries $a$, $b$, $c$ and $d$.
\begin{enumerate}
\item[(i)] Use brute force to enumerate all    $(\lambda, \mu) \in (\bbF_{p^2})^2$ to check $M =0$ or not.
\item[(ii)] Regard one of $\lambda$ and $\mu$ as a variable.
For simplicity, regard $\lambda$ as a variable.
For each $\mu \in \bbF_{p^2}$, compute the roots in $\bbF_{p^2}$ of $G\coloneqq \gcd(a, b, c, d) \in \bbF_{p^2}[\lambda ]$.
\item[(iii)] Regarding both $\lambda$ and $\mu$ as variables, use an approach based on resultants.
\end{enumerate}

It is estimated that the complexity of (i) is $O(p^5)$, and that those of (ii) and (iii) are bounded by the same bound $\tilde{O} (p^4)$;
more precisely the upper-bound of the complexity of (ii) is less than that of (iii) if we consider logarithmic factors, see \cite[\S5.1.2]{KH20}.

From this, we adopt the fastest variant (ii) with complexity $\tilde{O}(p^4)$ in our implementation.
The number of $(\lambda, \mu, \nu)$ with $\nu = 1$ computed in Step (2-2) is $ \leq p^2 \times \mathrm{deg}(G)  = O (p^3)$.
Since the number of possible choices of $(E_{A_1,B_1},E_{A_2,B_2})$ is $\# \calS(p) = O (p^2)$, computing $(\lambda, \mu, \nu)$ with $\nu = 1$ for all $(E_{A_1,B_1},E_{A_2,B_2})$ is done in $\# \calS(p) \times  \tilde{O}(p^4) = \tilde{O} (p^6) $ operations in $\bbF_{p^2}$.

For Step (3), the complexity of this step heavily depends on the number of superspecial Howe curves obtained in Step (2), that is, $\# \calH_0(p)$.
Since each isomorphism test is done in $O(1)$, the complexity of Step (3) is $O ( (\# \calH_0(p) )^2 )$.
As of this writing, we have not succeeded in finding any sharp bound on $\# \calH_0(p)$.
We can naively estimate $\# \calH_0(p) = O (p^5)$ from the complexity analysis of Step (2), whereas we expect $\# \calH_0 (p) = O(p^3)$ from the practical behavior \cite[\S4.2, Table 1]{KH20}.
Thus, the complexity of Step (3) is naively $O(p^{10})$, but in practice $O (p^{6})$ which does not exceed the complexity of Steps (1)-(2).

Note that to determine the (non-)existence of a superspecial Howe curve, it is not necessary to compute a root in Step (2-2), but it suffices to compute the gcd $G$ only.
Since each gcd can be computed in time $\tilde{O}(p)$ by fast gcd algorithms, one can verify that the total complexity of this variant of Algorithm \ref{alg:main1} is $\tilde O(p^5)$.

\begin{remark}\label{rem:compHW}
In Step (2-1), we compute a Cartier--Manin matrix over $\bbF_{p^2}[\lambda, \mu]$.
Bostan, Gaudry, and Schost showed that
in general, computing the Cartier--Manin matrix $M$ of a hyperelliptic curve $y^2 = f(x)$ defined over a field $K$ can be accomplished by multiplying matrices obtained from recurrences
for the coefficients of $f(x)^n$; see \cite[\S8]{BGS} or \cite[\S2]{HS2} for details.
The algorithm of Harvey and Sutherland \cite{HS2}, which is an improvement of their earlier algorithm~\cite{HS} presented at ANTS XI, is also based on this reduction, and it is the fastest algorithm to compute $M$ for the case of $K=\bbF_p$.
From this, we suspect that one of the best ways to compute $M$ in Step (2-1) would be to extend the Harvey--Sutherland algorithm \cite{HS2} to the case of $\bbF_{p^2} (\lambda, \mu)$.
However, since we have not yet succeeded in making this extension, we compute $M$ using the reduction mentioned above, or by using formul{\ae} given in \cite[\S4]{KHS20} for $M$ specific to Howe curves.
It is estimated (to appear in a revised version of \cite{KH20}) that the complexity of the latter method is bounded by $\tilde{O}(p^3)$, which is less than or equal to that of Step (2-2).
\end{remark}

config: arxiv


TITLE: Easy interpretation of matrix multiplication with a set
QUESTION [0 upvotes]: I have just started learning convex optimization. I am having little bit difficulties in some notations.
Currently I just encountered the following equation:
$$
\boldsymbol{epi}(wf) =  \left[ \begin{array}{ccc}
I & 0 \\
0 & w
 \end{array} \right]\boldsymbol{epi}(f)
$$
where $w$ is positive and $f$ is convex. I have seen other matrix multiplications, but never encountered a matrix multiplication with a set, also how can I interpret it? Geometric interpretation would be helpful. Thanks.
Book reference page 79, 3.2.1 Nonnegative weighted sums

REPLY [0 votes]: The case $w = 0$ is obvious, and thus obmitted. For $w > 0$, let $D_w$ be the $(n+1)$-by-$(n+1)$ diagonal matrix with diagonal entries $\underbrace{1,\ldots,1}_{n \text{ times}}$, $w$ respectively. Then, $$\text{epi}(wf) := \{(z, t) \in \mathbb R^{n+1} | wf(z) \le t\} = \{(z, w\tau) |  z \in \mathbb R^n, t\in \mathbb R, f(z) \le \tau\} = \{D_w[z\;\tau]^T | (z, \tau) \in \text{epi}(f)\} = D_w\text{epi}(f),$$
as claimed.


text:
\begin{document}

\title{Analysis of unconstrained nonlinear MPC schemes with time varying control horizon\footnote{This work was supported by the DFG priority program 1305, Grant Gr1569/12-1.}}

\author{Lars Gr\"{u}ne\footnote{Lars Gr\"{u}ne, J\"{u}rgen Pannek, Martin Seehafer and Karl Worthmann are with the Mathematical Institute, University of Bayreuth, 95440 Bayreuth, Germany.
	\newline {\tt lars.gruene@uni-bayreuth.de}, {\tt juergen.pannek@uni-bayreuth.de},
	\newline {\tt martin.seehafer@uni-bayreuth.de}, {\tt karl.worthmann@uni-bayreuth.de}}
	\and J\"{u}rgen Pannek \and Martin Seehafer \and Karl Worthmann}

\date{June 2010}

\maketitle

\begin{abstract}
For discrete time nonlinear systems
satisfying an exponential or finite time controllability assumption,
we present an analytical formula for a suboptimality estimate for
model predictive control schemes without stabilizing
terminal constraints. Based on our formula, we perform a detailed
analysis of the impact of the optimization horizon and the possibly
time varying control horizon on stability and performance of the
closed loop.

\medskip

Key Words: nonlinear model predictive control, suboptimality, stability,
controllability, networked control systems
\end{abstract}

\section{Introduction}

The stability and performance analysis of model predictive control (MPC) schemes has attracted considerable attention during the last years. MPC relies on an iterative online solution of finite horizon optimal control problems in order to deal with an optimal control problem on an infinite horizon. To this end, a performance criterion --- often the distance to some desired reference --- is optimized over the predicted trajectories of the system. This method is particularly attractive due to its ability to explicitly incorporate constraints in the controller design. Due to the rapid development of efficient optimization algorithms MPC becomes increasingly applicable also to nonlinear and large scale systems.

Two central questions in the analysis of MPC schemes are asymptotic stability, i.e., whether the closed loop system trajectories converge to the reference and stay close to it, and closed loop performance of the MPC controlled system. In particular -- since desired performance specifications (like, e.g., minimizing energy or maximizing the output in a chemical process) can be explicitly included in the optimization objective -- the latter provides information on how good this objective is eventually satisfied by the resulting closed loop system. For MPC schemes with stabilizing terminal constraints the available analysis methods have reached a certain degree of maturity, see, e.g., the survey \cite{MaRRS00} and the references therin. Despite their widespread use in applications, cf.\ \cite{QB2003}, for schemes without stabilizing terminal constraints --- considered in this paper --- corresponding results are more recent and less elaborated. Concerning stability, the papers \cite{AlaB95,GMTT05,JadH05} show (under different types of controllability or detectability conditions) that stability can be expected if the optimization horizon is chosen sufficiently large, without, however, aiming at giving precise estimates for these horizons.

Closed loop performance of MPC controlled systems is measured by evaluating an infinite horizon functional along the closed loop trajectory. Suboptimality estimates, which typically allow to conclude stability of the closed loop, are then obtained by comparing this value with the optimal value of the infinite horizon problem. In \cite{ShaX97} an estimation method of this type for discrete time linear systems is presented which relies on a numerical approximation of the finite time optimal value function. Since for nonlinear or large scale systems this function is usually not computable, in \cite{GruR08} a method for finite or infinite dimensional discrete time nonlinear systems using ideas from relaxed dynamic programming has been presented. This approach allows for performance estimates based on controllability properties. Motivated by these results, in \cite{G07} a linear program has been developed whose solution precisely estimates the degree of suboptimality from exponential or finite time controllability.

The present paper builds upon \cite{G07} extending the analysis from this reference to MPC schemes with time varying {\em control horizon}, i.e., the interval between two consecutive optimizations or, equivalently, the interval on which each resulting open loop optimal control is applied. This setting is motivated by networked control systems in which the network performance determines the control horizon, see \cite{GPW08,GPW09} and the discussion after Remark \ref{minrem}, below. In particular, we thoroughly investigate the impact of different --- possibly time varying --- control horizons on the closed loop behavior.

Moreover, we give an analytic solution to the linear program from \cite{G07} and -- as a consequence -- an explicit formula for the suboptimality estimate based on the $\KL_0$-function characterizing our controllability assumption. This allows for a much more detailed analysis which is the main contribution of this paper. We investigate -- among others -- the impact of the {\em optimization horizon}, i.e., the interval on which the predicted trajectory is optimized (and which we choose identical to the prediction horizon), on the suboptimality and stability of the MPC closed loop. Especially, we prove conjectures from \cite{G07} with respect to minimal stabilizing horizons which were based on numerical observations. Furthermore, we analyze the influence of adding a final weight in the finite horizon cost functional.

The paper is organized as follows. In Section \ref{setupsec} we describe the setup and problem formulation. In Section \ref{controlsec} we introduce our controllability assumption and briefly summarize the needed results from \cite{G07}. In Section \ref{stabsec} we show that our suboptimality result can be used to conclude stability, extending \cite[Section 5]{G07} to time varying control horizons. In Section \ref{alphasec} we present the explicit formula for our suboptimality index $\alpha$ in Theorem \ref{alpha_formula_thm}. In the ensuing sections we examine effects of different parameters on $\alpha$. In particular, in Section \ref{alphasec1} we investigate the impact of the optimization horizon and in Sections \ref{alphasec2} and \ref{alphasec3} we scrutinize qualitative and quantitative effects, respectively, of different control horizons. Finally, in Section \ref{exsec} we illustrate our results with numerical examples. A number of technical lemmata and their proofs can be found in the appendix in Section \ref{appendix}.

\section{Setup and Preliminaries}\label{setupsec}

We consider a nonlinear discrete time control system given by
\begin{equation}
	\label{2:eq:discrete control system}
	x(n + 1) = f(x(n), u(n)), \quad x(0) = x_0
\end{equation}
with $x(n) \in X$ and $u(n) \in U$ for $n \in \N_0$. Here the state space $X$

and the control value space $U$ are arbitrary metric spaces. We denote
the space of control sequences $u: \N_0 \rightarrow U$ by $\UU$ and
the solution trajectory for given $u \in \UU$ by $x_u(\cdot)$. Note that
constraints can be incorporated by replacing $X$ and $U$ by appropriate
subsets of the respective spaces. For simplicity of exposition,
however, we will not address feasibility issues in this paper.

A typical class of such discrete time systems are sampled--data systems induced by a controlled --- finite or infinite dimensional --- differential equation with sampling period $T>0$. In this situation, the discrete time $n$ corresponds to the continuous time $t = n T$.

Our goal is to minimize the infinite horizon cost $J_\infty(x_0, u) = \sum_{n = 0}^\infty l(x_u(n), u(n))$ with running cost $l: X \times U \rightarrow \R_0^+$ by a multistep state feedback control (rigorously defined below in Definition \ref{2:def:m_i feedback law}). We denote the optimal value function for this problem by $V_\infty(x_0) := \inf_{u \in \UU} J_\infty(x_0,u)$. Since infinite horizon optimal control problems are in general computationally infeasible, we use a receding horizon approach in order to compute an approximately optimal controller. To this end, we consider the finite horizon functional
\begin{equation} \label{2:eq:finite cost functional}
	J_N(x_0, u) = \sum_{n = 0}^{N - 1} l(x_u(n), u(n))
\end{equation}
with {\em optimization horizon} $N\in\N$ inducing the optimal value function
\begin{equation} \label{2:eq:finite value function}
	V_N(x_0) = \inf_{u\in\UU} J_N(x_0,u).
\end{equation}
By solving this finite horizon optimal control problem we obtain $N$ control values $\mu(x_0,0),\linebreak[0] \mu(x_0,1),\linebreak[0]  \ldots,\linebreak[0]  \mu(x_0,N-1)$ depending on the state $x_0$. Implementing the first $m_0 \in \{1,\ldots,N-1\}$ elements of this sequence yields a new state $x(m_0)$. Iterative application of this construction then provides a control sequence on the infinite time interval, whose properties we intend to investigate in this paper. To this end, we introduce a more formal description of this construction.
\begin{definition}
	Given a set $M\subseteq\{1,\ldots,m^\star\}$, $m^\star \in \mathbb{N}$, we call a control horizon sequence $(m_i)_{i \in \N_0}$ {\em admissible} if $m_i\in M$ holds for all $i\in \N_0$. Furthermore, for $k, n\in\N_0$ we define
	\begin{eqnarray*}
		\sigma(k) & := & \sum_{j=0}^{k-1} m_i \quad \mbox{(using the convention $\sum_{j=0}^{-1}=0$)}\\ \varphi(n) & := & \max \{\sigma(k)\,|\, k\in\N_0, \sigma(k)\le n\}.
	\end{eqnarray*}
\end{definition}

Using this notation, the applied control sequence can be expressed as
\[
\ldots, \mu(x(\sigma(k)),0), \ldots, \mu(x(\sigma(k)),m_k-1), \mu(x(\sigma(k+1)),0), \ldots
\]
A closed loop interpretation of this construction can be obtained via multistep feedback laws.

\begin{definition} \label{2:def:m_i feedback law}
        For $m^\star \geq 1$ and $M\subseteq \{1,\ldots,m^\star\}$ a multistep feedback law is a map $\mu : X \times \{ 0,\linebreak[0]  \ldots, \linebreak[0] m^\star - 1 \} \rightarrow U$ which for an admissible control horizon sequence $(m_i)_{i \in \N_0}$ is applied according to the rule $x_\mu(0)=x_0$,
	\begin{equation} \label{2:def:m_i feedback law:eq1}
		x_\mu(n + 1) = f(x_\mu(n), \mu(x_\mu ( \varphi(n) ), n - \varphi(n))).
	\end{equation}
\end{definition}
Using this definition, the above construction is equivalent to the following definition.
\begin{definition} \label{2:def:mpc m-step feedback law}
        For $m^\star\ge 1$ and $N\ge m^\star+1$ we define the multistep MPC feedback law $\mu_{N, m^\star}(x_0,n) := u^\star(n)$, where $u^\star$ is a minimizing control for \eqref{2:eq:finite value function} with initial value $x_0$.
\end{definition}
\begin{remark}
	For simplicity of exposition here we assume that the infimum in \eqref{2:eq:finite value function} is a minimum, i.e., that a minimizing control sequence $u^*$ exists.
\label{minrem}\end{remark}

Note that in ``classical'' MPC only the first element of the obtained finite horizon optimal sequence of control values is used. Our main motivation for considering this generalized feedback concept with varying control horizons $m_i$ are networked control systems (NCS) in which the transmission channel from the controller to the plant is subject to packet dropouts. In order to compensate these dropouts, at each successful transmission time $\sigma(k)$ a whole sequence of control values is transmitted to the plant. This sequence is then used until the next successful transmission at time $\sigma(k+1) = \sigma(k)+m_k$, for details see \cite{GPW08}. Note that in this application the control horizon $m_k$ is not known at time $\sigma(k)$.

In this paper we consider the conceptually simplest MPC approach imposing neither terminal costs nor terminal constraints.
In order to measure the suboptimality degree of the multistep feedback for the infinite horizon problem we define
\begin{equation*}
	V_\infty^{\mu,(m_i)}(x_0) := \sum_{n = 0}^\infty l(x_{\mu}(n), \mu(x_\mu(\varphi(n)), n - \varphi(n))).
\end{equation*}
Our approach relies on the following result from relaxed dynamic programming \cite{LinR06,Rant06}, which is a straightforward generalization of proposition \cite[Proposition 2.4]{G07}, cf.\ \cite{GPW08} for a proof.
\begin{proposition} \label{2:prop:m-step suboptimality estimate}
	Consider a multistep feedback law $\wmu: X \times \{ 0, \ldots, m^\star - 1\} \rightarrow U$, a set $M\subseteq\{1,\linebreak[0] \ldots,\linebreak[0] m^\star\}$ and a function $\wV: X \rightarrow \R_0^+$ and assume that for each admissible control horizon sequence $(m_i)_{i\in\N_0}$ and each $x_0\in X$ the corresponding solution $x_\wmu(n)$ with $x_\wmu(0) = x_0$ satisfies
	\begin{equation}
		\label{2:prop:m-step suboptimality estimate:eq1}
		\wV(x_0) \geq \wV(x_\wmu(m_0)) + \alpha \sum_{k = 0}^{m_0 - 1} l(x_\wmu(k), \wmu(x_0, k))
	\end{equation}
	for some $\alpha\in(0,1]$. Then for all $x_0 \in X$ and all admissible $(m_i)_{i\in\N_0}$ the estimate $\alpha V_\infty(x_0) \leq \linebreak[0] \alpha \linebreak[0] V_\infty^{\wmu,(m_i)}(x_0)\linebreak[0]  \leq \linebreak[0] \wV(x_0)$ holds.
\end{proposition}

\section{Controllability and performance bounds}\label{controlsec}

In this section we introduce an asymptotic controllability assumption and deduce several consequences for our optimal control problem. In order to facilitate this relation we will formulate our basic controllability assumption, below, not in terms of the trajectory but in terms of the running cost $l$ along a trajectory.\\
To this end, we say that a continuous function $\rho: \R_{\geq 0} \rightarrow \R_{\geq 0}$ is of class $\KK_\infty$ if it satisfies $\rho(0) = 0$, is strictly increasing and unbounded. Furthermore, we say that a continuous function $\beta: \R_{\geq 0} \times \R_{\geq 0} \rightarrow \R_{\geq 0}$ is of class $\KL_0$ if for each $r > 0$ we have $\lim_{t \rightarrow \infty} \beta(r, t) = 0$ and for each $t \geq 0$ we either have $\beta(\cdot, t) \in \KK_\infty$ or $\beta(\cdot, t) \equiv 0$. Note that in order to allow for tighter bounds for the actual controllability behavior of the system we use a larger class than the usual class $\KL$. It is, however, easy to see that each $\beta \in \KL_0$ can be overbounded by a $\tilde{\beta} \in \KL$, e.g., by setting $\tilde \beta(r, t) = \sup_{\tau \geq t} \beta(r, \tau) + e^{-t} r$. Moreover, we define $l^\star(x) := \min_{u \in U} l(x, u)$.

\begin{assumption} \label{3:ass:controllability}
	Given a function $\beta \in \KL_0$, for each $x_0 \in X$ there exists a control function $u_{x_0} \in \UU$ satisfying $l(x_{u_{x_0}}(n), u_{x_0}(n)) \leq \beta(l^\star(x_0), n)$ for all $n \in \N_0$.
\end{assumption}

Special cases for $\beta \in \KL_0$ are
\begin{equation}
	\label{3:eq:exponential controllability}
	\beta(r, n) = C \sigma^n r
\end{equation}
for real constants $C \geq 1$ and $\sigma \in (0, 1)$, i.e., {\em exponential controllability}, and
\begin{equation}
	\label{3:eq:finite time controllability}
	\beta(r,n) = c_n r
\end{equation}
for some real sequence $(c_n)_{n \in \N_0}$ with $c_n \geq 0$ and $c_n = 0$ for all $n \geq n_0$, i.e., {\em finite time controllability} (with linear overshoot).\\
For certain results it will be useful to have the property
\begin{equation}
	\label{3:eq:submultiplicativity}
	\beta(r, n + m) \leq \beta( \beta(r, n), m) \quad \mbox{for all } r \geq 0, n, m \in \N_0.
\end{equation}
Property \eqref{3:eq:submultiplicativity} ensures that any sequence of the form $\lambda_n = \beta(r, n)$, $r > 0$, also fulfills $\lambda_{n + m} \leq \beta(\lambda_n, m)$. It is, for instance, always satisfied in case \eqref{3:eq:exponential controllability} and satisfied in case \eqref{3:eq:finite time controllability} if and only if $c_{n + m} \leq c_n c_m$. If needed, this property can be assumed without loss of generality, cf. \cite[Section 3]{G07}.

In order to ease notation, we define the value
\begin{equation}
	\label{3:eq:definition B_N}
	B_N(r) := \sum_{n = 0}^{N - 1} \beta(r,n).
\end{equation}
for any $r \geq 0$ and any $N \in \mathbb{N}_{\geq 1}$ . An immediate
consequence of Assumption \ref{3:ass:controllability} and Bellman's
optimality principle $V_N(x) = \min_{u\in U}\{l(x,u) +
V_{N-1}(f(x,u))\}$ are the following lemmata from \cite{G07}.

\begin{lemma}\label{VNboundlemma}
	For each $N \geq 1$ the inequality
	\begin{equation}
		\label{cont_bound}
		V_N(x_0) \leq B_N(l^\star(x_0))
	\end{equation}
	holds.
\end{lemma}

\begin{lemma}\label{lemma}
	Suppose Assumption \ref{3:ass:controllability} holds and consider $x_0 \in X$ and an optimal control $u^\star$ for the finite horizon optimal control problem \eqref{2:eq:finite value function} with optimization horizon $N \geq 1$. Then for each $j = 0, \ldots, N - 2$ the inequality
	\begin{equation}
		J_{N-j}(x_{u^\star}(j), u^\star(j + \cdot)) \leq B_{N - j}(l^\star(x_{u^\star}(j))
	\end{equation}
	and for each $m = 1, \ldots, N - 1$ and each $j = 0, \ldots, N - m - 1$ the inequality
	\begin{equation}
		V_{N}(x_{u^\star}(m)) \leq J_j(x_{u^\star}(m), u^\star(m + \cdot)) + B_{N - j} (l^\star (x_{u^\star}(m + j)))
	\end{equation}
	holds for $B_{N - j}$ from \eqref{3:eq:definition B_N}.
\end{lemma}

Now we provide a constructive approach in order to compute $\alpha$ in
\eqref{2:prop:m-step suboptimality estimate:eq1} for systems
satisfying Assumption \ref{3:ass:controllability}. Note that
\eqref{2:prop:m-step suboptimality estimate:eq1} only depends on $m_0$
and not on the remainder of the control horizon sequence. Hence, we
can perform the computation separately for each control horizon $m$ and
obtain the desired $\alpha$ for variable $m$ by minimizing over the
$\alpha$-values for all admissible $m$.

For our computational approach we consider arbitrary values
$\lambda_0, \ldots, \lambda_{N - 1} > 0$ and $\nu > 0$ and start by
deriving necessary conditions under which these values coincide with
an optimal sequence $l(x_{u^\star}(n), u^\star(n))$ and an optimal
value $V_N(x_{u^\star}(m))$, respectively.

\begin{proposition}\label{4:prop:necessary conditions}
	Suppose Assumption \ref{3:ass:controllability} holds and consider $N
        \geq 1$, $m \in \{ 1, \ldots, N - 1 \}$, a sequence $\lambda_n
        > 0$, $n = 0, \ldots, N - 1$, and a value $\nu > 0$. Consider $x_0
        \in X$ and assume that there exists a minimizing control
        $u^\star \in \UU$ for \eqref{2:eq:finite value function} such
        that $\lambda_n$ equals $l(x_{u^\star}(n), u^\star(n))$ for all
        $n \in \{0, \ldots, N - 1\}$. Then
	\begin{equation}
		\label{4:prop:necessary conditions:eq1}
		\sum_{n = k}^{N - 1} \lambda_n \leq B_{N - k}(\lambda_k), \quad	k = 0, \ldots, N - 2
	\end{equation}
	holds true and if furthermore $\nu = V_N(x_{u^\star}(m))$ we have
	\begin{equation}
		\label{4:prop:necessary conditions:eq2}
		\nu \leq \sum_{n = 0}^{j - 1} \lambda_{n + m} + B_{N - j}(\lambda_{j + m}), \quad j = 0, \ldots, N - m - 1.
	\end{equation}
\end{proposition}
\begin{proof}
	If the stated conditions hold, then $\lambda_n$ and $\nu$ meet the inequalities given in Lemma \ref{lemma}, which is exactly \eqref{4:prop:necessary conditions:eq1} and \eqref{4:prop:necessary conditions:eq2}.
\end{proof}

Using this proposition a sufficient condition for suboptimality of the
MPC feedback law $\mu_{N,m}$ is given in Theorem
\ref{4:thm:optimality} which is proved in \cite{G07}.

\begin{theorem} \label{4:thm:optimality}
	Consider $\beta \in \KL_0$, $N \geq 1$, $m \in \{ 1, \ldots, N - 1 \}$, and assume that all sequences $\lambda_n > 0$, $n = 0, \ldots, N - 1$ and values $\nu > 0$ fulfilling \eqref{4:prop:necessary conditions:eq1}, \eqref{4:prop:necessary conditions:eq2} satisfy the inequality
	\begin{equation}
		\label{4:thm:optimality:eq1}
		\sum_{n = 0}^{N - 1} \lambda_n - \nu \geq \alpha \sum_{n = 0}^{m - 1} \lambda_n
	\end{equation}
	for some $\alpha\in(0,1]$. Then for each optimal control problem \eqref{2:eq:discrete control system}, \eqref{2:eq:finite value function} satisfying Assumption \ref{3:ass:controllability} the assumptions of Proposition \ref{2:prop:m-step suboptimality estimate} are satisfied for the multistep MPC feedback law $\mu_{N,m}$ and in particular the inequality
$\alpha V_\infty(x) \leq \alpha V_\infty^{\mu_{N, m}}(x) \leq V_N(x)$
	holds for all $x \in X$.
\end{theorem}

In view of Theorem \ref{4:thm:optimality}, the value $\alpha$ can be interpreted as a performance bound which indicates how good the receding horizon MPC strategy approximates the infinite horizon problem. In the remainder of this section we present an optimization based approach for computing $\alpha$. To this end, consider the following optimization problem.

\begin{problem}\label{optprob}
	Given $\beta \in \KL_0$, $N \geq 1$ and $m \in \{ 1, \ldots, N - 1 \}$, compute
	\begin{equation*}
		\alpha_{N,m}^1 := \inf_{\lambda_0, \ldots, \lambda_{N - 1}, \nu} \frac{\sum_{n = 0}^{N - 1} \lambda_n - \nu}{\sum_{n = 0}^{m - 1} \lambda_n}
	\end{equation*}
	subject to the constraints \eqref{4:prop:necessary conditions:eq1}, \eqref{4:prop:necessary conditions:eq2}, and $\lambda_0, \ldots, \lambda_{N - 1}, \nu > 0$.
\end{problem}

The following is a straightforward corollary from Theorem \ref{4:thm:optimality}.

\begin{corollary}\label{optcor}
	Consider $\beta \in \KL_0$, $N \geq 1$, $m \in \{ 1, \ldots, N
        - 1 \}$, and assume that the optimization problem
        \ref{optprob} has an optimal value $\alpha \in (0, 1]$. Then
        for each optimal control problem \eqref{2:eq:discrete control
          system}, \eqref{2:eq:finite value function} satisfying
        Assumption \ref{3:ass:controllability} the assumptions of
        Theorem \ref{4:thm:optimality} are satisfied and the
        assertions from Theorem \ref{4:thm:optimality} hold.
\end{corollary}

As already mentioned in \cite[Remark 4.3]{G07}, our setting can be easily extended to the setting including an additional weight $\omega \geq 1$ on the final term, i.e., altering our finite time cost functional by adding $(\omega - 1) l(x_u(N-1), u(N-1))$. Note that the original form of the functional $J_N$ is obtained by setting $\omega = 1$. All results in this section remain valid if the statements are suitably adapted. In particular, \eqref{2:eq:finite cost functional} and \eqref{3:eq:definition B_N} become
\begin{eqnarray}
	J_N(x_0, u) & := & \sum_{n = 0}^{N - 2} l(x_u(n), u(n)) + \omega l(x_u(N-1), u(N-1)) \nonumber \\
	\label{3:eq:definition B_N_omega}
	B_N(r) & := & \sum_{n = 0}^{N - 2} \beta(r,n) + \omega \beta(r,N-1).
\end{eqnarray}
and the formula in Problem \ref{optprob} alters to
\begin{equation}\label{opt_with_omega}
	\alpha_{N,m}^\omega := \inf_{\lambda_0, \ldots, \lambda_{N - 1}, \nu} \frac{\sum_{n = 0}^{N - 2} \lambda_n + \omega \lambda_{N-1}- \nu}{\sum_{n = 0}^{m - 1} \lambda_n}.
\end{equation}

\section{Asymptotic stability}\label{stabsec}

In this section, which extends \cite[Section 5]{G07} to varying control horizons, we show how the performance bound $\alpha=\alpha_{N,m}^\omega$ can be used in order to conclude asymptotic stability of the MPC closed loop. More precisely, we investigate the asymptotic stability of the zero set of
$l^\star$. To this end, we make the following assumption.

\begin{assumption}\label{A-ass}
	There exists a closed set $A \subset X$ satisfying:
	\begin{itemize}
		\item[(i)] For each $x \in A$ there exists $u \in U$ with $f(x, u) \in A$ and $l(x, u) = 0$, i.e., we can stay inside $A$ forever at zero cost.
		\item[(ii)] There exist $\KK_\infty$--functions	$\alpha_1$, $\alpha_2$ such that the inequality
		\begin{equation}
			\label{lbound}
			\alpha_1(\| x \|_A) \leq l^\star(x) \leq \alpha_2(\| x \|_A)
		\end{equation}
		holds for each $x \in X$ where $\| x \|_A := \min_{y \in A}\| x - y \|$.
	\end{itemize}
\end{assumption}
This assumption assures global asymptotic stability of $A$ under the
optimal feedback for the infinite horizon problem, provided $\beta(r,
n)$ is summable. We remark that condition (ii) can be relaxed in
various ways, e.g., it could be replaced by a detectability condition
similar to the one used in \cite{GMTT05}. However, in order to keep
the presentation in this paper technically simple we will work with
Assumption \ref{A-ass}(ii) here. Our first stability result is
formulated in the following theorem. Here we say that a multistep
feedback law $\mu$ asymptotically stabilizes a set $A$ if there exists
$\tilde\beta\in\KL_0$ such that for all admissible control horizon
sequences the closed
loop system satisfies $\| x_\mu(n) \|_A \leq \tilde{\beta}(\| x_0
\|_A, n)$.

\begin{theorem} \label{stabthm}
Consider $\beta \in \KL_0$, $m^\star \ge 1$ and $N \geq m^\star+1$ and
a set $M\subseteq \{1,\ldots,m^\star\}$. Assume that $\alpha^\star :=
\min_{m \in M} \{ \alpha_{N,m}^\omega \} > 0$ where $\alpha_{N,m}^\omega$ denotes
the optimal value of optimization Problem \ref{optprob}. Then for each
optimal control problem \eqref{2:eq:discrete control system},
\eqref{2:eq:finite value function} satisfying the Assumptions
\ref{3:ass:controllability} and \ref{A-ass} the multistep MPC
feedback law $\mu_{N, m^\star}$ asymptotically stabilizes the set
$A$ for all admissible control horizon sequences
$(m_i)_{i\in\N_0}$. Furthermore, the function $V_N$ is a
Lyapunov function at the transmission times $\sigma(k)$ in the sense
that
	\begin{eqnarray}
		\label{lyapineq}
		V_N(x_{\mu_{N, m^\star}}(\sigma(k+1)))
                & \leq &
                V_N(x_{\mu_{N, m^\star}}(\sigma(k))) \\
                &&  - \,\, \nonumber
                \alpha^\star V_{m_k}(x_{\mu_{N,
                    m^\star}}(\sigma(k)))
	\end{eqnarray}
holds for all $k \in \N_0$ and $x_0\in X$.
\end{theorem}
\begin{proof}
	From \eqref{lbound} and Lemma \ref{VNboundlemma} we
        immediately obtain the inequality
	\begin{equation}
		 \label{lyapbound}
		\alpha_1(\| x \|_A) \leq V_N(x) \leq B_N(\alpha_2(\| x \|_A)).
	\end{equation}
	Note that $B_N \circ \alpha_2$ is again a
        $\KK_\infty$--function. The stated Lyapunov inequality
        \eqref{lyapineq} follows immediately from the definition of
        $\alpha^\star$ and \eqref{2:prop:m-step suboptimality
          estimate:eq1} which holds according to Corollary
        \ref{optcor} for all $m \in M$. Again, using \eqref{lbound} we
        obtain $V_m(x) \geq \alpha_1(\| x \|_A)$ and thus a standard
        construction (see, e.g., \cite{NeTe04}) yields a
        $\KL$--function $\rho$ for which the inequality
        $V_N(x_{\mu_{N, m^\star}}(\sigma(k))) \leq \rho
        (V_N(x), k)\leq \rho
        (V_N(x), \lfloor \sigma(k)/m^\star\rfloor)$ holds. In
        addition, using the definition of
        $\mu_{N, m^\star}$, for $p = 1, \ldots,
        m_k-1$, $k\in\N_0$, and abbreviating $x(n)=x_{\mu_{N, m^\star}}(n)$
        we obtain
	\begin{eqnarray*}
		&& V_N(x(\sigma(k)+p)) \\
		&& \le  \sum_{n = \sigma(k)+p}^{\sigma(k+1)-1} l(x(n),
                \mu_{N, m^\star}(x(\varphi(n)), n-\varphi(n)))\\
		&& \quad + \,\, V_{N - m_k + p}(x(\sigma(k+1))) \\
		&& \le  \sum_{n = \sigma(k)}^{\sigma(k+1)-1} l(x(n),
                \mu_{N, m^\star}(x(\varphi(n)), n-\varphi(n)))\\
		&& \quad + \,\, V_{N - m_k + p}(x(\sigma(k+1))) \\
		&& \leq  \,\, V_N(x(\sigma(k))) + V_N(x(\sigma(k+1)))\,\,
                \leq \,\, 2 V_N(x(\sigma(k)))
	\end{eqnarray*}
	where we have used \eqref{lyapineq} in the last inequality. Hence, we obtain the estimate $V_N(x_{\mu_{N,
            m^\star}}(n)) \leq 2 \rho(V_N(x),\lfloor
        \varphi(n)/m^\star\rfloor)$ which implies
	\begin{eqnarray*}
		\|x_{\mu_{N,m^\star}}(n)\|_A & \leq & \alpha_1^{-1}(V_N(x_{\mu_{N,m^\star}}(n))) \\
		& \leq & \alpha_1^{-1}(2\rho(V_N(x),\lfloor
        \varphi(n)/m^\star\rfloor)) \\
		& \leq & \alpha_1^{-1}(2 \rho(B_N( \alpha_2(\| x
                \|_A)), \lfloor
        (n-m^\star)/m^\star\rfloor))
	\end{eqnarray*}
	and thus asymptotic stability with $\KL$-function given by, e.g., $\tilde{\beta}(r, n) = \linebreak[0] \alpha_1^{-1}(2 \rho(B_N( \alpha_2(r)),\linebreak[0] \lfloor
        (n-m^\star)/m^\star\rfloor)) + r e^{-n}$.
\end{proof}
\begin{remark}\label{rem:tight}
(i) For the ``classical'' MPC case $m^\star=1$ and $\beta$ satisfying
\eqref{3:eq:submultiplicativity}
it is shown in
\cite[Theorem 5.3]{G07} that the criterion from Theorem \ref{stabthm}
is tight in the sense that if $\alpha^\star<0$ holds then there exists
a control system which satisfies Assumption \ref{3:ass:controllability}
but which is not stabilized by the MPC scheme. We conjecture that the
same is true for the general case $m^\star \ge 2$.

(ii) Note that in Theorem \ref{stabthm} we use a criterion for arbitrary but fixed $m\in M$ in order to conclude asymptotic stability for time varying $m_i\in M$. This is possible since our proof yields $V_N$ as a common Lyapunov function for all $m\in M$, cf.\ also \cite[Section 2.1.2]{Lib03}.
\end{remark}

\input{alpha_formula}
\input{alpha_properties}
\input{control_horizon}

\section{Example}\label{exsec}

In this section we compare our analytical results with numerical MPC simulations. The first example is a linear inverted pendulum which is solved for a grid of initial values. The second example is a nonlinear form of the inverted pendulum. We use it to show that enlarging the control horizon $m$ exhibits a stabilizing effect even for long optimization horizons $N$. Since numerical optimization for large control horizons appears to be difficult, we added a third example, a nonlinear arm--rotor--platform model, which allows us to show numerical results for $m=1, \ldots, N-1$.

\subsection{Linear Inverted Pendulum}

Our first example is a linear inverted pendulum on a cart given by
\begin{equation*}
	\dot{x}(t) = \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ g &
            -k & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array}
        \right) x + \left( \begin{array}{c} 0 \\ 1 \\ 0 \\ 1
          \end{array} \right) u,
\end{equation*}
in which we want to stabilize the upright position $x^\star = (0, 0, 0, 0)$ using linear MPC. Here, we used the optimization horizon $N = 10$, the sampling interval $T = 0.7$ and the cost functional $J_N(x_0, u) = \sum_{n = 0}^{N - 1} \|Qx_u(n)\|_1 + \|Ru(n)\|_1$ with $Q = 2 \, \text{Id}$ and $R = 4\, \text{Id}$. Moreover, we use the constants $g = 9.81$ and $k = 0.1$ for gravitation and friction respectively.\\
Since Assumption \ref{3:ass:controllability} exhibits a set--valued nature we consider a uniform grid $\mathcal{G}$ of initial values from the set $[-0.05, 0.05]^2 \times [-1, 1] \times [-0.05, 0.05]$ which contains the origin $x^\star$. For each $m=1,\ldots,9$ we simulate the MPC closed loop trajectories $x_{\mu_{N,m}}$ with control horizon $m_i\equiv m$ and initial value $x \in \mathcal{G}$. Along each trajectory we then compute $\alpha_{N,m}^{\omega}$ as the minimum of the suboptimality degrees from Formula \eqref{2:prop:m-step suboptimality estimate:eq1} applied with $x_0=x_{\mu_{N,m}}(n)$, $n=0,m,2m,\ldots,19$. A selection of these values is plotted in Fig.\ \ref{5:fig:curve}, in which each dashed line represents the values $\alpha_{N,1}^{\omega},\ldots,\alpha_{N,N-1}^{\omega}$ for a corresponding initial value. In addition, the minima over all trajectories are plotted as a solid line.
\begin{figure}[!ht]
	\begin{center}
		\includegraphics[width=0.48\textwidth]{pictures/LinearInvertedPendulum}
		\hfill
		\includegraphics[width=0.48\textwidth]{pictures/LinearInvertedPendulum2.jpg}
	\end{center}
	\caption{Approximation of $\alpha_{10,m}^\omega$, $\omega \in \{1, \ldots, 8\}$, for the linear inverted pendulum.}
	\label{5:fig:curve}
\end{figure}

The results indicate that the closed loop is asymptotically stable for each $m_i$ and confirm that choosing control horizons $m_i > 1$ may indeed improve the suboptimality bound. Moreover, it is interesting to compare Fig.\ \ref{5:fig:curve} with Fig.\ \ref{typical_values}. While Fig.\ \ref{typical_values} shows the minimal $\alpha$-values for a set of exponentially controllable systems, the curves in Fig.\ \ref{5:fig:curve} represent the numerically computed $\alpha$-values for one particular system and a grid of initial values. Yet, the curves in Fig.\ \ref{5:fig:curve} at least approximately resemble the shape of the curves in Fig.\ \ref{typical_values}.\\
The second part of Fig.\ \ref{typical_values} treats the enlarged weights on the final term. Comparing the presented analytical results to our simulations depicted in the right part of Fig.\ \ref{5:fig:curve} we obtain the same tendency: If the weight on the final term is increased, then the degree of suboptimality $\alpha$ is growing faster for small control horizons $m$.

\subsection{Nonlinear Inverted Pendulum}

In order to show that similar effects can be experienced for nonlinear control problems, we consider the presented inverted pendulum on a cart problem in the nonlinear form
\begin{align*}
	\dot{x}_1(t) & = x_2(t)\\
	\dot{x}_2(t) & = -\frac{g}{l}\sin(x_1(t) + \pi) - \frac{k_L}{l} x_2(t) | x_2(t) | - u(t) \cos(x_1(t) + \pi) - k_R \mbox{sgn}(x_2(t))\\
	\dot{x}_3(t) & = x_4(t)\\
	\dot{x}_4(t) & = u(t)
\end{align*}
with gravitation constant $g = 9.81$, length $l = 10$ and friction terms $k_R = k_L = 0.01$. Again, we aim at stabilizing the upright position $x^\star = (0, 0, 0, 0)$. Here, we consider the stage cost
\begin{align*}
	l(x(i), u(i)) := & \int\limits_{t_i}^{t_{i+1}} 10^{-4} u(t)^2 + \Big( 3.51 \sin(x_1(t))^2 + 4.82 \sin(x_1(t)) x_2(t) + 2.31 x_2(t)^2 \\
	& \quad + 0.1 \left( (1 - \cos(x_1(t))) \cdot (1 + \cos(x_2(t))^2) \right)^2 + 0.01 x_3(t)^2 + 0.1 x_4(t)^2 \Big)^2 dt
\end{align*}
which gives us the cost functional
\begin{align*}
	J_N(x_0, u) = &\sum\limits_{i = 0}^{N - 2} l(x(i), u(i)) + \omega l(x(N-1), u(N-1))
\end{align*}
over an optimization horizon $N = 70$ and sampling length $T = 0.05$. Moreover, the tolerances of the optimization routine and the differential equation solver are set to $10^{-6}$ and $10^{-7}$ respectively. Since this cost functional is $2 \pi$--periodic, we add box--constraints limiting $X$ to the interval $[-2 \pi + 0.01, 2 \pi - 0.01]$. Using the initial value $x_0 = (\pi + 1.5, 0, 0, 0)$, we simulated the MPC closed--loop trajectories $x_{\mu_{N,m}}$ for $m = 1, \ldots, 10$ and final weights $\omega = 1, \ldots, 10$ with control horizon $m_i \equiv m$.\\
Since the numerical optimization is not reliable on start of the NMPC algorithm, a startup sequence of 20 NMPC iterations using $m=1$ is implemented to obtain an initial guess of the control which can be assumed to be close to the global optimum. Moreover, the problem appears to be practically stabilizable only. To compensate this issue, we used the estimation constant $\varepsilon = 10^{-4}$, cf. \cite[Theorem 21]{GruP09} for details.\\
In Fig.\ \ref{fig:nonlinear}, the minimal $\alpha$--value along a closed--loop trajectory is shown for a variety of final weights $\omega$ and control horizons $m$.

\begin{figure}[!ht]
	\begin{center}
		\includegraphics[width=0.48\textwidth]{pictures/NonlinearInvertedPendulum}
		\hfill
		\includegraphics[width=0.48\textwidth]{pictures/NonlinearInvertedPendulum2.jpg}
	\end{center}
	\caption{Approximation of $\alpha_{70,m}^{\omega}$, $m \in \{1, \ldots, 10\}$, for the nonlinear inverted pendulum.}
	\label{fig:nonlinear}
\end{figure}

For this simulation, we were able to increase the range of $m$ from 3 to 20 for which acceptable $\alpha$ values can be computed by internally repeating the optimization at every sampling point. This allows us to keep track of a suitable initial guess of the control while the system is running in open--loop. For $m \geq 21$ we experience numerical problems during the optimization and although most of the resulting trajectories converge to the target point, we cannot see this from our estimates.\\
Note that for $\omega = 1$ the $\alpha$ values are negative for control horizons $m = 1, \ldots, 4$. Still, larger control horizons exhibit a positive $\alpha$ value such that stability is guaranteed. Additionally, an increase in $\alpha$ can be experienced for all control horizons $m$ considered in this example if $\omega$ is increased. This corresponds to the known stabilizing effect of terminal costs.\\
Since computing these estimates can be done with very small additional effort compared to the MPC procedure, such an analysis should be done before enlarging the optimization horizon.

\subsection{Nonlinear Arm--Rotor--Platform Modell}

Last, we consider an arm/\-rotor/\-platform (ARP) model:
\begin{align*}
	\dot{x}_{1}(t) & = x_{2}(t) + x_{6}(t) x_{3}(t) \\
	\dot{x}_{2}(t) & = -\frac{k_{1}}{M} x_{1}(t) - \frac{b_{1}}{M} x_{2}(t) + x_{6}(t) x_{4}(t) - \frac{m r b_{1}}{M^{2}} x_{6}(t) \\
	\dot{x}_{3}(t) & = - x_{6}(t) x_{1}(t) + x_{4}(t) \displaybreak[0] \\
	\dot{x}_{4}(t) & = - x_{6}(t) x_{2}(t) - \frac{k_{1}}{M} x_{3}(t) - \frac{b_{1}}{M} x_{4}(t) + \frac{m r k_{1}}{M^{2}} \\
	\dot{x}_{5}(t) & = x_{6}(t) \\
	\dot{x}_{6}(t) & = -a_{1} x_{5}(t) - a_{2} x_{6}(t) + a_{1} x_{7}(t) + a_{3} x_{8}(t) - p_{1} x_{1}(t) - p_{2} x_{2}(t) \\
	\dot{x}_{7}(t) & = x_{8}(t) \\
	\dot{x}_{8}(t) & = a_{4} x_{5}(t) + a_{5} x_{6}(t) - a_{4} x_{7}(t) - (a_{5} + a_{6}) x_{8}(t) + \frac{1}{J} u(t)
\end{align*}
For details on the specification of the model parameters we refer to \cite[Chapter 7.3.2]{FK96}. \\
For this example, we fix the initial values to $x(t_0) = (0, 0, 0, 0, 10, 0, 0, 0)$, the absolute and relative tolerances for the solver of the differential equation both to $10^{-10}$, the length of the open--loop horizon within the MPC--algorithm to $H = N \cdot T$ with $N = 13$ and sampling period $T = 0.05$, and set the optimality tolerance of the SQP solver to $10^{-8}$. Moreover, the cost functional is given by
\begin{align*}
	J(x, u) = \sum\limits_{j = 0}^{N - 2} \int_{t_j}^{t_{j+1}} \| x(t) \| + u(t)^2 dt + \omega \int_{t_{N-1}}^{t_{N}} \| x(t) \| + u(t)^2 dt
\end{align*}
and the practical region of the equilibrium is estimated using the constant $\varepsilon = 5 \cdot 10^{-7}$. Again, we used a startup sequence of 5 NMPC iterations with $m=1$ to improve the initial guess of the control.

\begin{figure}[!ht]
	\begin{center}
		\includegraphics[width=0.48\textwidth]{pictures/Robot}
		\hfill
		\includegraphics[width=0.48\textwidth]{pictures/Robot2.jpg}
	\end{center}
	\caption{Approximation of $\alpha_{13,m}^\omega$ for the arm--rotor--platform model.}
	\label{fig:arp}
\end{figure}

Similar to Fig.\ \ref{fig:nonlinear}, Fig.\ \ref{fig:arp} shows the minimal $\alpha$--value along a closed--loop trajectory for a variety of final weights $\omega$ and all possible control horizons $m = 1, \ldots, N$. Again, we obtain an improvement of our suboptimality estimate if the final weight $\omega$ is increased. Considering the control horizon $m$, however, we hardly experience any improvement for small $m$ and a decrease of $\alpha$ for $m$ being large.\\
Note that suboptimality estimates which are computed for every sampling instant inherit a different weighting of these instants if $m$ is changed. Yet, a fair comparison can be obtained if only those control horizon lengths are taken into account which are an integer factor of the largest one and use the estimate \eqref{2:prop:m-step suboptimality estimate:eq1}. In the left of Fig.\ \ref{fig:arp2} we display such a comparison for $m \in \{ 1, 2, 3, 4, 6, 12 \}$. The corresponding cost of the closed--loop costs $V^{\mu_{N,m}}$ considering the first  are shown on the right of Fig.\ \ref{fig:arp2}. It exhibits the expected decrease in $\omega$, but also the rise in $m$. Moreover, increasing the control horizon $m$ implies that the system remains in open--loop for a longer period of time which may be harmful even in terms of stability if modelling errors or external perturbations occur, cf. \cite{Magni}. A detailed quantitative analysis of these effects in our setting is currently under investigation.

\begin{figure}[!ht]
	\begin{center}
		\includegraphics[width=0.48\textwidth]{pictures/Robot3}
		\hfill
		\includegraphics[width=0.48\textwidth]{pictures/Robot4.jpg}
	\end{center}
	\caption{Weighted approximation of $\alpha_{13,m}^\omega$ (left) and closed--loop cost (right) for the arm--rotor--platform model.}
	\label{fig:arp2}
\end{figure}

\input{appendix}


TITLE: Given three real numbers $a,b,c$ so that $\{a, b, c\}\subset [1, 2]$ . Prove that $7abc\geq ab(a+ b)+ bc(b+ c)+ ca(c+ a)$ .
QUESTION [0 upvotes]: I need to a fresh solution with $a:\neq {\rm mid}\{a, b, c\}$ , but mine

$$\begin{align*}
7abc &- ab(a+ b)- bc(b+ c)- ca(c+ a)= \\
 &= a(2b- c)(2c- b)- (b+ c)(a- b)(a- c)\geq 0
\end{align*}$$

REPLY [0 votes]: Let
$$P = 7abc - ab(a+ b)- bc(b+ c)- ca(c+ a).$$
The second derivative in each variable is clearly $\leq 0$, so the minimum is achieved at the end points.
Checking them, the minimum is 0.


TITLE: Convergence of the difference between the Nth harmonic number and Ln(N)
QUESTION [1 upvotes]: My question is how would you go about proving that the sequence given by the difference of the nth harmonic number and the natural log of that number converges.

REPLY [1 votes]: Let $H_n$ denote the partial sum of the harmonic series.
Show that $H_n - \log(n)$ is a $decreasing$ sequence that is bounded below.
(Note that $H_1 - \log(1)  = 1$, $H_2 - \log(2) \approx 0.8069$, and the sequence is not increasing.)
We have
$$\frac1{k+1} < \int_{k}^{k+1}\frac{dx}{x}=\log(k+1)-\log(k) <\frac1{k.}$$
Then for $n > 1$
$$\sum_{k=1}^{n-1}\frac1{k+1}<\log n <\sum_{k=1}^{n-1}\frac1{k},\\H_n-1<\log n< H_n-\frac1{n}.$$
Hence,
$$0 < \frac1{n} < H_n -\log n \leq 1.$$
So $H_n - \log n $ is bounded between $0$ and $1$ for all $n \in \mathbb{N}$.
Also
$$\frac1{n+1} < \log(n+1)-\log(n),\\\frac1{n+1} - \log(n+1)< -\log(n),\\ \sum_{k=1}^{n}\frac1{k} + \frac1{n+1} - \log(n+1)<\sum_{k=1}^{n}\frac1{k}  - \log(n).$$
Hence $H_{n+1} - \log(n+1) < H_n - \log(n)$ and the sequence is decreasing and convergent to a limit between $0$ and $1$.