The least-disturbance principle and weak constraints

Certain problems, notably in computer vision, involve adjusting a set of real-valued labels to satisfy certain constraints. They can be formulated as optimisation problems, using the 'least-disturbance' principle: the minimal alteration is made to the labels that will achieve a consistent labelling. Under certain linear constraints, the solution can be achieved iteratively and in parallel, by hill-climbing. However, where 'weak' constraints are imposed on the labels - constraints that may be broken at a cost - the optimisation problem becomes non-convex; a continuous search for the solution is no longer satisfactory. A strategy is proposed for this case, by construction of convex envelopes and by the use of 'graduated' non-convexity.