0
$\begingroup$

I have a rectangular cuboid-shaped 3D "cell" with scalar values at each vertex $(v_1,\ldots,v_8)$. Within this cuboid I do tri-linear interpolation. What I want is the maximum value of that function intersected with a sphere.

I reckon this is an optimization problem, or at least wikipedia tells me that it is. How would I go about finding the maximum value? I'm not interested in where this maximum occurs exactly, in case that makes things easier.

2 Answers 2

1

It seems that trying to do this with constrained optimization using a Lagrange multiplier is more hassle than it's worth. I'd do this as a sequence of line searches along great circles of the sphere as follows:

I'll assume that the sphere is a unit sphere at the origin; otherwise you can linearly transform your coordinate system to make it so. Start at some point $x$ on the sphere, compute the gradient $\nabla f(x)$ of your function $f$ at $x$, and project it into the tangent plane: $g=\nabla f(x)-(\nabla f(x)\cdot x)x$.

Now the one-dimensional function for your line search would be

f(\phi)=f(x'(\phi))=f\left(\cos\phi\,x+\sin\phi\frac g{|g|}\right)\;.

Find the optimal value of $\phi$ using your favourite one-dimensional optimization algorithm, and use the point x'(\phi) as the starting point for the next iteration. If this converges too slowly, you can use conjugate gradients to speed it up; I don't think you have to worry about the projection interfering with the conjugacy condition since the search will quickly get you close to the optimum and then the projection won't change much and you'll effectively be doing a two-dimensional optimization in the tangent plane at the optimum.

0

Given the cuboid $C:=[x_0,x_1]\times[y_0,y_1]\times[z_0,z_1]$ with vertices $v_{ijk}=(x_i,y_j,z_k)$ and assigned values $u_{ijk}$ there is a unique "trilinear function" $T$ with $T(v_{ijk})=u_{ijk}$.

Enclose your sphere $S$ with center $p$ and radius $r>0$ in a cube C'\subset C of sidelength $2r$. C' has vertices v'_{ijk} and assigned values u'_{ijk}:=T(v_{ijk}').

You cannot expect that $T$ has a unique maximum on $S$. If, e.g., $T$ is $=1$ on four tetrahedrally arranged vertices v_{ijk}' of C' and $=-1$ on the other four vertices of C' then $T$ has four local maxima, four local minima and six saddle-points on $S$. Therefore, if you need the exact value of the maximum, you have to do a lot of work in such a case.

The following is an easy way out and should produce a good approximation, in particular if $S$ is rather small compared to $C$.

I propose to do a linear regression on the data concerning C', where I omit the ' in the sequel. This means the following: There is a unique linear function $f(x,y,z):=a x+ by + c z + d$ which makes $\sum_{ijk} \bigl(f(v_{ijk})- u_{ijk}\bigr)^2$ minimal. The unknown coefficients $a$, $b$, $c$, $d$ depend linearly on the data vector $u:=(u_{ijk})$. Symmetry considerations suggest that $a={\sum_{jk} (u_{1jk}-u_{0jk})\over 4(x_1-x_0)}\ ,$ and similarly for $b$ and $c$ ; finally $d$ should be chosen such that at the center $p$ of $C$ one has $f(p)={1\over8}\sum_{ijk} u_{ijk}$.

The maximum $M$ of $f$ on the sphere $S$ is then given by $M=f(p)+r\sqrt{a^2+b^2+c^2}\ .$