Oracle-based online robust optimization via online learning

A. Ben-Tal, E. Hazan, T. Koren, Shie Mannor

Research output: Contribution to journalArticleScientificpeer-review

25 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)628-638
JournalOperations Research
Volume63
Issue number3
DOIs
Publication statusPublished - 2015
Externally publishedYes

Keywords

  • robust optimization
  • online learning
  • online convex optimization
  • oracle-based algorithms

Fingerprint Dive into the research topics of 'Oracle-based online robust optimization via online learning'. Together they form a unique fingerprint.

Cite this