Oracle-Based Robust Optimization via Online Learning

Oracle-Based Robust Optimization via Online Learning

0.00 Avg rating0 Votes
Article ID: iaor20164669
Volume: 63
Issue: 3
Start Page Number: 628
End Page Number: 638
Publication Date: Jun 2015
Journal: Operations Research
Authors: , , ,
Keywords: learning, internet, networks, programming: quadratic, statistics: regression, heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.