Minimum of objective function over set of integers with constraints?

Question

I have the following objective function: \begin{equation} f(i,j,k) = a + b_1 i + b_2 j + b_3 k + \sqrt{(a + b_1 i + b_2 j + b_3 k)^2-d^2}, d\geq 0 \end{equation} Is it possible to analytically find the minimum: \begin{equation} \underset{(i,j,k) \in\mathbb{Z}^3}{\min}f(i,j,k), \,s.t.\, b_1i+b_2j+b_3k \geq \max(-a, d-a) \end{equation} Or do I need to use some kind of iterative algorithm? References discussing problems of the above kind are also welcome.

Answer 1

Let $w=a + b_1 i + b_2 j + b_3 k.$ Your constraint $ b_1i+b_2j+b_3k \geq \max(-a, d-a)$ expands to the two constraints $$ b_1i+b_2j+b_3k \geq -a$$ $$ b_1i+b_2j+b_3k \geq d-a$$ which can be rewritten as $w\ge 0$ and $w \ge d$ respectively. Given the assumption $d\ge 0,$ the second constraint makes the first one redundant.

Now rewrite the objective as minimizing $g(w) = w + \sqrt{w^2 - d^2}.$ (We'll worry about getting from $w$ back to $i,j,k$ later.) The first derivative is $$g^\prime(w)=1 + \frac{w}{\sqrt{w^2 - d^2}}\ge 1,$$so $g()$ is monotonically increasing. Given the requirement that $w\ge d\ge 0,$ you want the smallest $w\ge d$ that can be obtained as an integer-weighted combination of the $b_i$, meaning you can recast the problem as finding $$\min_{(i,j,k)\in \mathbb{Z}^3} a + b_1 i + b_2 j + b_3 k$$ subject to $$a + b_1 i + b_2 j + b_3 k \ge d.$$

I don't know if there is an exact method of solving that (I suspect it would depend on the specific coefficient values), but you could certainly solve it as an integer linear program using a standard ILP solver.