Optimization Online


Tractable approximation of hard uncertain optimization problems

Ernst Roos (e.j.roos***at***tilburguniversity.edu)
Dick den Hertog (d.denhertog***at***tilburguniversity.edu)
Aharon Ben-Tal (abental***at***technion.ac.il)
Frans de Ruiter (fjctderuiter***at***gmail.com)
Jianzhe Zhen (trevorzhen***at***gmail.com)

Abstract: Robust Optimization is a widespread approach to treat uncertainty in optimization problems. Finding a computationally tractable formulation of the robust counterpart of an uncertain optimization problem is a key step in applying this approach. Techniques for finding a computationally tractable robust counterpart are available for constraints concave in the uncertain parameters. In many problems, however, the uncertain parameters appear in a convex way, which is problematic as no general techniques exist for such problems. In this paper, we provide a systematic way to construct conservative approximations to such problems. Specifically, we reformulate the original problem as an adjustable robust optimization problem in which the nonlinearity of the original problem is captured by the new uncertainty set. This adjustable robust optimization problem is linear whenever the original uncertainty set is polyhedral, which allows for the application of a multitude of techniques from adjustable robust optimization. Additionally, we prove that preprocessing a constraint with a concave transformation that preserves its convexity can tighten the conservative approximation obtained. We subsequently apply our theory to quadratic constraints, constraints that are the sum of maxima and the sum of maxima squared, as well as constraints from geometric programming. We demonstrate the quality of the approximations with a study of geometric programming problems and numerical examples from radiotherapy optimization, which contain a constraint of the sum of maxima squared type.

Keywords: Robust optimization, nonlinear inequality, convex analysis

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 06/27/2018
Entry Accepted: 06/27/2018
Entry Last Modified: 11/09/2020

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