Robust-to-Dynamics Optimization

Amir Ali Ahmadi () and Oktay Günlük ()
Additional contact information
Amir Ali Ahmadi: Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08540
Oktay Günlük: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Mathematics of Operations Research, 2025, vol. 50, issue 2, 965-992

Abstract: A robust-to-dynamics optimization (RDO) problem is an optimization problem specified by two pieces of input: (i) a mathematical program (an objective function f : R n → R and a feasible set Ω ⊆ R n ) and (ii) a dynamical system (a map g : R n → R n ). Its goal is to minimize f over the set S ⊆ Ω of initial conditions that forever remain in Ω under g . The focus of this paper is on the case where the mathematical program is a linear program and where the dynamical system is either a known linear map or an uncertain linear map that can change over time. In both cases, we study a converging sequence of polyhedral outer approximations and (lifted) spectrahedral inner approximations to S . Our inner approximations are optimized with respect to the objective function f , and their semidefinite characterization—which has a semidefinite constraint of fixed size—is obtained by applying polar duality to convex sets that are invariant under (multiple) linear maps. We characterize three barriers that can stop convergence of the outer approximations to S from being finite. We prove that once these barriers are removed, our inner and outer approximating procedures find an optimal solution and a certificate of optimality for the RDO problem in a finite number of steps. Moreover, in the case where the dynamics are linear, we show that this phenomenon occurs in a number of steps that can be computed in time polynomial in the bit size of the input data. Our analysis also leads to a polynomial-time algorithm for RDO instances where the spectral radius of the linear map is bounded above by any constant less than one. Finally, in our concluding section, we propose a broader research agenda for studying optimization problems with dynamical systems constraints , of which RDO is a special case.

Keywords: Primary: 90C05; 90C17; 90C34; 90C22; 39A05; 39A30; 37C05; optimization in dynamical systems; semi-infinite linear programs; joint spectral radius; semidefinite programming-based approximations (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.0116 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:2:p:965-992

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().