# Discrete optimization

I'm having troubles with searching for analytical solution of following problem. Let we work in 3-D space and have the set of points (uniform net at cube's facets):

($-1,\hspace{2mm} -1+j*h,\hspace{2mm} -1+k*h$),

($1,\hspace{2mm} -1+j*h,\hspace{2mm} -1+k*h$),

($-1+i*h,\hspace{2mm} -1,\hspace{2mm} -1+k*h$),

($-1+i*h,\hspace{2mm} 1,\hspace{2mm} -1+k*h$),

($-1+i*h,\hspace{2mm} -1+j*h,\hspace{2mm} -1$),

($-1+i*h,\hspace{2mm} -1+j*h,\hspace{2mm} 1$),

where $h$ is const, $i = 0,1,2,...,2/h, \hspace{2mm} j = 0,1,2,...,2/h,\hspace{2mm} k = 0,1,2,...,2/h$.

Let's pass in review the foolowing vectors: $(0,0,0)$ is the beginning of each vector and the end of the vector is points that was written above.

It's necessary to find formula for mimimal positive (nonnegative) value of cosine of the angle between two vectors $(a,b,c)$ and $(d,e,f)$, where $|a-d| \leq h, |b-e| \leq h, |c-f| \leq h$ (for example, $a$ can be $d$, $d+h$ or $d-h$ only).

Const $h$ is such than $2/h$ is integer always.

And I repeat again, I'm interested in analytical solution.

-
You can factor $h$ out of $f$ entirely. You can write $f$ as $\frac{<(i,j,k),(a,b,c)>}{||(i,j,k)|| \; ||(a,b,c)||}$. So it comes down to minimizing the cosine of the angle between $(i,j,k)$ and $(a,b,c)$. – copper.hat May 8 '12 at 16:40
Of course, $f$ is not defined at $0$. I would suspect that choosing something like $(i,j,k) = (1,0,0)$ and $(a,b,c) = (0,1,0)$ would give you the minimum which I suspect is $0$. – copper.hat May 8 '12 at 16:56

1. You should not change the problem statement so much that the existing answer no longer connects to it.

2. The problem boils down to minimizing the angle between $\mathbf v$ and $\mathbf v+\mathbf w$ where $\mathbf w$ is restricted to have coordinates $\pm h$ or $0$. On geometric grounds, we should seek the shortest $\mathbf v$ and longest $\mathbf w$. Such as: $\mathbf v = (1,0,0)$ and $\mathbf w = (-h,h,h)$.

-

The analytical solution is $0$.

You can factor $h$ out of the $f$ to get $$f((i,j,k),(a,b,c)) = \frac{<(i,j,k),(a,b,c)>}{||(i,j,k)|| \; ||(a,b,c)||}$$ Since all of $(i,j,k),(a,b,c)$ are non-negative, then $f \geq 0$ also.

Since $f((1,0,0), (0,1,0)) = 0$, this is a solution to the problem.

-