Ph.D Student Shtern Shimrit Robust Tracking via Semidefinite Programming and Noncovex Quadratically Constrained Quadratic Programming Department of Industrial Engineering and Management Professor Emeritus Aharon Ben-Tal Abstract

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.