Robust Quadratic Programming with Mixed-Integer Uncertainty

Areesh Mittal (), Can Gokalp () and Grani A. Hanasusanto ()
Additional contact information
Areesh Mittal: Graduate Program in Operations Research and Industrial Engineering, University of Texas, Austin, Texas 78705
Can Gokalp: Graduate Program in Operations Research and Industrial Engineering, University of Texas, Austin, Texas 78705
Grani A. Hanasusanto: Graduate Program in Operations Research and Industrial Engineering, University of Texas, Austin, Texas 78705

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 201-218

Abstract: We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S -lemma method—which is valid only in the case of continuous uncertainty—is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.

Keywords: robust optimization; quadratic programming; copositive programming; semidefinite programming (search for similar items in EconPapers)
Date: 2020
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.0901 (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:32:y:2020:i:2:p:201-218

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 ().