Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


A Scenario Approach for Estimating the Suboptimality of Linear Decision Rules in Two-Stage Robust Optimization


M.J. Hadjiyiannis, P.J. Goulart, D. Kuhn

IEEE Conference on Decision and Control, Orlando, FL, USA

Robust dynamic optimization problems involving adaptive decisions are computationally intractable in general. Tractable upper bounding approximations can be obtained by requiring the adaptive decisions to be representable as linear decision rules (LDRs). In this paper we investigate families of tractable lower bounding approximations, which serve to estimate the degree of suboptimality of the best LDR. These approximations are obtained either by solving a dual version of the robust optimization problem in LDRs or by utilizing an inclusion-wise discrete approximation of the problemís uncertainty set. The quality of the resulting lower bounds depends on the distribution assigned to the uncertain parameters or the choice of the discretization points within the uncertainty set, respectively. We prove that identifying the best possible lower bounds is generally intractable in both cases and propose an efficient procedure to construct suboptimal lower bounds. The resulting instance-wise bounds outperform known worst-case bounds in the majority of our test cases.


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@InProceedings { HadGou:2011:IFA_3929,
    author={M.J. Hadjiyiannis and P.J. Goulart and D. Kuhn},
    title={{A Scenario Approach for Estimating the Suboptimality of
	  Linear Decision Rules in Two-Stage Robust Optimization}},
    booktitle={IEEE Conference on Decision and Control},
    address={Orlando, FL, USA},
Permanent link