Simple algorithms for nonconvex feasibility: analysis and some convergence results

Host Institution:

University of Newcastle

Title of Seminar:

Simple algorithms for nonconvex feasibility: analysis and some convergence results

Speaker's Name:

Robert Hesse

Speaker's Institution:

Institute for Numerical and Applied Mathematics, University of Goettingen

Time and Date:

Friday 5 October, 10.00am (EST)

Seminar Abstract:

CARMA/SigmaOpt/OCANA Seminar

In this talk projection algorithms for solving (nonconvex) feasibility problems in Euclidian spaces are considered. Of special interest are the Method of Alternating Projections (MAP) and the Averaged Alternating Reflection Algorithm (AAR) which cover some of the state of the art algorithms for our intended application, the phase retrieval problem. In the case of convex feasibility, firm nonexpansiveness of projection mappings is a global property that yields global convergence of MAP, and, for consistent problems, AAR. Based on epsilon-delta-regularity of sets (Bauschke, Luke, Phan, Wang 2012) a relaxed local version of firm nonexpansiveness with respect to the intersection is introduced for consistent feasibility problems. This combined with a type of coercivity condition, which relates to the regularity of the intersection, yields local linear convergence of MAP for a wide class of nonconvex problems, and even local linear convergence of AAR in more limited nonconvex settings.

Seminar Convenor:

This email address is being protected from spambots. You need JavaScript enabled to view it.

AGR IT support: