Diminishing-Step Subgradient Updates

In Lagrangian relaxation for air routing, the dual function is piecewise-linear and non-smooth, so a constant step in subgradient ascent makes iterates oscillate forever around the optimal multiplier. This lesson introduces the diminishing-step rule -- stepsizes that shrink to zero while remaining non-summable -- and shows how to apply two-parameter harmonic schedules to push the dual iterates toward the optimum.

Step 1 of 157%

Tutorial

Why Constant Steps Fail

From the previous lesson, the subgradient-ascent update for the Lagrangian dual φ(λ)\varphi(\lambda) is

λk+1=λk+αk gk,gk∈∂φ(λk).\lambda^{k+1} = \lambda^k + \alpha_k\, g_k, \qquad g_k \in \partial\varphi(\lambda^k).

With a constant stepsize αk=α,\alpha_k = \alpha, the iterates do not converge to the optimal multiplier λ∗.\lambda^*. Instead, they oscillate in a neighborhood whose radius is proportional to α.\alpha. To pin the iterates down to λ∗,\lambda^*, we must let the stepsize shrink to zero:

αk→0.\alpha_k \to 0.

But shrinking alone is not enough. If αk\alpha_k shrinks too fast, the total travel ∑kαk\sum_k \alpha_k is finite and the iterates may stall before ever reaching λ∗.\lambda^*. So we also require

∑k=0∞αk=∞.\sum_{k=0}^{\infty} \alpha_k = \infty.

A stepsize sequence satisfying both is called a diminishing-step rule. The canonical choice is the harmonic schedule

αk=ak+1,a>0,\alpha_k = \dfrac{a}{k+1}, \qquad a > 0,

since αk→0\alpha_k \to 0 and ∑1/(k+1)=∞.\sum 1/(k+1) = \infty. With a=1,a = 1, the first few values are

α0=1,α1=12,α2=13,α3=14,…\alpha_0 = 1, \quad \alpha_1 = \tfrac{1}{2}, \quad \alpha_2 = \tfrac{1}{3}, \quad \alpha_3 = \tfrac{1}{4}, \ldots

Throughout this lesson we assume λ\lambda is unrestricted (e.g. an equality-constrained relaxation of a flow-balance constraint), so no projection is required.

↑ ↓ navigate · Enter open · Esc close · ⌘K/Ctrl K toggle