Worst case complexity of direct search under convexity (Q5962720)

This paper considers directional direct-search methods applied to the unconstrained minimization of a real-valued, convex, and continuously differentiable objective function \(f\). It is proved that the direct-search methods of directional type, based on imposing sufficient decrease to accept new iterates, have the same worst case complexity bound and global rate of the gradient method for the unconstrained minimization of a convex and smooth function. The presented results are derived for convex functions where the supreme distance between any point in the initial level set and the solutions set is bounded. Such property is satisfied when the solutions set is bounded, but it is also met in several instances where the solutions sets are unbounded. It is shown that the number of iterations needed to reduce the norm of the gradient of the objective function below a certain threshold is at most proportional to the inverse of the threshold. It is also shown that the absolute error in the function values decay at a sublinear rate proportional to the inverse of the iteration counter. Finally, it is proved that the sequence of absolute errors of function values and iterates converges \(r\)-linearly in the strongly convex case.