Variable Splitting Methods for Constrained State Estimation in Partially Observed Markov Processes

Rui Gao, Filip Tronarp, Simo Särkkä

Abstract

In this paper, we propose a class of efficient, accurate, and general methods for solving state-estimation problems with equality and inequality constraints. The methods are based on recent developments in variable splitting and partially observed Markov processes. We first present the generalized framework based on variable splitting, then develop efficient methods to solve the state-estimation subproblems arising in the framework. The solutions to these subproblems can be made efficient by leveraging the Markovian structure of the model as is classically done in so-called Bayesian filtering and smoothing methods. The numerical experiments demonstrate that our methods outperform conventional optimization methods in computation cost as well as the estimation performance.

Introduction

State estimation is a fundamental task in robotics, indoor positioning, and target tracking, where the goal is to determine the state of a system (e.g., position and velocity) from noisy sensor measurements. In many real-world scenarios, physical laws or environmental boundaries impose constraints on these states—for instance, a vehicle cannot pass through a wall, or a ship must remain within a navigable channel.

Incorporating these equality and inequality constraints into state-space models significantly increases computational complexity. Traditional "batch" optimization methods, which treat the entire time history as a single high-dimensional vector, suffer from the "curse of dimensionality." As the duration of tracking increases, these methods become prohibitively slow or exceed available memory. This paper introduces a framework that bridges the gap between high-accuracy constrained optimization and the high-speed recursive efficiency of Bayesian filtering.

Methodology

The proposed framework merges variable splitting optimization with the recursive efficiency of Kalman smoothing. The approach follows two main pillars:

  1. Variable Splitting: Algorithms such as the Alternating Direction Method of Multipliers (ADMM), Peaceman–Rachford Splitting (PRS), and the Split Bregman Method (SBM) are used to decouple the complex constrained problem into simpler subproblems. By introducing auxiliary variables, the cost function is separated from the constraints.
  2. Markovian Exploitation: The authors leverage the Markov property of state-space models—where the current state depends only on the previous one—to solve the primary state-update subproblem.

By reformulating the state-update subproblem as a standard state-space model where constraints are treated as "artificial measurements," the authors can employ the Iterated Extended Kalman Smoother (IEKS). This allows the computational cost to grow linearly ($O(T)$) with the number of time steps, a significant improvement over the cubic or higher growth typical of batch methods.

Trajectory estimation showing how the constrained CIEKS-ADMM method respects the physical boundary compared to the unconstrained estimate.

Experimental Results

The framework was evaluated using a simulated four-dimensional ship tracking model involving position, velocity, and a nonlinear inequality constraint representing a geographical boundary.

Scalability and Speed

The proposed methods (CIEKS-PRS, CIEKS-SBM, CIEKS-ADMM) demonstrated remarkable scalability. For a sequence of $10^4$ steps, the CIEKS-SBM method achieved a nearly 80x speedup over traditional batch SBM (26.7 seconds vs. 2,193 seconds). Most notably, while traditional batch methods failed due to memory exhaustion at $10^5$ time steps, the proposed recursive methods successfully processed up to $10^6$ data points.

Comparison of computation time (seconds) across different sequence lengths (T). Batch methods fail at larger scales, while the proposed methods scale linearly.

Accuracy

As shown in the trajectory analysis, unconstrained estimates frequently drift into forbidden zones. In contrast, the constrained estimates produced by the CIEKS-based methods closely follow the ground truth while strictly adhering to the defined physical boundaries.

Conclusion

By treating constraints as pseudo-measurements within a variable splitting framework, this research enables high-fidelity, constrained state estimation for massive datasets. The resulting algorithms are not only more accurate than unconstrained filters but also orders of magnitude faster and more memory-efficient than standard batch optimizers. Future work will explore extending this framework to systems with non-Gaussian noise and jump Markov models.

Summary updated

Abstract

In this paper, we propose a class of efficient, accurate, and general methods for solving state-estimation problems with equality and inequality constraints. The methods are based on recent developments in variable splitting and partially observed Markov processes. We first present the generalized framework based on variable splitting, then develop efficient methods to solve the state-estimation subproblems arising in the framework. The solutions to these subproblems can be made efficient by leveraging the Markovian structure of the model as is classically done in so-called Bayesian filtering and smoothing methods. The numerical experiments demonstrate that our methods outperform conventional optimization methods in computation cost as well as the estimation performance.
BibTeX
@article{gao2020variable,
  author = {Rui Gao and Filip Tronarp and Simo Särkkä},
  title = {{Variable Splitting Methods for Constrained State Estimation in Partially Observed Markov Processes}},
  journal = {IEEE Signal Processing Letters},
  year = {2020},
  url = {https://openreview.net/forum?id=_LLdFsgYeU},
}
Figure