LINEAR-PROGRAMMING WITH STOCHASTIC ELEMENTS - AN ONLINE APPROACH

In this paper, we study linear programming problems with both the cost and right-hand-side vectors being stochastic. Kalman filtering techni ques are integrated into the infeasible interior-point method to devel op an on-line algorithm. We first build a ''noisy dynamic model'' base d on the Newton equation developed in the infeasible-interior-point me thod. 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 thi s model and prove that the proposed on-line approach is globally conve rgent to a ''true value solution'' in the mode of quadratic mean.