Constraint violation and efficiency in search
Another example is interior-point algorithms for convex optimizations, which (if I remember correctly) start at an arbitrary point and try to simultaneously get into the feasible region and optimize the objective function. They are provable and (to some extent) practically faster than the simplex algorithm (and related algorithms like the criss-cross algorithm), which does a local search inside the feasible polytope.