This paper proposes a method for construction of approximate feasible primalsolutions from dual ones for large-scale optimization problems possessingcertain separability properties. Whereas infeasible primal estimates cantypically be produced from (sub-)gradients of the dual function, it is oftennot easy to project them to the primal feasible set, since the projectionitself has a complexity comparable to the complexity of the initial problem. Wepropose an alternative efficient method to obtain feasibility and show that itsproperties influencing the convergence to the optimum are similar to theproperties of the Euclidean projection. We apply our method to the localpolytope relaxation of inference problems for Markov Random Fields anddemonstrate its superiority over existing methods.
展开▼
