Warm-Start Interior-Point Methods for Online Second-Order Cone Programming
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/ε))$ 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 $δ$, Newton's method warm-started at the previous round's solution $x^*_{t-1}$ converges to $x^*_t$ to accuracy $ε$ in $O(\log\log(1/ε))$ iterations. Over $T$ rounds the total cost is…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.24778
curl -X POST /api/v1/records/arxiv/2607.24778/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.24778/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'