Pith. sign in

REVIEW 2 major objections 3 minor 4 references

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

T0 review · 2 major / 3 minor · reviewed 2026-06-29 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Direct-search methods under polyhedral convex constraints achieve complexity guarantees when polling sets include directions outside the approximate tangent cone.

desk verdict This paper defines new requirements on polling sets that support complexity bounds for constrained direct search and gives explicit constructions for the polyhedral case that force inclusion of directions outside the tangent cone. read the letter →

arxiv 2605.27814 v1 pith:NIMENDVS submitted 2026-05-27 math.OC

Lindon Roberts , Clément W. Royer This is my paper · ORCID
classification math.OC
keywords directsearchderivative-freeoptimizationpolyhedralconstraintspollingsetsworst-casecomplexityconvexconstrained
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces a new theoretical foundation for direct-search derivative-free optimization that applies to general convex constraints and supplies worst-case complexity guarantees comparable to model-based approaches. For polyhedral convex constraints it constructs explicit polling sets that satisfy the required conditions. These sets must contain directions lying outside the approximate tangent cone, which supplies a theoretical basis for practical heuristics that add such directions. Numerical tests show that including the extra directions produces better performance on constrained test problems.

What carries the argument

Polling sets built to satisfy new theoretical requirements for direct search on polyhedral convex constraints; the sets deliver complexity guarantees and force inclusion of directions outside the approximate tangent cone.

What would settle it

A polyhedral test problem and polling set that meets the requirements yet fails to deliver the expected complexity bound, or a controlled experiment showing no performance improvement when the extra directions are added.

Watch

Extended reading notes

Core claim

A new set of requirements on polling directions for direct search under convex constraints enables worst-case complexity analysis. When the constraints are polyhedral, explicit polling sets meeting these requirements can be constructed, and every such set necessarily contains directions outside the approximate tangent cone at the current iterate.

Load-bearing premise

The new requirements on polling sets for general convex constraints can be satisfied by concrete constructions that produce the stated complexity guarantees.

Editorial extensions

If this is right

  • Complexity guarantees hold for any polling set satisfying the new requirements on convex constraints.
  • For polyhedral constraints the required polling sets always contain directions outside the approximate tangent cone.
  • Adding the extra directions improves observed performance on numerical test problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Similar explicit constructions might be found for certain non-polyhedral convex constraints.
  • The framework could narrow the gap between direct-search and interpolation-based methods for constrained problems.
  • Practitioners could adopt these sets when designing algorithms that must balance theory and observed speed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper introduces a new theoretical framework for direct-search methods that applies to general convex constraints and yields worst-case complexity guarantees when polling sets satisfy certain requirements. For the special case of polyhedral convex constraints, explicit constructions of polling sets meeting these requirements are given; these sets necessarily contain directions lying outside the approximate tangent cone. Numerical experiments on test problems confirm that including such directions improves practical performance over standard positive spanning sets.

Significance. If the new requirements are shown to be well-posed and the complexity analysis holds, the work supplies the missing direct-search counterpart to recent unified treatments of model-based methods under constraints. The polyhedral constructions and the explicit justification for directions outside the tangent cone are concrete contributions that both support existing heuristics and open a path to broader theory. Reproducible numerical results and the focus on verifiable constructions strengthen the manuscript.

major comments (2)
  1. [§3.2, Definition 3.3] §3.2, Definition 3.3: the stated requirements on the polling set for general convex constraints must be shown to reduce exactly to the classical positive-spanning-set condition when the feasible set is the whole space; otherwise the complexity claim in Theorem 4.1 does not recover the known unconstrained bound.
  2. [§5.1, Theorem 5.2] §5.1, Theorem 5.2: the proof of the O(1/ε²) complexity bound relies on the existence of a direction in the polling set whose cosine with the negative gradient is bounded away from zero uniformly; the polyhedral construction in Algorithm 5.1 must be verified to guarantee this bound independently of the current iterate and the active-set geometry.
minor comments (3)
  1. [§2.3] Notation for the approximate tangent cone is introduced in §2.3 but used without re-statement in §4; a single displayed definition would improve readability.
  2. [Table 2] Table 2 reports performance ratios but omits the number of function evaluations per successful poll; adding this column would make the practical benefit of the extra directions easier to quantify.
  3. [References] The reference list is missing the 2023 paper by Larson et al. on model-based methods under polyhedral constraints, which is directly comparable.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the recommendation for minor revision. The two major comments identify points where additional clarification will strengthen the manuscript; we address each below and will incorporate the necessary changes.

