Groupe d’études et de recherche en analyse des décisions


An Analytic Center Self-Concordant Cut Method for the Convex Feasibility Problem


We consider a case of the convex feasibility problem where the set is defined by an infinite number of certain strongly convex self-concordant inequalities. At each iteration, the algorithm adds a self-concordant cut through an approximate analytic center of the current set of localization until a feasible point is found. We show that the algorithm is a fully polynomial approximation scheme.

, 14 pages