Generalization of minimisation problem

Question

First I would like introduce my problem ! There is an easy way to solve this one :

Find the value of $$ \inf_{(a,b)\in \mathbb{R}^2} \int_0^1 (t^2-at-b)^2 dt $$ and precise for which values $a$ and $b$ it is reaching.

Well by considering this dot product for two polynoms in $\mathbb{R}[X]^2$, $P$ and $Q$

$$ (P|Q)=\int_0^1 P(t)Q(t)dt $$

By Gram-Schimdt process we find that

$$ \inf_{(a,b)\in \mathbb{R}^2} \int_0^1 (t^2-at-b)^2 dt= \int_0^1 \left(t^2-t+\frac{1}{6}\right)^2 dt =\frac{1}{180} $$

Well I'm capable to find this in less 20 minutes with a pen and a papper, now imagine we want to know the value of :

$$ \inf_{(a_k)\in \mathbb{R}^n} \int_0^1 \left(t^n-\sum_{k=0}^{n-1} a_k \cdot t^k\right)^2 dt $$

Have you got any idea to solve this one for $n=100$ by example without computer and also find if it exist is limit when $n$ comes to infinity ?

Answer 1

You can write the polynomial in the integral in the orthogonal basis of (shifted) Legendre polynomials: $$ t^n-\sum_{i=0}^{n-1} a_i t^i = \sum_{i=0}^n c_i \cdot \bar{P}_i(t). $$ We will need that the coefficient of $\overline{P}_k$ is $\frac{2^k\cdot(2k-1)!!}{k!}$ and $\int_0^1 \overline{P}_k=\frac1{2k+1}$.

The leading coefficient enforces $c_n=\frac{n!}{2^n\cdot (2n-1)!!}$; the remaining coefficients $c_0,\ldots,c_{n-1}$ are free.

From the orthogonality we have $$ \int_0^n \left(\sum_{i=0}^n c_i\bar{P}_i(t)\right)^2 dt = \sum_{i=0}^n |c_i|^2\int_0^n \big(\bar{P}_i(t)\big)^2 dt \\ \ge |c_n|^2\int_0^n \big(\bar{P}_n(t)\big)^2 dt = \left(\frac{n!}{2^n\cdot (2n-1)!!}\right)^2 \cdot \frac1{2n+1} = \frac{(n!)^2}{4^n\cdot (2n-1)!!\cdot (2n+1)!!}. $$ The minimum is attained when $c_0=c_1=\ldots=c_{n-1}=0$.

Therefore, the minimum is $$ \frac{(n!)^2}{4^n\cdot (2n-1)!!\cdot (2n+1)!!} . $$

The minimum is attained when $$ t^n-\sum_{i=0}^{n-1} a_i t^i = c_n \overline{P}_n(t) = \frac{n!}{(2n)!} \cdot \big(x^n(1-x)^n\big)^{(n)}, $$ so $$ a_i = \frac{n!}{(2n)!} \cdot (-1)^{n-i+1}\binom{n}{i} (i+1)(i+2)\ldots(i+n). $$

Answer 2

You can represent the polynomial $t^n-\sum_{k=0}^{n-1}a_kt^k$ as $$t^n-a^Tb(t)$$ where $a=[a_0\ a_2\cdots\ a_{n-1}]^T$ and $b(t)=[1\ t\ \cdots\ t^{n-1}]^T$. Then, the function that you want to minimize becomes $$f(a)=\int_{0}^1(t^n-a^Tb(t))(t^n-a^Tb)^Tdt\\=\int_{0}^1 (a^Tb(t)b(t)^Ta-2t^na^Tb(t)+t^{2n})dt\\=a^TQa-2a^Tp+1/(2n+1)$$ where $Q=\int_{0}^1b(t)b(t)^Tdt\implies Q=[q_{ij}],\ q_{ij}=\int_{0}^1 t^{i-1}t^{j-1}dt=\frac{1}{i+j-1}$ i.e. $Q$ is a Hilbert matrix. $p=\int_{0}^1t^n b(t) dt=c$ where $c=\left[\frac{1}{n+1}\ \frac{1}{n+2}\ \cdots\ \frac{1}{2n}\right]^T$. Then, minimizing $f(a)$ w.r.t $a$ will give the minimizer $a=Q^{-1}p$

Answer 3

This is only a partial answer. It describes how to compute the coefficients $(a_k)$

For a null gradient, we need $$ \begin{align} 0 &=\frac{\partial}{\partial a_j}\int_0^1\left(t^n-\sum_{k=0}^{n-1} a_k \cdot t^k\right)^2\,\mathrm{d}t\\ &=2\int_0^1\left(t^{n+j}-\sum_{k=0}^{n-1}a_k\cdot t^{k+j}\right)\,\mathrm{d}t\\ &=2\left(\frac1{n+j+1}-\sum_{k=0}^{n-1}\frac{a_k}{k+j+1}\right)\tag{1} \end{align} $$ for $0\le j\le n-1$. Written as a matrix, $(1)$ is $$ \begin{bmatrix} \frac1{n+1}\\ \frac1{n+2}\\ \frac1{n+3}\\ \vdots\\ \frac1{2n} \end{bmatrix} = \begin{bmatrix} 1&\frac12&\frac13&\cdots&\frac1n\\ \frac12&\frac13&\frac14&\cdots&\frac1{n+1}\\ \frac13&\frac14&\frac15&\cdots&\frac1{n+2}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \frac1n&\frac1{n+1}&\frac1{n+2}&\cdots&\frac1{2n-1} \end{bmatrix} \begin{bmatrix} a_0\\ a_1\\ a_2\\ \vdots\\ a_{n-1} \end{bmatrix}\tag{2} $$ The square matrix in $(2)$ is the Hilbert Matrix. The determinant is not $0$ and there is an explicit formula for the inverse; the $(i,j)$ element is $$ (-1)^{i+j}(i+j+1)\binom{n+i}{n-j-1}\binom{n+j}{n-i-1}\binom{i+j}{i}^2\tag{3} $$ where $i,j$ are $0$-based. $(2)$ and $(3)$ give explicit values for $a_j$.