Mesh-dependent iteration count growth in primal-dual active set strategies

Ioannis P. A. Papadopoulos; Michael Hinterm\"uller

Mesh-dependent iteration count growth in primal-dual active set strategies

T0 review · 2 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read The paper proves that the standard primal-dual active set solver, despite superlinear convergence on each fixed mesh, needs exponentially many iterations on refined obstacle problems and loses well-posedness in the continuum limit.

desk verdict Finite-dimensional peeling results and the numerical study are solid, but the infinite-dimensional convergence theorem rests on unproven hypotheses that the abstract and conclusions overstate. read the letter →

arxiv 2607.26622 v2 pith:N5RF3RVH submitted 2026-07-29 math.OC

Ioannis P. A. Papadopoulos , Michael Hintermüller This is my paper · ORCID

classification math.OC MSC 35R3549J4065K1065K1590C3390C53

keywords primal-dualactivesetsemismoothNewtonmethodmeshdependenceobstacleproblemthinSignorinipeelinginfinite-dimensionalconvergence

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 establishes that the widely used primal-dual active set strategy, when applied to discretized variational inequalities, does not converge mesh-independently: as the mesh is uniformly refined, the number of iterations grows without bound. For obstacle problems the growth is exponential—asymptotically doubling per refinement—and the paper proves the mechanism: during the deactivation phase, a node whose whole star patch is active cannot leave the active set in the next iteration, so the active set can only shrink one layer of nodes at a time. For thin-obstacle and Signorini problems the growth is only linear, because active nodes always border inactive nodes, but the paper shows the solver still loses its local superlinear convergence in the infinite-dimensional limit. A global convergence-rate identity ties the speed of the iteration to the size of the dual feasibility violation on the inactive set; in the infinite-dimensional setting this quantity vanishes for the standard obstacle problem, making the iterates ill-defined from the second iteration onward, while for codimension-one obstacles it stays positive and guarantees only sublinear convergence.

What carries the argument

The central mechanism is Theorem 6.2, the 'sticky active sets' result: for a P1 finite-element discretization of the constant-obstacle problem with positive forcing, if a node and all nodes in its star patch (the union of elements touching that node) are active, the node must remain active at the next iteration. This implies the layer-by-layer peeling effect: only boundary nodes of the active set can deactivate, so each iteration removes at most one layer. Complementing it is Theorem 5.3, a global convergence-rate identity stating that the squared energy-distance to the solution decreases exactly by the squared dual feasibility violation of the multiplier on the current inactive set; this ra

What would settle it

On a fine 1D mesh, run the PDAS solver on the constant-obstacle problem and record the active set each iteration. Theorem 6.2 predicts that a node whose two neighbours are active stays active; if any such interior node deactivates, the theorem is false. Alternatively, replace the constant obstacle with a smooth nonconstant one (e.g. phi = 1 + 0.1 sin x) keeping f = 20: if iteration counts stop doubling, the exponential-growth claim depends essentially on the constant-obstacle assumption.

Watch

Extended reading notes

Core claim

The central claim is that the primal-dual active set (PDAS) iteration converges superlinearly on every fixed finite-element mesh, yet the convergence rate is not uniform in the mesh size for obstacle and Signorini problems. For the obstacle problem, Theorem 6.2 shows that a degree of freedom whose entire star patch is active at iteration k must be active at iteration k+1, provided the obstacle is constant and the forcing is strictly positive. Consequently the active set can only shed one layer of nodes per iteration during deactivation, so a uniformly refined problem needs exponentially many iterations; in the limit h→0 the infinite-dimensional iterate is ill-defined from the second iteratio

Load-bearing premise

The exponential-growth claim rests on a theorem that assumes a constant obstacle and strictly positive forcing, and the infinite-dimensional convergence theorem assumes active-set nesting and primal feasibility that are not established by induction; if either premise fails, the paper's headline conclusions do not follow.

Editorial extensions

If this is right

On uniformly refined meshes, naive PDAS solvers for obstacle problems require an iteration count that grows roughly like the number of layers of nodes to peel, i.e. exponentially in the number of refinements, so direct solves become prohibitively expensive.
For thin-obstacle and Signorini problems, iteration counts grow only additively, so the mesh dependence is mild but still present; local superlinear convergence disappears as h→0.
In infinite dimensions, the obstacle-problem PDAS iteration is not merely slow but mathematically ill-defined after the first correction, because the multiplier iterate becomes a measure concentrated on the free boundary.
The convergence-rate identity gives a concrete target for acceleration: reducing the dual feasibility violation on the inactive set is exactly what reduces the contraction factor.
Grid sequencing or multilevel initial guesses can hide the peeling cost by supplying an initial active set close to the true one, but the cost then shifts to solving on every parent mesh.

Reading between the lines

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

Beyond the paper: any PDAS variant whose deactivation step is local in the finite-element stencil—line-search, inexact, or damped versions included—should inherit the same exponential peeling cost on codimension-zero obstacles, a prediction the paper does not test.
Beyond the paper: because the obstacle-problem failure is caused by a multiplier iterate that is a measure, switching multiplier discretization to the primal space should not restore mesh independence; the paper's numerical appendix shows it does not, implying genuinely structural solver changes are needed.
Beyond the paper: the same codimension mechanism may explain the exponential growth the paper reports for state-constrained and H1-control optimal control problems, where the constraint acts on the whole domain rather than a codimension-one set.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

What you should know: this paper documents a real and important phenomenon. HIK/PDAS iteration counts grow under mesh refinement—exponentially for obstacle problems, linearly for Signorini and thin-obstacle problems—and the authors provide reproducible code, clean finite-dimensional proofs, and a convincing explanation via dual-feasibility violation. The layer-by-layer peeling theorem (6.2) and the rate formula (5.3) are genuine contributions.

The experimental core is the strongest part. The tables show the exponential doubling for obstacle problems and the mild additive growth for Signorini, and the convergence plots support the narrative. The software is archived, so the numbers can be checked. That alone justifies a serious referee.

The finite-dimensional analysis is also in good shape. Theorem 5.3 is a neat global rate tied to the norm of the multiplier on the inactive set, and Theorem 6.2—for constant obstacle and positive forcing—cleanly explains why only boundary dofs can deactivate. The proof is self-contained and the intuition (codimension of the active set) is correct.

The soft spot is Theorem 7.7. It assumes A* ⊆ A^k and u^k ≤ φ for the infinite-dimensional iterates, and the proof sends h→0 in the finite-dimensional identity (5.2), which needs the discrete analogues of those assumptions at each k. The paper never proves these by induction. Section 7.1 establishes regularity and well-posedness of the iterates, but not primal feasibility or the active-set inclusion. Proposition 7.2 even uses u^k ≤ φ as an hypothesis to derive the negativity of λ^k. So the claimed sublinear convergence is conditional in a way the abstract and conclusions do not communicate: the conclusion says "we prove that HIK converges at a sublinear rate" without the theorem's qualifiers. This matters because Theorem 7.7 is the linchpin of the infinite-dimensional explanation for the thin-obstacle and Signorini behavior. The earlier remark (7.8) that proving linear rate is open shows the authors are aware of gaps, but the gap here is before that: the asserted sublinear rate itself is not unconditional.

Also minor: the abstract says "for obstacle problems" when Theorem 6.2 covers only constant obstacle and f ≥ c_f > 0. That is overreach but easily fixed in revision.

Overall, the paper deserves peer review. The finite-dimensional theory and numerical evidence are publishable on their own; the infinite-dimensional part needs either proofs of the missing hypotheses or a clearly labeled conditional theorem. A good referee can help sort that out.

Referee Report

2 major / 4 minor

Summary. The paper studies mesh-dependent iteration counts of the primal-dual active set strategy (HIK) on uniformly refined finite-element discretizations of obstacle, thin-obstacle, and Signorini problems. Numerically, obstacle problems show roughly exponential growth (iteration count roughly doubling per refinement), while thin-obstacle and Signorini problems show mild linear growth. The paper offers three theoretical contributions: (i) a finite-dimensional global convergence-rate identity (Theorem 5.3) expressing the HIK contraction factor in terms of the dual-feasibility violation of the current multiplier on the inactive set; (ii) a 'sticky active sets' theorem (Theorem 6.2) asserting that for the constant-obstacle problem a degree of freedom whose whole star patch is active cannot deactivate in one iteration, implying layer-by-layer peeling; and (iii) an infinite-dimensional analysis showing that for the thin obstacle problem the HIK iterates remain well-defined with W^{2,p}×L^q regularity and claiming a guaranteed sublinear convergence rate (Theorem 7.7), whereas for the classical obstacle problem the second multiplier iterate is a singular measure and the next active set is ill-defined. The paper includes reproducible Julia code and extensive numerical tables.

