Ph.D Student | Shimrit Shtern |
---|---|

Subject | Robust Tracking via Semidefinite Programming and Noncovex Quadratically Constrained Quadratic Programming |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Emeritus Ben-Tal Aharon |

Full Thesis text |

A tracking system aims at revealing
properties of moving objects, such as location, velocity, size etc., through
sensor measurements. Tracking takes place in both civilian GPS and video
security systems, as well as military missile warning and interception, and
border surveillance systems. The problem of target tracking is a specific case
of estimation of the state of a dynamic linear system contaminated with
additive noise. There are two approaches to the estimation problem, the *Bayesian
approach* which assumes probabilistic noise, and the *robust approach*
which assumes unknown but bounded noise. The Kalman Filter (KF) is a Bayesian
filter, which is widely used in tracking systems; under the assumption that the
moments of the noise vector are known, the KF is the optimal linear filter,
minimizing the expected square error. However, in situations of *adversarial*
target tracking, i.e., when the target deliberately attempts to hide from the
tracker, the robust estimation approach is perhaps more appropriate. Filters
derived using this approach are designed to have a good worst-case performance.
Such filters include *set-value estimators* (SVE), which provide sets that
are guaranteed to contain the true state vector. The classical SVEs are derived
by dynamic programming and ``set calculus", their estimate depending only
on the most recent measurement. The resulting estimation set tightness may be
unknown or may depend on the measurements realization.

Alternatively, we apply the robust
optimization approach, and derive the Greedy *Affinely Adjustable Robust
Filter* (GAARF), which is in fact an innovative SVE, as a solution for the
underlying uncertain problem. To obtain this filter, a solution to a nonconvex
quadratically constrained quadratic problem (QCQP) with block-separable
constraints is required. The later problem is generally an NP-Hard one,
therefore, we focus on algorithms which approximate the optimal solution. One
such algorithm is the *Block Optimal Descent* (BOD) algorithm, which is
based on iteratively solving block sub-problems. These subproblems are globally
solvable due to their hidden convexity. We prove that the BOD method with a
specific initialization provides a 1/Ö2m-approximation, and has sublinear
rate of convergence. Additionally, we look at the SDP relaxation of the QCQP,
whose optimal solution is known to be a 2/p-approximation, and show that it can be efficiently solved by
a specially designed interior point algorithm. The GAARF is then attained by
using this relaxation, and minimizing the resulting estimation set’s size. We
prove that, though our formulation considers the entire measurement history,
the problem can still be solved efficiently, even for long time horizons.
Furthermore, the Rolling-GAARF (RGAARF), a variation of the GAARF, which applies
a rolling window approach, is developed to maintain a fixed computational cost
per iteration. It turns out that the classical SVEs generate sub-optimal
solutions of the same rolling window problem using a window size equal to one.

Numerical experiments demonstrate the advantages of GAARF over both the KF and the classical SVEs when dealing with adversarial noise, and that RGAARF, with an appropriately chosen window size, has similar performance to GAARF while significantly reducing the computational cost.