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∞. We examine conditions under which these constraints can be relaxed by using dual variables in L1–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’.