Introduction

One way to generate the local approximation $\mbox{$\cal Q$}$$_k(\delta)= f(x_k)+ <g_k,\delta>+ \frac{1}{2}<\delta, B_k \delta>$ of the objective function $\mbox{$\cal F$}$$(x), \quad x \in \Re^n$ around $x_k$ is to make Multivariate Lagrange Interpolation.
We will sample $\mbox{$\cal F$}$ at different points and construct a quadratic polynomial which interpolates these samples.
The position and the number $N$ of the points are not random. For example, if we try to construct a polynomial $L: \Re^2->\Re: z= c_1+ c_2 x + c_3 y$ of degree 1 (a plane), which interpolates locally a function F$: \Re^2 \rightarrow \Re$, we need exactly 3 points $A, B$ and $C$. Why do we need exactly 3 points (apart from the fact that 3 points in 3D determines a plane)? Because we need to solve for $c_1, c_2, c_3$ the following linear system:

$$\begin{pmatrix} 1 & A_x & A_y \\ 1 & B_x & B_y \\ 1 & C_x ... ...c_2 \\ c_3 \end{pmatrix} =\begin{pmatrix}f(A) \\ f(B) \\ f(C) \end{pmatrix}$$ (3.1)

The matrix above is called the ``Vandermonde Matrix''.
We can say even more: What happens if these three points are on the same line? There is a simple infinity of planes which passes through three aligned points. The determinant of the Vandermonde Matrix (called here after the ``Vandermonde determinant'') will be null. The interpolation problem is not solvable. We will say that ''the problem is NOT poised''.
In opposition to the univariate polynomial interpolation (where we can take a random number of point, at random different places), the multivariate polynomial interpolation imposes a precise number of interpolation points at precise places.
In fact, if we want to interpolate by a polynomial of degree $d$ a function F$: \Re^n \rightarrow \Re$, we will need $$N=r_n^d=C_{n}^{d+n}$$ points (with $$C_k^n= \frac{n!}{k!(n-k)!}$$ ). If the Vandermonde determinant is not null for this set of points, the problem is ``well poised''.
Example: If we want to construct a polynomial $\mbox{$\cal Q$}$$: \Re^2->\Re: z= c_1+ c_2 x + c_3 y + c_4 x^2 + c_5 xy + c_6 y^2$ of degree 2, which interpolates locally a function F$: \Re^2 \rightarrow \Re$, at points $\{A, B, C, D, E, F\}$we will have the following Vandermonde system:

$$\begin{pmatrix} 1 & A_x & A_y & A_x^2 & A_x A_y & A_y^2 \\ 1 ... ...begin{pmatrix}f(A) \\ f(B) \\ f(C) \\ f(D) \\ f(E) \\ f(F) \end{pmatrix}$$

Beware! Never try to resolve directly Vandermonde systems. These kind of systems are very often badly conditioned (determinant near zero) and can't be resolved directly.
If we already have a polynomial of degree $d$ and want to use information contained in new points, we will need a block of exactly $C_{n-1}^{d+n-1}$ new points. The new interpolating polynomial will have a degree of $d+1$. This is called ''interpolation in block''.