# WORHP Kata of June 2023: Thin plate spline ⌚ 2023-06-01

A kata (in the context of programming) is a small training unit to practise coding. In this series of WORHP Katas we present standard problems of optimization which you can use to get familiar with optimization (and our optimization software WORHP).

Kata: Thin plate splines can be used to interpolate data in a smooth way.
For data points $(x_i, y_i, z_i)$, $i=1,\dots, N$, the thin plate spline $f(x,y)$ is minimizing the distance to the data points and simultaneously (using an appropriate value of $\lambda\ge 0$) the curvature of the function $f$:
$\displaystyle\sum\limits_{i=1}^N \| z_i - f(x_i,y_i)\|^2 + \lambda \iint \left(\frac{\partial^2 f}{\partial x^2}\right)^2 +2 \left(\frac{\partial^2 f}{\partial x \partial y}\right)^2 +\left(\frac{\partial^2 f}{\partial y^2}\right)^2 \, dx \,dy$

To solve this problem numerically, we can discretize it on an equidistant grid and replace the partial derivatives by their numerical approximations (using adjacent points on the grid). Instead of the integrals, we will only sum up the integrand function on the equidistant grid.

Now, find the discretized version of $f(x,y)$ on $(x, y) \in \{ 0, 1, \dots, 20\} \times \{ 0, 1, \dots, 20\}$ to interpolate these data points:
$\begin{array}{r|rrrrrr} x_i & 5 & 10 & 15 & 5 & 10 & 15 \\\hline y_i & 5 & 5 & 5 & 15 & 15 & 15 \\\hline z_i & -1 & -2 & 0 & 0 &2 & 1 \end{array}$

A solution will be provided with the next WORHP Kata.

Solution of last WORHP Kata: For the points $x_i \in \mathbb{R}^3$, $i=1,\dots, 12$ we formulate this optimization problem:
$\begin{array}{rl} \displaystyle\min\limits_{x} & \sum\limits_{i=1}^{12} \sum\limits_{j=i+1}^{12} \frac{1}{\|x_i - x_j\| + \varepsilon} \\ \text{subject to} & \| x_i \| = 1,\quad i=1,\dots, 12 \end{array}$

To avoid division by zero during the WORHP iterations, we added a value of $\varepsilon = 10^{-7}$ to the denominator.
For the initial guess, we can use random values, or some systematic guesses, cf. this CPP code. In both cases our solver WORHP returns the vertices of an icosahedron:
The value of the objective function is approximately $49.165$.