Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets

We study online optimization under nested, shrinking feasible regions in two models: convex optimization with nested evolving feasible sets (\CONES) and adversarial constrained online convex optimization (\COCO). Our algorithms separate loss control from geometric movement control. Constrained minimizers and cumulative-loss tests preserve the relevant regret budget, while a deterministic resettable nested convex-body chaser controls movement between resets. For \CONES with a $G$-Lipschitz, $\mu$-strongly convex objective on a diameter-$D$ domain, adaptive sublevel-set chasing gives nonpositive regret at every prefix and movement $O\!\left(\rho_d\sqrt{GD\log(eT)/\mu}\right)$. Already in dimension two, every randomized algorithm with terminal expected regret at most $R_T$ incurs $\Omega\!\left(\sqrt{\log(T/(R_T+1))}\right)$ expected movement on some deterministic nested sequence. Uniform linear growth away from the constrained minimizer sets instead gives horizon-independent movement. For general convex \COCO, one-step-delayed chasing with regularized-leader resets gives $\Reg_T=O(G_fD\rho_d\sqrt T)$ and $\CCV_T=O(G_gD\rho_d\sqrt T)$; for strongly convex losses, both quantities are logarithmic in $T$. Substituting $\rho_d=O(\sqrt{d\log(1+d)})$ makes the dimension dependence polynomial.