Significance. If the core claims hold, the paper identifies and explains a practically important phenomenon: a supposedly superlinearly convergent active-set solver can lose mesh independence in a problem-dependent way, from mild linear growth to exponential growth, depending on the codimension of the constraint. The finite-dimensional rate identity in Theorem 5.3 is a clean and useful diagnostic, and the distinction between bulk obstacles and codimension-one obstacles is conceptually valuable. The regularity analysis for the thin obstacle problem is nontrivial and appears largely sound. The paper also ships reproducible software, which strengthens its empirical claims. However, the infinite-dimensional transfer and the peeling proof have load-bearing gaps detailed below; the paper is not yet at the level of its abstract and conclusions.

major comments (2)

[§7.1, Theorem 7.7] The proof passes h→0 in the finite-dimensional identity (5.2), but Theorem 5.3 requires A*_h ⊆ A^k_h and u^k_h ≤ φ on the discrete constraint set. Theorem 7.7 assumes only the continuous analogues A* ⊆ A^k and u^k ≤ φ on Γ, and the proof never verifies these discrete hypotheses by induction, nor does it show that the continuous assumptions survive discretization. Lemma 7.5 and Proposition 7.6 transfer regularity and active-set convergence, but not primal feasibility or active-set inclusion. Therefore (7.14)–(7.15) are conditional, and the abstract/conclusion claim that HIK 'converges at a guaranteed sublinear rate' for the thin obstacle problem is not established as written. Proposition 7.2, used to guarantee a nontrivial sublinear rate, has the same unproved hypothesis u^k≤φ.
[§6, proof of Theorem 6.2] The proof asserts 'Aφ=0' from ∇φ_h=0. For the reduced P1 stiffness matrix with homogeneous Dirichlet conditions incorporated, the coefficient vector φ=φ̄ at the interior dofs does not represent the constant function φ̄ on Ω, since the boundary dofs are fixed to zero. Already in 1D, A times the all-ones vector is nonzero at nodes adjacent to the boundary. Hence the elimination of A_{S,A}φ in (6.10) is not justified in general, and the contradiction b_{S^k}≤0 does not follow. The theorem may be salvageable for Problem 1 after the first iteration by restricting to active sets whose star patches avoid ∂Ω, but that restriction is neither stated nor proved.

minor comments (4)

[Abstract and §6] The abstract's 'obstacle problems' is broader than the hypotheses of Theorem 6.2, which assume a constant obstacle and f ≥ c_f > 0. The numerical and theoretical claims should be qualified accordingly.
[§7.1, Proposition 7.6] The Hölder exponent in the boundary-integral estimate appears to be (3q-4)/(4q), not (4q-5)/(4q), and positivity of this exponent requires q > 4/3 rather than q > 5/4. The convergence conclusion is likely repairable with q chosen in (4/3, 8/5), but the displayed estimate is not correct as written.
[Table 2 and §4] The statement 'exponential iteration growth (asymptotically doubling with each refinement)' fits the 1D and 2D obstacle results, but the 3D column (5,7,10,15,27) shows a slower growth pattern. A brief qualification would avoid overstating the observed rate.
[Various] Minor typos: 'W ell-posedness' in §7.1, 'seeminlgly' in §4, 'freedeom' in §8. The PETSc routine name 'vinewtonrsls' in the abstract appears to be intentional but may be confusing to readers not familiar with PETSc.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction in the central derivations; minor reliance on co-authored HIK/M-matrix facts and an unproven induction hypothesis in the infinite-dimensional transfer.

full rationale

The paper's central finite-dimensional results are derived, not fitted. Theorem 6.2 is proved from Lemma 6.4's sparsity identity [A_{N,I^k}v_{I^k}]_i=0 for i in int A^k, the constant-obstacle identity A phi = 0, and load positivity b_i = integral f phi_i dx > 0 under f >= c_f > 0; it does not use the observed iteration counts as inputs. Theorem 5.3's identity (5.2) is obtained by a Schur-complement calculation from the stated hypotheses A* subset A^k and u^k <= phi, so it is a conditional algebraic identity rather than a fitted prediction. The infinite-dimensional divergence for Problem 1 follows from the explicit representation lambda^2 = f|_A1 - [grad u^2] delta_{partial A1} and ||lambda^2||_{H^{-1}(I^1)} = 0, again an independent computation. The paper does cite [29] and [30] (co-authored by a co-author) for HIK/SSN equivalence and M-matrix primal feasibility; these are background facts, externally published, and do not contain the paper's peeling or divergence conclusions, so the self-citation is not load-bearing. The one genuine weakness is in Theorem 7.7: it assumes A* subset A^k and u^k <= phi a.e. on Gamma and does not prove these by induction when passing the finite-dimensional identity (5.2) to h -> 0. This is an omitted verification and a correctness risk for the claimed sublinear rate, but it is not circularity: the rate formula does not reduce to its assumptions by construction. Table 2 is empirical data, not a fitted parameter renamed as a prediction. Overall no circular step is exhibited.

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

