TITLE: Taylor expansion of $\sqrt{n-k}$
QUESTION [5 upvotes]: I am reading a paper which casually assumes the asymptotic $\sqrt{n-k} \simeq \sqrt{n}-\frac{k}{2\sqrt{n}}$. This expression is what Wolfram calls Taylor expansion at infinity and from what I understand we work with $\sqrt{x-k}=\sqrt{x}\cdot \sqrt{1-k/x}$ and then we proceed on doing the Taylor expansion. My problem is that we also cannot do Taylor expansion near zero because said function is not differentiable there.
Another point is: do the Taylor expansion near point $1$ for $\sqrt{x}$ so that
$$\sqrt{x}\sqrt{1-k/x} = \sqrt{x} - \frac{k}{2\sqrt{x}} - \frac{k^2}{8x^{3/2}}\frac{1}{\xi^{3/2}},$$ where $\xi$ as in Legendre residual form (between $1-k/x$ and $1$). We can then deduce that $\sqrt{n-k}\leq \sqrt{n}-k/2\sqrt{n},$ but what about the lower bound? Is there a way to fix an inequality relating the remainder and the second term of the above expansion?
My real question, is how to use the aforementioned fact in order to get a result of the form $$\sqrt{x-1/2}\geq \sqrt{x}\left(1-\frac{4}{x}\right).$$ The first two terms of $\sqrt{x-1/2}$ in the above expansion should be $\sqrt{x}-\frac{1}{4\sqrt{x}},$ so the remainder term should be $\geq -\frac{15}{4\sqrt{x}}$ or something.

REPLY [0 votes]: If you want to show that $\sqrt{x-1/2}\geq \sqrt{x}\left(1-\frac{4}{x}\right),$
the following argument is simpler than bounding Taylor series terms:
(a)  for $\frac12\le x<4$:   $\sqrt{x-1/2}\geq0\gt \sqrt{x}\left(1-\frac{4}{x}\right);$
(b) for $x>\frac{32}{15}, \frac{15}2>\frac{16}x,$ so $x-\frac12>x-8+\frac{16}x=x(1-\frac4x)^2, $ so $\sqrt{x-1/2}>\sqrt x(1-\frac4x);$
so we have shown $\sqrt{x-1/2}>\sqrt x\left(1-\frac4x\right)$ for all $x$ where $\sqrt{x-1/2}$ is defined.


TITLE: Prove $Tx=x$, for $x\in H$, if and only if $(Tx,x)=\|x\|^2$ and $\ker(I-T)=\ker(I-T^*)$
QUESTION [0 upvotes]: Let $H$ be a complex Hilbert space and $T:H\rightarrow H$ an operation such that $\|T\|\leq 1$. Show that

$Tx=x$ if and only if $(Tx,x)=\|x\|^2$
$\ker(I-T)=\ker(I-T^*)$.

My attempt
1. $(Tx,x)=(x,x)=\|x\|^2$ if $Tx=x$. Conversely, WTS $\|Tx-x\|=0$ $\forall x\in H$.
We get $\|Tx-x\|=(Tx-x,Tx-x)=\|Tx\|^2-(x,Tx)$. But $\|T\|\leq 1$ has not been used.
Please how do I proceed?

REPLY [2 votes]: For the first point, first off since $\left \langle Tx,x\right\rangle=\|x\|^2$ you also have $\left \langle x,Tx\right\rangle = \overline{\|x\|^2}=\|x\|^2$. Thus
$$0 \leq\left\langle Tx-x,Tx-x\right\rangle =\|Tx\|^2+\|x\|^2-\left\langle Tx, x\right\rangle-\left\langle x,Tx\right\rangle= \|Tx\|^2-\|x\|^2 $$
Since $\|T\|\leq 1$,
$$0 \leq \|Tx\|^2-\|x\|^2 \leq \|x\|^2-\|x\|^2=0 $$
and hence $Tx=x$.
For the second point, using the first point
\begin{align*}x\in \ker(I-T)\iff Tx=x \iff \left \langle Tx,x\right\rangle =\|x\|^2\end{align*}
Now observe that if $\|T\|\leq 1$ then also $\|T^*\|\leq 1$. Indeed,
\begin{align*}\|T^*\|&=\sup_{x\neq 0}\frac{\|T^*x\|}{\|x\|}=\sup_{x\neq 0}\frac{\left\langle T^*x,T^*x\right\rangle^{1/2}}{\|x\|}=\sup_{x\neq 0}\frac{\left\langle TT^*x,x\right\rangle^{1/2}}{\|x\|}\leq \sup_{x\neq 0}\frac{\|TT^*x\|^{1/2}}{\|x\|^{1/2}}\leq\\
&\leq\sup_{x\neq 0}\frac{\|T^*x\|^{1/2}}{\|x\|^{1/2}}=\|T^*\|^{1/2}\end{align*}
i.e. $\|T^*\|\leq \|T^*\|^{1/2}$ and thus $\|T^*\|\leq 1$ (remark: this argument can be easily extended to prove that in general $\|T\|=\|T^*\|$ for any bounded linear operator $T$).
Therefore the first point may be applied to $T^*$, too.
\begin{align*}
x\in \ker (I-T^*)\iff T^*x=x\iff \left \langle T^*x,x\right\rangle = \|x\|^2\iff \left \langle x,Tx\right\rangle =\|x\|^2
\end{align*}
But $\left \langle Tx,x\right\rangle =\|x\|^2 $ implies $\left \langle x, Tx\right\rangle = \left \langle Tx,x\right\rangle =\|x\|^2$, as shown above, and viceversa, thus the equivalence is proved.


TITLE: Solving modular equations of two variables
QUESTION [2 upvotes]: $$7x + 9y \equiv 0 \pmod {31}$$
$$2x - 5y \equiv 2 \pmod {31}$$
I'm supposed to find the x, but I'm stuck in the middle.
First I tried to get rid of y.
$$53x \equiv 18 \pmod {31}$$
Here now I don't know what to do with this. Can anyone help me out?Thanks.

REPLY [5 votes]: You need to find the inverse of $53\equiv 22$ modulo $31$. To do it, you may use the Euclidean algorithm. ote you can also look at this as a $$\begin{pmatrix}7&9\\2&-5\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}0\\2\end{pmatrix}$$
Note that $$\det\begin{pmatrix}7&9\\2&-5\end{pmatrix}=-53\equiv 9$$
But $9\times 7=63\equiv 1$ so
$$\begin{pmatrix}x\\y\end{pmatrix}=7\begin{pmatrix}-5&-9\\-2&7\end{pmatrix}\begin{pmatrix}0\\2\end{pmatrix}=\begin{pmatrix} 29\\23\end{pmatrix}$$
That is, one can work as usual using Cramer's rule as long as $\det A\not \equiv 0$ modulo what you're working in.


text:
\subsection{Single Patch Integration}

The following test investigates the efficiency of geometry evaluations with respect to the calculation time.
Such operations are needed for the calculation of tangents and the outward normal to the NURBS patch in each quadrature point. The test setting is illustrated in \figref{fig:integration_test_setting}. A unit square, defined by a linear NURBS patch $\be$ is located in the $xy$--plane. Three different collocation points $\pt{x}_s$, $\pt{x}_n$ and $\pt{x}_r$ are chosen, so that the boundary integral on $\be$ gets singular, nearly singular and regular respectively. Thus, the integration is subject to different strategies as described in \ref{sec:integration}. The tolerance for the integration error is chosen as $\err_Q=10^{-9}$. The integration is performed for the discrete single layer $\mat{V}_\be$ and double layer potential $\mat{K}_\be$.

\tikzfig{tikz/integration_test_setting}{1.0}{Unit square NURBS patch $\be$ and the location of the collocation points $\pt{x}$ for the regular, nearly singular and singular integration}{integration_test_setting}{figure10}

\revdel{Table 2 lists the number of required Gauss points for this particular case. Due to the subdivision scheme, accurate nearly singular integration takes approximately six times more quadrature points than the regular. While this factor is almost constant for different orders $p_c$ of the Cauchy data basis function, it is envisaged, that $p_c$ plays a significant role when it comes to singular integration. In the defined test setting, precise singular integration demands up to $20$ times more quadrature points than for the regular case. It should be noted that for $\mat{K}_\be$ on a plane, some terms degenerate to zero and accurate integration is thus not as difficult as in the usual case. The number of required Gauss points stays constant as a consequence and is lower than for $\mat{V}_\be$. Nevertheless, accurate integration in the context of a BEM demands a large number of quadrature points and therefore, many geometry evaluations.}{Removed GP table from this section}
\revcomment{Removed GP table from this section}

Three different types of patches $\be$ are now investigated. They differ in the description of the geometry and that of Cauchy data. The patch is called \emph{superparametric} if the order of the NURBS basis functions for the Cauchy data is kept constant $p_c=1$ and that of the geometry $p_g$ is refined by means of order elevation. For the \emph{isogeometric} patch, Cauchy data and geometry are described by the same NURBS basis functions. As implemented in the BEM formulation presented, a \emph{subparametric} patch is defined by a geometry representation of lowest possible order, while refinement is performed on the Cauchy data description only. In order to obtain comparable runtimes, the integration process is repeated $100$~times.

In \figref{fig:time_super} the integration time for different orders on the superparametric patch $t_{sup}$ is related to that of the unrefined patch $t_{0}$. In the case of superparametric $\be$, the number of Gauss points required stays constant, since the NURBS basis functions for the Cauchy data do not vary. \Figref{fig:time_super} thus depicts the increase of computational effort due to more expensive geometrical evaluations with increasing geometry order $p_g$. In the test case and for $p_g=5$ the calculation time is almost twice that much as for the lowest possible order describing $\be$. The evaluation of the traction fundamental solution $\fund{T}$ for $\mat{K}_\be$ additionally requires the evaluation of the unit outward normal $\vek{n}$. Hence the construction of $\mat{K}_\be$ will benefit slightly more, if geometrical information is evaluated on the lowest geometry order available.

\tikzfig{plots/GP-plane_planestrain_KERNEL_U_and_T_GEOMETRY}{1.0}
{The ratio of integration time on a superparametric and an unrefined patch ($t_{sup}/t_{0}$) for the discrete single layer (left) and double layer (right) operators with regular, nearly singular and singular integration related to the order $p_g$ of geometry description for a fixed number of quadrature points.}{time_super}{figure11}

The presented subparametric formulation makes profit of this in the sense that geometrical evaluations are performed on the original CAD representation. To visualise the performance, the next test case is related to such subparametric patches and hence, the NURBS basis functions for the Cauchy data only are
\revdel{thus}{}
refined. In \figref{fig:time_sub} the speedup factor $t_{iso}/t_{sub}$ compared to an isogeometric formulation, where the geometry is also refined, is shown. For the described planar test case, an order elevation by $2$ provides a speedup in patch integration of approximately $25\%$ for $\mat{V}_\be$ and $35\%$ for $\mat{K}_\be$ due to the additional evaluation of $\vek{n}$.

\tikzfig{plots/GP-plane_planestrain_KERNEL_U_and_T_ALL}{1.0}
{Speedup factor of integration time for the subparametric formulation ($t_{sub}$) compared to the isoparametric BEM ($t_{iso}$) for the discrete single layer (left) and double layer (right) operators with regular, nearly singular and singular integration depending on the order $p_c$ of the Cauchy data.
}{time_sub}{figure12}

config: arxiv


TITLE: Question about theta of $T(n)=4T(n/5)+n$
QUESTION [3 upvotes]: I have this recurrence relation $T(n)=4T(\frac{n}{5})+n$  with the base case $T(x)=1$  when $x\leq5$. I want to solve it and find it's $\theta$. I think i have solved it correctly but I can't get the theta because of this term $\frac{5}{5^{log_{4}n}}$ . Any help?
$T(n)=4(4T(\frac{n}{5^{2}})+\frac{n}{5})+n$
$=4^{2}(4T(\frac{n}{5^{3}})+\frac{n}{5^{2}})+4\frac{n}{5}+n$
$=...$
$=4^{k}T(\frac{n}{5^{k}})+4^{k-1}\frac{n}{5^{k-1}}+...+4\frac{n}{5}+n$
$=...$
$=4^{m}T(\frac{n}{5^{m}})+4^{m-1}\frac{n}{5^{m-1}}+...+4\frac{n}{5}+n$  Assuming $n=4^{m}$
$=4^{m}T(\lceil(\frac{4}{5})^{m}\rceil)+((\frac{4}{5})^{m-1}+...+1)n$
$=n+\frac{1-(\frac{4}{5})^{m}}{1-\frac{4}{5}}n=n+5n-n^{2}\frac{5}{5^{log_{4}n}}$
$=6n-n^{2}\frac{5}{5^{log_{4}n}}$

