Linear programming with stochastic elements: An on-line approach

In this paper, we study linear programming problems with both the cost and right-hand-side vectors being stochastic. Kalman filtering techniques are integrated into the infeasible-interior-point method to develop an on-line algorithm. We first build a ‘noisy dynamic model’ based on the Newton equation developed in the infeasible-interior-point method. Then, we use Kalman filtering techniques to filter out the noise for a stable direction of movement. Under appropriate assumptions, we show a new result of the limiting property of Kalman filtering in this model and prove that the proposed on-line approach is globally convergent to a ‘true value solution’ in the mode of quadratic mean.