A Generalized ℓ 1 \ell_{1} -Merit Function SQP Method Using Function Approximations with Tunable Accuracy
Dane S. Grundvig, Matthias Heinkenschloss · 2025
Read A Generalized ℓ 1 \ell_{1} -Merit Function SQP Method Using Function Approximations with Tunable Accuracy by Dane S. Grundvig, Matthias Heinkenschloss (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-06199.txt.
Introduction
Dane Grundvig and Matthias Heinkenschloss develop an optimization method in a twenty twenty-five paper. The method solves smooth problems where some rules must hold exactly. Each check of the goal and the rules can be costly, as when it needs a full physics simulation.
Their version of sequential quadratic programming swaps the true functions for cheap models with tunable accuracy. The method sets how exact each model must be, based on progress so far, and uses error bounds to stay in zones where the models can be trusted. It keeps the same convergence promises as the classic method. A test case steers flow in a heated fluid model.
Catalog record
| CREATOR | Dane S. Grundvig, Matthias Heinkenschloss |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-06199
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Generalized ℓ 1 \ell_{1} -Merit Function SQP Method Using Function Approximations with Tunable Accuracy Thanks: This research was supported in part by AFOSR Grant FA9550-22-1-0004, NSF Grant DMS-2231482, and a 2022 National Defense Science and Engineering Graduate (NDSEG) Fellowship Dane S. Grundvig, Matthias Heinkenschloss Abstract This paper develops a generalization of the line-search sequential quadratic programming (SQP) algorithm with ℓ 1 \ell_{1} -merit function that uses objective and constraint function approximations with tunable accuracy to solve smooth equality-constrained optimization problems. The evaluation of objective and constraint functions and their gradients is potentially computationally expensive, but it is assumed that one can construct effective, computationally inexpensive models of these functions. This paper specifies how these models can be used to generate new iterates. At each iteration, the models have to satisfy function error and relative gradient error tolerances determined by the algorithm based on its progress. Moreover, bounds for the model errors are used to explore regions where the combined objective function and constraint models are sufficiently accurate. The algorithm has the same first-order global convergence properties as a line-search SQP algorithm with ℓ 1 \ell_{1} -merit function, but only uses objective and constraint function models and the model error bounds. The algorithm is applied to a discretized boundary control problem in which the evaluation of the objective and constraint functions requires the solution of the Boussinesq partial differential equation (PDE). The models are constructed from projection-based reduced-order models of the Boussinesq PDE. Keywords. Constrained optimization, sequential quadratic programming, line-search, inexact functions, inexact gradients, reduced order model. 1 Introduction We develop a generalization of the line-search sequential quadratic programming (SQP) algorithm with \ell_{1} -merit function that uses objective function and constraint function models with tunable accuracy to solve smooth equality-constrained optimization problems. Given smooth functions f:\mathbb{R}^{n}\rightarrow\mathbb{R} and c:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} , m<n , we consider the solution of \displaystyle\min\quad \displaystyle f(x), (1.1a) s.t. \displaystyle c(x)=0. (1.1b) We assume that evaluations of f and c and their derivatives are computationally expensive, e.g., because an evaluation of f and c at x requires an expensive simulation, but that one can compute differentiable, effective, computationally inexpensive to evaluate models m_{k} and h_{k} of the objective function around the current iterate x_{k} . Instead of a traditional line-search SQP method that uses a quadratic model of the Lagrangian \mathcal{L}(x,\lambda)=f(x)-\lambda^{T}c(x) (1.2) associated with ( 1.1 ) and a linear model of the constraints to compute a step, and, ultimately, a new iterate, our algorithm uses models m_{k}:\mathbb{R}^{n}\rightarrow\mathbb{R} and h_{k}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} , of the objective and constraint function built around the current iterate x_{k} to generate a new iterate by approximately solving subproblems of the type \displaystyle\min\quad \displaystyle m_{k}(x), (1.3a) s.t. \displaystyle h_{k}(x)=0. (1.3b) Because m_{k} , h_{k} , and their derivatives can be evaluated inexpensively, an approximate solution of ( 1.3 ) can be computed efficiently. If m_{k} and h_{k} are good approximations of f and c , respectively, a new iterate generated by approximately solving ( 1.3 ) is expected to be a better approximation of the solution of ( 1.1 ) than the current iterate x_{k} is. Unfortunately, the models m_{k} , h_{k} are not good models of f , c globally, but only in certain regions of the optimization variable space. In this paper, we specify what approximation properties are required of these models at the current iterate x_{k} , and how exactly these models can be used to generate a new iterate using a generalization of the line-search SQP method with \ell_{1} -merit function. While once generated, models m_{k} , h_{k} , and their derivatives are computationally inexpensive to evaluate, the computation of these models carries a computational cost. Therefore, it is desirable to use current models as much as possible. This paper extends our recent work [ 14 ] on unconstrained problems to the constrained case ( 1.1 ) and demonstrates the potential of the new algorithm on a boundary control problem governed by the Boussinesq partial differential equation (PDE). Our set-up is motivated by problems ( 1.1 ) with objective and constraint functions of the form f(x)=\widehat{f}(y(x);x),\qquad c(x)=\widehat{c}(y(x);x), (1.4) where f:\mathbb{R}^{N}\times\mathbb{R}^{n}\rightarrow\mathbb{R} and c:\mathbb{R}^{N}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} , and where y(x)\in\mathbb{R}^{N} , N\gg 1 , solves a large-scale system R(y(x);x)=0 , where R:\mathbb{R}^{N}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{N} often represents a discretized PDE and y(x)\in\mathbb{R}^{N} represents the discretized PDE solution for given parameters or controls x\in\mathbb{R}^{n} . The system R(y(x);x)=0 is also referred to as the full order model (FOM). A projection-based reduced order model (ROM) generates V,W\in\mathbb{R}^{N\times r} , r\ll N , and approximates y(x) by V\widehat{y}(x) , where \widehat{y}(x)\in\mathbb{R}^{r} solves the smaller scale ROM W^{T}R(V\widehat{y}(x);x)=0 . For many nonlinear systems, so-called hyperreduction methods are needed to make the solution of the resulting ROM truly computationally inexpensive. For details on ROMs see, e.g., [ 2 ] , [ 3 ] , [ 17 ] , [ 23 ] . A ROM implies models m_{k}(x)=\widehat{f}(V\widehat{y}(x);x),\qquad h_{k}(x)=\widehat{c}(V\widehat{y}(x);x) (1.5) of the objective and constraint functions ( 1.4 ). The index k signals that the ROM, i.e, the matrices V,W\in\mathbb{R}^{N\times r} , are built from FOM information at the iterate x_{k} and, possibly, at previous iterates. The approximation properties of the models ( 1.5 ) and of their derivatives can be controlled by the selection of V,W\in\mathbb{R}^{N\times r} . We use ROMs to compute function approximations in the boundary control problem governed by the Boussinesq PDE. However, we note that our generalization of the line-search SQP algorithm with \ell_{1} -merit function is agnostic about how the function approximations are computed. It specifies approximation properties that these function approximations have to satisfy. ROM-generated approximations are one way to generate these models. There are many approaches for smooth unconstrained optimization problems that allow objective function models with tunable accuracy, including [ 1 ] , [ 7 ] , [ 8 ] , [ 20 ] , [ 14 ] , [ 28 ] . These and related approaches have been used, e.g., in [ 19 ] , [ 22 ] , [ 25 ] , [ 27 ] , [ 29 ] to manage the construction of ROMs to accelerate PDE-constrained optimization problems. Our proposed algorithm builds on [ 14 ] , [ 28 ] and it is equal to the approach in [ 14 ] if there are no constraints. Line-search SQP methods with \ell_{1} -merit function go back to the work [ 15 ] , and have been successfully used to solve smooth equality-constrained problems ( 1.1 ). See, e.g., [ 6 , Ch. 17] , [ 5 ] , [ 21 , Ch. 18] , [ 12 ] . In comparison to the unconstrained case, there are relatively few approaches to solve problems like ( 1.1 ) using function models with tunable accuracy. Approaches include [ 16 ] , [ 26 ] , [ 31 ] , [ 30 ] . The last two papers consider models derived from PDE discretizations and include the PDE as an explicit constraint. This is different from the setting we tackle, where a discretized PDE appears implicitly, if at all. The paper [ 16 ] also considers a line-search SQP method with \ell_{1} -merit function, for PDE-constrained optimization, but in their problem, the constraints do not depend on the PDE solution and therefore inexactness only appears in