Discrete analog of the idea that a convex function has a unique minimum

35 Views Asked by At

Formally, I have an optimization problem to find the minimum of $c(n) = h(n) + b(n)$ where $h(n)$ is the cost of the solution to a min-cost flow problem involving moving $n \in \lbrace 0, 1, 2\ldots \rbrace$ units of flow through a fixed network. $b(n) = k (n-n_0)^2$ is a bias term. Due to the structure of the min-cost flow problem, I know that $h(n)$ is a convex function in $n$. By construction $b(n)$ is a convex function in $n$. Therefore, $c(n)$ is a convex function, and thus has a single minimum. I'm relying on this constraint in order to allow to search through $n$ by bisection in order to find the minimum.

The software library I'm using to solve the flow problem requires integer costs in the network. If I "integerize" the edge-costs with a function like $c_{int} = \lfloor K c_{float} \rfloor$ for some $K>>1$, and do the same transformation on the bias function $b(n)$, I end up with an overall objective function that is not convex, indeed $\lfloor K b(n) \rfloor$ itself won't necessarily be a convex function.

Here, it's not so much convexivity than it is the question as "does the objective function have a unique minimum?"

How can I prove that my integerized problem has a single minimum? Due to the possibility for "ties", a minimum would correspond to a contiguous range $n^* = \lbrace k, k+1, \ldots k+m \rbrace$ such that $c(n)=c_{min}$ for $n \in n*$ and $c(k-1)>c(k)$ and $c(k+m+1)>c(k)$