Convex stochastic optimization for random fields on graphs: A method of constructing Lagrange multipliers

The paper analyzes stochastic optimization problems involving random fields on infinite directed graphs. The primary focus is on a problem of maximizing a concave functional of the field subject to a system of convex and linear constraints. The latter are specified in terms of linear operators acting in the space L <Subscript>∞</Subscript>. We examine conditions under which these constraints can be relaxed by using dual variables in L <Subscript>1</Subscript>– stochastic Lagrange multipliers. We develop a method for constructing the Lagrange multipliers. In contrast to the conventional methods employed for such purposes (relying on the Yosida-Hewitt theorem), our technique is based on an elementary measure-theoretic fact, the “biting lemma”. Copyright Springer-Verlag Berlin Heidelberg 2001