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

Hezhi Luo (), Xiaodong Ding (), Jiming Peng (), Rujun Jiang () and Duan Li ()
Additional contact information
Hezhi Luo: Department of Mathematics, College of Science, Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310032, China
Xiaodong Ding: Department of Applied Mathematics, College of Science, Zhejiang University of Technology, Hangzhou, Zhejiang 310032, China
Jiming Peng: Department of Industrial Engineering, University of Houston, Houston, Texas 77204
Rujun Jiang: School of Data Science, Fudan University, Shanghai 200433, China
Duan Li: School of Data Science, City University of Hong Kong, Hong Kong

INFORMS Journal on Computing, 2021, vol. 33, issue 1, 180-197

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 l p -norm ((WCLO p )) 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 (WCLO 2 ) that can find a globally optimal solution to (WCLO 2 ) 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.

Keywords: worst-case linear optimization; successive convex optimization; convex relaxation; branch-and-bound; computational complexity (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0941 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:1:p:180-197

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().