Norm-induced Cuts: Outer Approximation for Lipschitzian Constraint Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911435700830208 |
|---|---|
| author | Göß, Adrian Martin, Alexander Pokutta, Sebastian Sharma, Kartikey |
| author_facet | Göß, Adrian Martin, Alexander Pokutta, Sebastian Sharma, Kartikey |
| contents | In this paper, we consider a finite-dimensional optimization problem minimizing a continuous objective on a compact domain subject to a multi-dimensional constraint function. For the latter, we assume the availability of a global Lipschitz constant. In recent literature, methods based on non-convex outer approximation are proposed for tackling one-dimensional equality constraints that are Lipschitz with respect to the maximum norm. To the best of our knowledge, however, there does not exist a non-convex outer approximation method for a general problem class. We introduce a meta-level solution framework to solve such problems and tackle the underlying theoretical foundations. Considering the feasible domain without the constraint function as manageable, our method relaxes the multidimensional constraint and iteratively refines the feasible region by means of norm-induced cuts, relying on an oracle for the resulting subproblems. We show the method's correctness and investigate the problem complexity. In order to account for discussions about functionality, limits, and extensions, we present computational examples including illustrations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11546 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Norm-induced Cuts: Outer Approximation for Lipschitzian Constraint Functions Göß, Adrian Martin, Alexander Pokutta, Sebastian Sharma, Kartikey Optimization and Control 90C26, 90C30, 90C56, 90C60 In this paper, we consider a finite-dimensional optimization problem minimizing a continuous objective on a compact domain subject to a multi-dimensional constraint function. For the latter, we assume the availability of a global Lipschitz constant. In recent literature, methods based on non-convex outer approximation are proposed for tackling one-dimensional equality constraints that are Lipschitz with respect to the maximum norm. To the best of our knowledge, however, there does not exist a non-convex outer approximation method for a general problem class. We introduce a meta-level solution framework to solve such problems and tackle the underlying theoretical foundations. Considering the feasible domain without the constraint function as manageable, our method relaxes the multidimensional constraint and iteratively refines the feasible region by means of norm-induced cuts, relying on an oracle for the resulting subproblems. We show the method's correctness and investigate the problem complexity. In order to account for discussions about functionality, limits, and extensions, we present computational examples including illustrations. |
| title | Norm-induced Cuts: Outer Approximation for Lipschitzian Constraint Functions |
| topic | Optimization and Control 90C26, 90C30, 90C56, 90C60 |
| url | https://arxiv.org/abs/2403.11546 |