Robust-to-Dynamics Optimization
Robust-to-Dynamics Optimization
复制标题
稳健的动力学优化
DOI：
10.1287/moor.2023.0116
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
O. Günlük
中科院分区：
文献类型：
--
作者：
Amir Ali Ahmadi;O. Günlük
鲁棒-动态优化（RDO）问题是由两个输入指定的优化问题：（i）数学规划（目标函数[公式：见正文]和可行集[公式：见正文]）和（ii）动力系统（映射[公式：见正文]）。它的目标是在g下永远保持在[Formula：see text]中的初始条件集[Formula：see text]上最小化f。本文的重点是数学规划是一个线性规划的情况下，动力系统是一个已知的线性映射或不确定的线性映射，可以随时间变化。在这两种情况下，我们研究了[公式：见正文]的多面体外近似和（提升的）谱面体内近似的收敛序列。我们的内部近似优化的目标函数f，和他们的半定特征，它有一个半定约束的固定大小，是通过应用极对偶凸集不变下（多）线性映射。我们描述了三个障碍，可以阻止收敛的外部近似[公式：见文字]是有限的。我们证明，一旦这些障碍被删除，我们的内部和外部近似程序找到一个最佳的解决方案和证书的RDO问题在有限数量的步骤的最优性。此外，在动态是线性的情况下，我们表明，这种现象发生在一些步骤中，可以在输入数据的位大小的时间多项式计算。我们的分析还导致了一个多项式时间算法RDO的情况下，线性映射的谱半径是有界以上的任何常数小于1。最后，在我们的结论部分，我们提出了一个更广泛的研究议程，研究动态系统约束的优化问题，其中RDO是一个特殊的情况。资金来源：O. Günlük的研究得到了海军研究办公室的部分支持[Grant N 00014 -21-1-2575]。这项工作部分由阿尔弗雷德·斯隆基金会，空军科学研究办公室，国防高级研究计划局[青年教师奖]，国家科学基金会[教师早期职业发展计划奖]和谷歌[教师奖]资助。
A robust-to-dynamics optimization (RDO) problem is an optimization problem specified by two pieces of input: (i) a mathematical program (an objective function [Formula: see text] and a feasible set [Formula: see text]) and (ii) a dynamical system (a map [Formula: see text]). Its goal is to minimize f over the set [Formula: see text] of initial conditions that forever remain in [Formula: see text] 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 [Formula: see text]. 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 [Formula: see text] 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. Funding: O. Günlük was partially supported by the Office of Naval Research [Grant N00014-21-1-2575]. This work was partially funded by the Alfred P. Sloan Foundation, the Air Force Office of Scientific Research, Defense Advanced Research Projects Agency [Young Faculty Award], the National Science Foundation [Faculty Early Career Development Program Award], and Google [Faculty Award].