A nonlinear semidefinite optimization relaxation for the worst-case linear optimization under uncertainties

• 成果类型: Article
• 署名作者: Peng, Jiming; Zhu, Tao
• 署名单位: University of Houston System; University of Houston; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0799-4
• 发表日期: 2015
• 页码: 593-614
• 关键词: robust solutions; complexity; POWER; RISK

摘要

In this paper, we consider the so-called worst-case linear optimization (WCLO) with uncertainties in the right-hand-side of the constraints. Such a problem arises from numerous applications such as systemic risk estimate in finance and stochastic optimization. We first show the problem is NP-hard and present a coarse semidefinite relaxation (SDR) for WCLO. An iterative procedure is introduced to sequentially refine the relaxation model based on the solution of the current relaxation model by simply changing some parameters in the coarse SDR. We show that the sequence of the proposed SDRs will converge to some nonlinear semidefinite optimization problem (SDO). A bi-section search algorithm is proposed to solve the resulting nonlinear SDO. Our preliminary experimental results illustrate that the nonlinear SDR can provide very tight bounds for the original WCLO and is able to locate the exact global solution in most cases within a few iterations on average.