Oracle-Based Robust Optimization via Online Learning

Aharon Ben-Tal (), Elad Hazan (), Tomer Koren () and Shie Mannor ()
Additional contact information
Aharon Ben-Tal: Department of Industrial Engineering and Management, Technion—Israel Institute of Technology, Haifa 3200003 Israel; and Center for Economic Research, Tilburg University, 5037 AB Tilburg, Netherlands
Elad Hazan: Department of Computer Science, Princeton University, Princeton, New Jersey 08544
Tomer Koren: Department of Industrial Engineering and Management, Technion—Israel Institute of Technology, Haifa 3200003 Israel
Shie Mannor: Department of Electrical Engineering, Technion—Israel Institute of Technology, Haifa 3200003 Israel

Operations Research, 2015, vol. 63, issue 3, 628-638

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.

Keywords: robust optimization; online learning; online convex optimization; oracle-based algorithms (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1374 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:63:y:2015:i:3:p:628-638

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().