Skip to main content

Oracle-Based Robust Optimization via Online Learning

Author(s): Ben-Tal, Aharon; Hazan, Elad; Koren, Tomer; Mannor, Shie

To refer to this page use:
Abstract: Robust optimization is a common optimization framework under uncertainty when problem parameters are unknown, but it is known that they belong to some given uncertainty set. In the robust optimization framework, a min-max problem is solved wherein a solution is evaluated according to its performance on the worst possible realization of the parameters. In many cases, a straightforward solution to a robust optimization problem of a certain type requires solving an optimization problem of a more complicated type, which might be NP-hard in some cases. For example, solving a robust conic quadratic program, such as those arising in a robust support vector machine (SVM) with an ellipsoidal uncertainty set, leads in general to a semidefinite program. In this paper, we develop a method for approximately solving a robust optimization problem using tools from online convex optimization, where at every stage a standard (nonrobust) optimization program is solved. Our algorithms find an approximate robust solution using a number of calls to an oracle that solves the original (nonrobust) problem that is inversely proportional to the square of the target accuracy.
Publication Date: 2015
Citation: Ben-Tal, Aharon, Elad Hazan, Tomer Koren, and Shie Mannor. "Oracle-Based Robust Optimization via Online Learning." Operations Research 63, no. 3 (2015): pp. 628-638. doi:10.1287/opre.2015.1374
DOI: 10.1287/opre.2015.1374
ISSN: 0030-364X
EISSN: 1526-5463
Pages: 628 - 638
Type of Material: Journal Article
Journal/Proceeding Title: Operations Research
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.