Certified Scalable Enclosures for Uncertain Underdetermined Systems

• Underdetermined models with uncertainty challenge solution reliability, especially when multiple solutions are possible; this issue arises in systems biology, sensing, and estimation.In systems and synthetic biology, multiple steady states can correspond to different cell types.Source: §1 · pp. 1–2
• Point-based methods can find candidate solutions but generally do not guarantee solutions are complete under uncertainty or multiplicity, while sampling methods depend on modelling choices and face difficulties propagating nonlinear uncertainty.Source: §1 · p. 2
• Set-based interval methods offer deterministic outer guarantees, but scalable verified solvers are mostly designed for square systems and may require regularity assumptions.Dependency and weak contraction in strongly coupled models motivate subdivision and tighter relaxations.Source: §1 · p. 2
• The paper develops a scalable LP-driven framework that produces deterministic outer bounds containing the entire admissible solution set.The framework targets underdetermined models with bounded, deterministic uncertainty.Source: §1 · p. 2
• Trapezoidal linearisation converts nonlinear uncertain underdetermined problems into linear inequalities for systematic box contraction and subdivision.The method constructs tight interval-affine inclusions.Source: §1 · p. 2
• The framework uses tractable LPs to compute rigorous component-wise outer enclosures through contraction and subdivision.Source: §1 · p. 2
• The algorithms are demonstrated in biomolecular nonlinear design, sensitivity analysis, and robust compressed sensing with bounded measurements.Source: §1 · p. 3

2.1 Motivation

• The design problem can be underdetermined when the number of reaction parameters exceeds the number of state variables.Source: §2.1 · pp. 3–4
• Given a target steady-state box and parameter search region, nonlinear design seeks an enclosure of all compatible parameters.Compatibility requires at least one state in the target box satisfying the model equations.Source: §2.1 · p. 4
• Trapezoidal linearisation recasts nonlinear constraints locally over a box as interval-affine inclusions, producing a polyhedral relaxation contracted through successive LPs.The two bounding lines need not be parallel.Source: §2.1 · p. 4
• For interval linear systems, the related task is to enclose the solution set induced by interval-valued coefficients and right-hand sides.Source: §2.1 · p. 4
• Robust compressed sensing seeks a sparse signal estimate whose measurements satisfy bounded observations under an interval sensing matrix.Source: §2.1 · p. 4
• The returned certificates are set-theoretic outer guarantees within the search domain, but need not be minimal and can be conservative due to interval dependency.Source: §2.1 · p. 4

3.1 Interval Analysis

• Interval analysis propagates interval-valued quantities with inclusion-isotonic operations, so computed extensions enclose the true function range.Natural interval extensions can overestimate because repeated occurrences of a variable are treated independently; subdivision can reduce this for Lipschitz functions.Source: §3.1 · p. 5

3.2 Interval linear systems

• The Oettli–Prager characterization gives an exact membership test for interval-linear solution sets, which can be reformulated as LP constraints for certified componentwise bounds.Source: §3.2 · p. 5

3.3 Parallel Linearization Approach [19]

• Parallel linearisation encloses a differentiable mapping over a box using affine bounds derived from Jacobian information.The construction assumes a continuously differentiable map and an available inclusion-isotonic interval extension of its Jacobian.Source: §3.3 · p. 6

3.4 Linear Programming Approach [19]

• The LP approach formulates interval-affine and Oettli–Prager constraints to compute certified componentwise enclosures.The bounding procedure solves 2n LPs to minimize and maximize each component, assuming finite optima or infeasibility.Source: §3.4 · pp. 6–7
• For nonnegative variables, interval-affine inclusions can be represented by endpoint-based linear inequalities.Source: §3.4 · pp. 6–7

4 Results

