Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910022439534592 |
|---|---|
| author | Kitaoka, Akira |
| author_facet | Kitaoka, Akira |
| contents | A data-driven inverse optimization problem (DDIOP) seeks to estimate an objective function (i.e., weights) that is consistent with observed optimal-solution data, and is important in many applications, including those involving mixed integer linear programs (MILPs). In the DDIOP for MILPs, the prediction loss on features (PLF), defined as the discrepancy between observed and predicted feature values, becomes discontinuous with respect to the weights, which makes it difficult to apply gradient-based optimization. To address this issue, we focus on a Lipschitz continuous and convex suboptimality loss. By exploiting its convex and piecewise-linear structure and the interiority of the minimum set, we show that a broad class of gradient-based optimization methods, including projected subgradient descent (PSGD), reaches the minimum suboptimality loss value in a finite number of iterations, thereby exactly solving the DDIOP for MILPs. Furthermore, as a corollary, we show that PSGD attains the minimum PLF in finitely many iterations. We also derive an upper bound on the number of iterations required for PSGD to reach finite convergence, and confirm the finite-step behavior through numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_14273 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods Kitaoka, Akira Machine Learning Artificial Intelligence Optimization and Control 90C90(primary), 90C25, 90C52, 90C11, 90C05, 68Q25 (secondary) A data-driven inverse optimization problem (DDIOP) seeks to estimate an objective function (i.e., weights) that is consistent with observed optimal-solution data, and is important in many applications, including those involving mixed integer linear programs (MILPs). In the DDIOP for MILPs, the prediction loss on features (PLF), defined as the discrepancy between observed and predicted feature values, becomes discontinuous with respect to the weights, which makes it difficult to apply gradient-based optimization. To address this issue, we focus on a Lipschitz continuous and convex suboptimality loss. By exploiting its convex and piecewise-linear structure and the interiority of the minimum set, we show that a broad class of gradient-based optimization methods, including projected subgradient descent (PSGD), reaches the minimum suboptimality loss value in a finite number of iterations, thereby exactly solving the DDIOP for MILPs. Furthermore, as a corollary, we show that PSGD attains the minimum PLF in finitely many iterations. We also derive an upper bound on the number of iterations required for PSGD to reach finite convergence, and confirm the finite-step behavior through numerical experiments. |
| title | Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods |
| topic | Machine Learning Artificial Intelligence Optimization and Control 90C90(primary), 90C25, 90C52, 90C11, 90C05, 68Q25 (secondary) |
| url | https://arxiv.org/abs/2405.14273 |