# How to minimize this function difference

Sorry about this somewhat lengthy introduction to my question. I thought it might be useful to know what I'm trying to do.

I decided that I would like to have sequence of polynomials in $\mathbb{P}_n (x)$ defined in domain $x\in[0,1]$ which gradually learn a function. So, given an initial polynomial $P_{\alpha_0}(x)=\sum_{i=1}^n a_i x^{i-1}$ where $\alpha_0 = (a_1,\ldots,a_n) \in \mathbb{R}^n$, I would introduce a new point $(x_0,y_0) \in [0,1]\times\mathbb{R}$ and try to find all $\beta \in\mathbb{R}^n$ such that $$P_{\alpha_0 + \beta}(x_0)=y_0$$ If the solution space to that is $S$, then the next step would be to find optimal solution which somehow minimises the non-local difference. Define a norm which penalizes non-local difference: $${\lVert P_{\alpha} \rVert}_{(x_0)} = \int_0^1 {(x-x_0)}^2{(P_{\alpha}(x))^2} dx$$ The objective would be to find such $\beta \in S$ that it minimises $${\lVert P_{\alpha_0} -P_{\alpha_0+\beta}\rVert}_{(x_0)}$$ and then have for the next round $\alpha_1 = \alpha_0 + \beta$.

Looking at solutions for the standard basis $\beta_i=(0,\ldots,0,b_{i,i},0,\ldots,0)$ (i.e. all but the $i$:th element are zero) one finds easily that $$P_{\alpha_0+\beta_i}(x_0)=y_0$$ when $$b_{i,i} = \frac{y_0 - P_{\alpha_0}(x_0)}{x_0^{i-1}}$$ Let's use $b_i = b_{i,i}$ for short.

The solution space $S$ is linear combination $\sum t_i \beta_i$ with the requirement that $\sum t_i = 1$.

Now, do you have any elegant ways to find the minimum for $${\lVert P_{\alpha_0} -P_{\alpha_0+\beta}\rVert}_{(x_0)} = \sum_{i,j}^n t_i t_j b_i b_j g_{x_0}(i,j)$$ where $$g_{x_0}(i,j) = (\frac{1}{i+j+1} -\frac{2 x_0}{i+j} + \frac{x_0^2}{i+j-1})$$ from the solution hyperplane $\sum t_i = 1$?

It's rather easy to find the equation for the null space of the partial differentials $$\frac{d{\lVert P_{\alpha_0} -P_{\alpha_0+\beta}\rVert}_{(x_0)}}{d t_k} = \sum_i t_i b_i g_{x_0}(k,j)$$ This is a linear mapping of the form $M t = 0$ where $M_{i,j} = b_i g_{x_0}(i,j)$. Testing numerically with some functions seems to indicate that $M$ is mostly of full rank and in those cases the solution would be $t=0$ which does not fulfill the requirement that $\sum t_i = 1$.

Adding this requirement to the mapping gives overdetermined equation $$\left( \begin{matrix} M \\ 1 \end{matrix} \right) t = \left( \begin{matrix} 0 \\ 1 \end{matrix} \right)$$

-
Hmm, does the question even make any sense or is the introduction too long? Or perhaps it is somewhat unclear. I don't need a direct answer. Any kind of indication where to look would be appreciated. – etorri Jul 7 '11 at 12:58

So the problem I had was to find such $t\in S \subset \mathbb{R}^n$ that it minimises the function (1) $$d(t,b,x_0)=\sum_{i,j=1}^n t_i t_j b_i b_j g_{ij}(x_0)$$ within the hyperplane $$S = \{t:\sum_1^n t_i = 1\}$$ From the original integral form of the function it is easy to see that it is positive for all $t$ and from the sum form that it grows with $\lVert t \rVert$ .

I chose the rather elaborate way of substituting $t_n$ with $1-\sum_1^{n-1} t_i$ in (1) and trying to find the zero of the partial differentials of the difference. For simplicity, I also denote $g_{ij}(x_0)$ with just $g_{ij}$ and the reduced vector ${(t_i)}_{i=1}^{n-1}$ with $t^*$.

With the substitution the equation (1) can be (after several steps) written as $$f(t^*)=\sum_{i,j=1}^{n-1} t_i^* t_j^* A_{ij} + \sum_{i=1}^{n-1} t_i^* b_n B_i + b_n^2 g_{nn}$$

where $A_{ij}=b_i b_j g_{ij} - 2 b_i b_n g_{in} + b_n^2 g_{nn}$ and $B_i = 2 b_i g_{in}-2b_n g_{nn}$.

The partial differentials (finally) have the form $$\frac{d f}{d t_k^*} = (\sum_{i=1}^{n-1} t_i (A_{ik}+A_{ki})) + B_k$$ and from this finding the zeros of the differentials can be written in matrix form as $$C t + B = 0$$ where $C_{ij}=A_{ij}+A_{ji}$ is a symmetric matrix. Finding solution to this is rather easy.

Testing numerically the solution shows that $C$ is easily ill-conditioned and the whole idea perhaps rather useless. Nevertheless, watching the polynomials twist and wiggle as new points are added is very entertaining.

-