No free parameters are fitted: the algorithm constant c=1 is immaterial after the first iterate, and the problem data (E, nu, f, phi, alpha) are chosen model inputs. The analysis relies on standard PDE/FEM background and on explicit structural assumptions about the mesh and the active sets; the most delicate of these are the hypotheses of Theorem 7.7 that are not proven for the infinite-dimensional iteration.

assumptions (8)

domain assumption P1-FEM nodal basis: entrywise box constraints on coefficients imply pointwise box constraints on the finite element function
Invoked in Section 3 to justify the discrete nonsmooth system (3.1) as equivalent to the pointwise-constrained problem; standard for P1 but not for higher-order elements.
domain assumption For P1 obstacle discretizations, A is a symmetric positive-definite Stieltjes matrix, yielding monotonicity u^k <= phi for k >= 2 via [29, Th. 3.2]
Used in Remark 5.2 to apply Theorem 5.3; this is an imported structural result about the stiffness matrix.
domain assumption Problem 1 setup: f >= c_f > 0 a.e. and phi = constant > 0
Needed in the proof of Theorem 6.2 to get node loads b_i > 0 and A phi = 0; the peeling theorem is therefore proven only for this constant-obstacle case.
domain assumption Infinite-dimensional HIK hypotheses for Theorem 7.7: A* subset A^k and u^k <= phi a.e. on Gamma for all k
Stated as hypotheses and used to take the h -> 0 limit of the finite-dimensional rate; not proven by induction for the infinite-dimensional thin-obstacle iteration.
standard math Elliptic regularity toolbox: Brezis regularity for obstacle (u in H^s, s < 5/2); Grisvard crack-tip decomposition giving u^2 in W^{2,p}, p < 4/3, and lambda^2 in L^q, q < 8/5
Imported external theorems in Section 7 that determine whether the multiplier iterates are pointwise defined.
domain assumption Gamma is represented exactly by a straight chain of shared edges in all meshes
Assumed at the start of Section 7.1 so that the discrete and continuous thin obstacles coincide; otherwise the variational-crime estimates in Proposition 7.6 would need modification.
domain assumption The domain is triangulated by a quasi-uniform sequence of simplicial meshes
Assumed in Section 2 for all FEM discretizations; needed for the standard approximation and inverse estimates used in Section 7.
standard math Standard functional-analysis/FEM background: Lax-Milgram, Sobolev embeddings, Strang's lemma, trace and interpolation inequalities
Used throughout Sections 5 and 7 without proof; standard but load-bearing for the convergence transfers.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Mesh-dependent iteration count growth in primal-dual active set strategies." pith.science (2026). https://pith.science/paper/N5RF3RVH

@misc{pith2026260726622,
  author       = {Pith},
  title        = {Pith review of: Mesh-dependent iteration count growth in primal-dual active set strategies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N5RF3RVH}},
  note         = {Machine review of arXiv:2607.26622}
}

read the original abstract

Primal-dual active set strategies (PDAS) are popular iterative solvers for mixed complementarity problems such as constrained optimization problems with pointwise inequality constraints. Examples include the reduced-space active set algorithm vinewtonrsls found in PETSc. When applied to discretized infinite-dimensional problems, PDAS exhibit local superlinear convergence thanks to their equivalence to a semismooth Newton method (SSN). However, for many problem classes the number of iterations, to reach convergence, grows without bound under mesh refinement. In this paper we numerically study PDAS iteration counts on uniformly refined meshes for obstacle problems, Signorini problems, and related models. As the mesh size tends to zero, PDAS applied to Signorini-type problems lose their local superlinear convergence, resulting in linear growth of the iteration count (adding some iterations with each refinement). For obstacle problems, PDAS stagnates, leading to exponential iteration growth (asymptotically doubling with each refinement). We explain these phenomena by (i) proving that, for obstacle problems, nodal degrees of freedom only peel away from the obstacle layer-by-layer during the deactivation phase, (ii) deriving a general global convergence rate for PDAS that depends on the magnitude of dual feasibility violation, and (iii) demonstrating why, in the infinite-dimensional setting, this leads to a well-defined solver, but without local superlinear convergence, for some problems yet divergence for others.