Notice that the cost of each matching, M , implicitly depends on the current setting of the weights w. It can be shown that since each c(H, T ; w) involves minimizing M ∈ M, which depends on w, it is not convex.
we can't hope to globally optimize our cost functions over w and must settle for an approximation.