Complexity Results and Active-Set Identification of a Derivative-Free Method for Bound-Constrained Problems

In this paper, we analyze a derivative-free line search method designed for bound-constrained problems. Our analysis demonstrates that this method exhibits a worst-case complexity comparable to other derivative-free methods for unconstrained and linearly constrained problems. In particular, when minimizing a function with n variables, we prove that at most O(nϵ-2) iterations are needed to drive a criticality measure below a predefined threshold ϵ, requiring at most O(n2ϵ-2) function evaluations. We also show that the total number of iterations where the criticality measure is not below ϵ is upper bounded by O(n2ϵ-2). Moreover, we investigate the method capability to identify active constraints at the final solutions. We show that, after a finite number of iterations, all the active constraints satisfying the strict complementarity condition are correctly identified.