Optimization Online


Randomized Sketching Algorithms for Low Memory Dynamic Optimization

Ramchandran Muthukumar (rmuthuk1***at***jhu.edu)
Drew Kouri (dpkouri***at***sandia.gov)
Madeleine Udell (udell***at***cornell.edu)

Abstract: 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 first- and 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.

Keywords: PDE-constrained optimization; matrix approximation; randomized algorithm; single-pass algorithm; sketching; adaptivity; trust-region method; flow control; Navier–Stokes equations; adjoint equation

Category 1: Nonlinear Optimization (Systems governed by Differential Equations Optimization )

Category 2: Other Topics (Dynamic Programming )

Category 3: Applications -- Science and Engineering (Optimization of Systems modeled by PDEs )

Citation: Submitted for publication, Sandia National Laboratories, 2019.

Download: [PDF]

Entry Submitted: 11/13/2019
Entry Accepted: 11/13/2019
Entry Last Modified: 10/01/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society