On the complexity of solving feasibility problems

L. F. Bueno(lfelipebuenogmail.com)
J. M. Martínez(martinezime.unicamp.br)

Abstract: 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.

Keywords: Complexity, Feasibility problem, First order methods, Reliable estimations

Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: November 2018

Download: [PDF]

Entry Submitted: 11/17/2018
Entry Accepted: 11/17/2018
Entry Last Modified: 11/17/2018

Modify/Update this entry