REPLY [1 votes]: An alternative approach is to prove that $T(n)\leqslant5n$ for every $n$. This holds for every $n\leqslant5$ and, if $T(n/5)\leqslant5(n/5)=n$, then $T(n)\leqslant4n+n=5n$. By induction, the claim holds.
On the other hand, $T(n)\geqslant n$ for every $n\gt5$, hence $T(n)=\Theta(n)$.


TITLE: Does the color of a quark matter in a meson?
QUESTION [6 upvotes]: QCD and confinement specify that hadrons must be color-neutral. My understanding is that this means you can have mesons (quark + antiquark) or baryons with 3 quarks, one of each color: Red+green+blue=neutral.
In a meson, does the color of the quark and antiquark matter? Must a red quark be paired with a red antiquark; or does the color change constantly due to the exchange of gluons which also carry color charg?

REPLY [6 votes]: The color charges are paired (color with anticolor), but there's no gauge invariant meaning to the identification of the color (RGB). And due to QM, the quark states are a superposition over all the colors (and antiquarks over the anticolors). The wikipedia page is pretty clear: http://en.wikipedia.org/wiki/Color_charge. As it notes, you also can't distinguish a color from a certain superposition of the two non-complementary anticolors (e.g., R from a combination of anti-G + anti-B).


TITLE: Is there a way to assign a number to a combination without finding and numbering every combination?
QUESTION [3 upvotes]: Imagine I have 4 letters. Is there some algorithm that produces
"abcd" -> 1
"bacd" -> 2
"bcad" -> 3
... etc
without finding and numbering every single combination? My goal is to get a number from 1 to 52! from a shuffled deck of cards. It's impractical to find and number all 52! combinations, so I need a way that doesn't require that. The order that the numbers appear in doesn't matter, as long as numbers don't repeat and there are no gaps.

REPLY [0 votes]: I may be wrong about this, but as far as I know, there's not a canonical enumeration of the elements of the permutation group $S_{52}$ as $\{\pi_1, \pi_2, \ldots, \pi_{52!} \}$. You may be better off representing the shuffled deck as a product of cycles, and that's easy to do. Not sure what you're doing with this, but it might be useful.
Assuming the cards are numbered 1, 2, ... , 52, you can perform the following process until you exhaust the deck. Card $n_1=1$ now occupies position $n_2$ (which could still be 1, of course). Card $n_2$ then has been displaced to position $n_3$. So  card $n_3$ has been displaced to position $n_4$, and so on. Because there are only 52 positions, you will eventually come to a card which has been displaced to the position originally occupied by card $n_1$. So you have a cycle $(n_1, n_2, \ldots, n_{M_1})$; this means that the card positions in the cycle have been rotated forward to the next position in the list, with an implicit wrap of the last to the first (the card in position $n_{M_1}$ has been displaced into position $n_1=1$). Note that it is completely possible that $M_1=1$, so that the first card is not moved, and that cycle has length 1. It is also possible that you traverse every single position before you arrive at the first position again, in which case the whole deck has been rearranged in a rotation (a single cycle of length 52).
For convenience, let's refine the notation and add a second subscript "$1$" to the elements of the cycle we just created to identify the fact that it is the "first" cycle: now we call the cycle we created above $(n_{1,1}, n_{1,2}, \ldots, n_{1,M_1})$.
If we have exhausted the deck, we are done. The shuffle is represented by a single cycle.
Otherwise, find the first position not yet considered, say position $n_{2,1}$, which will be the first member of our second cycle (hence the subscript "$2$"). As before, continue moving through the deck with the second cycle until you arrive back at position $n_{2,1}$ again, and we will have a second cycle $(n_{2,1}, n_{2,2}, \ldots, n_{2,M_2})$ containing $M_2$ positions. Note that the cycles are disjoint by construction.
And so on.
You eventually exhaust the deck with a finite number $N$ of cycles, each of which has a finite number of positions. These positions partition the deck into cycles by construction. So we can represent the shuffled deck as a product of partitions
$$(n_{1,1}, \ldots, n_{1,M_1})(n_{2,1}, \ldots, n_{2,M_2})\ldots(n_{N,1}, \ldots, n_{N,M_N})$$
where $M_1 + M_2 +  \ldots + M_N = 52$.


TITLE: How to apply the Implicit function Theorem in multi-variable Calculus
QUESTION [1 upvotes]: First of all, I'm sorry for any English mistakes I might make, it's not my first language.
I have some trouble understanding how to apply the implicit function theorem when there are several equations involved (don't know if I'm being entirely clear).
It is fairly straightforward when you have a function, say $F(x,y,z)=0$ and you want $z$ as a function of $x$ and $y$, but I've come across some exercises where there is more than one equation (or "function"?) involved.
I think it will be more clear if I show you an example:
"The three equations
$x^{2}-y\cos (uv)+z^{2}=0$,
$ x^{2}+y^{2}-\sin (uv)+2z^{2}=2$, and
$xy-\sin u\cos v+z=0$
define $x$ ,$y$, and $z$ as functions of $u$ and $v$. Find the partial derivatives $\frac{\partial x}{\partial u}$ and $\frac{\partial x}{\partial v}$ at the point $x=y=1, u=\frac{\pi }{2}, v=0, z=0$.
How would you apply the implicit function theorem here?

REPLY [2 votes]: It's exactly the same as your example with the equation $F(x,y,z)=0$. The difference is that you have to change the number of dimensions.
Let $F:{ \mathbb{R} }^{ 5 }\rightarrow { \mathbb{R} }^{ 3 }$ be:
$$
F(x,y,z,u,v)=({x}^{2}-y\cos {(uv)+{ z }^{ 2 },\quad{ x }^{ 2 }+{ y }^{ 2 }-\sin { (uv) } +2{ z }^{ 2 }-2,\quad xy-\sin { (u)\cos { (v) } +z) }  }
$$
So now, your equation is $F(x,y,z,u,v)=(0,0,0)$.
Then we have to prove that we could put $x$, $y$ and $z$ as functions of $u$ and $v$, which is the same as saying $\exists G(u,v)=(x,y,z)$. This is done using the implicit function theorem, that is composed of three steps:
In the first step we have to see if $F$ is a function of first class. In fact, $F\in { C }^{ \infty  }({ \mathbb{R} }^{ 5 })$ so it is obviously that it satisfies the first condition.
The second step is to see if the point that we are studying is agree with the equation. True again, because $F(1,1,0,\frac { \pi }{ 2 } ,0)=(0,0,0)$.
Finally, we have to see if this is true at the given point:
$$
det\left( \frac { \partial F }{ \partial (x,y,z) }  \right) \neq 0
$$
We know $F$, so we only have to make some operations:
$$
F'(x,y,z,u,v)=\begin{pmatrix} \frac { \partial F }{ \partial (x,y,z) }  &  \frac { \partial F }{ \partial (u,v) }  \end{pmatrix}
$$
$$
\frac { \partial F }{ \partial (x,y,z) } =\begin{pmatrix} 2x & -\cos { (uv) }  & 2z \\ 2x & 2y & 2z \\ y & x & 1 \end{pmatrix}
$$
$$
det\left( \frac { \partial F }{ \partial (x,y,z) } (1,1,0,\frac {\pi}{2},0) \right) =2\neq 0
$$
So, at the end, we can happily say that $\exists G(u,v)=(x,y,z)$, thanks to the implicit function theorem.
Now you want to find the partial derivatives of $x(u,v)$. So, we apply the implicit derivative:
$$
G'(\frac { \pi  }{ 2 } ,0)=-{ \left( \frac { \partial F }{ \partial (x,y,z) } (1,1,0,\frac { \pi  }{ 2 } ,0) \right)  }^{ -1 }\left( \frac { \partial F }{ \partial (u,v) } (1,1,0,\frac { \pi }{ 2 },0)  \right)
$$
$$
G'(\frac { \pi  }{ 2 } ,0)=-{ \begin{pmatrix} 2 & 1 & 0 \\ 2 & 2 & 0 \\ 1 & 1 & 1 \end{pmatrix} }^{ -1 }\begin{pmatrix} 0 & 0 \\ 0 & \frac { -\pi  }{ 2 }  \\ 0 & 0 \end{pmatrix}=\begin{pmatrix} 0 & \frac { \pi  }{ 2 }  \\ 0 & -\pi  \\ 0 & \frac { \pi  }{ 2 }  \end{pmatrix}
$$
$$
G'(\frac { \pi  }{ 2 } ,0)=\begin{pmatrix} \nabla x(\frac { \pi  }{ 2 } ,0) \\ \nabla y(\frac { \pi  }{ 2 } ,0) \\ \nabla z(\frac { \pi  }{ 2 } ,0) \end{pmatrix}\Rightarrow \begin{cases} \frac { \partial x }{ \partial u } (\frac { \pi  }{ 2 } ,0)=0 \\ \frac { \partial x }{ \partial v } (\frac { \pi  }{ 2 } ,0)=\frac { \pi  }{ 2 } \end{cases}
$$
I hope that this can help you. Sorry for my English skills and let me know if there is any error on my explanation.


TITLE: $f(x)$=$\left\lfloor { x }^{ 2 } \right\rfloor -\left\lfloor x \right\rfloor ^{ 2 }$ is discontinuous for all integer values of x except only at x=1
QUESTION [4 upvotes]: How to prove that $f(x)$=$\left\lfloor { x }^{ 2 } \right\rfloor -\left\lfloor x \right\rfloor ^{ 2 }$ is discontinuous for all integer values of x except only at $x=1$ ?
Ya,even I used intuition at the first go taking some trial values and checking.Then I plotted the graph on wolfram alpha.But if you can think of some other rigorous proof for this one,let me know.Thanks!

REPLY [0 votes]: The approach here is to find formula that are equivalent to $f$ locally. The idea being that it is simpler to spot the discontinuity from the locally
equivalent formula.
Note that $\lfloor x \rfloor = 1_{[0,\infty)}(x)-1$ for $|x|<1$. In particular,
for small positive $x$, we have $\lfloor x \rfloor =0$. Also note that
$\lfloor x \rfloor^2 = - \lfloor x \rfloor$ for small $x$.
Consider $f(n+\epsilon)$ for integer $n$ and small $\epsilon$.
If $n=0$, we have $\lfloor \epsilon^2 \rfloor = 0$.
Hence
$f(\epsilon) = -\lfloor \epsilon \rfloor^2 = \lfloor \epsilon \rfloor$ for small $\epsilon$, and so $f$ is discontinuous at $x=0$.
For $n \neq 0$ and sufficiently small $\epsilon$,
we have $\lfloor (n+\epsilon)^2 \rfloor = n^2 +\lfloor n \epsilon + \epsilon^2 \rfloor= n^2 + \lfloor n \epsilon\rfloor$, and
$\lfloor n+\epsilon\rfloor = n + \lfloor \epsilon\rfloor$. Hence
$\lfloor n+\epsilon\rfloor^2 = n^2 + 2n \lfloor \epsilon\rfloor + \lfloor \epsilon\rfloor^2$,
and so
$f(n+\epsilon) = \lfloor n \epsilon\rfloor -2n \lfloor \epsilon\rfloor - \lfloor \epsilon\rfloor^2 = \lfloor n \epsilon\rfloor -(2n-1) \lfloor \epsilon\rfloor$.
If $n<0$ this gives
$f(n+\epsilon) =\lfloor- \epsilon\rfloor +(1-2n) \lfloor \epsilon\rfloor$, from which we see that $f(n) = 0$ and $f(n+\epsilon) =-1$ for small positive $\epsilon$.
If $n>0$, we have $f(n+\epsilon) =\lfloor \epsilon\rfloor +(1-2n) \lfloor \epsilon\rfloor = 2(1-n) \lfloor \epsilon\rfloor$, hence $f$ is continuous
for $n = 1$, otherwise $f(n) = 0$ and $f(n+\epsilon) = -2(n-1)$ for small
negative $\epsilon$.


TITLE: Find the solution of partial differential equation about $x\left( t \right) $ and $t$
QUESTION [2 upvotes]: Let $J$ is a function about $x\left( t \right) $ and $t$, such that
  $$\frac{\partial J}{\partial t}=\frac{1}{4}\left( \frac{\partial J}{\partial x} \right) ^2-x^2-\frac{1}{2}x^4,\qquad \text{where}\, J\left[ x\left( 1 \right) ,1 \right] =0$$
  Find $J\left[ x\left( t \right) ,t \right]$.

When I learn optimal control theory, I saw this problem, but the author haven't shown me the solution. I have no ideal, too.

REPLY [2 votes]: $$\frac{\partial J}{\partial t}=\frac{1}{4}\left( \frac{\partial J}{\partial x} \right) ^2-x^2-\frac{1}{2}x^4 \tag 1$$
$$\frac{\partial^2 J}{\partial t\partial x}=\frac{1}{2} \frac{\partial J}{\partial x}\frac{\partial^2 J}{\partial x^2} -2x-2x^3$$
Change of function :
$$\frac{\partial J}{\partial x}=u(x,t)\quad\to\quad \frac{\partial u}{\partial t} -\frac{1}{2} u\frac{\partial u}{\partial x}= -2x-2x^3 \tag 2$$
Characteristic system of equations :
$$\frac{dt}{1}=\frac{dx}{-\frac{1}{2} u}=\frac{du}{-2x-2x^3}$$
First family of characteristic curves, from $\quad -2\frac{dx}{ u}=\frac{du}{-2x-2x^3} :$
$$2udu-(8x+8x^3)dx=0 \quad\to\quad u^2-4x^2-2x^4=c_1$$
Second family of characteristic curves, from $\frac{dt}{1}=\frac{dx}{-\frac{1}{2} u} :$
$$dx+\frac{u}{2}dt=0=dx+\frac{\sqrt{c_1+4x^2+2x^4}}{2}dt$$
$$dt+\frac{2dx}{\sqrt{c_1+4x^2+2x^4}}=0 \quad\to\quad t+\int\frac{2dx}{\sqrt{c_1+4x^2+2x^4}}=c_2 $$
The integral can be expressed on closed form. The formula involves a special function, namely the Elliptic Integral of the first kind :
http://www.wolframalpha.com/input/?i=integrate+2%2Fsqrt(C%2B4+x%5E2%2B2+x%5E4)&x=0&y=0

In interest of space and in order to make easier the writing, this big formula will be symbolized as :
$$\int\frac{2dx}{\sqrt{c_1+4x^2+2x^4}}=\Psi\left(c_1,x\right)$$
Where $\Psi$ is the above known function. Thus the second family of characteristic curves is :
$$ t+\Psi\left(c_1,x\right)=c_2$$
The general solution of the PDE $(2)$ is expressed on the form of the implicit equation :
$$F\left(\left(u^2-4x^2-2x^4\right) \:,\: \left(t+\Psi\left(u^2-4x^2-2x^4\:,\:x\right)\right) \right)=0$$
where $F$ is any differentiable function of two variables.
The function $F$ might be determined according to a boundary condition which has to be derived from a given boundary condition of Eq.$(1)$. Nevertheless it appears doubtful to find a closed form for $F$ considering the complicated function $\Psi$.
Supposing that the function $F$ be determined, which is optimistic, a more difficult step comes after, to go from $u(x,t)$ to $J(x,y)$, which suppose possible to find a closed form for $\int u(x,t)dx$.


TITLE: Can't understand step in posterior mean derivation
QUESTION [1 upvotes]: I was studying the Conjugate Priors section of Berkeley's Stat260: Bayesian Modeling and Inference where, when looking at Poisson Gamma conjugacy, the following is given (page 3)

The posterior distribution has density
  $$
P(\theta|x, \alpha)\propto \theta^{\sum_{j} x_{j} + \alpha_{1} - 1}e^{-(\alpha_{2}+n)\theta}
$$
  so that
  $$
