3
$\begingroup$

I am currently working on a problem where I have to minimize a $m$-strongly convex function $$f ~: ~\mathbb{R}^n \rightarrow \mathbb{R}^+$$ over a bounded integer lattice, $$L = \mathbb{Z}^n \cap [-10,10]^n \\$$

Let us denote a minimizer of $f$ over $L$ as $$x^*_{\text{int}} \in \underset{x \in L}{\text{argmin}} ~f(x).$$ I am wondering: is it possible to exploit the strong convexity to produce a lower bound on the difference between $f(x^*_{\text{int}})$ and the value of $f$ at any other (suboptimal) point $x \in L$. That is, can we produce a lower bound on the value of:

$$ \min_{x \in V} ~f(x) - f(x^*_{\text{int}})$$

where, $$V = L \setminus \underset{x\in L}{\text{argmin}} ~f(x)$$

I suspect that that answer is yes, but I am having difficulty deriving the bound. Aside from strong convexity, some other facts that may help are that:

  • $\|x-x^*_{\text{int}}\| \geq 1 $ for all for all points $x \in V$
  • $f$ is infinitely differentiable over $\mathbb{R}^d$
  • $f$ has Lipschitz continuous gradient over $L$
$\endgroup$
2
  • $\begingroup$ I think you mean $x_{int}^* \in \arg\min_{x\in L} f(x)$, rather than $\arg\min_{x \in S}$. $\endgroup$
    – Michael
    Sep 2, 2015 at 21:39
  • $\begingroup$ @Michael Yeap! Fixed. $\endgroup$
    – Berk U.
    Sep 3, 2015 at 0:03

1 Answer 1

3
$\begingroup$

Unfortunately, no. Here is an example for $n=1$ (1-dimension). For parameters $m>0$, $b\in\mathbb{R}$ define:
$$f(x) = (m/2)(x-b)^2 $$ For any $b \in \mathbb{R}$, this function $f$ is strongly convex with modulus $m$.

Now fix $\epsilon \in (0, 1/2)$ and define $b = 1/2 - \epsilon$. Then the minimizer of $f(x)$ over the integers is $x^*_{int} = 0$, and: $$ f(1) - f(0) = (m/2)(1/2+\epsilon)^2 - (m/2)(1/2-\epsilon)^2 = m \epsilon$$ and this value can be arbitrarily small (for fixed $m$) by choosing $\epsilon$ arbitrarily small.


You can generalize to $n$ dimensions by defining: $$f(x_1, \ldots, x_n) = \sum_{i=1}^n (m/2)(x_i-b)^2 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.