When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?

Ahmadreza Marandi, Dick den Hertog

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Adjustable Robust Optimization (ARO) yields, in general, better worst-case solutions than static Robust Optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we derive conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that if the uncertainty is constraint-wise and the adjustable variables lie in a compact set, then under one of the following sets of conditions robust solutions are optimal for the corresponding (ARO) problem: (i) the problem is fixed recourse and the uncertainty set is compact, (ii) the problem is convex with respect to the adjustable variables and concave with respect to the parameters defining constraint-wise uncertainty. Furthermore, if we have both constraint-wise and nonconstraint-wise uncertainty, under similar sets of assumptions we prove that there is an optimal decision rule for the Adjustable Robust Optimization problem that does not depend on the parameters defining constraint-wise uncertainty. Also, we show that for a class of problems, using affine decision rules that depend on both types of uncertain parameters yields the same optimal value as ones depending solely on the nonconstraint-wise uncertain parameter. Additionally, we provide several examples not only to illustrate our results, but also to show that the assumptions are crucial and omitting one of them can make the optimal worst-case objective values different.
Original languageEnglish
Pages (from-to)555-568
JournalMathematical Programming
Volume170
Issue number2
DOIs
Publication statusPublished - Aug 2018

Fingerprint

Robust Optimization
Optimization Problem
Uncertainty
Uncertain Parameters
Decision Rules
Compact Set

Keywords

  • robust optimization
  • adjustable robust optimization
  • constraint-wise uncertainty
  • hybrid uncertainty

Cite this

@article{36b64ae726454d2e8a93a9ed2deb94e6,
title = "When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?",
abstract = "Adjustable Robust Optimization (ARO) yields, in general, better worst-case solutions than static Robust Optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we derive conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that if the uncertainty is constraint-wise and the adjustable variables lie in a compact set, then under one of the following sets of conditions robust solutions are optimal for the corresponding (ARO) problem: (i) the problem is fixed recourse and the uncertainty set is compact, (ii) the problem is convex with respect to the adjustable variables and concave with respect to the parameters defining constraint-wise uncertainty. Furthermore, if we have both constraint-wise and nonconstraint-wise uncertainty, under similar sets of assumptions we prove that there is an optimal decision rule for the Adjustable Robust Optimization problem that does not depend on the parameters defining constraint-wise uncertainty. Also, we show that for a class of problems, using affine decision rules that depend on both types of uncertain parameters yields the same optimal value as ones depending solely on the nonconstraint-wise uncertain parameter. Additionally, we provide several examples not only to illustrate our results, but also to show that the assumptions are crucial and omitting one of them can make the optimal worst-case objective values different.",
keywords = "robust optimization, adjustable robust optimization, constraint-wise uncertainty, hybrid uncertainty",
author = "Ahmadreza Marandi and {den Hertog}, Dick",
year = "2018",
month = "8",
doi = "10.1007/s10107-017-1166-z",
language = "English",
volume = "170",
pages = "555--568",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent? / Marandi, Ahmadreza; den Hertog, Dick.

In: Mathematical Programming , Vol. 170, No. 2, 08.2018, p. 555-568.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?

AU - Marandi, Ahmadreza

AU - den Hertog, Dick

PY - 2018/8

Y1 - 2018/8

N2 - Adjustable Robust Optimization (ARO) yields, in general, better worst-case solutions than static Robust Optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we derive conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that if the uncertainty is constraint-wise and the adjustable variables lie in a compact set, then under one of the following sets of conditions robust solutions are optimal for the corresponding (ARO) problem: (i) the problem is fixed recourse and the uncertainty set is compact, (ii) the problem is convex with respect to the adjustable variables and concave with respect to the parameters defining constraint-wise uncertainty. Furthermore, if we have both constraint-wise and nonconstraint-wise uncertainty, under similar sets of assumptions we prove that there is an optimal decision rule for the Adjustable Robust Optimization problem that does not depend on the parameters defining constraint-wise uncertainty. Also, we show that for a class of problems, using affine decision rules that depend on both types of uncertain parameters yields the same optimal value as ones depending solely on the nonconstraint-wise uncertain parameter. Additionally, we provide several examples not only to illustrate our results, but also to show that the assumptions are crucial and omitting one of them can make the optimal worst-case objective values different.

AB - Adjustable Robust Optimization (ARO) yields, in general, better worst-case solutions than static Robust Optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we derive conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that if the uncertainty is constraint-wise and the adjustable variables lie in a compact set, then under one of the following sets of conditions robust solutions are optimal for the corresponding (ARO) problem: (i) the problem is fixed recourse and the uncertainty set is compact, (ii) the problem is convex with respect to the adjustable variables and concave with respect to the parameters defining constraint-wise uncertainty. Furthermore, if we have both constraint-wise and nonconstraint-wise uncertainty, under similar sets of assumptions we prove that there is an optimal decision rule for the Adjustable Robust Optimization problem that does not depend on the parameters defining constraint-wise uncertainty. Also, we show that for a class of problems, using affine decision rules that depend on both types of uncertain parameters yields the same optimal value as ones depending solely on the nonconstraint-wise uncertain parameter. Additionally, we provide several examples not only to illustrate our results, but also to show that the assumptions are crucial and omitting one of them can make the optimal worst-case objective values different.

KW - robust optimization

KW - adjustable robust optimization

KW - constraint-wise uncertainty

KW - hybrid uncertainty

U2 - 10.1007/s10107-017-1166-z

DO - 10.1007/s10107-017-1166-z

M3 - Article

VL - 170

SP - 555

EP - 568

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -