<p>The framework of parametric search allows you to do this in many cases. While it was first developed by Meggido for parallel implementation, the idea is more general. Roughly speaking, you start with an oracle $g(x)$ that tells you, given a point $x$, to which side (left or right) the optimum-achieving $x^*$ lies. The idea is to "pretend" to simulate the cost function on the optimal solution. At some point, you're stuck because you don't know which path of a branch to take (since you don't know $x^*$). You identify the breakpoints of this branch, and then using $g$ decide which ones to explore further.</p>

<p>I'm handwaving a lot, because parametric search is quite complicated. <a href="http://www.cs.uu.nl/research/techreps/repo/CS-2002/2002-050.pdf" rel="nofollow">This survey</a> talks about ways of making it practical, and also has a decent explanation of the basic idea. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.4952" rel="nofollow">This older survey</a> gives a number of examples of parametric search. </p>

CC BY-SA 2.5
2011-03-10T20:35:12.797Z
2011-03-10T20:35:12.797Z
Suresh Venkat
<p>Let's say I had an optimization problem</p>

<p>$$ \min_{x \in D} f(x) $$</p>

<p>Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist.</p>

<p>Imagine I had a polynomial time algorithm that - given $f$ - could provide me with an interval for the optimal objective function value $f^*$ using finite numbers $LBD$ and $UBD$ where $LBD &lt; f^* \leq UBD$. </p>

<p>Could I use this to show that the $\epsilon$-evaluation problem can be solved in polynomial time? Here the $\epsilon$-evaluation problem is a problem that for any $\epsilon &gt; 0$ finds a real number $z$ such that $f^* \leq z \leq f^* + \epsilon$. </p>

<p>For the purposes of this problem, we can assume that I have a computer that can store real numbers and perform exact elementary operations with them. </p>

CC BY-SA 2.5
2011-03-10T11:03:38.913Z
You need to be more clear about what you mean by "upper bound recognition problem". Is it: given $l\leq u$, decide if $l \leq f^* \leq u$? Also you should specify the model of computation, is it the Real-RAM (= BSS) model? (if the answer to these is yes then you can efficiently find $f^*$ using binary search).
Kaveh
<ds.algorithms><optimization><computing-over-reals><computable-analysis>
Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?
Berk U.
# Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?

(Asked by: username_0 on 2011-03-10)

Let's say I had an optimization problem

$$ \min\_{x \in D} f(x) $$

Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist.

Imagine I had a polynomial time algorithm that - given $f$ - could provide me with an interval for the optimal objective function value $f^\*$ using finite numbers $LBD$ and $UBD$ where $LBD < f^\* \leq UBD$.

Could I use this to show that the $\epsilon$-evaluation problem can be solved in polynomial time? Here the $\epsilon$-evaluation problem is a problem that for any $\epsilon > 0$ finds a real number $z$ such that $f^\* \leq z \leq f^\* + \epsilon$.

For the purposes of this problem, we can assume that I have a computer that can store real numbers and perform exact elementary operations with them.

**Tags:** ds.algorithms, optimization, computing-over-reals, computable-analysis
> **Comments:**
> **username_1**: You need to be more clear about what you mean by "upper bound recognition problem". Is it: given $l\leq u$, decide if $l \leq f^* \leq u$? Also you should specify the model of computation, is it the Real-RAM (= BSS) model? (if the answer to these is yes then you can efficiently find $f^*$ using binary search).  

---

## 1 answers

### Answer by username_2 on 2011-03-10. Score: 2 | Accepted answer

The framework of parametric search allows you to do this in many cases. While it was first developed by Meggido for parallel implementation, the idea is more general. Roughly speaking, you start with an oracle $g(x)$ that tells you, given a point $x$, to which side (left or right) the optimum-achieving $x^\*$ lies. The idea is to "pretend" to simulate the cost function on the optimal solution. At some point, you're stuck because you don't know which path of a branch to take (since you don't know $x^\*$). You identify the breakpoints of this branch, and then using $g$ decide which ones to explore further.

I'm handwaving a lot, because parametric search is quite complicated. [This survey](http://www.cs.uu.nl/research/techreps/repo/CS-2002/2002-050.pdf) talks about ways of making it practical, and also has a decent explanation of the basic idea. [This older survey](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.4952) gives a number of examples of parametric search.


---

