Lagrangian relaxation is a well known technique for combinatorial optimization and it has recently been successfully applied to various natural language processing tasks (Koo et al., 2010;M.Rush et al., 2010;Chang and Collins, 2011;M.Rush and Collins, 2011).
we first describe word-based methods in detail.