Strengthened SDP relaxation for an extended trust region subproblem with an application to optimal power flow

• 成果类型: Article
• 署名作者: Eltved, Anders; Burer, Samuel
• 署名单位: Technical University of Denmark; University of Iowa
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01737-9
• 发表日期: 2023
• 页码: 281-306
• 关键词: Optimization; constraints

摘要

We study an extended trust region subproblem minimizing a nonconvex function over the hollow ball r <= parallel to x parallel to <= R intersected with a full-dimensional second order cone (SOC) constraint of the form parallel to x - c parallel to <= b(T) x - a. In particular, we present a class of valid cuts that improve existing semidefinite programming (SDP) relaxations and are separable in polynomial time. We connect our cuts to the literature on the optimal power flow (OPF) problem by demonstrating that previously derived cuts capturing a convex hull important for OPF are actually just special cases of our cuts. In addition, we apply our methodology to derive a new class of closed-form, locally valid, SOC cuts for nonconvex quadratic programs over the mixed polyhedral-conic set {x >= 0 : parallel to x parallel to <= 1). Finally, we show computationally on randomly generated instances that our cuts are effective in further closing the gap of the strongest SDP relaxations in the literature, especially in low dimensions.