How does the No free lunch theorem apply in linear programming?

Given a linear Programm.

Calculate the optimal solution.

Then you can calculate with the simplex method the solution in finite steps.

My understand of this theorem is now averaged over all possible linear programm choosing any value for your variables is as good as doing the algorithm.

But you never know if your solution is optimal or even feasible with guessing and your are almost always wrong.

  • $\begingroup$ Can you add some context? I'm not sure what you're asking. $\endgroup$ – Math1000 Jan 16 '15 at 19:27
  • $\begingroup$ Do you need even more context? $\endgroup$ – user3613886 Jan 16 '15 at 21:28

No free lunch means no arbitrage, roughly speaking, as definition can be tricky according to the probability space you're on (discrete of not). See the book of Delbaen and Schachermayer for that. Linear programming can be tought as optimization in the set of choices, and one method for this is the simplex method. No free lunch tells you in this case that there is not better method than guessing. But as @Math1000 write, you could elaborate a bit, but I'm allowing myself to be vague, as your question is vague.

| cite | improve this answer | |
  • $\begingroup$ I want to understand why averaged over all objectives, constraints the simplex method is not better than guessing? $\endgroup$ – user3613886 Jan 16 '15 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.