Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.02123 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929525471838208 |
|---|---|
| author | Hao, Hao Zhang, Peter |
| author_facet | Hao, Hao Zhang, Peter |
| contents | Robust optimization provides a principled and unified framework to model many problems in modern operations research and computer science applications, such as risk measures minimization and adversarially robust machine learning. To use a robust solution (e.g., to implement an investment portfolio or perform robust machine learning inference), the user has to a priori decide the trade-off between efficiency (nominal performance) and robustness (worst-case performance) of the solution by choosing the uncertainty level hyperparameters. In many applications, this amounts to solving the problem many times and comparing them, each from a different hyperparameter setting. This makes robust optimization practically cumbersome or even intractable. We present a novel procedure based on the proximal point method (PPM) to efficiently approximate many Pareto efficient robust solutions at once. This effectively reduces the total compute requirement from $N \times T$ to $2 \times T$, where $N$ is the number of robust solutions to be generated, and $T$ is the time to obtain one robust solution. We prove this procedure can produce exact Pareto efficient robust solutions for a class of robust linear optimization problems. For more general problems, we prove that with high probability, our procedure gives a good approximation of the efficiency-robustness trade-off in random robust linear optimization instances. We conduct numerical experiments to demonstrate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02123 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximating Multiple Robust Optimization Solutions in One Pass via Proximal Point Methods Hao, Hao Zhang, Peter Optimization and Control Robust optimization provides a principled and unified framework to model many problems in modern operations research and computer science applications, such as risk measures minimization and adversarially robust machine learning. To use a robust solution (e.g., to implement an investment portfolio or perform robust machine learning inference), the user has to a priori decide the trade-off between efficiency (nominal performance) and robustness (worst-case performance) of the solution by choosing the uncertainty level hyperparameters. In many applications, this amounts to solving the problem many times and comparing them, each from a different hyperparameter setting. This makes robust optimization practically cumbersome or even intractable. We present a novel procedure based on the proximal point method (PPM) to efficiently approximate many Pareto efficient robust solutions at once. This effectively reduces the total compute requirement from $N \times T$ to $2 \times T$, where $N$ is the number of robust solutions to be generated, and $T$ is the time to obtain one robust solution. We prove this procedure can produce exact Pareto efficient robust solutions for a class of robust linear optimization problems. For more general problems, we prove that with high probability, our procedure gives a good approximation of the efficiency-robustness trade-off in random robust linear optimization instances. We conduct numerical experiments to demonstrate. |
| title | Approximating Multiple Robust Optimization Solutions in One Pass via Proximal Point Methods |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.02123 |