  We present a new primal-dual algorithm for computing the value of the
Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing
its nonanticipativity constraints. This dual is widely used in decomposition
methods for the solution of SMIPs. The algorithm relies on the well-known
progressive hedging method, but unlike previous progressive hedging approaches
for SMIP, our algorithm can be shown to converge to the optimal Lagrangian dual
value. The key improvement in the new algorithm is an inner loop of optimized
linearization steps, similar to those taken in the classical Frank-Wolfe
method. Numerical results demonstrate that our new algorithm empirically
outperforms the standard implementation of progressive hedging for obtaining
bounds in SMIP.
