Robust optimization for models with uncertain SOC and SDP constraints

J. Zhen, F.J.C.T. de Ruiter, Ernst Roos, Dick den Hertog

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints with
an ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem can then (approximately) be solved by using adjustable robust linear optimization techniques. For example, we show that if linear decision rules are used, then the final robust counterpart consists of SOC or SDP constraints, respectively, which have the same computational complexity as the nominal version of the original constraints. We propose an efficient method to obtain good lower bounds. Moreover, we extend our approach to other classes of robust optimization problems, such as nonlinear problems that contain waitand-see variables or linear problems that contain bilinear uncertainty. Numerically, we apply our approach to reformulate the problem on finding the minimum volume circumscribing ellipsoid of a polytope, and solve
the resulting reformulation with linear and quadratic decision rules as well as Fourier-Motzkin elimination. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it with the state-ofthe-art copositive approach. Moreover, we apply the proposed approach to a robust regression problem and a robust sensor network problem, and use linear decision rules to solve the resulting adjustable robust linear optimization problems, which solves the problem to (near) optimality.
Original languageEnglish
JournalINFORMS Journal on Computing
Publication statusAccepted/In press - Aug 2020

Keywords

  • robust optimization
  • second-order cone
  • semidefinite programming
  • adjustable robust optimization
  • linear decision rules

Fingerprint Dive into the research topics of 'Robust optimization for models with uncertain SOC and SDP constraints'. Together they form a unique fingerprint.

Cite this