• Trapezoidal linearisation brackets the nonlinear function with affine maps of potentially different slopes, accommodating interval-valued Jacobians and underdetermined constraints.The resulting relaxation is used to contract the parameter search box while retaining feasible parameters.Source: §4 · p. 7
• Every feasible parameter value associated with a state in the target box is retained by the certified outer enclosure.The theorem applies to continuously differentiable models over the target state box and initial parameter search box.Source: §4 · p. 7
• For nonnegative variables, interval-affine feasibility is equivalent to componentwise endpoint linear inequalities.This reformulation is exact under entrywise interval uncertainty.Source: §4 · p. 7
• LPs provide componentwise bounds, and infeasibility of any LP certifies that the current parameter box contains no solution.Repeated contraction produces nested parameter boxes with nonincreasing componentwise widths.Source: §4 · p. 8
• Subdivision can reduce the quadratic enclosure-width term, but contraction may stagnate when Jacobian spread over the target state box dominates.In that regime, tightening the state box can be more effective than further parameter subdivision.Source: §4 · p. 9
• For interval-linear systems, Oettli–Prager constraints yield certified outer box enclosures through LPs, with positive/negative-part lifting avoiding orthant enumeration.The lifting gives an outer relaxation for sign-indefinite variables.Source: §4 · pp. 10–11
• The two trapezoidal variants trade construction cost for tightness: Variant 2 is cheaper, while Variant 1 is often tighter at moderate box widths.Variant 2 can be conservative when the Jacobian varies substantially over the parameter box.Source: §4 · p. 11

5 Applications

• Across the applications, interval-affine enclosures are contracted by componentwise LPs, with subdivision used to mitigate dependency overestimation.The evaluation covers nonlinear circuit design, compressed sensing, and sensitivity-analysis linear systems.Source: §5 · pp. 11–12

5.1 Design of Nonlinear Biomolecular Circuits

• For the positive-feedback loop, the contracted parameter box is [89.73, 110.33] × [0.9, 1.1] × [8.2, 9.6]; for the IFFL, subdivision yields [89.7, 110.3] × [0.9, 1.1] × [9.73, 10.05].Both variants give nearly identical bounds for the positive-feedback example; the IFFL's Variant 2 contraction improves as subdivision and iteration counts increase.Source: §5.1 · p. 12, Figure 1 · p. 13

5.2 Interval linear systems

• The interval-linear examples use exact Oettli–Prager characterizations as linear constraints, unlike nonlinear design, where a shared-point-slope linearization may fail when Jacobians vary over boxes.The approach is demonstrated on underdetermined and square systems and sensitivity-analysis interval systems.Source: §5.2 · p. 13
• The contracted interval enclosure [z]c = [0.8, 1.35] × [−0.64, 4.68] × [−1.64, −0.48] × [−10, 10] contains all feasible solutions; the proposed Oettli–Prager-based approach also yields x ∈ [x] = [−101, 17] × [−15, 99] × [−90, 90].Source: §5.2 · p. 14
• For order-of-magnitude coefficient uncertainty α, β, γ, δ, ε, ζ, η, θ ∈ [1, 10], the certified sensitivity enclosure is ∆x ∈ [−0.042, 0.48] × [−1.25, 0.11] × [−0.25, 0.11].The procedure also applies without a monotonicity assumption on ∆x.Source: §5.2 · p. 14
• The compressed-sensing formulation correctly identifies nonzero signal components, including s2, s3, s4, and s6, while suppressing zero components despite measurement noise.Robust feasibility is formulated using positive/negative-part lifting and linear bounds on interval-matrix products.Source: §5.2 · p. 15

6 Discussion

• Across nonlinear design, interval-linear benchmarks, and compressed sensing, LP-based relaxations yield certified componentwise enclosures while remaining computationally tractable for the problem sizes considered.The reported practical scope is limited to the problem sizes considered.Source: §6 · p. 15
• Interval dependency can inflate interval-affine bounds and weaken contraction; subdivision reduces this conservatism but introduces combinatorial growth.The authors keep iteration counts small and subdivide only when contraction stagnates.Source: §6 · p. 15
• One contraction round for a parameter box in R^p requires 2p linear programs; uniform subdivision and repeated passes increase the LP count with the number of subboxes and iterations.The stated enclosure pass for a polyhedral relaxation in R^n requires 2n linear programs.Source: §6 · p. 15

7 Conclusions

• Underdetermined models can have continua of solutions, while sampling and point-based solvers do not certify solutions for all admissible realizations.The framework targets guaranteed outer enclosures for nonlinear underdetermined design with bounded uncertainty.Source: §7 · p. 15
• For nonlinear steady-state design, trapezoidal linearization constructs interval-affine relaxations, and families of LPs iteratively contract search boxes, with subdivision used when dependency limits contraction.For interval-linear systems, Oettli–Prager characterizations yield tractable LPs that certify enclosures in underdetermined and square settings.Source: §7 · pp. 15–16
• The reusable LP bounding primitives apply to biomolecular circuit design, sensitivity analysis, and robust compressed sensing, making enclosure tightness and runtime an explicit trade-off.The conclusion describes this trade-off as tenable.Source: §7 · p. 16