Global optimization via optimal decision trees
Abstract The global optimization literature places large emphasis on reducing intractable optimization problems into more tractable structured optimization forms. In order to achieve this goal, many existing methods are restricted to optimization over explicit constraints and objectives...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151167 |
| _version_ | 1826192165263376384 |
|---|---|
| author | Bertsimas, Dimitris Öztürk, Berk |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Bertsimas, Dimitris Öztürk, Berk |
| author_sort | Bertsimas, Dimitris |
| collection | MIT |
| description | Abstract
The global optimization literature places large emphasis on reducing intractable optimization problems into more tractable structured optimization forms. In order to achieve this goal, many existing methods are restricted to optimization over explicit constraints and objectives that use a subset of possible mathematical primitives. These are limiting in real-world contexts where more general explicit and black box constraints appear. Leveraging the dramatic speed improvements in mixed-integer optimization (MIO) and recent research in machine learning, we propose a new method to learn MIO-compatible approximations of global optimization problems using optimal decision trees with hyperplanes (OCT-Hs). This constraint learning approach only requires a bounded variable domain, and can address both explicit and inexplicit constraints. We solve the MIO approximation to find a near-optimal, near-feasible solution to the global optimization problem. We further improve the solution using a series of projected gradient descent iterations. We test the method on numerical benchmarks from the literature as well as real-world design problems, demonstrating its promise in finding global optima efficiently. |
| first_indexed | 2024-09-23T09:07:13Z |
| format | Article |
| id | mit-1721.1/151167 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:07:13Z |
| publishDate | 2023 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1511672024-01-12T18:26:08Z Global optimization via optimal decision trees Bertsimas, Dimitris Öztürk, Berk Sloan School of Management Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Abstract The global optimization literature places large emphasis on reducing intractable optimization problems into more tractable structured optimization forms. In order to achieve this goal, many existing methods are restricted to optimization over explicit constraints and objectives that use a subset of possible mathematical primitives. These are limiting in real-world contexts where more general explicit and black box constraints appear. Leveraging the dramatic speed improvements in mixed-integer optimization (MIO) and recent research in machine learning, we propose a new method to learn MIO-compatible approximations of global optimization problems using optimal decision trees with hyperplanes (OCT-Hs). This constraint learning approach only requires a bounded variable domain, and can address both explicit and inexplicit constraints. We solve the MIO approximation to find a near-optimal, near-feasible solution to the global optimization problem. We further improve the solution using a series of projected gradient descent iterations. We test the method on numerical benchmarks from the literature as well as real-world design problems, demonstrating its promise in finding global optima efficiently. 2023-07-25T19:18:38Z 2023-07-25T19:18:38Z 2023-07-21 2023-07-23T03:11:11Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/151167 Bertsimas, Dimitris and Öztürk, Berk. 2023. "Global optimization via optimal decision trees." PUBLISHER_CC en https://doi.org/10.1007/s10898-023-01311-x Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer US Springer US |
| spellingShingle | Bertsimas, Dimitris Öztürk, Berk Global optimization via optimal decision trees |
| title | Global optimization via optimal decision trees |
| title_full | Global optimization via optimal decision trees |
| title_fullStr | Global optimization via optimal decision trees |
| title_full_unstemmed | Global optimization via optimal decision trees |
| title_short | Global optimization via optimal decision trees |
| title_sort | global optimization via optimal decision trees |
| url | https://hdl.handle.net/1721.1/151167 |
| work_keys_str_mv | AT bertsimasdimitris globaloptimizationviaoptimaldecisiontrees AT ozturkberk globaloptimizationviaoptimaldecisiontrees |