Decision vs Optimization version for Problems of two Parameters

Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.

Now the corresponding decision problem $foo(M)$ would be:
Is there a solution to foo with quality at least $M$ of size $k$.

For problems on one parameter (for example vertex cover) it is obvious that solving the optimization problem sovles the decision problem.

But here I do not see such a correspondance between the $k$-foo optimization problem and the $foo(M)$ decision problem. How does for example showing that $foo(M)$ is NP-hard implies that $k$-foo is NP-hard?

The $k$-center problem is an example of such a problem where the decision version takes the radius as input and asks wether a solution of size $k$ exists.

Having more than one input doesn't change anything:

Consider an optimization problem $MinQ$:


Input: $x, k$

Output: find $y$ satisfying $Q(x,k,y)$ which minimizes $f(x,k,y)$:
$$g(x,k) = \min_{y : Q(x,k,y)} f(x,k,y)$$

The corresponding decision problem $Q$ is:


Input: $x, k, l$

Query: is there a $y$ satisfying $Q(x,k,l)$ such that $f(x,k,y) \leq l$?

To solve the decision problem,
we can solve the optimization problem,
then check if the output is less than $l$.
I.e. there is a very easy reduction from $Q$ to $MinQ$:


input: $x,k,l$

1. $m = MinQ(x,k)$

2. return $m \leq k$

StackExchange Computer Science Q#11589, answer score: 2