§7.1.2, (7.2) — dual constraint dilation
ProvedCompetitiveOnlinePD.WeightedCaching.dual_dilationlinear-optimizationonline-algorithmsweighted-caching
Let be a finite universe of unit-size pages, let be an integer, and let be arbitrary real costs. A finite request list has no prescribed horizon or restriction on repetitions or on relative to . All states below are computed by the shared prefix algorithm. Write for its interval slack, for its unscaled dual objective, and .
At every reached endpoint or intermediate event-side clock, every valid interval, including a still-zero coordinate, satisfies
Dividing both and by gives a nonnegative feasible dual with objective exactly .
This is an invariant of the actual saturation feedback, with no supplied dual-feasibility or uncapped-exponential hypothesis.
Differences from the source:
- encoding: finite unit-page universes and arbitrary request prefixes → a finite page type, finite lists and one-based natural indices restricted to valid requests and occurrence intervals; reason: every finite prefix is included, also the empty list; no final horizon or future request is an input to a transition
- encoding: the next request time in the interval sums → the absent next occurrence is T+1 solely as a summation sentinel; reason: last intervals include all intervening requests through T; the sentinel is never a request
- reading: the boxed parenthetical r(p_t,t) < t′ < r(p_t,t)+1 → updates between occurrence request times t(p,j)+1 and t(p,j+1)-1; reason: the consecutive counters admit no integer update time; printed p.152 specifies the intended lifetime
- encoding: continuous updates until capacity is satisfied → an exact real scalar flow with simultaneous events, first-stop infimum and left/right activation states; reason: this gives the stated zero, jump, exponential and saturation rules without discretization; completion is a conclusion
- reading: no visible operator between the two printed dual-objective sums → the second sum is subtracted; reason: equation (7.8), the dual constraints and the dual-profit derivatives fix the minus sign
Preamble
import Definitions.Def_CompetitiveOnlinePD_WeightedCaching_Observables
Formal statement
namespace CompetitiveOnlinePD.WeightedCaching
open scoped BigOperators
theorem dual_dilation
{P : Type} [Fintype P] [DecidableEq P]
(k : ℕ) (hk : 1 ≤ k) (c : P → ℝ) (hc : ∀ p, 1 ≤ c p)
(H : List P) (s : State P) (hs : reached k c H s) :
(∀ v ∈ intervals H, slack H s v.1 v.2 ≤ c v.1 * (1 + Real.log (k : ℝ))) ∧
dualFeasible c H (scaleDual (1 + Real.log (k : ℝ)) s) ∧
dualValue k H (scaleDual (1 + Real.log (k : ℝ)) s) =
dualValue k H s / (1 + Real.log (k : ℝ)) := by sorry
end CompetitiveOnlinePD.WeightedCaching
Source
Buchbinder & Naor, The Design of Competitive Online Algorithms via a Primal-Dual Approach, copyright 2009, DOI:10.1561/0400000024, https://doi.org/10.1561/0400000024, (7.2), printed p.155 (PDF p.66)