[Submitted on 17 Jun 2026]

View PDF HTML (experimental)

Abstract:We analyze the computational complexity of solving a sequence of related second-order cone programs (SOCPs) whose right-hand-side data $b_t$ varies between rounds. The standard primal-dual interior-point algorithm solves each round at cost $\tilde{O}(n^{2.5}\log(1/\epsilon))$ from a cold start. We show that when the per-round perturbation $\|b_t - b_{t-1}\|_2$ is bounded by a problem-specific threshold $\delta$, Newton's method warm-started at the previous round's solution $x^*_{t-1}$ converges to $x^*_t$ to accuracy $\epsilon$ in $O(\log\log(1/\epsilon))$ iterations. Over $T$ rounds the total cost is $\tilde{O}(n^{2.5}\log(1/\epsilon) + T n^2 \log\log(1/\epsilon))$, compared to $\tilde{O}(T n^{2.5}\log(1/\epsilon))$ for cold start at each round; the per-round speedup for large $T$ is $\Theta(\sqrt{n}\,\log(1/\epsilon)/\log\log(1/\epsilon))$. The argument combines an infinitesimal local-norm sensitivity bound on the central-path optimum, a self-concordant finite-difference corollary, and the standard quadratic-convergence basin of Newton's method on a self-concordant barrier. The local-norm formulation circumvents the rank-deficiency issues of Euclidean sensitivity bounds for fat constraint matrices. A multi-seed experiment on bounded SOCPs with $n=50$, $p=100$ confirms a 30-70x per-round speedup across the predicted regime.

Submission history

From: Krishna Harish [view email]
[v1] Wed, 17 Jun 2026 02:34:52 UTC (17 KB)