Randomized Sketching For Dynamic Optimization And Inexact Adaptive Semismooth Newton Methods

Abstract

Dynamic optimization problems are ubiquitous in science and engineering. Examples include, pathogen propagation in built environment, vortex control in nuclear reactors, magnetic drug targeting, and full waveform inversion. Typically, such problems can be written as optimization problems constrained by partial di erential equations known as state equations. The optimization variables are termed as state and control variables which are connected via the state equation. Such problems su er from many computational challenges. In particular, the gradient based methods require storing the entire state trajectory and auxiliary variables such as Lagrange multipliers / adjoint variables. In case the underlying state equation is uniquely solvable in terms of control, the minimization problem can be written only in terms of control. This leads to the so-called reduced space formulation. To compute one instance of gradient, one solve of the state equation and one linear solve of adjoint equation is needed. To compute the hessian-times-vector product, for a second order method, two additional linear solves are needed. To carry out these solves, one needs to store the state, adjoint and other auxiliary variables. This can again be prohibitively expensive for large scale problems. There exists reduced order model (ROM) based approaches, such as proper orthogonal decomposition or reduced basis methods, to reduce the storage costs. However, the approximation capabilities of a xed ROM can signi cantly degrade as the optimization progresses. To overcome this, adaptive ROMs have been introduced. However, these approaches tend to be intrusive and do not easily adapt to the legacy codes. For dynamic optimization problems one could also use checkpointing, but this could lead to large gradient computation costs. The purpose of this dissertation is twofold. At rst we introduce an inexact adaptive semismooth Newton method and provide a convergence analysis of this algorithm for generic optimization problems in function spaces. Notice that in case of smooth problems, one can directly replace the semismooth Newton method by the standard Newton's method and all our results still apply. In our setting, nonsmoothness arise due to the control constraints. Secondly, we consider dynamic optimization problems, where inexactness arise due to matrix sketching. We use the adaptive randomized sketching to compress the state to reduce the memory requirements. Matrix sketching is ideally suited for such problems as it does not require storing the entire state solution trajectory, but instead it operates in a sequential manner. I.e., as the solution to the state equation are generated, one can simultaneously generate the sketch (reduce representation). This is unlike the ROM based approaches such as POD where one needs to store the entire solution trajectory. In addition, the approach can be directly applied to legacy codes. Matrix sketching leads to low rank approximations of the state. In our setting, this further leads to inexact gradients and hessian-times-vector product. The latter approximation errors are carefully controlled within the adaptive semismooth Newton method. This results in a provably convergent and e cient algorithm. Notice that, in general, one may also need to sketch the adjoint and other auxiliary equations used to generate hessian-times-vector product. The presented approach is applied to two challenging examples. In the rst case, PDE constraints are given by the linear heat equation. The main challenge arise due to measuretype constraints on the initial value control. In the second example, we consider nonlinear Allen-Cahn PDE as constraints, in addition to the control constraints. E ciency of the proposed algorithm is shown on both these examples. In particular, the rst example clearly illustrates the bene ts of using adaptive rank condition.