Easy to optimize but hard to evaluate Are there any known natural examples of optimization problems for which it is much easier to produce an optimal solution than to evaluate the quality of a given candidate solution?

For the sake of concreteness, we may consider polynomial-time solvable optimization problems of the form: "given x, minimize $f(x, y)$", where $f:\{0,1\}^*\times\{0,1\}^* \to \mathbb{N}$ is, say, #P-hard. Such problems clearly exist (for instance, we could have $f(x, 0) = 0$ for all $x$ even if $f$ is uncomputable), but I am looking for ``natural'' problems exhibiting this phenomenon.
Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard.

Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$.

Task: Maximize the number of edges in an $n$-vertex graph under the  constraint that its maximum clique size is at most $k$.

Solution: It is known from extremal graph theory that the optimal graph will be  the Turan graph $T(n,k)$ (see here), which can be easily constructed in polynomial time. On the other hand, checking the quality of a given candidate solution (a given graph) involves checking that its maximum clique size is at most $k$, which is NP-hard.

Note: If we only want to check whether the solution is optimal, then it is easy, because the Turan graph is known to be the unique optimum, so it is enough to compare the candidate graph with the Turan graph, which has a simple structure. On the other hand, if we want to evaluate the quality of a candidate solution, as requested in the question, that is, whether it is feasible and how far it is from the optimum, then we have to check whether it satisfies the maximum clique constraint.