Polling Set Construction and Worst-Case Complexity for Direct Search under Polyhedral Convex Constraints

Direct search is one of the most popular derivative-free optimization (DFO) paradigms. To analyze and implement direct search, one typically relies on positive spanning sets, a quite separate notion from ideas used in the analysis of interpolation sets in model-based DFO. In this talk, we will introduce a new theoretical underpinning for direct-search methods, that is coherent with model-based DFO theory and can be defined for general convex constraints. For polyhedral convex constraints, we are able to construct polling sets that meet our new theoretical requirements and gives some theoretical justification to existing practical heuristics. Our numerical results confirm that adding these extra directions significantly improves practical performance over both existing theoretical poll set constructions and existing heuristics. This is joint with work Clément Royer (Univerité Paris Dauphine-PSL).