Semi definite programming approach for robust tracking

S. Shtern, A. Ben-Tal

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)


Tracking problems are prevalent in the present day GPS and video systems. The problem of target tracking is a specific case of dynamic linear system estimation with additive noise. The most widely used filter for these systems is the Kalman filter (KF). The optimality of the KF and similar Bayesian filters is guaranteed under particular probabilistic assumptions. However, in practice, and specifically in applications such as tracking, these probabilistic assumptions are not realistic; indeed, the system noise is typically bounded and in fact might be adversarial. For such cases, robust estimation approaches, such as H∞ filtering and set-value estimation, were introduced with the aim of providing filters with guaranteed worst case performance. In this paper we present an innovative approximated set-value estimator (SVE) which is obtained through a semi-definite programming problem. We demonstrate that our problem is practically tractable even for long time horizons. The framework is extended to include the case of partially statistical noise, thus combining the KF and SVE frameworks. A variation of this filter which applies a rolling window approach is developed, achieving fixed computational cost per-iteration and coinciding with the classical SVE when window size is one. Finally, we present numerical results that show the advantages of this filter when dealing with adversarial noise and compare the performance of the various robust filters with the KF.
Original languageEnglish
Pages (from-to)615-656
JournalMathematical Programming
Issue number1
Publication statusPublished - Mar 2016
Externally publishedYes


  • robust optimization
  • semidefinite programming
  • estimation of linear systems


Dive into the research topics of 'Semi definite programming approach for robust tracking'. Together they form a unique fingerprint.

Cite this