Polytope Division Method: A Scalable Sampling Method for Problems with High-dimensional Parameters
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_ | 1866917813334048768 |
|---|---|
| author | Nielen, Evie Tse, Oliver Veroy, Karen |
| author_facet | Nielen, Evie Tse, Oliver Veroy, Karen |
| contents | Configuration Optimization Problems (COPs), which involve minimizing a loss function over a set of discrete points $\boldsymbolγ \subset P$, are common in areas like Model Order Reduction, Active Learning, and Optimal Experimental Design. While exact solutions are often infeasible, heuristic methods such as the Greedy Sampling Method (GSM) provide practical alternatives, particularly for low-dimensional cases. GSM recursively updates $\boldsymbolγ$ by solving a continuous optimization problem, which is typically approximated by a search over a discrete sample set $S \subset P$. However, as the dimensionality grows, the sample size suffers from the curse of dimensionality. To address this, we introduce the Polytope Division Method (PDM), a scalable greedy-type approach that adaptively partitions the parameter space and targets regions of high loss. PDM achieves linear scaling with problem dimensionality and offers an efficient solution approach for high-dimensional COPs, overcoming the limitations of traditional methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17938 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polytope Division Method: A Scalable Sampling Method for Problems with High-dimensional Parameters Nielen, Evie Tse, Oliver Veroy, Karen Numerical Analysis 65K10, 51M20, 65D99, 65N99 Configuration Optimization Problems (COPs), which involve minimizing a loss function over a set of discrete points $\boldsymbolγ \subset P$, are common in areas like Model Order Reduction, Active Learning, and Optimal Experimental Design. While exact solutions are often infeasible, heuristic methods such as the Greedy Sampling Method (GSM) provide practical alternatives, particularly for low-dimensional cases. GSM recursively updates $\boldsymbolγ$ by solving a continuous optimization problem, which is typically approximated by a search over a discrete sample set $S \subset P$. However, as the dimensionality grows, the sample size suffers from the curse of dimensionality. To address this, we introduce the Polytope Division Method (PDM), a scalable greedy-type approach that adaptively partitions the parameter space and targets regions of high loss. PDM achieves linear scaling with problem dimensionality and offers an efficient solution approach for high-dimensional COPs, overcoming the limitations of traditional methods. |
| title | Polytope Division Method: A Scalable Sampling Method for Problems with High-dimensional Parameters |
| topic | Numerical Analysis 65K10, 51M20, 65D99, 65N99 |
| url | https://arxiv.org/abs/2410.17938 |