I don’t see why such a “proof of waste” algorithm would be an obstacle to such an optimizer existing. Wouldn’t it just be that for such computational problems,

I don’t see why such a “proof of waste” algorithm would be an obstacle to such an optimizer existing. Wouldn’t it just be that for such computational problems, the optimal implementation would still be rather costly? That doesn’t mean the optimizer failed. If it made the program as efficient as possible, for the computational task it implements, then the optimizer has done its job.