Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation