# Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?

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.

• 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 Mar 10 '11 at 11:03

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.