Back to Search
Start Over
An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation
- Source :
- Computational Optimization and Applications. 80:89-120
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- The worst-case linear optimization (WCLO) with uncertainties in the right-hand-side of the constraints often arises from numerous applications such as systemic risk estimate in finance and stochastic optimization, which is known to be NP-hard. In this paper, we investigate the efficient global algorithm for WCLO based on its nonlinear semidefinite relaxation (SDR). We first derive an enhanced nonlinear SDR for WCLO via secant cuts and RLT approaches. A secant search algorithm is then proposed to solve the nonlinear SDR and its global convergence is established. Second, we propose a new global algorithm for WCLO, which integrates the nonlinear SDR with successive convex optimization method, initialization and branch-and-bound, to find a globally optimal solution to the underlying WCLO within a pre-specified $$\epsilon$$ -tolerance. We establish the global convergence of the algorithm and estimate its complexity. Preliminary numerical results demonstrate that the proposed algorithm can effectively find a globally optimal solution to the WCLO instances.
- Subjects :
- 021103 operations research
Control and Optimization
Linear programming
Applied Mathematics
0211 other engineering and technologies
Initialization
010103 numerical & computational mathematics
02 engineering and technology
01 natural sciences
Computational Mathematics
Nonlinear system
Search algorithm
Convex optimization
Convergence (routing)
Stochastic optimization
Relaxation (approximation)
0101 mathematics
Algorithm
Mathematics
Subjects
Details
- ISSN :
- 15732894 and 09266003
- Volume :
- 80
- Database :
- OpenAIRE
- Journal :
- Computational Optimization and Applications
- Accession number :
- edsair.doi...........43d7c83ebe264937dd6a83ad7c64eaef