E[\theta|x, \alpha] = \color{#C00}{\frac{\sum_{j}x_{j}+\alpha_{1}}{n+\alpha_{2}} = \kappa\frac{\alpha_{1}}{\alpha_{2}} + (1-\kappa)\frac{\sum_{j}x_{j}}{n}}
$$
  where $\kappa = \alpha_{1}/(\alpha_{2}+n)$.

Embarrassingly, I can't understand the equality I emphasized in red - despite my efforts expanding the equation with the value of $\kappa$ to $$\frac{\alpha^{2}}{\beta(\beta+n)} + \frac{\sum_{j}x_{j}}{n}-\frac{\alpha\sum_{j}x_{j}}{n(\beta+n)}$$
I cannot see how the equality holds. Can someone please help me with this?

REPLY [1 votes]: I think there is a typo in your quoted definition of $\kappa$. If you redefine it to be $\kappa\equiv\beta/(\beta+n)$, then everything makes sense:
$$\frac{\sum_{i}x_{i}+\alpha}{n+\beta}=\frac{\sum_{i}x_{i}}{n+\beta}+\frac{\alpha}{n+\beta} = \frac{n}{n+\beta}\cdot\frac{\sum_{i}x_{i}}{n} + \frac{\alpha}{\beta}\cdot\frac{\beta}{n+\beta}$$
$$= (1-\kappa)\cdot\frac{\sum_{i}x_{i}}{n} + \kappa\frac{\alpha}{\beta}$$


TITLE: How do i remove imaginary numbers from denominators?
QUESTION [1 upvotes]: I am calculating towards getting the value of an unknown variable B. I got stuck when i came to the point where i have B = 1 divided on a complex number. I guess its the correct way to show this as a whole complex number and not as a dividation
$$ 1=B(0.25-0.25i) $$
$$B=\frac{1}{0.25-0.25i} $$
How can i easily get further on the part of putting B on the form B = 4+5i - numbers just an example.
(feel free to edit post if i write mathematical names wrong)

REPLY [4 votes]: When you have an imaginary number in the denominator, multiply the numerator and denominator by the conjugate of the denominator.
For example, given $a +bi, \,$ its conjugate is $a-bi$.
In your case the conjugate of the denominator is $0.25 + 0.25i$. So $$\begin{align} B=\frac{1}{0.25-0.25i}& =\frac{1}{0.25-0.25i}\cdot\dfrac{0.25 + 0.25i}{0.25 + 0.25i}\\ \\ & = \dfrac{0.25 + 0.25i}{\frac 1{16} + \frac 1{16}} \\ \\ & = \dfrac{\frac 14(1+i)}{\frac 1{8}} \\ \\ &= 2(1+i)\end{align}$$


TITLE: Question on Segre embedding
QUESTION [5 upvotes]: This is in fact a problem in GTM52 of Hartshone.

Define $\psi : \mathbb{P}^{n}\times \mathbb{P}^{m}\longrightarrow \mathbb{P}^{N}$ where $N=rs+r+s$ by $(a_0,...,a_r)\times (b_0,...,b_s)=(...a_ib_j...)$
  Show that $Im\psi$ is a subvariety of $\mathbb{P}^N$.

Hartshone gave a hint as follow :

Let the homogeneous coordinate of $\mathbb{P}^N$ be $z_{ij}, i=0,..r; j=0,...,s$ and let $\mathfrak{a}$ be the kernel of the homomorphism $k[{z_{ij}}]\rightarrow k[x_0,...,x_r,y_0,...,y_s]$ which sends $z_{ij}$ to $x_iy_j$. Then show that $Im\psi=Z(\mathfrak{a})$

My idea is to prove that : $I(Im\psi)\subseteq I(Z(\mathfrak{a}))$ and $I(Z(\mathfrak{a}))\subseteq I(Im\psi)$ but this lead to a calculation of $\mathfrak{a}$.
So, how can I use the hint of Hartshone to solve it ? Please give me some hint.
Thank for reading my question !

REPLY [3 votes]: Recall the definition of an algebraic subset in projective space, it is the zero locus of some set of homgeneous polynomials. In this case, these polynomials are $z_{ab} z_{cd} - z_{ad} z_{cb}$ ("exchange the first coordinates") and $z_{ab} z_{cd} - z_{cb} z_{ad}$ ("exchange the second coordinates") for $0 \leq a,c \leq r$ and $0 \leq b,d \leq s$. Since we have $x_a y_b x_c x_d = x_a y_d x_c x_b$ and $x_a y_b x_c x_d = x_c y_b x_a x_d$, the image of $\psi$ lies in the zero locus of the polynomials. Conversely, assume that $p=[p_{ij}] \in \mathbb{P}^N$ lies in the zero locus, i.e. we have $p_{ab} p_{cd} = p_{ad} p_{cb}$ and $p_{ab} p_{cd} = p_{cb} p_{ad}$. Some coordinate is $\neq 0$, say w.l.o.g. $p_{00}=1$. Now try to deduce $p_{ab} = p_{a0} p_{0b}$ and $p_{0b}=p_{b0}$, and infer that $p$ lies in the image.
One can also check that $\psi$ is an isomorphism onto its image; in particular the image is irreducible, i.e. a variety.


TITLE: Meaning of notation with two letters inside of parentheses [binomial coefficient]
QUESTION [0 upvotes]: What does the notation in the red box mean?
$$\Huge e^{\displaystyle \large \sum_{k=0}^n \bbox[2px,border:2px solid red]{\color{black}
{ {n \choose k}}}~\omega^k}$$

REPLY [1 votes]: Binomial coefficients. Relevant here is that:
$\begin{align}
  \sum_{0 \le k \le n} \binom{n}{k} a^k b^{n - k}
    = (a + b)^n
\end{align}$


TITLE: Leibniz rule X Direct integral computation
QUESTION [1 upvotes]: This question arose on a very complicated context, but it is very simple:
I have for $0<a<1$ the integral $\int_0^t (t-x)^{a-1} dx$ and 'd like to derive on $t$. The imediate result is $t^{a-1} $, which is a positive function for $t$ positive.
Suppose that I'd like to use Leibniz rule, so $\dfrac{\partial}{\partial t} \displaystyle\int_0^t (t-x)^{a-1} dx=(t-t)^{a-1}+ \displaystyle\int_0^t \dfrac{\partial}{\partial t}(t-x)^{a-1} dx=\displaystyle\int_0^t (a-1) (t-x)^{a-2} dx$
But this is a positive function? Because $(a-1)<0$ and $(t-x)^{a-2} \geq0$, so the integrandum is everywhere nonpositive...!
Thank you so much

REPLY [1 votes]: The problem lies in the fact that the function $g(x) = (t - x)^{a - 1}$ is not defined at $x = t$. You are treating it as if $g(t) = (t - t)^{a - 1}  = 0$, but this does not actually make sense; the graph of $g$ has vertical asymptote as $x$ approaches $t$ from the left.
If you treat your problem carefully by instead writing $\int_0^{t - \delta} (t - x)^{a - 1} \, dx$, you can get the proper calculation.


TITLE: Found a trick to show that $f$ is linear (?)
QUESTION [1 upvotes]: Let $f: \mathbb R^3 \longrightarrow R^3$ be given by
$$f:\left(\begin{array}{c}{x_{1}} \\ {x_{2}} \\ {x_{3}}\end{array}\right) \longmapsto \left(\begin{array}{c}{x_{1}+x_{2}} \\ {x_{2}} \\ {x_{3}-x_{1}}\end{array}\right)$$
Prove that $f$ is linear.
my answer
I could use
\begin{array}{l}{f(\mathbf{u}+\mathbf{v})=f(\mathbf{u})+f(\mathbf{v})} \\ {f(c \mathbf{u})=c f(\mathbf{u})}\end{array}
to prove that $f $ is linear. Put I have found a trick to do this without much effort.
Claim: $f$ is linear if the coordinates of $f(\bf u)$ are linear.
In this case $x_1+x_2$, $x_2$ and $x_3-x_1$ are linear, therefore $f$ is linear.
Does this theorem and the belonging proof exist?

REPLY [1 votes]: This is a proof if you know those three maps are linear, and that a sum of linear maps is linear. But the fact that this exercise was assigned suggests that you are meant to just check the axioms directly, which is only a couple lines anyway. For example,
$$f\left(c\begin{pmatrix}x_1 \\ x_2 \\ x_3 \end{pmatrix}\right)=f\begin{pmatrix}cx_1 \\ cx_2 \\ cx_3 \end{pmatrix}=\begin{pmatrix}cx_1+cx_2 \\ cx_2 \\ cx_3-cx_1 \end{pmatrix}=\begin{pmatrix}c(x_1+x_2) \\ cx_2 \\ c(x_3-x_1) \end{pmatrix}=c\begin{pmatrix}x_1+x_2 \\ x_2 \\ x_3-x_1 \end{pmatrix}=cf\begin{pmatrix}x_1 \\ x_2 \\ x_3 \end{pmatrix}.$$

REPLY [1 votes]: You can write your $f$ in components as $f=(f_1,f_2,f_3)$. Since each of the components is linear you have:
$$f(u+v) = (f_1(u+v),f_2(u+v),f_3(u+v)) $$
$$= (f_1(u)+f_1(v),f_2(u)+f_2(v),f_3(u)+f_3(v))$$
$$ = (f_1(u), f_2(u), f_3(u)) + (f_1(v), f_2(v), f_3(v)) = f(u)+f(v)$$
similarly you can show $f(cx) = cf(x)$.
This means your $f$ is indeed linear if each of the components is linear.


TITLE: Show that $\operatorname{sgn}(\sigma^n)=(-1)^n$ for specific permutation in $S_7$.
QUESTION [0 upvotes]: Let $\sigma = \begin{pmatrix} 1 &2&3&4&5&6&7\\ 4&5&7&2&1&3&6 \end{pmatrix}\in S_7$.
Show that $\operatorname{sgn}(\sigma^n)=(-1)^n$.

So I know that $\operatorname{sgn}(\sigma)=\operatorname{sgn}((4,2,5,1))\operatorname{sgn}((7,6,3))=(-1)^3(-1)^2=-1$, but I'm not sure how to continue. Any help is appreciated

REPLY [2 votes]: Now you use the fact that the sign function is a group homomorphism. So, $\operatorname{sgn}(\sigma^n)=\operatorname{sgn}(\sigma)^n$.


TITLE: What is the probability that the second blue ball is drawn on the eleventh draw?
QUESTION [1 upvotes]: An urn contains $10$ white, $9$ black, $8$ red and $3$ blue balls.  Balls are drawn one by one at random from the urn until $2$ blue balls are obtained. Find the probability of drawing the second blue balls on the $11$th draw.
Answer is $19/406$
Acc. To me it should be like a total of $11$ balls are drawn, so total no. of cases is $30C11$ and for blue ball it should be $3C1$ and lastly $2C1$
$27C9 \times 3C1 \times 2C1$
.....
$$P(n)= \frac{27C9 \times 3C1 \times 2C1}{30C11}$$

REPLY [0 votes]: Your answer calculated the probability of drawing $11$ balls with $2$ of them blue. It did not account for one of the blue balls having to be in the $11th$ position. This reduces the numerator by a factor of $11$.
$$P(n)= \frac{27C9 \times 3C1 \times 2C1}{30C11 \times 11}$$


TITLE: Probability of losing at least K consecutive games after N games
QUESTION [0 upvotes]: Player A play 100 coinflip games,
The probability of Head/Tails is exact 50%
What is the probability that A loses at least 7 games consecutive out of 100 games?
Extended :
What is the probability that A loses at least K consecutive games when he/she plays N games? (k < N)
My though is :
The probability of losing 7 consecutive games out of 100 games (94 cases : 1-7, 2-8, 3-9,.....) is: $94(\frac{1}{2})^{100}$
Do the same thing with 8 consecutive games and above (up to 100) : $93(\frac{1}{2})^{100}$, $92(\frac{1}{2})^{100}$,....., $(\frac {1} {2})^{100}$
The probability of losing at least 7 games consecutive out of 100 games is :
$$\sum_{x=6}^{99} (100-x) \frac{1}{2}^{100}$$
but I think it won't be true when increase to K consecutive games out of 1000 games and above.

REPLY [0 votes]: This is a binomial probability question. For clarity, let's say that A needs to lose 7 games. Then the probability is actually $\binom{100}{7}(\frac12)^7(\frac12)^{93}$ because there are $\binom{100}{7}$ ways you could re-arrange the ways that A loses those seven games amongst the 100 that A plays. So if she needs to lose at least 7, take the contrapositive case
and go 1-p(A losing less than 7), then you'll just have to take the binomial probability for A loses one game, A loses 2 games all the way up to A loses 6 games.
However, for 100 coin flips, since the number of trials is so large and numbers like $\frac12^{100}$ so small you can take the normal distribution approximation, which I assume would be suited to the follow up question of when you're looking for $P(X≤K)$ where K≤N. What you need to do is to find the mean(given by $\mu$), which in the case of binomial, is equal to the probability of success which is half in this case. Then you need to find the $\sigma$, which is given by the formula $\sigma=\sqrt{npq}$ where n=number of times the experiment is conducted, p is the probability of success and q is the probability of failure. So for a coin tossed N times, $\sigma=\frac{\sqrt{N}}{2}$. Then you convert K(the number of losses you want) into a z-score, using the formula $z=\frac{K-\mu}{\sigma}$. So then your z-score becomes $z=\frac{K-\frac12}{\frac{\sqrt{N}}{2}}$ which simplfies down to $z=\frac{2K-1}{\sqrt{N}}$. Then you can google the z-scores table and match your z-score to the probability on the table or you can evaluate the integral $\int\limits_{-\infty}^{z}\frac{1}{\sqrt{2\pi}}e^{-\frac12x^2}dx$ which is the standard normal distribution curve.


TITLE: How does Infrared Relate to heat?
QUESTION [30 upvotes]: I never understood the relationship between Infrared and Heat. Is IR emitted when heat is generated, is heat generated when IR is made, and how do the two relate?

REPLY [6 votes]: The easiest answer is that below 3,000 Kelvin in temperature, heat radiates EM (often referred to as light by physicists although it is all EM not just visible light) in the infrared. Because most heat generates light in the infrared, scientists often refer to infrared light as heat. This is a generalized term or a convention.
Technically heat energy and light are different things, but heat energy can be measured by its EM radiation. Given enough temperature, heat can produce visible light as in our sun as well as ultraviolet as in our sun. Also, although heat energy and light are different things, heat energy produces radiation in the EM spectrum and most heat produced on earth produces light in the infrared.


text:
\section{Calculation of $\alpha_{N,m}^\omega$}\label{alphasec}

In this section we continue the analysis of Problem \ref{optprob} in the extended version \eqref{opt_with_omega}, i.e., including an additional terminal weight. Although this is an optimization problem of much lower complexity than the original MPC optimization problem, still, it is in general nonlinear. However, it becomes a linear program if $\beta(r,n)$ (and thus $B_k(r)$ from \eqref{3:eq:definition B_N}) is linear in $r$.
\begin{lemma}\label{linlemma}
	Let $\beta(r, t)$ be linear in its first argument. Then Problem \ref{optprob} yields the same optimal value $\alpha_{N,m}^\omega$ as
	\begin{equation}\label{minexplin}
		\min_{\lambda_0, \lambda_1, \ldots, \lambda_{N-1}, \nu} \sum_{n = 0}^{N - 2} \lambda_n + \omega \lambda_{N-1} - \nu
	\end{equation}
	subject to the (now linear) constraints \eqref{4:prop:necessary conditions:eq1}, \eqref{4:prop:necessary conditions:eq2} with $B_N(k)$ from \eqref{3:eq:definition B_N_omega} and
	\begin{equation}\label{posval_lin}
		\lambda_0, \ldots, \lambda_{N - 1}, \nu \geq 0, \quad \sum_{n = 0}^{m - 1} \lambda_n = 1.
	\end{equation}
\end{lemma}
For a proof we refer to \cite[Remark 4.3 and Lemma 4.6]{G07}, observing that this proof is easily extended to $\omega \geq 1$.
\begin{proposition}\label{Alpha_Formula_LP_Lemma}
	Let $\beta(\cdot,\cdot)$ be linear in its first argument and define $\gamma_k:=B_k(r)/r$. Then the optimal value of Problem \ref{optprob} equals the optimal value of the optimization problem
	\begin{equation*}
		\min_{\lambda}\quad 1 - (\gamma_{m+1} - \omega)\, \lambda_{N-1}
	\end{equation*}
	subject to $\lambda = (\lambda_1,\ldots,\lambda_{N-1})^T \geq 0$ componentwise and the linear constraints
	\begin{eqnarray}
		\gamma_N \sum\limits_{n=1}^{m-1} \lambda_n + \sum_{n=m}^{N-2} \lambda_n + \rlap{$\omega$}\phantom{\gamma_{m+1}} \lambda_{N-1} & \leq & \gamma_N -1 \label{Alpha_Formula_LP_Lemma_Restriction1} \\
		\sum_{n=j}^{N-2} \lambda_n - \gamma_{N-j\phantom{+m}}\, \lambda_j + \rlap{$\omega$}\phantom{\gamma_{m+1}} \lambda_{N-1} & \leq & 0 \qquad\qquad(j=\phantom{m} 1,\ldots,N-2) \label{Alpha_Formula_LP_Lemma_Restriction2} \\
		\sum_{n=j}^{N-2} \lambda_n - \gamma_{N-j+m}\, \lambda_j + \gamma_{m+1} \lambda_{N-1} & \leq & 0 \qquad\qquad (j=\phantom{1} m,\ldots,N-2). \label{Alpha_Formula_LP_Lemma_Restriction3}
	\end{eqnarray}
\end{proposition}
\begin{proof}
	We proceed from the linear optimization problem stated in Lemma \ref{linlemma} and show that Inequality \eqref{4:prop:necessary conditions:eq2}, $j=N-m-1$, is active in the optimum. To this end, we assume the opposite and deduce a contradiction. $\lambda_{N-1}>0$ allows -- due to the continuity of $B_{m+1}(\lambda_{N-1})$ with respect to $\lambda_{N-1}$ -- for reducing this variable without violating Inequality \eqref{4:prop:necessary conditions:eq2}, $j=N-m-1$. As a consequence the objective function decreases strictly whereas all other constraints remain valid. Hence, $\lambda_{N-1}=0$ holds. Since $\lambda_{N-2} \leq B_{m+2}(\lambda_{N-2})$ Inequalities \eqref{4:prop:necessary conditions:eq2}, $j=N-m-2$, and \eqref{4:prop:necessary conditions:eq1}, $k=N-2$, hold trivially. Analogously to $\lambda_{N-1}>0$ we show $\lambda_{N-2}=0$. Iterative application of this observation provides $\lambda_m=\ldots,\lambda_{N-1}=0$. But then the right hand side of \eqref{4:prop:necessary conditions:eq2}, $j=N-m-1$, is equal to zero which -- in combination with $\nu \geq 0$ -- leads to the claimed contradiction.

	This enables us to treat Inequality \eqref{4:prop:necessary conditions:eq2}, $j=N-m-1$, as an equality constraint. In conjunction with the non-negativity conditions imposed on $\lambda_m,\ldots,\lambda_{N-1}$ this ensures $\nu \geq 0$. Moreover, $\lambda_0 \geq 0$ is satisfied for all feasible points due to Inequality \eqref{4:prop:necessary conditions:eq1}, $k=0$, and the linearity of $B_N$. Next, we utilize Equalities \eqref{posval_lin} and \eqref{4:prop:necessary conditions:eq2}, $j=N-m-1$, in order to eliminate $\nu$ and $\lambda_0$ from the considered optimization problem. Using these equalities and the the definition of $\gamma_{m+1}$ converts the objective function from Lemma \ref{Alpha_Formula_LP_Lemma} into the desired form. Furthermore, Equality \eqref{posval_lin} provides the equivalence of Inequalities \eqref{4:prop:necessary conditions:eq1}, $k=0$, and \eqref{Alpha_Formula_LP_Lemma_Restriction1}. Taking Equality \eqref{4:prop:necessary conditions:eq2}, $j=N-m-1$, into account yields
	\begin{equation*}
		\sum_{n=m+j}^{N-2} \lambda_n + \gamma_{m+1} \lambda_{N-1} - \gamma_{N-j}\lambda_{m+j} \leq 0
	\end{equation*}
	for \eqref{4:prop:necessary conditions:eq2}, $j=0,\ldots,N-m-2$. Shifting the control variable $j$ shows the equivalence to \eqref{Alpha_Formula_LP_Lemma_Restriction3}, $j=m,\ldots,N-2$. Paraphrasing \eqref{4:prop:necessary conditions:eq1} provides \eqref{Alpha_Formula_LP_Lemma_Restriction2} for $k=1,\ldots,N-2$.
\end{proof}

Before we proceed, we formulate Problem \ref{Alpha_Formula_Relaxed_Problem} by dropping Inequalities \eqref{Alpha_Formula_LP_Lemma_Restriction2}, $j=m,\ldots,N-2$. The solution of this relaxed (optimization) problem paves the way for dealing with Problem \ref{optprob}.
\begin{problem}\label{Alpha_Formula_Relaxed_Problem}
	Minimize $1 - (\gamma_{m+1} - \omega)\, \lambda_{N-1}$ subject to $\lambda = (\lambda_1,\ldots,\lambda_{N-1})^T \geq 0$ componentwise and $A \lambda \leq \bar{b}$, where
	\begin{equation*}
		A:=\left( \begin{array} {cccccc}
			a_1    & a_2    & \dots  & a_{N-2} & \omega  \\
			d_1    & 1      & \dots  & 1       & b_1     \\
			0      & d_2    & \ddots & \vdots  & \vdots  \\
			\vdots & \ddots & \ddots & 1       & b_{N-3} \\
			0      & \dots  & 0      & d_{N-2} & b_{N-2} \\
		\end{array} \right) \quad\mbox{and}\quad \bar{b}:=\left( \begin{array}{c}
			\gamma_{N} - 1 \\
			0 \\
			\vdots \\
			0 \\
			0 \\
		\end{array} \right)
	\end{equation*}
	with
	{\begin{equation*}
		a_j = \left\{ \begin{array}{cl}
			\gamma_N & \mbox{for $j<m$} \\
			1 & \mbox{otherwise}
		\end{array} \right. \quad
		b_j = \left\{ \begin{array}{cl}
			\omega & \mbox{for $j<m$} \\
			\gamma_{m+1} & \mbox{otherwise}
		\end{array} \right. \quad
		d_j = \left\{ \begin{array}{cl}
			1- \gamma_{N-j} & \mbox{for $j<m$} \\
			1- \gamma_{N-j+m} & \mbox{otherwise}
		\end{array} \right.
	\end{equation*}}
\end{problem}
\begin{theorem}\label{alpha_formula_thm}
	Let $\beta(\cdot,\cdot)$ be linear in its first argument and satisfy \eqref{3:eq:submultiplicativity}. Then the optimal value ${\alpha} = {\alpha}_{N,m}^\omega$ of Problem \ref{optprob} for given optimization horizon $N$, control horizon $m$, and weight $\omega$ on the final term satisfies ${\alpha}_{N,m}^\omega=1$ if and only if $\omega \geq \gamma_{m+1}$. Otherwise, we get
	{\begin{equation}\label{alpha_formula}
		{\alpha}_{N,m}^\omega =	1 - \frac {(\gamma_{m+1}-\omega) \prod\limits_{i=m+2}^N (\gamma_i - 1) \prod\limits_{i=N-m+1}^{N} (\gamma_i - 1)} {\left(\prod\limits_{i=m+1}^N \gamma_{i} - (\gamma_{m+1}-\omega) \prod\limits_{i=m+2}^{N} (\gamma_{i}-1)\right) \left( \prod\limits_{i=N-m+1}^N \gamma_{i} - \prod\limits_{i=N-m+1}^N (\gamma_{i}-1) \right)}.
	\end{equation}}
\end{theorem}
\begin{proof}
	We have shown that the linear optimization problem stated in Proposition \ref{Alpha_Formula_LP_Lemma} yields the same optimal value as Problem \ref{optprob} for $\mathcal{KL}_0$-functions which are linear in their first argument. Technically, this is posed as a minimization problem. Taking the restriction $\lambda_{N-1} \geq 0$ into account leads to the determinable question whether the coefficient of $\lambda_{N-1}$ is positive or not. As a consequence, the aim is either minimizing or maximizing $\lambda_{N-1}$. In the first case, i.e., $\gamma_{m+1} - \omega \leq 0$, choosing $\lambda_1=\ldots=\lambda_{N-1} = 0$ solves the considered task and provides the optimal value $\alpha_{N,m}^\omega = 1$.

	In order to prove the assertion we solve the relaxed Problem \ref{Alpha_Formula_Relaxed_Problem} and show that its optimum is also feasible for Problem \ref{optprob}. Suppose that $\lambda_{m+1} - \omega > 0$ holds, then Lemma \ref{appendix_lgs} shows the optimum's crucial characteristic to satisfy the linear system of equations $A \lambda = \bar{b}$ with $A$ and $\bar{b}$ from Problem \ref{Alpha_Formula_Relaxed_Problem}. We proceed by deriving formulae for $\lambda_{N-2},\ldots,\lambda_1$ depending (only) on $\lambda_{N-1}$. These allow for an explicit calculation of $\lambda_{N-1}$ from $A_1 \lambda = \bar{b}_1$. To this end, define $\delta_i :=-d_i > 0$ and begin with showing the equality
	\begin{equation}\label{Alpha_Formula_Representation_Lambda_m_bis_N-2}
		\lambda_{N-1-i} = \left( \prod_{j=1}^{i-1} ( 1 + \delta_{N-1-j} )/\delta_{N-1-j} \right) \gamma_{m+1} \lambda_{N-1} / \delta_{N-1-i}
	\end{equation}
	for $i=1,\ldots,N-1-m$ by induction which is obvious for $i=1$. Thus, we continue with the induction step using Lemma \ref{appendix_technical_lemma:1}:
	{\small\begin{eqnarray*}
		\lambda_{N-1-i} & = & \frac {1}{\delta_{N-1-i}} \left[ \gamma_{m+1} \lambda_{N-1} + \sum_{k=1}^{i-1} \lambda_{N-1-k} \right] \stackrel{I.A.}{=} \frac {\gamma_{m+1} \lambda_{N-1}}{\delta_{N-1-i}} \left[ 1 + \sum_{k=1}^{i-1} \frac {\prod_{j=1}^{k-1} ( 1 + \delta_{N-1-j} )} {\prod_{j=1}^k \delta_{N-1-j}} \right] \\
		& = & \frac {\gamma_{m+1} \lambda_{N-1}} {\prod_{j=1}^i \delta_{N-1-j}} \sum_{k=0}^{i-1} \left( \prod_{j=1}^{k-1} (1+\delta_{N-1-j}) \prod_{j=k+1}^{i-1} \delta_{N-1-j} \right)
		\stackrel{\eqref{appendix_technical_lemma:1_eq1}} {=} \frac {\gamma_{m+1} \prod_{j=1}^{i-1} ( 1 + \delta_{N-1-j} )} {\prod_{j=1}^i \delta_{N-1-j}} \lambda_{N-1}.
	\end{eqnarray*}}
	Similarly, in consideration of \eqref{appendix_technical_lemma:1_eq1} applied with $N-1 = m$ one obtains the representation $\lambda_{m-i} = \left( \prod_{j=1}^{i-1} (1+\delta_{m-j}) / \delta_{m-j} \right) (\omega \lambda_{N-1} + \sum_{j=m}^{N-2} \lambda_j) / \delta_{m-i}$ for $i=1,\ldots,m-1$. We consider the left hand side of $A_1 \lambda = \bar{b}_1$:
	\begin{eqnarray*}
		& & \gamma_N \sum_{i=1}^{m-1} \lambda_i + \sum_{i=m}^{N-2} \lambda_i + \omega \lambda_{N-1} = \gamma_N \sum_{i=1}^{m-1} \lambda_{m-i} + \sum_{i=1}^{N-1-m} \lambda_{N-1-i} + \omega \lambda_{N-1} \\
		& = & \left[ \gamma_N \left( \omega + \gamma_{m+1} \sum_{i=1}^{N-1-m} \frac {\prod_{j=1}^{i-1} (1+\delta_{N-1-j})}{\prod_{j=1}^i \delta_{N-1-j}} \right) \sum_{i=1}^{m-1} \frac {\prod_{j=1}^{i-1} (1+\delta_{m-j})}{\prod_{j=1}^{i} \delta_{m-j}} \right] \lambda_{N-1} \\
			& + & \left[ \gamma_{m+1} \sum_{i=1}^{N-1-m} \frac {\prod_{j=1}^{i-1} (1+\delta_{N-1-j})}{\prod_{j=1}^i \delta_{N-1-j}} + \omega \right] \lambda_{N-1} \\
		& = & \left[ \gamma_N \left( \omega + \gamma_{m+1} \sum_{i=1}^{N-1-m} \frac {\prod_{j=1}^{i-1} \gamma_{m+1+j}}{\prod_{j=1}^i (\gamma_{m+1+j}-1)} \right) \sum_{i=1}^{m-1} \frac {\prod_{j=1}^{i-1} \gamma_{N-m+j}} {\prod_{j=1}^{i} (\gamma_{N-m+j}-1)} \right] \lambda_{N-1} \\
			& + & \left[ \gamma_{m+1} \sum_{i=1}^{N-1-m} \frac {\prod_{j=1}^{i-1} \gamma_{m+1+j}}{\prod_{j=1}^i (\gamma_{m+1+j} - 1)} + \omega \right] \lambda_{N-1}
	\end{eqnarray*}
	The common denominator of this expression is $\prod_{i=1}^{N-1-m} (\gamma_{m+1+i} - 1) \prod_{i=1}^{m-1} (\gamma_{N-m+i} - 1)$ which is equal to $\prod_{i=m+2}^N (\gamma_i - 1) \prod_{i=N+1-m}^{N-1} (\gamma_i - 1)$. Thus, the nominator equals $\lambda_{N-1}$ with the coefficient
	{\footnotesize\begin{eqnarray*}
	& & \Big( \omega \prod_{i=m+2}^N (\gamma_i - 1) + \gamma_{m+1} \underbrace{\sum_{i=m+2}^N \prod_{j=m+2}^{i-1} \gamma_j \prod_{j=i+1}^N (\gamma_j - 1)}_{\stackrel {\eqref{appendix_technical_corollary:1_eq1}} = \prod_{i=m+2}^N \gamma_i - \prod_{i=m+2}^N (\gamma_i - 1)} \Big) \Big( \gamma_N \underbrace{\sum_{i=1}^{m-1} \left( \prod_{j=1}^{i-1} \gamma_{N-m+j} \prod_{j=i+1}^{m-1} (\gamma_{N-m+j} - 1) \right)}_{\stackrel {\eqref{appendix_technical_lemma:1_eq1}} = \prod_{j=N-m+1}^{N-1} \gamma_j - \prod_{j=N-m+1}^{N-1} (\gamma_j - 1)} + \prod_{i=N-m+1}^{N-1} (\gamma_i - 1) \Big)
	\end{eqnarray*}}
	where we used \eqref{appendix_technical_lemma:1_eq1} from Lemma \ref{appendix_technical_lemma:1} with $\delta_{N-1-j} = \gamma_{N-m+j} - 1$. Hence, taking the coefficient $(\gamma_{m+1} - \omega)$ of $\lambda_{N-1}$ in the objective function and $\bar{b}_1 = \gamma_N - 1$ into account, we obtain formula \eqref{alpha_formula} as the optimal value of Problem \ref{Alpha_Formula_Relaxed_Problem}.

	However, the assertion claims this to be the optimal value for Problem \ref{optprob} as well. In order to prove this it suffices to show that the optimum of Problem \ref{Alpha_Formula_Relaxed_Problem} satisfies the Inequalities \eqref{Alpha_Formula_LP_Lemma_Restriction2}, $j=m\ldots,N-2$. As a consequence, it solves the optimization problem stated in Proposition \ref{Alpha_Formula_LP_Lemma} which is equivalent to Problem \ref{optprob}. As a byproduct, this covers the necessity of the previously considered condition $\gamma_{m+1}-\omega \leq 0$ in order to obtain $\alpha_{N,m}^\omega = 1$.

	We perform a pairwise comparison of Inequality \eqref{Alpha_Formula_LP_Lemma_Restriction3} and \eqref{Alpha_Formula_LP_Lemma_Restriction2} for $j \in \{m,\ldots,N-2\}$ in order to show that the Inequalities \eqref{Alpha_Formula_LP_Lemma_Restriction2}, $j=m,\ldots,N-2$ are dispensable. To this end, it suffices to show
	\begin{equation}\label{Alpha_Formula_Inequality_Lemma_Proof1}
		(\gamma_{m+1}-\omega) \lambda_{N-1} \geq (\gamma_{N-j+m} - \gamma_{N-j}) \lambda_j \qquad j=m,\ldots,N-2.
	\end{equation}
	Equation \eqref{Alpha_Formula_Representation_Lambda_m_bis_N-2} characterizes the components $\lambda_j$, $j=m,\ldots,N-2$, in the optimum of Problem \ref{Alpha_Formula_Relaxed_Problem} by means of the equation $\left( \prod_{i=m+2}^{N-j+m} (\gamma_i-1) \right) \lambda_j = \gamma_{m+1} \left( \prod_{i=m+2}^{N-j+m-1} \gamma_i \right) \lambda_{N-1}$, $j = m,\ldots,N-2$. Using this representation $\lambda_j$ which (only) depends on $\lambda_{N-1}$ Inequality \eqref{Alpha_Formula_Inequality_Lemma_Proof1} is equivalent to
	\begin{equation*}
		(\gamma_{m+1} - \omega) \prod_{i=m+2}^{N-j+m} (\gamma_i - 1) \geq (\gamma_{N-j+m} - \gamma_{N-j}) \prod_{i=m+1}^{N-j+m-1} \gamma_i,\qquad j = m,\ldots,N-2.
	\end{equation*}
	Since the left hand side of this expression is equal to
	\begin{equation*}
		(\gamma_{m+1}-\omega) \prod_{i=m+2}^{N-j+m-1} (\gamma_i - 1) (c_0 - 1) + (\gamma_{m+1}-\omega) \prod_{i=m+2}^{N-j+m-1} (\gamma_i - 1) \left[ \sum_{n=1}^{N-j+m-2} c_n + \omega c_{N-j+m-1} \right],
	\end{equation*}
	$(c_0 - 1) \geq 0 $, and $(\gamma_{N-j+m} - \gamma_{N-j}) = \sum_{n=N-j-1}^{N-j+m-2} c_n + \omega c_{N-j+m-1} - \omega c_{N-j-1}$ Lemma \ref{Appendix_Lemma_Inequalities} applied for $k=1$ completes the proof.
\end{proof}
\begin{remark}
	If condition \eqref{3:eq:submultiplicativity} is not satisfied the $\alpha_{N,m}^\omega$-value which has been deduced in Theorem \ref{alpha_formula_thm} may still be used as a lower bound for the optimal value of Problem \ref{optprob} for $\mathcal{KL}_0$-functions which are linear in their first arguments, cf. Corollary \ref{convergenceNtoINFINITY}.
\end{remark}

At first glance, exponential controllability with respect to the stage costs may seem to be restrictive. However, since the stage costs can be used as a design parameter, cf. \cite[Section 7]{G07}, this includes even systems which are only asymptotically controllable. In order to illustrate this assertion we consider the control system defined by $x(n+1) = x(n) + u(n)x(n)^3$ -- which is the Euler approximation of the differential equation $\dot{x}(t) = u(t) x(t)^3$ with time step $1$ -- with $U = [-1,1]$ on $X = (-1,1) \subset \mathbb{R}$.\footnote{The state and control restrictions are necessary to preserve the characteristics of the continuous time system for the Euler approximation.} This system is asymptotically stabilizable with control function $u(\cdot) \equiv -1$, i.e., $x(n+1) = x(n) - x(n)^3$. However, it is not exponentially stabilizable. Defining
\begin{equation*}
	l(x(n),u(n)) := e^{- \frac {1}{2x(n)^2}}
\end{equation*}
for $0 < \| x(n) \| < 1$ and $l(x(n),u(n)) := \| x(n) \|$ otherwise allows for choosing $\beta(r,t) = r e^{-t/e}$, i.e., a $\mathcal{KL}$-function of type \eqref{3:eq:exponential controllability}. We have to establish the inequality
\begin{equation*}
	l(x(n+1)) = l(x(n)-x(n)^3) = e^{- \frac {1}{2x(n)^2(1-x(n)^2)^2}} \leq e^{-1} l(x(n)) = e^{-1} e^{-\frac{1}{2x(n)^2}}
\end{equation*}
which implies Assumption \ref{3:ass:controllability} inductivly and is equivalent to
\begin{equation*}
	1 \geq 2x(n)^2(1-x(n)^2)^2 + (1-x(n))^2 = 1 - 3x(n)^4 + 2x(n)^6.
\end{equation*}
Since $\| x(n) \| \leq 1$ this inequality holds. Thus, we have obtained exponential controllability with respect to suitably chosen stage costs.
\begin{remark}
	Note that Assumption \ref{3:ass:controllability} is not merely an abstract condition. Rather, in connection with Formula \eqref{alpha_formula} it can be used for analyzing differences in the MPC closed loop performance for different stage costs $l(\cdot,\cdot)$ and thus for developing design guidelines for selecting good cost functions $l(\cdot,\cdot)$. This has been carried out, for instance, for the linear wave equation with boundary control in \cite{Altmueller}, for a semilinear parabolic PDE with distributed and boundary control in \cite{AltmuellerBFG} (see also \cite{G07} for a preliminary study), and for a discrete time 2d test example in \cite{G07}.
\end{remark}

\section{Characteristics of $\alpha_{N,m}^\omega$ depending on the optimization horizon $N$}\label{alphasec1}

Theorem \ref{alpha_formula_thm} enables us to easily compute the performance bounds $\alpha_{N,m}^\omega$ which are needed in Theorem \ref{stabthm} in order to prove stability provided $\beta$ is known. However, even if $\beta$ is not known exactly, we can deduce valuable information. The following corollary is obtained by a careful analysis of the fraction in \eqref{alpha_formula}.
\begin{corollary} \label{convergenceNtoINFINITY}
	For each fixed $m$, $\beta$ of type \eqref{3:eq:exponential controllability} or \eqref{3:eq:finite time controllability} and $\omega\ge 1$ we have $\lim_{N\to\infty} \alpha_{N,m}^\omega=1$. In particular, for sufficiently large $N$ the assumptions of Theorem \ref{stabthm} hold and hence the closed loop system is asymptotically stable.
\end{corollary}
\begin{proof}
	Since $\beta(r,n)$ is summable, i.e., $\sum_{n=0}^\infty \beta(r,n) < \infty$, there exists an index $\widetilde{m}$ such that $\omega \sum_{n=\widetilde{m}}^\infty c_n \leq \varepsilon < 1$. It suffices to investigate the case $\gamma_{m+1} - \omega > 0$ because otherwise the assertion holds trivially. We have to show that the subtrahend of the difference in formula \eqref{alpha_formula} converges to zero as the optimization horizon $N$ tends to infinity. To this aim, we divide the term under consideration into two factors. One of them is the following which is bounded for sufficiently large $N$, i.e., $N > \widetilde{m} + m$,
	{\small\begin{equation*}
		\frac {\prod_{N-m+1}^N (\gamma_i - 1)} {\prod_{N-m+1}^N \gamma_i - \prod_{N-m+1}^N (\gamma_i - 1)} < \frac {m (\gamma_{\widetilde{m}} + \varepsilon - 1)} {m(\gamma_{\widetilde{m}} - (\omega - 1) c_{\widetilde{m}} - (\gamma_{\widetilde{m}} - (\omega - 1) c_{\widetilde{m}} + \varepsilon - 1))} = \frac {\gamma_{\widetilde{m}} + \varepsilon - 1} {1 - \varepsilon} < \infty.
	\end{equation*}}
	Hence, we focus on the other factor, i.e.,
	\begin{eqnarray*}
		\frac {(\gamma_{m+1} - \omega) \prod_{m+2}^N (\gamma_i - 1)} {\prod_{m+1}^N \gamma_i - (\gamma_{m+1} - \omega) \prod_{m+2}^N (\gamma_i - 1)}
		& = & \frac {\prod_{m+1}^N \gamma_i} {\prod_{m+1}^N \gamma_i - (\gamma_{m+1} - \omega) \prod_{m+2}^N (\gamma_i - 1)} - 1 \\

		& = & \frac {\gamma_{m+1}} {\omega + (\gamma_{m+1} - \omega) \left( \frac{ \prod_{m+2}^N \gamma_i - \prod_{m+2}^N (\gamma_i - 1)} {\prod_{m+2}^N \gamma_i} \right)} - 1.
	\end{eqnarray*}
	Showing the convergence of this term to zero for $N$ tending to infinity completes the proof. Thus, it suffices to prove $\prod_{m+2}^N (\gamma_i - 1)/ \gamma_i \longrightarrow 0$ for $N$ tending to infinity.
	Taking into account $\gamma_{\widetilde{m}} - (\omega - 1) c_{\widetilde{m}} \leq \gamma_i$ for all $i \geq \widetilde{m}$, we derive the desired convergence by the estimate
	\begin{equation*}
		\prod_{m+2}^N \frac {\gamma_i - 1}{\gamma_i} \leq \prod_{m+2}^{\widetilde{m}} \frac {\gamma_i - 1}{\gamma_i} \left( \frac {\gamma_{\widetilde{m}} - (\omega - 1) c_{\widetilde{m}} + \varepsilon - 1} {\gamma_{\widetilde{m}} - (\omega - 1) c_{\widetilde{m}}} \right)^{N-\widetilde{m}} \stackrel {N \rightarrow \infty} {\longrightarrow} 0.
	\end{equation*}
\end{proof}

Corollary \ref{convergenceNtoINFINITY} ensures stability for sufficiently large optimization horizons $N$ which has already been shown in \cite{GMTT05} under similar conditions (see also \cite{JadH05} for an analogous result in continuous time). Our result generalizes this assertion to arbitrary, but fixed control horizons $m$. Furthermore, similar to \cite{GruR08} for $\omega=1$, it also implies that for $N\to\infty$ the infinite horizon cost $V_\infty^{\mu_{N,m}}$ will converge to the optimal value $V_\infty$ (using the inequality $\alpha_{N,m}^1 V_\infty^{\mu_{N,m}} \le V_N$ from Theorem \ref{4:thm:optimality} and the obvious inequality $V_N\le V_\infty$ for $\omega=1$).

However, compared to these references, our approach has the significant advantage that we can also investigate the influence of different quantitative characteristics of $\beta$, e.g., the overshoot $C$ and decay rate $\sigma$ in the exponentially controllable case \eqref{3:eq:exponential controllability}. For instance, the task of calculating all parameter combinations $(C,\, \sigma)$ implying a nonnegative $\alpha_{N,m}^\omega$ and thus stability for a given optimization horizon $N$ can be easily performed, cf. Figure \ref{stability_region_m1}\footnote{The idea to visualize the parameter dependent stability regions in this way goes back to \cite{Voit08}.}.

\begin{figure}[!ht]
	\begin{center}
		\includegraphics[width=8.cm]{pictures/StabilityRegion_m1}
	\end{center}
	\caption{Illustration of the stability region guaranteed by Theorem \ref{alpha_formula_thm} for various optimization horizons $N$ given a $\mathcal{KL}$-function of type \eqref{3:eq:exponential controllability} for ``classical'' MPC, i.e., $m=1$.}
	\label{stability_region_m1}
\end{figure}

As expected, the stability region grows with increasing optimization horizon $N$. Moreover, Theorem \ref{alpha_formula_thm} enables us to quantify the observed enlargement, e.g., doubling $N=2$ increases the considered area by $129.4$ percent. Furthermore, we observe that for a given decay rate $\sigma$ there always exists an overshoot $C$ such that stability is guaranteed. Indeed, Theorem \ref{alpha_formula_thm} enables us to prove this. To this end, we deal with the special case $C=1$ exhibiting a significantly simpler expression for $\alpha_{N,m}^\omega$.

\begin{proposition}\label{exp_stab_C1}
	Let the $\mathcal{KL}_0$-function be of type \eqref{3:eq:exponential controllability} and $C=1$. Then the optimal value $\alpha_{N,m}^\omega$ is equal to $\min\{1,\, 1 - (1+\sigma\omega-\omega) \sigma^{N-1}\} > 0$.
\end{proposition}
\begin{proof}
	We define the auxiliary quantity $\eta := 1 + \sigma \omega - \omega$. Then, we obtain the equalities $\gamma_i = (1-\eta \sigma^{i-1})/(1-\sigma)$, $\gamma_{i} - 1 = \sigma (1 - \eta \sigma^{i-2}) / (1-\sigma)$, and $\gamma_{m+1} - \omega = \eta (1-\sigma^{m}) / (1-\sigma)$. Thus, the necessary and sufficient condition $(\gamma_{m+1}-\omega) \leq 0$ from Theorem \ref{alpha_formula_thm} holds if and only if $\eta \leq 0$. Hence, we restrict ourselves to $\eta > 0$ and the right hand side of formula \eqref{alpha_formula} is equal to
	{\small\begin{eqnarray*}
		\alpha_{N,m}^\omega & = & 1 - \frac {
			\frac {\eta (1-\sigma^m)} {1-\sigma} \prod_{m+2}^N \frac {\sigma (1-\sigma^{i-2}\eta)} {1-\sigma} \prod_{N-m+1}^N \frac {\sigma (1-\sigma^{i-2}\eta)} {1-\sigma}
		} {
			\left( \prod_{m+1}^N \frac {1-\sigma^{i-1}\eta}{1-\sigma} - \frac {(1-\sigma^m)\eta}{1-\sigma} \prod_{m+2}^N \frac {\sigma(1-\sigma^{i-2}\eta)}{1-\sigma} \right) \left( \prod_{N-m+1}^N \frac {1-\sigma^{i-1} \eta}{1-\sigma} - \prod_{N-m+1}^N \frac {\sigma(1-\sigma^{i-2}\eta)}{1-\sigma} \right)
		}\\
		& = & 1 - \frac {
			\eta (1-\sigma^m) \sigma^{N-1} \prod_{N-m+1}^{N-m+1} (1-\sigma^{i-2}\eta)
		} {
			\underbrace{\left( (1-\sigma^{N-1} \eta) - \eta (1-\sigma^m) \sigma^{N-m-1} \right)}_{=1-\sigma^{N-m-1} \eta} \cdot \underbrace{\left( (1-\sigma^{N-1} \eta) - (1-\sigma^{N-m-1}\eta) \sigma^m \right)}_{= 1-\sigma^m}
		}\\
		& = & 1 - \eta \sigma^{N-1},
	\end{eqnarray*}}
	where we have omitted the control index.
\end{proof}
\begin{remark}
	Note that the optimal value $\alpha_{N,m}^\omega$, i.e., the solution of Problem \ref{optprob}, does not depend on the control horizon $m$ for $C=1$. Consequently, the control horizon $m$ does not play a role for this special case.
\end{remark}

Proposition \ref{exp_stab_C1} states that we always obtain a strictly positive value $\alpha_{N,m}^\omega$ for $C=1$. Due to continuity of the involved expressions this remains true for $C = 1 + \varepsilon$ for sufficiently small $\varepsilon$. Thus, for any decay rate $\sigma\in(0,1)$ and sufficiently small $C>1$ (depending on $N$, $m$ and $\omega$) we obtain $\alpha_{N,m}^\omega>0$ and thus asymptotic stability. However, this property does not hold if we exchange the roles of $\sigma$ and $C$, i.e., for a given overshoot $C>1$ stability cannot in general be concluded for a sufficiently small decay rate $\sigma>0$.

Next, we investigate the relation between $\gamma = \sum_{n=0}^\infty c_n$ and the optimization horizon $N$ for finite time controllability in one step, i.e., for a $\mathcal{KL}_0$-function of type \eqref{3:eq:finite time controllability} satisfying \eqref{3:eq:submultiplicativity} defined by $c_0 = \gamma$ and $c_n = 0$ for all $n \in \mathbb{N}_{\geq 1}$. For this purpose, let $\gamma$ be strictly greater than $\omega \geq 1$. Otherwise Theorem \ref{alpha_formula_thm} provides $\alpha_{N,m}^\omega = 1$ regardless of the optimization horizon $N$. In this case, Formula \eqref{alpha_formula} yields
\begin{equation*}
	\alpha_{N,m}^\omega = 1 - \frac {(\gamma - \omega) (\gamma - 1)^{N-1}}{(\gamma^{N-m} - (\gamma - \omega) (\gamma - 1)^{N-m-1}) (\gamma^{m} - (\gamma - 1)^{m})}.
\end{equation*}
We aim at determining the minimal optimization horizon $N$ guaranteeing stability for a given parameter $\gamma$. In order to ensure stability, we have to show $\alpha_{N,m}^\omega \geq 0$. We begin our examination with the smallest possible control horizon $m=1$. This leads to the inequality
\begin{equation*}
	\alpha_{N,1}^\omega = 1 - \frac {(\gamma - \omega) (\gamma - 1)^{N-1}}{\gamma^{N-1} - (\gamma - \omega) (\gamma - 1)^{N-2}} = \frac {\gamma^{N-1} - (\gamma - \omega) (\gamma - 1)^{N-2} \gamma}{\gamma^{N-1} - (\gamma - \omega) (\gamma - 1)^{N-2}} \geq 0.
\end{equation*}
Since the logarithm is monotonically increasing this is in turn equivalent to
\begin{equation*}
	N \geq 2 + \frac { \ln (\gamma - \omega) } {\ln \gamma - \ln (\gamma - 1)} =: f(\gamma).
\end{equation*}
We show that $f(\gamma)$ tends to $\gamma \ln \gamma$ asymptotically. To this end, we consider
\begin{equation*}
	\lim_{\gamma \rightarrow \infty} \frac {f(\gamma)}{\gamma \ln \gamma} = \underbrace{\lim_{\gamma \rightarrow \infty} \frac {2}{\gamma \ln \gamma}}_{= 0} + \underbrace{\lim_{\gamma \rightarrow \infty} \frac {\ln (\gamma - \omega)}{\ln \gamma}}_{= 1} \cdot \lim_{\gamma \rightarrow \infty} \frac {\frac 1 \gamma}{\ln \gamma - \ln (\gamma - 1)} = \lim_{\gamma \rightarrow \infty} \frac {\gamma (\gamma - 1)}{\gamma^2} = 1
\end{equation*}
where we have used L'Hospital's rule. Clearly, ceiling the derived expression for the optimization horizon $N$ doesn't change the obtained result.

We continue with analysing the coherancy between $\gamma$ and $N$ for control horizons $m$ which provide the largest optimal value, i.e., $m = \lfloor N/2 \rfloor$, cf. Section \ref{alphasec2} below. Analogously, $\alpha_{N,\lfloor N/2 \rfloor}^\omega \geq 0$ induces lower bounds
\begin{equation*}

	N \geq \begin{cases}
		2 \ln \left( \frac {2\gamma - \omega - 1}{\gamma - 1}\right) / (\ln \gamma - \ln (\gamma - 1)) & \text{for even $N$} \\[2mm]
		\left( \ln \left( \frac {2 \gamma - \omega}{\gamma} \right) + \ln \left( \frac {2 \gamma - \omega}{\gamma - 1} \right) \right) / (\ln \gamma - \ln (\gamma - 1)) & \text{for odd $N$}
	\end{cases}
\end{equation*}
for the optimization horizon $N$. Again in consideration of L'Hospital's rule, the investigated expression exhibits asymptotically a behaviour like $2 \ln 2 \cdot \gamma$, cf. Figure \ref{finite_time_one_step_asymptotic}. Since the obtained approximation $2 \ln 2 \cdot \gamma$ holds for both estimates corresponding to even and odd natural numbers $N$ for $m=\lfloor N/2 \rfloor$, we have illustrated the resulting horizon lengths for given $\gamma$ with respect to both. Moreover, these estimates coincide with the numerical results derived in \cite[Section 6]{G07}.

\begin{figure}[!ht]
	\begin{center}
		\includegraphics[width=6.2cm]{pictures/MinimalStabilizingHorizon_m1}
		\includegraphics[width=6.2cm]{pictures/MinimalStabilizingHorizon_mN2}
	\end{center}
	\caption{Minimal stabilizing optimization horizons for one step finite time controllability for $m=1$ and $m = \lfloor N/2 \rfloor$ in comparison with their asymptotic approximations.}
	\label{finite_time_one_step_asymptotic}
\end{figure}

\begin{remark}
	As a consequence of Lemma \ref{linlemma} it follows that these estimates provide upper bounds for the minimal stabilizing horizons for $\mathcal{KL}_0$-functions $\beta(\cdot,\cdot)$ which are linear in their first argument and satisfy \eqref{3:eq:submultiplicativity}, e.g., for $c_0 = \gamma = C \sum_{n=0}^\infty \sigma^n$ with $C \geq 1$, $\sigma \in (0,1)$.
\end{remark}


TITLE: Why weights are not squared in the weighted Euclidean distance formula?
QUESTION [0 upvotes]: I am working on Data Mining and need distance between data points.
With two points $(x_1, y_1), (x_2, y_2)$ & weights $w_1$ and $w_2$ respectively. The euclidean distance is:
$$
\sqrt{w_1\times(x_2-x_1)^2+w_2\times(y_2-y_1)^2}.
$$
I think intuitively $w_1$ & $w_2$ were supposed to be squared as they are getting square rooted in the result.

REPLY [2 votes]: You are right.
$w$ is just a name for $\frac{1}{s^2}$, where $s$ for standard deviation.
Full answer here:
http://www.econ.upf.edu/~michael/stanford/maeb4.pdf


TITLE: Set of probability generating functions complete?
QUESTION [1 upvotes]: A probability generating function of a possibly defective distribution is a function
$f(z) = \sum_{i=0}^\infty a_i z^i $,
for which
$\sum_{i=0}^\infty a_i\leq 1$.
Let $C$ be the set of all functions $f$ satisfying the above. Is it then true that $C$ is a Banach space (i.e., it is a complete normed vector space, which means that Cauchy sequences are convergent). If yes, with respect to which norm?

REPLY [0 votes]: The class of generating functions of sub-probability distribution on non-negative integers is not a vector space. However, it is a complete metric space: we can identify generating functions with the coefficient sequences. The set of sequences under consideration is a closed subset of the complete space $l^1$.


text:
\section{Production Unit Control}\label{sec:control}

In this section, optimal control of the production unit is addressed with particular focus on the temperature and CO$_2$ levels.

Because binary constraints are present, and the overall objective is to not violate growth constraints while minimizing the energy demand, a predictive controller with relaxed constraint specification is employed.
The task of state estimation is omitted due to page limitation and full state availability at every time instance is assumed.
As to this point, control is designed as a tracking problem of particular desired temperature and CO$_2$ levels whereas economic factors embodied in the optimization objective (refer to economic MPC, cf. \cite{Rawlings2012}) may be considered as well.

\subsection{System Discretization and Predictive Control Design}
Predictive control is performed at discrete time step, for which the dynamics $x(t_k + 1) = x(t_k) + \Delta t f(x(t_k),u(t_k),d(t_k)) =: f_d(x(t_k),u(t_k),d(t_k))$ are utilized, where $t_k = n \Delta t$, $n \in \N_0$, and $\Delta t >0$ is the sample time.
Due to the ``high'' nonlinearity of the continuous-time dynamics, a sufficiently small sample time should be chosen such that the behaviour is approximated adequately on a given time interval \eg the prediction horizon.
However, using simulations of the system response to sample controls for a set of initial states, it could be observed that the state changes are relatively slow compared to the timescale of the system \sut a model discretization time of $\Delta t = 30$ sec is regarded sufficient for control.

The predictive controller is applied on the nonlinear model, under awareness of the numerical difficulties involved in nonlinear optimization \citep[see \eg][for a study]{Kamel2017}, with a sampling frequency of $\Delta t = 30$ sec, which equals that of the model discretization.
Using the prediction horizon $N=5$, which yields a $2.5$ min lookahead time, the optimization setup is rendered sufficiently fast (computationally).

The particular difficulty in using longer prediction horizons lies in the fact that the computational load increases significantly.
Although local linearizations could be used to reduce this burden, linear dynamics approximation may be unsuitable when predicting over longer horizons in which the state and/or input may reach values ``outside'' the validity of the linear approximation.
It will be shown in Section \ref{sec:result}, however, that the horizon length is sufficient for constraint satisfaction as well as efficient reference tracking.

The (bounded) disturbance $\mathbf{d}(t)$ is assumed to be known for the entire horizon length $[t_k,t_k + N]$ for any $t_k$ \eg by using short-term weather forecast, while at each time step, the discretized trajectory is shifted and only the last value at $t_k + N$ is updated.
That is, at each time instance, the previous climate data for the specified time horizon remains as predicted while adding a new measure $\mathbf{d}(t_k+N)$ to the sequence.
This allows to consider the time-varying system $f_d(\mathbf{x}(t_k),\mathbf{u}(t_k),\mathbf{d}(t_k)) = f_d(\mathbf{x}(t_k),\mathbf{u}(t_k),t_k)$.
As this could be considered a strong assumption, it should be pointed out that short-term weather forecast supplies reliable and sufficiently accurate data. Whereas the external disturbance may additionally be regarded as near constant on the inspected time interval, given a current environment state.

At every time $t_k$, the solution to
\begin{subequations} \label{eq:MPC}
	\begin{align}
	\begin{split}
	\min_{\substack{\varepsilon,\mathbf{u}_{i}(t_k) \\ i=0,\dotsc,N-1}} &\sum_{i=0}^{N-1} r(\mathbf{x}_{i}(t_k) - \mathbf{x}^{\text{ref}}(t_k +i), \mathbf{u}_{i}(t_k)-\mathbf{u}^{\text{ref}}(t_k+i)   ) \\

	&+ V_P(\mathbf{x}_{N}(t_k))  + \alpha \varepsilon^2   \label{eq:MPC-1}
	\end{split}\\
	\text{s.t.} \quad &\mathbf{x}_{i+1}(t_k) = f_d(\mathbf{x}_{i}(t_k),\mathbf{u}_{i}(t_k),t_k+i) \\
	&\mathbf{x}_{0}(t_k) = \mathbf{x}(t_k) \\
	& \mathbf{x}_{i}(t_k) \in \X, \; i = 0,\dotsc,N \\
	& \mathbf{u}_{i}(t_k) \in \U, \; i = 0,\dotsc,N-1 \\
	& \nu_{i}(t_k) = \nu_{i}^2(t_k) + \varepsilon, \; i = 0,\dotsc,N-1 \label{eq:MPC-6}
	\end{align}
\end{subequations}
is computed for some $\alpha \gg 1$ and $V_P(x)= \left( x - \mathbf{x}^{\text{ref}}(t_k +N)\right)^\top P\left( x - \mathbf{x}^{\text{ref}}(t_k +N)\right)$, with $P \succeq 0$.
The optimization \eqref{eq:MPC} yields the minimizing control sequence $\{\mathbf{u}_{0}^\ast(t_k),\dotsc,\mathbf{u}_{N-1}^\ast(t_k)\}$, while $\mathbf{u}_0^\ast(t_k) =: \mathbf{u}^\ast(t_k)$ is applied to the system, as well as an optimal relaxation $\varepsilon^\ast(t_k)$.
The binary constraints in $\mathbb{U}$ are tackled via constraint relaxation according to \eqref{eq:MPC-6}.
Forcing $\varepsilon \rightarrow 0$ through the cost $\alpha \varepsilon^2$ with $\alpha \gg 1$ renders $\nu \in \{0,1\}$ the only admissible values, whereas \eqref{eq:MPC-6} comprises a set of constraints for all $\{u_{\text{V}}, u_{\text{H}},u_{\text{W}1},u_{\text{W2}},u_{\text{W}3}\} \ni \nu$.

In \eqref{eq:MPC-1}, $\mathbf{x}^{\text{ref}}(t),\, \mathbf{u}^{\text{ref}}(t)$ are reference trajectories to be specified in the following Section \ref{subsec:tracking}, $r(x,u):\mathbb{X} \times \mathbb{U} \rightarrow \mathbb{R}_{\geq 0}$ is a positive semi-definite running cost and $P = \text{diag}(5000,\num{1.1e12},0,\dotsc,0)$ is a terminal weight matrix.

\subsection{Reference Specification}
\label{subsec:tracking}

 Plant growth can be quantified primarily over the instantaneous photosynthetic rate (occurring at $s^{-1}$ rate) and the net assimilation over 24 hrs (circadian rhythm)\citep{Gaudreau1994}.
 Photosynthesis is best when incident light, CO$_2$ concentration, and temperature are at levels optimal for the plant growth. The model equation \eqref{eq:dB/dt} only describes the plant growth due to photosynthesis while the circadian rhythm is introduced through the reference trajectories.

 An approximated reference for the daily light input trajectory $u_{\mathrm{I}j}^{\text{ref}}$, $j=1,\dotsc,4$ is specified using a cosine function. In particular
 \begin{align*}
 u_{\mathrm{I}j}^{\text{ref}}(t) = 50 - 50 \cos(2 \pi f_{\mathrm{Hz}}t), \quad j = 1,\dotsc,4,
 \end{align*}
 where $f_{\mathrm{Hz}}= 1/(2\cdot 60 \cdot 24) = 1/\mathrm{Day}$.
 Furthermore, a cosine trajectory is adopted for $T^{\text{ref}} \text{ and } C^{\text{ref}}$ such that the times of peak values in light intensity, temperature and CO$_2$ concentration coincide.
The near optimal reference is suggested as
\begin{align*}
T^{\text{ref}}(t) &= 20 - 3 \cos(2 \pi f_{\mathrm{Hz}}t),\\
C^{\text{ref}}(t) &= \num{9.05e-4} - \num{1.8e-04} \cos(2 \pi f_{\mathrm{Hz}}t).
\end{align*}

Regarding the input reference values,
\begin{align*}
	u_{\mathrm{T}}^{\text{ref}}(t) &= u_{\mathrm{V}}^{\text{ref}}(t) = u_{\mathrm{H}}^{\text{ref}}(t) = u_{\mathrm{W}1}^{\text{ref}}(t) = u_{\mathrm{W}2}^{\text{ref}}(t)= u_{\mathrm{W}3}^{\text{ref}}(t)
	\equiv 0

\end{align*}
is used, as to capture the value of minimum energy expenses.
For this study, the disturbance trajectory was generated using records of past weather data of Chemnitz, Germany.

For tracking, respective state and input weights are set sufficiently high.
Specifically, the stage cost function
\begin{equation}
\begin{split}
	r(&\mathbf{x}(t_k), \mathbf{u}(t_k)) = 5000 \, ( \, T(t_k) - T^{\text{ref}} (t_k+i) \, )^2 \,\\
	& + \num{1.11e12} \, ( \, C(t_k) - C^{\text{ref}} (t_k+i) \, )^2 \,\\
	& + \left(\mathbf{u}_{i}(t_k)-\mathbf{u}^{\text{ref}}(t_k+i) \right)^\top R \left( \mathbf{u}_{i}(t_k)-\mathbf{u}^{\text{ref}}(t_k+i) \right),\\
\text{with } &R = \text{diag}(0.1,1,0.25,0.5,0.5,0.5,100,\dotsc,100).
\end{split}
\end{equation}

The values of state penalties are chosen to compensate the different scales of various states. In turn the actuation costs for all actuators except LEDs are equivalent to the current consumed in amperes. For example, when $u_\mathrm{T}=50$, 5\si{\ampere} of current is consumed by the TEC.


TITLE: If $j:K→K'$ is a field isomorphism, what is the meaning of $j(p)$, being $p$ a polynomial over $K$.
QUESTION [1 upvotes]: I believe the title explains my question, though to clarify, I encountered a text in which the author defines $j:K→K'$ as a field isomorphism and $p$ as a polynomial that splits over $K$.
The polynomial $p$ is defined as a function, in other words it's equation contains the indeterminate $t$, while $j$ is simply defined as a mapping between $K$ and $K'$, so what could the author be referring to when talking about $j(p)$?

REPLY [1 votes]: The polynomial $p$ is defined as a function

No, that's wrong. It's a common misunderstanding: polynomials are not functions. The formal definition is that a polynomial over a (commutative) ring $R$ is an infinite sequence $(a_0, a_1, \ldots)$ where each $a_i\in R$ and there is $M$ such that $a_m=0$ for all $m>M$ (side note: we can omit the second condition to obtain formal power series). Smallest such $M$ is called the degree of the polynomial. The addition and multiplication are given by:
$$(a_0, a_1, \ldots)+(b_0,b_1,\ldots)=(a_0+a_1, b_0+b_1, \ldots)$$
$$(a_0, a_1, \ldots)\cdot (b_0, b_1, \ldots)=(c_0, c_1, \ldots)$$
$$c_i=\sum_{k=0}^{i}a_{k}\cdot b_{i-k}$$
That's all. With that we define a special $X$ (or $t$ in your case) polynomial by $X:=(0,1,0,\ldots)$ if $R$ has $1$. We also identify $r\in R$ with a polynomial $(r, 0,\ldots)$. Then every polynomial can be written in a form
$$a_0+a_1\cdot X+a_2\cdot X^2+\cdots+a_n\cdot X^n$$
for $a_i\in R$. The set of all polynomials is denoted by $R[X]$. With the addition and multiplication defined as above its a ring (even algebra over $R$).
Now if $f:R\to S$ is a ring homomorphism and $p=(a_0,a_1,\ldots)$ is a polynomial then $f$ can be extended to a ring homomorphism
$$F:R[X]\to S[X]$$
$$F((a_0,a_1,\ldots)) = (f(a_0), f(a_1), \ldots)$$
or with usual notation
$$F\big(\sum a_i\cdot X^i\big)=\sum f(a_i)\cdot X^i$$
And this is most likely what the author is referring to.
Side note: If $p=(a_0,a_1,\ldots)$ is a polynomial then it induces a polynomial function $\overline{p}:R\to R$ given by
$$\overline{p}(x)=a_0+a_1\cdot x + a_2\cdot x^2 + \cdots $$
(note that the sum is finite since $a_i=0$ eventually). Do not confuse it with addition and scalar multiplication in $R[X]$, here $x$ is simply an element of $R$ and we add and multiply in $R$. Denote by $R\{X\}$ the set of all polynomial functions (which is a ring under pointwise addition and multiplication).
It can be shown that a mapping
$$\Phi:R[X]\to R\{X\}$$
$$\Phi(p)=\overline{p}$$
is a ring homomorphism. It is surjective by definition.
You may think that I'm just doing some formal irrelevant distinction between polynomials and polynomial functions but that's not the case. Consider any finite ring $R=\{a_0,a_1,\ldots, a_n\}$. Define two polynomials:
$$P_1=0$$
$$P_2=(X-a_0)(X-a_1)\cdots(X-a_n)$$
These are two different polynomials because they have different coefficients ($P_2$ is of degree $n$). However the induced polynomial functions are the same because $\overline{P_2}(x)=0$ for any $x\in R$. Thus $\Phi$ is not injective over a finite ring.
It can be shown that $\Phi$ is an isomorphism if and only if the underlying ring $R$ is infinite.