Optimization Online


Robust optimization for models with uncertain SOC and SDP constraints

Jianzhe Zhen (jianzhe.zhen***at***epfl.ch)
Frans J.C.T. de Ruiter (fjctderuiter***at***gmail.com)
Ernst Roos (e.j.roos***at***uvt.nl)
Dick den Hertog (d.denHertog***at***uvt.nl)

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 wait-and-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-of-the-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.

Keywords: Robust optimization, second-order cone, semidefinite programming, adjustable robust optimization, linear decision rules.

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 12/11/2017
Entry Accepted: 12/11/2017
Entry Last Modified: 10/08/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society