A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing

Alexander M. Rush, Michael Collins

Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems in na…