Motivation
Optimal control problems with pointwise bounds on the control, such as
umin21∥y−z∥L22+2β∥u∥L22subject to −Δy=u in Ω, y=0 on ∂Ω, u≤ψ,
reduce, after eliminating the state, to a quadratic program in L2(Ω) with a pointwise upper bound. The primal-dual active set strategy solves such problems by guessing the set where the bound is active, solving one linear system on that guess, and updating the guess from the new primal and dual values. It is used routinely in PDE-constrained optimization because each iteration costs one linear solve and, in practice, very few iterations are needed.
Hintermüller, Ito and Kunisch (SIAM J. Optim. 13 (2002) 865–888; authors' version hal-01660511) showed that this strategy is a semismooth Newton method for a nonsmooth reformulation of the optimality system, built on the notion of slant differentiability of Chen, Nashed and Qi (SIAM J. Numer. Anal. 38 (2000) 1200–1216). In finite dimension this gives local superlinear convergence (missions I–IV of this series). This mission concerns the paper's function-space result, Theorem 4.1: in L2(Ω), under a norm gap on the operator, the method still converges locally superlinearly. Ulbrich (SIAM J. Optim. 13 (2003) 805–841) developed a related semismooth Newton theory for superposition operators in function spaces, which also requires a norm gap.
Setting
Let (Ω,μ) be a finite measure space (the paper takes a bounded domain Ω⊂Rn with Lebesgue measure) and Lp=Lp(Ω) the real Lebesgue spaces, with inner product (⋅,⋅) on L2. The paper writes A for an operator and calligraphic A, I for active and inactive sets.
Slant differentiability (Definition 1). For Banach spaces X, Z, a map F:X→Z is slantly differentiable in an open set U if there is G:U→L(X,Z), a slanting function, with
h→0lim∥h∥1∥F(x+h)−F(x)−G(x+h)h∥=0(x∈U).(A)
For δ∈R, the candidate slanting function of the pointwise max is Gm(y)(x)=1 if y(x)>0, 0 if y(x)<0, δ if y(x)=0 (4.1).
The problem. Given f,ψ∈L2 and a self-adjoint A∈L(L2) with
(Ay,y)≥γ∥y∥2(γ>0),(H1)
minimize 21(y,Ay)−(f,y) subject to y≤ψ. The solution y∗ and its multiplier λ∗ are the unique solution of
Ay∗+λ∗=f,λ∗−max(0,λ∗+c(y∗−ψ))=0 a.e.,(4.2)
for any fixed c>0. The norm gap hypothesis is
A=C+βI,C∈L(L2,Lq),β>0,q>2.(H2)
The algorithm. From (y0,λ0)∈L2×L2, set Ak={x:λk(x)+c(yk(x)−ψ(x))>0}, Ik=Ω∖Ak, and solve
Ayk+1+λk+1=f,yk+1=ψ on Ak,λk+1=0 on Ik.
A sequence obeying this rule for every k is a run. Superlinear convergence of xk→x∗ means xk→x∗ and, for every η>0, eventually ∥xk+1−x∗∥≤η∥xk−x∗∥.
Formalization targets
Goal: Theorem 4.1 (p. 15)
The page reads: "Assume that (H1), (H2) hold and that ψ and f are in L^q(Ω). Then the primal-dual active set strategy or, equivalently, the semismooth Newton method converge superlinearly if ‖y⁰ − y*‖ is sufficiently small and λ⁰ = β(y⁰ − ψ)." The formalized goal is the statement the proof establishes: with c=β, there is ρ>0 such that every run with
∥y0−y∗∥L2<ρ,λ0=f−Ay0
converges superlinearly to (y∗,λ∗) in L2×L2. The initialization differs from the printed one; see Formalization scope.
Milestones
- Theorem 1.1 (Chen–Nashed–Qi): slant differentiability near a zero x∗ with uniformly bounded G(x)−1 gives local superlinear convergence of xk+1=xk−G(xk)−1F(xk).
- Proposition 4.1(ii): for 1≤p<q≤∞, max(0,⋅):Lq→Lp is slantly differentiable with slanting function Gm.
- (4.9)–(4.10): for c=β, (4.2) is equivalent to βy∗−βψ+max(0,Cy∗−f+βψ)=0 and λ∗=f−Cy∗−βy∗.
- Equivalence of the algorithms: along a run with c=β and λ0=f−Ay0, λk+β(yk−ψ)=f−Cyk−βψ for all k, so the active sets are those of the reduced algorithm.
- Slant differentiability of the reduced map F(y)=βy−βψ+max(0,Cy−f+βψ) on L2, with GF(y+h)=βI+Gm(Cy−f+βψ+Ch)C, δ=1.
- Bounded inverses: GF(z) is invertible on L2, with ∥GF(z)−1∥ bounded uniformly in z.
Two companion items accompany the goal: existence of a run from every y0, and Proposition 4.1(i), the paper's counterexamples showing that Gm fails to be a slanting function from Lp to Lp.
Significance
Theorem 4.1 is the infinite-dimensional justification of a method used throughout control-constrained optimal control: it shows that the method converges locally superlinearly for the continuous problem itself, not only for each discretization. Example 1 of the paper shows that distributed control of the Poisson equation, and boundary control with Sobolev embeddings, satisfy (H2). Proposition 4.1 isolates the structural reason: the pointwise max is a Newton-differentiable map only between spaces with a norm gap.
None of these results is known to be machine-checked. A complete development would provide slant differentiability in Banach spaces, the Chen–Nashed–Qi local convergence theorem, the norm-gap differentiability of max(0,⋅) between Lebesgue spaces, and invertibility of block operators on L2 of a measurable partition. Each of these is reusable for other semismooth Newton analyses in function space.
Difficulty
The obvious argument fails at the max. In finite dimension, max(0,⋅) is slantly differentiable with Gm because a small perturbation does not change the sign of any nonzero component. In L2, a perturbation h of small norm can flip the sign of y on a set of positive measure, and on that set the error max(0,y+h)−max(0,y)−Gm(y+h)h is as large as ∣y∣. Proposition 4.1(i) shows that this error is not o(∥h∥Lp) in Lp for any p. Superlinear convergence in L2 therefore needs the argument of the max to be controlled in a stronger norm than the error is measured in, which is what (H2) and f,ψ∈Lq provide. A second difficulty is that the two-variable algorithm is not literally a Newton method for a map of y alone; it must be identified with the reduced algorithm, and that identification depends on the initialization.
Formalization scope
- Spaces. Lp is Mathlib's
Lp ℝ p μ on an arbitrary finite measure space; q∈(2,∞] is an extended real with 2 < q. The paper's bounded Lipschitz domain is replaced by a finite measure space: the proofs use only ∣Ω∣<∞, and Mathlib has no notion of Lipschitz boundary.
- Pointwise statements on Lp classes are almost everywhere statements about representatives. (H2) is stated as Ay=Cy+βy a.e. for every y∈L2, which avoids building the inclusion Lq⊆L2.
- Hypotheses kept: self-adjointness of A, (H1) with explicit γ>0, (H2) with β>0 and q>2, f,ψ∈Lq. The solution (y∗,λ∗) of (4.2) is a hypothesis; it exists and is unique under (H1), as the paper states on p. 12.
- The initialization. The printed λ0=β(y0−ψ) does not support the proof, which uses "λ0+β(y0−ψ)=f−Cy0−βψ" and c=β. That identity holds exactly for λ0=f−Ay0. The goal uses λ0=f−Ay0 and c=β. With the printed initialization the first active set is {y0>ψ}, and for y0 slightly below y∗ the first iterate solves the unconstrained problem, which can be far from y∗.
- Superlinear convergence is stated for the pair (yk,λk) in the product norm max(∥y∥,∥λ∥), without dividing by ∥xk−x∗∥, so finite termination qualifies. "Sufficiently small" is an ∃ρ>0 chosen before the run, on ∥y0−y∗∥ only.
- No trivialization. The goal mentions neither the reduced algorithm, nor GF, nor Proposition 4.1; the norm gap q>2 is not weakened to C∈L(L2), under which Proposition 4.1(i) shows that Gm need not be a slanting function; and the companion
run_exists shows that the runs the goal quantifies over exist.
- Definitions (
PDASNewton.FunSpace.Setting): slanting functions, superlinear convergence, Gm, property (A) for max(0,⋅):Lq→Lp, system (4.2), one step and runs of the algorithm. These duplicate the finite-dimensional definitions of the other missions of the series in a separate namespace.
Proofs of any milestone are welcome, as are reusable lemmas on Lebesgue spaces (Hölder on sets of small measure, multiplication operators, Lax–Milgram on L2 of a measurable subset).
Selected references
- M. Hintermüller, K. Ito, K. Kunisch, The primal-dual active set strategy as a semismooth Newton method, SIAM J. Optim. 13(3) (2002) 865–888. https://doi.org/10.1137/S1052623401383558 ; authors' version https://hal.science/hal-01660511
- X. Chen, Z. Nashed, L. Qi, Smoothing methods and semismooth methods for nondifferentiable operator equations, SIAM J. Numer. Anal. 38 (2000) 1200–1216. https://doi.org/10.1137/S0036142999356719
- M. Ulbrich, Semismooth Newton methods for operator equations in function spaces, SIAM J. Optim. 13 (2003) 805–841. https://doi.org/10.1137/S1052623400371569
- L. Qi, J. Sun, A nonsmooth version of Newton's method, Math. Programming 58 (1993) 353–367. https://doi.org/10.1007/BF01581275