Solving stochastic programming problems via Kalman filter and affine scaling

Kalman filtering theory has been around for more than two decades and has been the backbone of modern applied stochastic estimation. It is used extensively in many areas including engineering and econometrics. A Kalman filter estimates the states of a system from observations made about the stochastic inputs and outputs of the system. The Kalman filter performs its operations in an attractive recursive fashion, and can be easily implemented on a computer. Kamarkar's algorithm is a relatively recent invention, which is an interior point algorithm to solve linear programming problems. It has been shown to be very effective in solving large linear programs. There are several variants of this algorithm, and the primal affine scaling algorithm is a popular one. This algorithm has also been extended to solve convex programs with linear constraints. A comprehensive treatment of various interior point algorithms has been the main focus of a recent book by Fang and Puthenpura. In this paper, we first establish a parallelism between the Kalman filter and the affine scaling algorithm. This is done by appropriate modeling of the affine scaling algorithm in a state space form and identifying the corresponding elements in a Kalman filter framework. In this case, the stochastic elements of the filter are suppressed to emulate a deterministic system. These ideas have immediate extension to quadratic programming as well. Here several interesting concurrences (both conceptual and computational) between the affine scaling algorithm and the Kalman filter are established. This enables us to derive a unified treatment of both the estimation and the optimization problems. When we activate the stochastic elements of the Kalman filtering theory, we can effectively deal with stochastic linear programming problems. We obtain some theoretical results and a new Kamarkar-based algorithm is developed for this problem. This new approach appears to be very promising for applications in stochastic optimization and control of systems.