Convex Cost Functions and Equilibrium Existence

A link cost function $c_a(x_a)$ is convex on $[0,\infty)$ if, for every $x,y\geq 0$ and every $\lambda \in [0,1],$

$$c_a(\lambda x + (1-\lambda)y) \leq \lambda \, c_a(x) + (1-\lambda)\, c_a(y).$$

When $c_a$ is twice differentiable, an equivalent (and easier) test is

$$c_a''(x_a) \geq 0 \quad \text{for all } x_a \geq 0.$$

Convexity matters for traffic assignment because it turns the equilibrium problem into a convex optimization problem.

The BPR latency function

$$t_a(x_a) = t_a^0\left(1 + \alpha \left(\frac{x_a}{c_a}\right)^\beta\right)$$

is convex on $[0,\infty)$ whenever $\beta \geq 1.$ Differentiating twice,

$$t_a''(x_a) = \frac{t_a^0\, \alpha\, \beta(\beta-1)}{c_a^{\beta}}\, x_a^{\beta-2} \geq 0.$$

For instance, with $t_0 = 10,$ $\alpha = 0.15,$ $c = 100,$ and $\beta = 4,$

$$t''(x) = \frac{10 \cdot 0.15 \cdot 4 \cdot 3}{100^4}\, x^2 \geq 0,$$

so this BPR latency is convex.