2081. Cutting plane algorithms for local exploration in black-box optimization: Heuristics for cut generation
Invited abstract in session WB-35: MINLP 1, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.
Wednesday, 10:30-12:00Room: Michael Sadler LG15
Authors (first author is the speaker)
| 1. | David Alejandro Linan Romero
|
| Mathematics, KTH | |
| 2. | David Ek
|
| Research & Development, LKAB | |
| 3. | Daniel Marjavaara
|
| LKAB | |
| 4. | Anders Forsgren
|
| Department of Mathematics, KTH Royal Institute of Technology | |
| 5. | Jan Kronqvist
|
| Mathematics, KTH Royal Institute of Technology |
Abstract
This work introduces a black-box (BB) cutting plane (BCP) algorithm and provides a computational and theoretical comparison of cut generation techniques that solely rely on BB function evaluations. BCP differs from standard cutting plane methods in the sense that, instead of evaluating a solution candidate and generating a cut for this candidate at each iteration, BCP samples multiple solution candidates within a neighborhood and uses their objective function information to heuristically generate a cut at each iteration. Different heuristics to approximate cuts are compared, including those based on the simplex gradient and its variants. These strategies are tested against a newly proposed cut generation technique that relies on the solution of an auxiliary linear programming (LP) problem that considers the history of previously evaluated objective function values and offers the option to adaptatively update previously generated cuts. Overall, the results show that the proposed cut generation technique allows BCP to find better objective function values, at the expense of requiring extra computational time for the solution of auxiliary LPs. From a practical perspective, the key novelty of this work is the development of an open-source implementation of BCP that gives the user freedom to experiment with different cut generation heuristics. This is desirable in a purely BB context where the mathematical properties of BB functions (e.g., convexity, smoothness) are unknown.
Keywords
- Engineering Optimization
- Algorithms
- Programming, Nonlinear
Status: accepted
Back to the list of papers