A counterexample to De Pierro's conjecture

The convex feasibility problem consists in finding a point in the intersection of a finite family of closed convex sets. When the intersection is empty, a best compromise is to search for a point that minimizes the sum of the squared distances to the sets. In 2001, Alvaro de Pierro conjectured that the limit cycles generated by the \varepsilon-under-relaxed cyclic projection method converge when \varepsilon\downarrow 0 towards a least squares solution. While the conjecture has been confirmed under fairly general conditions, we show that the property is false in general by constructing a system of three compact convex sets in \mathbb{R}^3 for which the \varepsilon-under-relaxed cycles do not converge.

A key feature of this construction is that for any chosen value of \varepsilon\in (0,1] the under-relaxed projections between C_1, C_2 and C_3 converge to the same unique \varepsilon-cycle, no matter what starting point is chosen. This cycle is located in a horisontal plane, with the z-coordinate depending on \varepsilon. As \varepsilon\downarrow 0 these limit cycles oscillate between the planes z=-1 and z=1, and hence contradict the conjecture, as the relevant limit does not exist.

This is joint work with Roberto Cominetti and Andrew Williamson, see arXiv:1801.03216.

Slides from a talk in Ballarat at VADU2018 (19-21 February 2018).