{"id":{"repo_id":"duquesne","oai_identifier":"oai:dsc.duq.edu:etd-2232"},"canonical_url":"https://search.dev.ndltd.org/etd/duquesne/oai:dsc.duq.edu:etd-2232","repository":{"repo_id":"duquesne","name":"Duquesne","base_url":"https://dsc.duq.edu/do/oai/"},"display":{"title":"A No Free Lunch Result for Optimization and Its Implications","abstract":"The No Free Lunch (NFL) theorems for optimization tell us that when averaged over all possible optimization problems the performance of any two optimization algorithms is statistically identical. This seems to imply that there are no \"general-purpose\" optimization algorithms. That is, the NFL theorems show that, mathematically, any superior performance of an optimization algorithm on one set of problems is offset by inferior performance of that algorithm on the set of all other problems. In this thesis we consider the seemingly negative implications of the NFL theorems. We first extend a previous NFL theorem to get a new NFL result. We then use ideas from probability theory and cryptography to show that if we believe that extraordinarily small probability events will not happen, then there exists (at least) one algorithm that is indeed a general-purpose algorithm. Thus, the implications of the new NFL result are not as negative as expected.","abstract_html":"The No Free Lunch (NFL) theorems for optimization tell us that when averaged over all possible optimization problems the performance of any two optimization algorithms is statistically identical. This seems to imply that there are no "general-purpose" optimization algorithms. That is, the NFL theorems show that, mathematically, any superior performance of an optimization algorithm on one set of problems is offset by inferior performance of that algorithm on the set of all other problems. In this thesis we consider the seemingly negative implications of the NFL theorems. We first extend a previous NFL theorem to get a new NFL result. We then use ideas from probability theory and cryptography to show that if we believe that extraordinarily small probability events will not happen, then there exists (at least) one algorithm that is indeed a general-purpose algorithm. Thus, the implications of the new NFL result are not as negative as expected.","abstract_has_math":false,"creators":["Smith, Marisa"],"institution":null,"degree_name":"MS","degree_level":"Immediate Access","degree_discipline":"Computational Mathematics","degree_department":null,"school":null,"contributors":["Jeffrey Jackson","John Kern","Mark Mazur"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-01-01T08:00:00Z","date_published":"2009-01-01T08:00:00Z","updated_at":"2026-07-24T02:10:29Z","subjects":["No Free Lunch (NFL) theorems","optimization","probability theory","learning theory"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://dsc.duq.edu/etd/1216","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jeffrey Jackson","John Kern","Mark Mazur"]},{"key":"dc:creator","label":"Author","values":["Smith, Marisa"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2018-08-03T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computational Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Immediate Access"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["No Free Lunch (NFL) theorems","optimization","probability theory","learning theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://dsc.duq.edu/etd/1216"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The No Free Lunch (NFL) theorems for optimization tell us that when averaged over all possible optimization problems the performance of any two optimization algorithms is statistically identical. This seems to imply that there are no \"general-purpose\" optimization algorithms. That is, the NFL theorems show that, mathematically, any superior performance of an optimization algorithm on one set of problems is offset by inferior performance of that algorithm on the set of all other problems. In this thesis we consider the seemingly negative implications of the NFL theorems. We first extend a previous NFL theorem to get a new NFL result. We then use ideas from probability theory and cryptography to show that if we believe that extraordinarily small probability events will not happen, then there exists (at least) one algorithm that is indeed a general-purpose algorithm. Thus, the implications of the new NFL result are not as negative as expected."]},{"key":"dc:title","label":"Title","values":["A No Free Lunch Result for Optimization and Its Implications"]}]}],"canonical_facts":{"dc:contributor":["Jeffrey Jackson","John Kern","Mark Mazur"],"dc:creator":["Smith, Marisa"],"dc:date.available":["2018-08-03T07:00:00Z"],"dc:description.abstract":["The No Free Lunch (NFL) theorems for optimization tell us that when averaged over all possible optimization problems the performance of any two optimization algorithms is statistically identical. This seems to imply that there are no \"general-purpose\" optimization algorithms. That is, the NFL theorems show that, mathematically, any superior performance of an optimization algorithm on one set of problems is offset by inferior performance of that algorithm on the set of all other problems. In this thesis we consider the seemingly negative implications of the NFL theorems. We first extend a previous NFL theorem to get a new NFL result. We then use ideas from probability theory and cryptography to show that if we believe that extraordinarily small probability events will not happen, then there exists (at least) one algorithm that is indeed a general-purpose algorithm. Thus, the implications of the new NFL result are not as negative as expected."],"dc:identifier":["https://dsc.duq.edu/etd/1216"],"dc:language":["English"],"dc:subject":["No Free Lunch (NFL) theorems","optimization","probability theory","learning theory"],"dc:title":["A No Free Lunch Result for Optimization and Its Implications"],"thesis:degree_discipline":["Computational Mathematics"],"thesis:degree_level":["Immediate Access"],"thesis:degree_name":["MS"]},"updated_at":"2026-07-24T02:10:29Z"}