Global optimization: a machine learning approach
Many approaches for addressing global optimization problems typically rely on relaxations of nonlinear constraints over specific mathematical primitives. This is restricting in applications with constraints that are implicit or consist of more general primitives. Trying to address such limitations,...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2024
|
| Online Access: | https://hdl.handle.net/1721.1/157394 |
| _version_ | 1824458348498518016 |
|---|---|
| author | Bertsimas, Dimitris Margaritis, Georgios |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Bertsimas, Dimitris Margaritis, Georgios |
| author_sort | Bertsimas, Dimitris |
| collection | MIT |
| description | Many approaches for addressing global optimization problems typically rely on relaxations of nonlinear constraints over specific mathematical primitives. This is restricting in applications with constraints that are implicit or consist of more general primitives. Trying to address such limitations, Bertsimas and Ozturk (2023) proposed OCTHaGOn as a way of solving very general global optimization problems by approximating the nonlinear constraints using hyperplane-based decision-trees and then using those trees to construct a unified MIO approximation of the original problem. We provide extensions to this approach, by (i) approximating the original problem using other MIO-representable ML models besides decision trees, such as gradient boosted trees, multi layer perceptrons and suport vector machines (ii) proposing adaptive sampling procedures for more accurate ML-based constraint approximations, (iii) utilizing robust optimization to account for the uncertainty of the sample-dependent training of the ML models, (iv) leveraging a family of relaxations to address the infeasibilities of the final MIO approximation. We then test the enhanced framework in 81 global optimization instances. We show improvements in solution feasibility and optimality in the majority of instances. We also compare against BARON, showing improved optimality gaps and solution times in more than 9 instances. |
| first_indexed | 2025-02-19T04:24:28Z |
| format | Article |
| id | mit-1721.1/157394 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:24:28Z |
| publishDate | 2024 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1573942025-01-05T04:23:25Z Global optimization: a machine learning approach Bertsimas, Dimitris Margaritis, Georgios Sloan School of Management Massachusetts Institute of Technology. Operations Research Center Many approaches for addressing global optimization problems typically rely on relaxations of nonlinear constraints over specific mathematical primitives. This is restricting in applications with constraints that are implicit or consist of more general primitives. Trying to address such limitations, Bertsimas and Ozturk (2023) proposed OCTHaGOn as a way of solving very general global optimization problems by approximating the nonlinear constraints using hyperplane-based decision-trees and then using those trees to construct a unified MIO approximation of the original problem. We provide extensions to this approach, by (i) approximating the original problem using other MIO-representable ML models besides decision trees, such as gradient boosted trees, multi layer perceptrons and suport vector machines (ii) proposing adaptive sampling procedures for more accurate ML-based constraint approximations, (iii) utilizing robust optimization to account for the uncertainty of the sample-dependent training of the ML models, (iv) leveraging a family of relaxations to address the infeasibilities of the final MIO approximation. We then test the enhanced framework in 81 global optimization instances. We show improvements in solution feasibility and optimality in the majority of instances. We also compare against BARON, showing improved optimality gaps and solution times in more than 9 instances. 2024-10-21T19:58:06Z 2024-10-21T19:58:06Z 2024-10-07 2024-10-13T03:11:58Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/157394 Bertsimas, D., Margaritis, G. Global optimization: a machine learning approach. J Glob Optim (2024). PUBLISHER_CC en https://doi.org/10.1007/s10898-024-01434-9 Journal of Global Optimization Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer US Springer US |
| spellingShingle | Bertsimas, Dimitris Margaritis, Georgios Global optimization: a machine learning approach |
| title | Global optimization: a machine learning approach |
| title_full | Global optimization: a machine learning approach |
| title_fullStr | Global optimization: a machine learning approach |
| title_full_unstemmed | Global optimization: a machine learning approach |
| title_short | Global optimization: a machine learning approach |
| title_sort | global optimization a machine learning approach |
| url | https://hdl.handle.net/1721.1/157394 |
| work_keys_str_mv | AT bertsimasdimitris globaloptimizationamachinelearningapproach AT margaritisgeorgios globaloptimizationamachinelearningapproach |