On the complexity of solving feasibility problems with regularized models

Abstract

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 regularized pth-order model of the sum of squares of the expensive constraints subject to the cheap constraints. Under a Hölder continuity property with constant $\beta \in (0,1]$ on the pth 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(|\log (\epsilon )|{\gamma }^{\zeta (p,\beta )}{\omega }_p^{1+(1/2)\zeta (p,\beta )})$ and evaluation complexity (of the expensive constraints) $O(|\log (\epsilon )|[{\gamma }^{\zeta (p,\beta )}{\omega }_p^{1+(1/2)\zeta (p,\beta )}+(1-\beta )/(p+\beta -1)|\log (\gamma \sqrt{\epsilon })|])$, where $\zeta (p,\beta )=-(p+\beta )/(p+\beta -1)$ and ${\omega }_p=\epsilon$ if p = 1, while ${\omega }_p=\mathrm{\Phi }(x^0)$ if p>1. Moreover, if the derivatives satisfy a Lipschitz condition and a uniform regularity assumption holds, both complexities reduce to $O(|\log (\epsilon )|)$, independently of p.

Keywords:

• Complexity
• feasibility problem
• high order methods

2010 Mathematics Subject Classifications:

• 90C30
• 65K05
• 49M37
• 90C60
• 68Q25

Acknowledgments

The authors are indebted to Prof. Nick Gould for his comments on a first version of this work. The authors are also indebted to the anonymous referees whose comments helped a lot to improve the submitted version of this work.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) (grants 2013/07375-0, 2016/01860-1, and 2018/24293-0) and Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) (grants 302538/2019-4 and 302682/2019-8).

Notes on contributors

E. G. Birgin

E. G. Birgin is a professor in the Department of Computer Science at the Institute of Mathematics and Statistics of the University of São Paulo. He is a member of the editorial boards of Mathematical Programming Computation, Computational Optimization and Applications, Journal of Global Optimization, Springer Nature Operations Research Forum, Computational and Applied Mathematics, International Transactions in Operational Research, Pesquisa Operacional, CLEI Electronic Journal, and Bulletin of Computational Applied Mathematics. He has published over 100 papers on computational optimization and applications.

L. F. Bueno

L. F. Bueno is an associate professor in the Department of Science and Technology at the Federal University of São Paulo in São José dos Campos. He is deputy coordinator of the graduate program in Applied Mathematics. He has been working with operational research, focusing on the development of computational optimization methods and their applications.

J. M. Martínez

J. M. Martínez is a professor in the Department of Applied Mathematics at the University of Campinas, Brazil. He is a member of the Brazilian Academy of Sciences, former Editor in Chief of Computational and Applied Mathematics, member of the editorial board of Numerical Algorithms and Optimization Methods and Software, and the author of over 200 papers on numerical mathematics, optimization, and applications.