On the complexity of solving feasibility problems

We consider feasibility problems defined by a set of constraints that exhibit gradient H\"older continuity plus additional constraints defined by the affordability of obtaining approximate minimizers of quadratic models onto the associated feasible set. Each iteration of the method introduced in this paper involves the approximate minimization of a two-norm regularized quadratic subject to the affordable constraints. We obtain complexity results regarding the number of iterations and evaluations that are necessary to obtain an approximate KKT point for the problem of minimizing the sum of squares of the first type of constraints subject to the second type of constraints. Such results are a consequence of recent developments on the minimization of functions with H\"older-continuity assumptions. In addition, we show that much stronger results may be obtained when a meaningful non-degeneracy assumption is satisfied. Examples indicate that the estimations so far obtained are reliable.


November 2018



View On the complexity of solving feasibility problems