Optimization Online


An Online-Learning Approach to Inverse Optimization

Andreas Bärmann(Andreas.Baermann***at***math.uni-erlangen.de)
Alexander Martin(Alexander.Martin***at***math.uni-erlangen.de)
Sebastian Pokutta(Sebastian.Pokutta***at***isye.gatech.edu)
Oskar Schneider(Oskar.Schneider***at***fau.de)

Abstract: In this paper, we demonstrate how to learn the objective function of a decision-maker while only observing the problem input data and the decision-maker’s corresponding decisions over multiple rounds. Our approach is based on online learning and works for linear objectives over arbitrary feasible sets for which we have a linear optimization oracle. As such, it generalizes previous approaches based on KKT-system decomposition and dualization. The two exact algorithms we present – based on multiplicative weights updates and online gradient descent respectively – converge at a rate of O(1/sqrt(T)) and thus allow taking decisions which are essentially as good as those of the observed decision-maker already after relatively few observations. We also discuss several useful generalizations, such as the approximate learning of non-linear objective functions and the case of suboptimal observations. Finally, we show the effectiveness and possible applications of our methods in a broad computational study

Keywords: Learning Objective Functions, Online Learning, Multiplicative Weights Update Algorithm, Online Gradient Descent, Mixed-Integer-Programming

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Other Topics (Game Theory )

Category 3: Integer Programming


Download: [PDF]

Entry Submitted: 10/30/2018
Entry Accepted: 10/30/2018
Entry Last Modified: 10/30/2018

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