Barzilai-Borwein methods for travel demand model feedback
Solving travel demand equilibrium with Barzilai-Borwein step sizes. New look at step sizes for iterative feedback of travel demand models, with a promising alternative to constant and "MSA" (i.e. 1/n). One or another easily-calculated formula computes each iteration's step size from the linear trend of the current and previous iterations. No need to make trial runs to tune the step sizes or other parameters. No complicated objective functions or line-searches. Tested upon vehicle trip tables but applicable to almost any variable chosen for successive averaging (e.g. skims, link volumes). In the trial runs, the step sizes clustered around the fastest-converging constants, and the runs converged as fast.
Paper (revised from the one presented at the 2016 TRB Annual Meeting)
Poster (the BB formulas look different but are equivalent)
A simple BB robust to random noise. If a problem being solved with a BB method reaches a state in which successive iterates are dominated by random, independent noise of constant variance, then successive residuals (direction vectors) will be of roughly equal length, and orthogonal (by independence). As shown in the paper, the "long" BB1 step size will tend to duplicate whatever its previous step size was, and the "short" BB2 step size will tend to be 1/2 of the previous. Neither satisfies Blum's (and Robbins & Monro) criterion for convergence, BB1 not contracting and BB2 contracting too fast. A simple adaption applicable to travel demand models (for which the step size must be between 0 and 1) is to pick a blend of BB1 and BB2 that does satisfy Blum. One such blend, "BBB", is
b = 2(BB1) / (BB1 + 1), but confine between 0 and 1
BBB = b*(BB2) + (1-b)*(BB1)
It's simple to show that equal-length orthogonal residuals will result in
BBB = (previous step size) / (previous step size + 1)
which recursively yields a harmonic sequence satisfying Blum for convergence to the central limit. But in any case, this blended step is between the two BB step sizes, so it retains BB behavior when it's not random noise, and thus doesn't impede BB solutions. (Caveat: This doesn't have an underlying model or objective, and it doesn't have a way to respond to significant changes of the noise variance, such as prescribed changes to an ABM's sampling rate, and has not yet been tested with frozen-random-numbers ABM applications.)