Optimization Online


Outlier detection in time series via mixed-integer conic quadratic optimization

Andres Gomez (gomezand***at***usc.edu)

Abstract: We consider the problem of estimating the true values of a Wiener process given noisy observations corrupted by outliers. The problem considered is closely related to the Trimmed Least Squares estimation problem, a robust estimation procedure well-studied from a statistical standpoint but poorly understood from an optimization perspective. In this paper we show how to improve existing mixed-integer quadratic optimization formulations for this problem. Specifically, we convexify the existing formulations via lifting, deriving new mixed-integer conic quadratic reformulations. The proposed reformulations are stronger and substantially faster when used with current mixed-integer optimization solvers. In our experiments, solution times are improved by at least two orders-of-magnitude.

Keywords: Trimmed Least Squares, outlier detection, mixed-integer optimization, conic quadratic optimization, convexification, lifting

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Applications -- Science and Engineering (Statistics )

Citation: Research report AG 19.05, ISE, University of Southern California, November 2019

Download: [PDF]

Entry Submitted: 11/21/2019
Entry Accepted: 11/22/2019
Entry Last Modified: 04/28/2021

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