Randomized Sketching Algorithms for Low-Memory Dynamic Optimization
Randomized Sketching Algorithms for Low-Memory Dynamic Optimization
复制标题
DOI：
10.1137/19m1272561
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
R. Muthukumar;D. Kouri;Madeleine Udell
中科院分区：
文献类型：
--
作者：
R. Muthukumar;D. Kouri;Madeleine Udell
\bfA \bfb \bfs \bft \bfr \bfA \bfc \bft提出了一种求解动态优化问题的有限记忆方法。这类问题的内存需求通常是一个主要障碍，特别是对于PDE约束的问题，如最优流量控制、全波形反演和光学层析成像。在这些问题中，PDE约束唯一地决定了给定控制下物理系统的状态；目标是找到使目标最小化的控制值。虽然控件通常是低维的，但状态的存储成本通常更高。本文提出在状态生成时使用随机矩阵逼近对状态进行压缩，并展示了如何使用压缩状态可靠地解决原始动态优化问题。具体来说，压缩状态被用来计算近似梯度和对向量应用Hessian。这些量的近似误差由草图的目标秩控制。这种近似的一二阶信息可以很容易地用于任何优化算法。作为一个例子，我们开发了一种基于后验误差信息自适应选择目标秩的草图信任域方法，并证明该方法收敛于原问题的一个平稳点。数值实验表明，该方法在平流-反应-扩散方程的最优控制和流体流过圆柱体的最优控制等具有挑战性的问题上具有良好的性能。
\bfA \bfb \bfs \bft \bfr \bfa \bfc \bft . This paper develops a novel limited-memory method to solve dynamic optimization problems. The memory requirements for such problems often present a major obstacle, particularly for problems with PDE constraints such as optimal flow control, full waveform inversion, and optical tomography. In these problems, PDE constraints uniquely determine the state of a physical system for a given control; the goal is to find the value of the control that minimizes an objective. While the control is often low dimensional, the state is typically more expensive to store. This paper suggests using randomized matrix approximation to compress the state as it is generated and shows how to use the compressed state to reliably solve the original dynamic optimization problem. Concretely, the compressed state is used to compute approximate gradients and to apply the Hessian to vectors. The approximation error in these quantities is controlled by the target rank of the sketch. This approximate firstand second-order information can readily be used in any optimization algorithm. As an example, we develop a sketched trust-region method that adaptively chooses the target rank using a posteriori error information and provably converges to a stationary point of the original problem. Numerical experiments with the sketched trust-region method show promising performance on challenging problems such as the optimal control of an advection-reaction-diffusion equation and the optimal control of fluid flow past a cylinder.