Algorithms for convex feasibility problems

27 Aug 2014. NUS researchers discovered a new algorithm for feasibility problems which accelerates present calculations.

Optimization is pervasive in many areas in industry and academia. Optimization algorithms try to find an optimal point in a feasible set. The convex feasibility problem is the problem of finding a point in the feasible set. Solving the underlying convex feasibility problem is an end in itself in some machine learning and imaging problems. In other cases, solving the convex feasibility problem is a necessary first step in an optimization algorithm.

The alternating projection algorithm, as its name suggests, tries to find a point in the intersection of a small number of closed convex sets by projecting onto these sets in some order. Its low cost per iteration makes it more suitable for large scale problems than other classical algorithms.

Professor Jeffrey PANG from the Department of Mathematics in NUS has discovered ways to accelerate the alternating projection method using two key observations. The projection onto a convex set generates a supporting half-space, and the problem of projecting onto the intersection of a small number of such half-spaces is a quadratic program that can be easily solved with established techniques (see Figure). Such methods reduce to the Newton method and achieve fast convergence when the boundaries of the sets are well behaved, and also have provable fast convergence properties.

Image shows the projection onto x1 and x2 generates two supporting half-spaces of the closed convex sets K1 and K2. The projection of x2 onto the intersection of these half-spaces gives x4, which is closer to the intersection than the next iterate of the alternating projection algorithm x3. (Image credit: Jeffrey PANG)

Reference

PANG CHJ. “Set intersection problems: supporting hyperplanes and quadratic programming.” Mathematical Programming. 2014