Tim, thanks for visiting scicomp
! I work in a group that does mixed-integer and non-convex optimization. Although the No Free Lunch Theorem was explained in an informal sense in a non-convex optimization class that I TAed, the typical discussion focused instead on computational complexity. As someone who has done some specialized work in optimization from the computational perspective, I couldn't answer your questions. (Though perhaps one of our other mods, AronAhmadia, might be able to answer them.)
My gut feeling is that questions about the No Free Lunch theorem related to algorithms, such as your first question, are okay. Questions about computational methods and their efficiency are definitely in our scope, although questions on scicomp
tend to be less theoretical.
The second question is probably out of our scope because it does not have an apparent computational application.