1

The function $f$ maps the positive integer lattice in $\mathbb{R}^n$ (i.e. the vectors in $\mathbb{R}^n$ whose coordinates are all integers) to $\mathbb{R}$. We know that $f$ is convex.

I want to come up with a function $g$ that is a continuation of $f$: that is, $g$ is defined on all of $\mathbb{R}^n_{\ge 0}$, $g$ agrees with $f$ on the integer lattice, and $g$ is convex.

Let $x$ be some positive constant in $\mathbb{R}$. I would also like to be able to find the minimum of $g$ on the box $B = \{v \, | \, 0 \le v_j \le x\}$ in polynomial time.

To summarize, my question:

What technique can I use to create $g$ as a continuation of $f$ such that I can find the minimum of $g$ on $B$ in polynomial time?

By "polynomial time," I mean polynomial time in both $x$ and $n$.

Thanks!

GMB
  • 4,186
  • Detail: An $\epsilon$-approximation is not good enough; I need an exact minimizing point. – GMB Apr 25 '13 at 06:08
  • I'm not even sure if a function that is convex on the lattice always has a convex continuation ... – Hagen von Eitzen Apr 25 '13 at 16:50
  • @HagenvonEitzen I think it does, at least if convexity is understood as the existence of a supporting affine function at every lattice point (i.e., an affine function equal to $f$ at that point and $\le f$ elsewhere). Indeed, the supremum of all supporting affine functions is a convex extension. I don't know anything about polynomial time, though. – ˈjuː.zɚ79365 May 27 '13 at 11:31

0 Answers0