Busca avançada
Ano de início
Entree


On the complexity of solving feasibility problems with regularized models

Texto completo
Autor(es):
Birgin, E. G. ; Bueno, L. F. ; Martinez, J. M.
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: OPTIMIZATION METHODS & SOFTWARE; v. 37, n. 2, p. 20-pg., 2020-07-11.
Resumo

The complexity of solving feasibility problems is considered in this work. It is assumed that the constraints that define the problem can be divided into expensive and cheap constraints. At each iteration, the introduced method minimizes a regularizedpth-order model of the sum of squares of the expensive constraints subject to the cheap constraints. Under a Holder continuity property with constant beta is an element of(0,1]on thepth derivatives of the expensive constraints, it is shown that finding a feasible point with precision epsilon > 0 or an infeasible point that is stationary with tolerance gamma > 0 of minimizing the sum of squares of the expensive constraints subject to the cheap constraints has iteration complexity O(vertical bar log(epsilon)vertical bar gamma zeta(p,beta)omega(1+(1/2)zeta(p,beta))(p)) and evaluation complexity (of the expensive constraints) O(vertical bar log(epsilon)vertical bar[gamma(zeta(p,beta))omega(1+(1/2)zeta(p,beta)+(1-beta)/(p+beta-1))(p)vertical bar log(gamma epsilon)|]), where zeta(p,beta) = -(p+beta)/(p+beta-1)and omega p = epsilon if p = 1, while omega p = phi(x0) if p > 1. Moreover, if the derivatives satisfy a Lipschitz condition and a uniform regularity assumption holds, both complexities reduce to O(vertical bar log(epsilon)vertical bar), independently of p. (AU)

Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
Beneficiário:Francisco Louzada Neto
Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
Processo FAPESP: 18/24293-0 - Métodos computacionais de otimização
Beneficiário:Sandra Augusta Santos
Modalidade de apoio: Auxílio à Pesquisa - Temático
Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
Beneficiário:Reinaldo Morabito Neto
Modalidade de apoio: Auxílio à Pesquisa - Temático