Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize.

Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to the optimization problem: calculate the optimal solution and check if it is $\ge k$.

Now, I was wondering, is it always possible to do the reduction (in polynomial time) the other way around?

For an example consider MAX-SAT: to reduce the optimization problem to the decision problem we can do a binary search in the integer range from 0 to the number of clauses. At each stoppage $k$ we check, with the decision problem solver, if there is a solution with $\ge k$.

There are a few conditions you would need to specify for this to even work, most importantly, that your function does have a maximum, otherwise you could try all k and end up going off into infinity. Likewise, you'd probably need to assume that f is only producing outputs on the integers or some other countable set.

If we're doing any sort of binary search, I think it is going to be exponential in the worst case unless we know an upper bound to start with. Assuming f returns numbers, finding the upper bound is going to be linear in terms of the maximum value. However, that means it's exponential in terms of the string-representation of the maximum value.

If we know an upper bound for the maximum of f, I can't see any reason why you couldn't do binary search to find it, but even then, it is polynomial in the upper bound, and could still be exponential in the length of the input, as opposed to the output.

StackExchange Computer Science Q#2983, answer score: 4