Journal
OPTIMIZATION LETTERS
Volume 17, Issue 3, Pages 771-788Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s11590-022-01929-y
Keywords
Semidefinite programming; Pareto optimality; Robust optimization
Ask authors/readers for more resources
This paper introduces the application of Pareto efficiency to robust linear programming and generalizes this concept to robust optimization problems in Euclidean spaces with uncertainty. Additionally, it demonstrates the value of this approach through exemplary cases in the field of robust semidefinite programming. Furthermore, the paper modifies a famous algorithm to improve the approximation guarantee in non-worst-case scenarios for the robust max-cut problem.
Pareto efficiency for robust linear programs was introduced by Iancu and Trichakis in [Manage Sci 60(1):130-147, 9]. We generalize their approach and theoretical results to robust optimization problems in Euclidean spaces with affine uncertainty. Additionally, we demonstrate the value of this approach in an exemplary manner in the area of robust semidefinite programming (SDP). In particular, we prove that computing a Pareto robustly optimal solution for a robust SDP is tractable and illustrate the benefit of such solutions at the example of the maximal eigenvalue problem. Furthermore, we modify the famous algorithm of Goemans and Williamson [Assoc Comput Mach 42(6):1115-1145, 8] in order to compute cuts for the robust max-cut problem that yield an improved approximation guarantee in non-worst-case scenarios.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available