Back to Search Start Over

Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties

Authors :
Jiming Peng
Duan Li
Hezhi Luo
Rujun Jiang
Xiaodong Ding
Source :
INFORMS Journal on Computing. 33:180-197
Publication Year :
2021
Publisher :
Institute for Operations Research and the Management Sciences (INFORMS), 2021.

Abstract

In this paper, we consider the so-called worst-case linear optimization (WCLO) with uncertainties on the right-hand side of the constraints. Such a problem often arises in applications such as in systemic risk estimation in finance and stochastic optimization. We first show that the WCLO problem with the uncertainty set corresponding to the [Formula: see text]p-norm ((WCLOp)) is NP-hard for p ɛ (1,∞). Second, we combine several simple optimization techniques, such as the successive convex optimization method, quadratic convex relaxation, initialization, and branch-and-bound (B&B), to develop an algorithm for (WCLO2) that can find a globally optimal solution to (WCLO2) within a prespecified ε-tolerance. We establish the global convergence of the algorithm and estimate its complexity. We also develop a finite B&B algorithm for (WCLO∞) to identify a global optimal solution to the underlying problem, and establish the finite convergence of the algorithm. Numerical experiments are reported to illustrate the effectiveness of our proposed algorithms in finding globally optimal solutions to medium and large-scale WCLO instances.

Details

ISSN :
15265528 and 10919856
Volume :
33
Database :
OpenAIRE
Journal :
INFORMS Journal on Computing
Accession number :
edsair.doi...........6adbc2bd608bfc26c432316a00d62352