read point-by-point responses

  1. Referee: [§3.2, Definition 3.3] §3.2, Definition 3.3: the stated requirements on the polling set for general convex constraints must be shown to reduce exactly to the classical positive-spanning-set condition when the feasible set is the whole space; otherwise the complexity claim in Theorem 4.1 does not recover the known unconstrained bound.

    Authors: We agree that the reduction must be verified explicitly. When the feasible set is the whole space the approximate tangent cone coincides with R^n, the normal cone is {0}, and the two requirements in Definition 3.3 collapse precisely to the classical positive-spanning-set condition (every nonzero vector has a positive inner product with at least one polling direction, and the set is finite). Consequently Theorem 4.1 recovers the standard O(1/ε²) bound. We will add a short remark immediately after Definition 3.3 that records this reduction and cites the classical reference. revision: yes

  2. Referee: [§5.1, Theorem 5.2] §5.1, Theorem 5.2: the proof of the O(1/ε²) complexity bound relies on the existence of a direction in the polling set whose cosine with the negative gradient is bounded away from zero uniformly; the polyhedral construction in Algorithm 5.1 must be verified to guarantee this bound independently of the current iterate and the active-set geometry.

    Authors: The proof of Theorem 5.2 invokes the uniform cosine bound only through the properties established for the constructed polling set in Proposition 5.1. Because Algorithm 5.1 augments a positive basis of the tangent cone with a fixed finite set of directions that span the orthogonal complement of every possible active-set subspace (the extreme rays of the dual cone), the minimal cosine is bounded below by a positive constant that depends only on the dimension and the fixed geometry of the polyhedron, not on the current iterate. We will insert a short lemma (new Lemma 5.3) that states this uniform lower bound explicitly and derives it from the construction, thereby making the dependence on the active-set geometry transparent. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: new requirements and constructions are independent of inputs

full rationale

The paper introduces a new theoretical underpinning for direct-search methods under general convex constraints that yields complexity guarantees when polling sets meet stated requirements. For the polyhedral case it supplies explicit constructions. No equation, definition, or claim is shown to reduce by construction to a fitted quantity, self-citation chain, or renamed input; the derivation chain therefore remains self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities visible. The new 'theoretical requirements' on polling sets are introduced but undefined here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polling Set Construction and Worst-Case Complexity for Direct Search under Polyhedral Convex Constraints." pith.science (2026). https://pith.science/paper/NIMENDVS

@misc{pith2026260527814,
  author       = {Pith},
  title        = {Pith review of: Polling Set Construction and Worst-Case Complexity for Direct Search under Polyhedral Convex Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NIMENDVS}},
  note         = {Machine review of arXiv:2605.27814}
}
read the original abstract

Direct search is one of the most popular derivative-free optimization paradigms, that relies on exploring the variable space using polling directions. To analyze and implement direct search, one typically relies on positive spanning sets. This concept is somewhat decorrelated from interpolation-based sets used in model-based algorithms, another class of derivative-free optimization methods. This discrepancy is even more pronounced for constrained problems, where recent advances in the interpolation-based setting have produced a unified picture that is still lacking in the direct-search case. In this paper, we introduce a new theoretical underpinning for direct-search methods, that can be defined for general convex constraints and lead to complexity guarantees, as in the model-based setting. By focusing on polyhedral convex constraints, we are able to construct polling sets that meet our new theoretical requirements. In particular, our polling sets necessarily include directions outside of the approximate tangent cone, giving theoretical justification to existing practical heuristics which incorporate this idea. Our numerical results confirm that adding these extra directions significantly improves practical performance.

Figures

Figures reproduced from arXiv: 2605.27814 by the authors.

Figure 1
Figure 1. Illustration of Example 5.3. A polling set is built by combining generators of [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Data and performance profiles comparing polling set generation using only tangent cone [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Distribution of estimated values Λ/ √ n for polling sets in each iteration of each general linear inequality constrained test problem. Regarding the method in Section 5.3: “Unconstrained” is case 1, “Full rank” is case 2, “Double desc.” is case 3(a), “Normal gens.” is case 3(b), and “Recursive” is case 3(c). In case case, the value of N is how many iterations were in each case across all problems. This is depicted i… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Example issue that can occur using generators of the normal cone as a polling set in case 3(b) [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]
Figure 5
Figure 5. Figure 5: Numerical results split by problem type. [PITH_FULL_IMAGE:figures/full_fig_p025_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

4 extracted references · 2 canonical work pages

  1. [1]

    ,Direct search based on probabilistic feasible descent for bound and linearly constrained problems, Comput. Optim. Appl., 72 (2019), pp. 525–559. [21]M. Hough and L. Roberts,Model-based derivative-free methods for convex-constrained optimization, SIAM J. Optim., 32 (2022), pp. 2552–2579. [22]Q. Huangfu and J. A. J. Hall,Parallelizing the dual revised simp...

    work page arXiv 2019

  2. [2]

    Optim., 17 (2007), pp

    ,Stationarity results for generating set search for linearly constrained optimization, SIAM J. Optim., 17 (2007), pp. 943–968. [26]J. Larson, M. Menickelly, and S. M. Wild,Derivative-free optimization methods, Acta Numer., 28 (2019), pp. 287–404. [27]R. M. Lewis, A. Shepherd, and V. Torczon,Implementing generating set search methods for linearly constrain...

    2007

  3. [3]

    Introduction to Model-Based Derivative-Free Optimization

    ,Pattern search methods for linearly constrained minimization, SIAM J. Optim., 10 (2000), pp. 917–941. [30]S. Lucidi and M. Sciandrone,A derivative-free algorithm for bound constrained mini- mization, Comput. Optim. Appl., 21 (2002), pp. 119–142. [31]J. J. Moré and S. M. Wild,Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20 (2009),...

    work page Pith review arXiv 2000

  4. [4]

    Op- tim., 35 (2025), pp

    ,Model construction for convex-constrained derivative-free optimization, SIAM J. Op- tim., 35 (2025), pp. 622–650. [37]L. Roberts and C. W. Royer,Direct search based on probabilistic descent in reduced spaces, SIAM J. Optim., 33 (2023), pp. 3057–3082. [38]J. Stoer and C. Witzgall,Convexity and Optimization in Finite Dimensions I, Springer-Verlag Berlin, H...

    2025

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.