Delphi.science

Dimension-Free Complexity Guarantees for Dual Dynamic Programming

Pablo Barros, Vincent Guigues, Jiaming Liang, Renato Monteiro

arXivarxiv/2606.10203Jun 8, 2026math.OCscore 0

This paper studies the complexity of a dual dynamic programming (DDP) method for solving a class of convex optimization problems with linear coupling constraints. Existing complexity results based on DDP depend on the dimensions of the state vectors and, in particular, grow exponentially with dimension. The goal of this paper is to establish a complexity bound that is independent of the dimension. Our approach first studies an unconstrained strongly convex problem and develops a flexible framework for DDP, called FDDP, for solving the associated dynamic programming equations, and establishes…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2606.10203
curl -X POST /api/v1/records/arxiv/2606.10203/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.10203/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'