Analytical bounds on the heat transport in internally heated convection - Kumar, Anuj; Arslan, Ali; Fantuzzi, Giovanni; Craske, John; Wynn, Andrew (Journal of Fluid Mechanics, 2022)
We obtain an analytical bound on the non-dimensional mean vertical convective heat flux between two parallel boundaries driven by uniform internal heating. We consider two configurations. In the first, both boundaries are held at the same constant temperature and measures the asymmetry of the heat fluxes escaping the layer through the top and bottom boundaries. In the second configuration, the top boundary is held at constant temperature, the bottom one is perfectly insulating, and is related to the difference between the horizontally-averaged temperatures of the two boundaries. For the first configuration, Arslan et al. (J. Fluid Mech., vol. 919, 2021, p. A15) recently provided numerical evidence that Rayleigh-number-dependent corrections to the only known rigorous bound may be provable if the classical background method is augmented with a minimum principle stating that the fluid's temperature is no smaller than that of the top boundary. Here, we confirm this fact rigorously for both configurations by proving bounds on that approach exponentially from below as the Rayleigh number is increased. The key to obtaining these bounds is inner boundary layers in the background fields with a particular inverse-power scaling, which can be controlled in the spectral constraint using Hardy and Rellich inequalities. These allow for qualitative improvements in the analysis that are not available to standard constructions.
CRIS-Team Scopus Importer:2022-09-26
Keywords: variational methods

Auxiliary Functions as Koopman Observables: Data-Driven Analysis of Dynamical Systems via Polynomial Optimization - Bramburger, Jason J.; Fantuzzi, Giovanni (Journal of Nonlinear Science, 2024)
We present a flexible data-driven method for dynamical system analysis that does not require explicit model discovery. The method is rooted in well-established techniques for approximating the Koopman operator from data and is implemented as a semidefinite program that can be solved numerically. Furthermore, the method is agnostic of whether data are generated through a deterministic or stochastic process, so its implementation requires no prior adjustments by the user to accommodate these different scenarios. Rigorous convergence results justify the applicability of the method, while also extending and uniting similar results from across the literature. Examples on discovering Lyapunov functions, performing ergodic optimization, and bounding extrema over attractors for both deterministic and stochastic dynamics exemplify these convergence results and demonstrate the performance of the method.
Keywords: Koopman operator; auxiliary function; dynamic mode decomposition; semidefinite programming; time average; Lyapunov function

Bounding extreme events in nonlinear dynamics using convex optimization - Fantuzzi, Giovanni; Goluskin, David (SIAM Journal on Applied Dynamical Systems, 2020)
We study a convex optimization framework for bounding extreme events in nonlinear dynamical systems governed by ordinary or partial differential equations (ODEs or PDEs). This framework bounds from above the largest value of an observable along trajectories that start from a chosen set and evolve over a finite or infinite time interval. The approach needs no explicit trajectories. Instead, it requires constructing suitably constrained auxiliary functions that depend on the state variables and possibly on time. Minimizing bounds over auxiliary functions is a convex problem dual to the nonconvex maximization of the observable along trajectories. This duality is strong, meaning that auxiliary functions give arbitrarily sharp bounds, for sufficiently regular ODEs evolving over a finite time on a compact domain. When these conditions fail, strong duality may or may not hold; both situations are illustrated by examples. We also show that near-optimal auxiliary functions can be used to construct spacetime sets that localize trajectories leading to extreme events. Finally, in the case of polynomial ODEs and observables, we describe how polynomial auxiliary functions of fixed degree can be optimized numerically using polynomial optimization. The corresponding bounds become sharp as the polynomial degree is raised if strong duality and mild compactness assumptions hold. Analytical and computational ODE examples illustrate the construction of bounds and the identification of extreme trajectories, along with some limitations. As an analytical PDE example, we bound the maximum fractional enstrophy of solutions to the Burgers equation with fractional diffusion.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Auxiliary functions; Bounds; Differential equations; Extreme events; Nonlinear dynamics; Polynomial optimization

Bounds for deterministic and stochastic dynamical systems using sum-of-squares optimization - Fantuzzi, Giovanni; Goluskin, David; Huang, D.; Chernyshenko, S. I. (SIAM Journal on Applied Dynamical Systems, 2016)
We describe methods for proving upper and lower bounds on infinite-time averages in deterministic dynamical systems and on stationary expectations in stochastic systems. The dynamics and the quantities to be bounded are assumed to be polynomial functions of the state variables. The methods are computer-assisted, using sum-of-squares polynomials to formulate sufficient conditions that can be checked by semidefinite programming. In the deterministic case, we seek tight bounds that apply to particular local attractors. An obstacle to proving such bounds is that they do not hold globally; they are generally violated by trajectories starting outside the local basin of attraction. We describe two closely related ways past this obstacle: one that requires knowing a subset of the basin of attraction, and another that considers the zero-noise limit of the corresponding stochastic system. The bounding methods are illustrated using the van der Pol oscillator. We bound deterministic averages on the attracting limit cycle above and below to within 1%, which requires a lower bound that does not hold for the unstable fixed point at the origin. We obtain similarly tight upper and lower bounds on stochastic expectations for a range of noise amplitudes. Limitations of our methods for certain types of deterministic systems are discussed, along with prospects for improvement.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Bounds; Stochastic expectations; Sum-of-squares optimization; Time averages

Bounds for internally heated convection with fixed boundary heat flux - Arslan, Ali; Fantuzzi, Giovanni; Craske, John; Wynn, Andrew (Journal of Fluid Mechanics, 2021)
We prove a new rigorous bound for the mean convective heat transport, where and are the non-dimensional vertical velocity and temperature, in internally heated convection between an insulating lower boundary and an upper boundary with a fixed heat flux. The quantity is equal to half the ratio of convective to conductive vertical heat transport, and also to plus the mean temperature difference between the top and bottom boundaries. An analytical application of the background method based on the construction of a quadratic auxiliary function yields uniformly in the Prandtl number, where R is the non-dimensional control parameter measuring the strength of the internal heating. Numerical optimisation of the auxiliary function suggests that the asymptotic value of this bound and the exponent are optimal within our bounding framework. This new result halves the best existing (uniform in) bound (Goluskin, Internally Heated Convection and Rayleigh-Bénard Convection, Springer, 2016, table 1.2), and its dependence on is consistent with previous conjectures and heuristic scaling arguments. Contrary to physical intuition, however, it does not rule out a mean heat transport larger than at high, which corresponds to the top boundary being hotter than the bottom one on average.
CRIS-Team Scopus Importer:2022-09-26
Keywords: variational methods

Bounds for Rayleigh–Bénard convection between free-slip boundaries with an imposed heat flux - Fantuzzi, Giovanni (Journal of Fluid Mechanics, 2018)
We prove the first rigorous bound on the heat transfer for three-dimensional Rayleigh–Bénard convection of finite-Prandtl-number fluids between free-slip boundaries with an imposed heat flux. Using the auxiliary functional method with a quadratic functional, which is equivalent to the background method, we prove that the Nusselt number Nu is bounded by Nu 6 0.5999R1/3 uniformly in the Prandtl number, where R is the Rayleigh number based on the imposed heat flux. In terms of the Rayleigh number based on the mean vertical temperature drop, Ra, we obtain Nu 6 0.4646Ra1/2. The scaling with Rayleigh number is the same as that of bounds obtained with no-slip isothermal, free-slip isothermal and no-slip fixed-flux boundaries, and numerical optimisation of the bound suggests that it cannot be improved within our bounding framework. Contrary to the two-dimensional case, therefore, the Ra-dependence of rigorous upper bounds on the heat transfer obtained with the background method for three-dimensional Rayleigh–Bénard convection is insensitive to both the thermal and the velocity boundary conditions.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Bénard convection; turbulent convection; variational methods

Bounds on heat transfer by incompressible flows between balanced sources and sinks - Song, Binglin; Fantuzzi, Giovanni; Tobasco, Ian (Physica D-Nonlinear Phenomena, 2023)
Internally heated convection involves the transfer of heat by fluid motion between a distribution of sources and sinks. Focusing on the balanced case where the total heat added by the sources matches the heat taken away by the sinks, we obtain a priori bounds on the minimum mean thermal dissipation 〈|∇T|2〉 as a measure of the inefficiency of transport. In the advective limit, our bounds scale with the inverse mean kinetic energy of the flow. The constant in this scaling law depends on the source–sink distribution, as we explain both in a pair of examples involving oscillatory or concentrated heating and cooling, and via a general asymptotic variational principle for optimizing transport. Key to our analysis is the solution of a pure advection equation, which we do to find examples of extreme heat transfer by cellular and ‘pinching’ flows. When the flow obeys a momentum equation, our bound is re-expressed in terms of a flux-based Rayleigh number R yielding 〈|∇T|2〉≥CR−α. The power α is 0,2/3 or 1 depending on the arrangement of the sources and sinks relative to gravity.
Created from Fastlane, Scopus look-up
Keywords: Advection–diffusion equation; Convection; Heat transport; Internal heating; Variational methods

Bounds on heat transfer for Bénard-Marangoni convection at infinite Prandtl number - Fantuzzi, Giovanni; Pershin, Anton; Wynn, Andrew (Journal of Fluid Mechanics, 2018)
The vertical heat transfer in Bénard-Marangoni convection of a fluid layer with infinite Prandtl number is studied by means of upper bounds on the Nusselt number as a function of the Marangoni number . Using the background method for the temperature field, it has recently been proved by Hagstrom & Doering (Phys. Rev. E, vol. 81, 2010, art. 047301) that . In this work we extend previous background method analysis to include balance parameters and derive a variational principle for the bound on , expressed in terms of a scaled background field, that yields a better bound than Hagstrom & Doering's formulation at a given . Using a piecewise-linear, monotonically decreasing profile we then show that , lowering the previous prefactor by 4.2Â %. However, we also demonstrate that optimisation of the balance parameters does not affect the asymptotic scaling of the optimal bound achievable with Hagstrom & Doering's original formulation. We subsequently utilise convex optimisation to optimise the bound on over all admissible background fields, as well as over two smaller families of profiles constrained by monotonicity and convexity. The results show that when the background field has a non-monotonic boundary layer near the surface, while a power-law bound with exponent is optimal within the class of monotonic background fields. Further analysis of our upper-bounding principle reveals the role of non-monotonicity, and how it may be exploited in a rigorous mathematical argument.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Marangoni convection; turbulent convection; variational methods

Bounds on heat transport for convection driven by internal heating - Arslan, Ali; Fantuzzi, Giovanni; Craske, John; Wynn, Andrew (Journal of Fluid Mechanics, 2021)
The mean vertical convective heat transport between isothermal plates driven by uniform internal heating is investigated by means of rigorous bounds. These are obtained as a function of the Rayleigh number R by constructing feasible solutions to a convex variational problem, derived using a formulation of the classical background method in terms of a quadratic auxiliary function. When the fluid's temperature relative to the boundaries is allowed to be positive or negative, numerical solution of the variational problem shows that best previous bound (Goluskin & Spiegel, Phys. Lett. A, vol. 377, issue 1-2, 2012, pp. 83-92) can only be improved up to finite R. Indeed, we demonstrate analytically that and therefore prove that <![CDATA[wTfor <![CDATA[R. However, if the minimum principle for temperature is invoked, which asserts that internal temperature is at least as large as the temperature of the isothermal boundaries, then numerically optimised bounds are strictly smaller than until at least. While the computational results suggest that the best bound on approaches asymptotically from below as, we prove that typical analytical constructions cannot be used to prove this conjecture.
CRIS-Team Scopus Importer:2022-09-26
Keywords: variational methods

Bounds on mean energy in the Kuramoto-Sivashinsky equation computed using semidefinite programming - Goluskin, David; Fantuzzi, Giovanni (Nonlinearity, 2019)
We present methods for bounding infinite-time averages in dynamical systems governed by nonlinear PDEs. The methods rely on auxiliary functionals, which are similar to Lyapunov functionals but satisfy different inequalities. The inequalities are enforced by requiring certain expressions to be sums of squares of polynomials, and the optimal choice of auxiliary functional is posed as a semidefinite program (SDP) that can be solved computationally. To formulate these SDPs we approximate the PDE by truncated systems of ODEs and proceed in one of two ways. The first approach is to compute bounds for the ODE systems, increasing the truncation order until bounds converge numerically. The second approach incorporates the ODE systems with analytical estimates on their deviation from the PDE, thereby using finite truncations to produce bounds for the full PDE. We apply both methods to the Kuramoto-Sivashinsky equation. In particular, we compute upper bounds on the spatiotemporal average of energy by employing polynomial auxiliary functionals up to degree six. The first approach is used for most computations, but a subset of results are checked using the second approach, and the results agree to high precision. These bounds apply to all odd solutions of period 2πL, where L is varied. Sharp bounds are obtained for L ≤≤ 10, and trends suggest that more expensive computations would yield sharp bounds at larger L also. The bounds are known to be sharp (to within 0.1% numerical error) because they are saturated by the simplest nonzero steady states, which apparently have the largest mean energy among all odd solutions. Prior authors have conjectured that mean energy remains O(1) for L ≥≥ 1 since no particular solutions with larger energy have been found. Our bounds constitute the first positive evidence for this conjecture, albeit up to finite L, and they offer some guidance for analytical proofs.
CRIS-Team Scopus Importer:2022-09-26
Keywords: auxiliary functional; bounds; Kuramoto-Sivashinsky equation; semidefinite programming; sum of squares polynomials

Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization - Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis (Annual Reviews in Control, 2021)
Chordal and factor-width decomposition methods for semidefinite programming and polynomial optimization have recently enabled the analysis and control of large-scale linear systems and medium-scale nonlinear systems. Chordal decomposition exploits the sparsity of semidefinite matrices in a semidefinite program (SDP), in order to formulate an equivalent SDP with smaller semidefinite constraints that can be solved more efficiently. Factor-width decompositions, instead, relax or strengthen SDPs with dense semidefinite matrices into more tractable problems, trading feasibility or optimality for lower computational complexity. This article reviews recent advances in large-scale semidefinite and polynomial optimization enabled by these two types of decomposition, highlighting connections and differences between them. We also demonstrate that chordal and factor-width decompositions allow for significant computational savings on a range of classical problems from control theory, and on more recent problems from machine learning. Finally, we outline possible directions for future research that have the potential to facilitate the efficient optimization-based study of increasingly complex large-scale dynamical systems.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Chordal sparsity; Factor-width decomposition; Large-scale systems; Matrix decomposition; Polynomial optimization; Scalability; Semidefinite optimization; Sum-of-squares

Chordal decomposition in operator-splitting methods for sparse semidefinite programs - Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis; Goulart, Paul; Wynn, Andrew (Mathematical Programming, 2020)
We employ chordal decomposition to reformulate a large and sparse semidefinite program (SDP), either in primal or dual standard form, into an equivalent SDP with smaller positive semidefinite (PSD) constraints. In contrast to previous approaches, the decomposed SDP is suitable for the application of first-order operator-splitting methods, enabling the development of efficient and scalable algorithms. In particular, we apply the alternating direction method of multipliers (ADMM) to solve decomposed primal- and dual-standard-form SDPs. Each iteration of such ADMM algorithms requires a projection onto an affine subspace, and a set of projections onto small PSD cones that can be computed in parallel. We also formulate the homogeneous self-dual embedding (HSDE) of a primal-dual pair of decomposed SDPs, and extend a recent ADMM-based algorithm to exploit the structure of our HSDE. The resulting HSDE algorithm has the same leading-order computational cost as those for the primal or dual problems only, with the advantage of being able to identify infeasible problems and produce an infeasibility certificate. All algorithms are implemented in the open-source MATLAB solver CDCS. Numerical experiments on a range of large-scale SDPs demonstrate the computational advantages of the proposed methods compared to common state-of-the-art solvers.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Chordal decomposition; First-order methods; Operator-splitting; Sparse SDPs

Clustering in Pure-Attention Hardmax Transformers and its Role in Sentiment Analysis - Alcalde Zafra, Albert; Fantuzzi, Giovanni; Zuazua Iriondo, Enrique (2024)
Transformers are extremely successful machine learning models whose mathematical properties remain poorly understood. Here, we rigorously characterize the behavior of transformers with hardmax self-attention and normalization sublayers as the number of layers tends to infinity. By viewing such transformers as discrete-time dynamical systems describing the evolution of points in a Euclidean space, and thanks to a geometric interpretation of the self-attention mechanism based on hyperplane separation, we show that the transformer inputs asymptotically converge to a clustered equilibrium determined by special points called leaders. We then leverage this theoretical understanding to solve sentiment analysis problems from language processing using a fully interpretable transformer model, which effectively captures `context' by clustering meaningless words around leader words carrying the most meaning. Finally, we outline remaining challenges to bridge the gap between the mathematical analysis of transformers and their real-life implementation. </block
https://cris.fau.de/converis/publicweb/Publication/324741614
Keywords: transformers; self-attention; clustering; AI interpretability; sentiment analysis

Construction of an optimal background profile for the Kuramoto-Sivashinsky equation using semidefinite programming - Wynn, Andrew; Fantuzzi, Giovanni (Physics Letters A, 2015)
A method to construct systematically an optimal background profile for the Kuramoto-Sivashinsky equation is developed by formulating the classical problem as an optimisation problem. In particular, we show that the infinite-dimensional problem can be rewritten as a finite-dimensional convex semidefinite problem, which is solved to construct a background profile and to obtain an upper bound on the energy of the solution ||u|| that applies to the infinite-dimensional PDE. The results are compared to existing analytical results, and support the fact that limsupt→∞||u||≤bsupesup is the optimal estimate achievable with the background profile method and a quadratic Lyapunov function.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Kuramoto-Sivashinsky; Optimal background profile; Semidefinite programming

Convex Relaxations of Integral Variational Problems: Pointwise Dual Relaxation and Sum-of-Squares Optimization - Fantuzzi, Giovanni; Chernyavsky, Alexandr; Goluskin, David; Bramburger, Jason (SIAM Journal on Optimization, 2023)
We present a method for finding lower bounds on the global infima of integral variational problems, wherein ∫Ωf(x,u(x),∇u(x))dx is minimized over functions u:Ω⊂Rn→Rm satisfying given equality or inequality constraints. Each constraint may be imposed over Ω or its boundary, either pointwise or in an integral sense. These global minimizations are generally non-convex and intractable. We formulate a particular convex maximization, here called the pointwise dual relaxation (PDR), whose supremum is a lower bound on the infimum of the original problem. The PDR can be derived by dualizing and relaxing the original problem; its constraints are pointwise equalities or inequalities over finite-dimensional sets, rather than over infinite-dimensional function spaces. When the original minimization can be specified by polynomial functions of (x,u,∇u), the PDR can be further relaxed by replacing pointwise inequalities with polynomial sum-of-squares (SOS) conditions. The resulting SOS program is computationally tractable when the dimensions m,n and number of constraints are not too large. The framework presented here generalizes an approach of Valmorbida, Ahmadi, and Papachristodoulou (IEEE Trans. Automat. Contr., 61:1649–1654, 2016). We prove that the optimal lower bound given by the PDR is sharp for several classes of problems, whose special cases include leading eigenvalues of Sturm-Liouville problems and optimal constants of Poincaré inequalities. For these same classes, we prove that SOS relaxations of the PDR converge to the sharp lower bound as polynomial degrees are increased. Convergence of SOS computations in practice is illustrated for several example

Data-driven discovery of invariant measures - Bramburger, Jason J.; Fantuzzi, Giovanni (Proceedings of the Royal Society A-Mathematical Physical and Engineering Sciences, 2024)

Decomposition and Completion of Sum-of-Squares Matrices - Zheng, Yang; Papachristodoulou, Antonis; Fantuzzi, Giovanni (Proceedings of the IEEE Conference on Decision and Control, 2018)
This paper introduces a notion of decomposition and completion of sum-of-squares (SOS) matrices. We show that a subset of sparse SOS matrices with chordal sparsity patterns can be equivalently decomposed into a sum of multiple SOS matrices that are nonzero only on a principal submatrix. Also, the completion of an SOS matrix is equivalent to a set of SOS conditions on its principal submatrices and a consistency condition on the Gram representation of the principal submatrices. These results are partial extensions of chordal decomposition and completion of scalar matrices to matrices with polynomial entries. We apply the SOS decomposition result to exploit sparsity in matrix-valued SOS programs. Numerical results demonstrate the high potential of this approach for solving large-scale sparse matrix-valued SOS programs.
CRIS-Team Scopus Importer:2022-09-26

Decomposition methods for large-scale semidefinite programs with chordal aggregate sparsity and partial orthogonality - Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis (Springer Verlag, 2018)
Many semidefinite programs (SDPs) arising in practical applications have useful structural properties that can be exploited at the algorithmic level. In this chapter, we review two decomposition frameworks for large-scale SDPs characterized by either chordal aggregate sparsity or partial orthogonality. Chordal aggregate sparsity allows one to decompose the positive semidefinite matrix variable in the SDP, while partial orthogonality enables the decomposition of the affine constraints. The decomposition frameworks are particularly suitable for the application of first-order algorithms. We describe how the decomposition strategies enable one to speed up the iterations of a first-order algorithm, based on the alternating direction method of multipliers, for the solution of the homogeneous self-dual embedding of a primal-dual pair of SDPs. Precisely, we give an overview of two structure-exploiting algorithms for semidefinite programming, which have been implemented in the open-source MATLAB solver CDCS. Numerical experiments on a range of large-scale SDPs demonstrate that the decomposition methods described in this chapter promise significant computational gains.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Chordal decomposition; Decomposition methods; Large-scale semidefinite programs; Operator-splitting algorithms; Partial orthogonality

Exact energy stability of Bénard-Marangoni convection at infinite Prandtl number - Fantuzzi, Giovanni; Wynn, Andrew (Journal of Fluid Mechanics, 2017)
Using the energy method we investigate the stability of pure conduction in Pearson's model for Bénard-Marangoni convection in a layer of fluid at infinite Prandtl number. Upon extending the space of admissible perturbations to the conductive state, we find an exact solution to the energy stability variational problem for a range of thermal boundary conditions describing perfectly conducting, imperfectly conducting, and insulating boundaries. Our analysis extends and improves previous results, and shows that with the energy method global stability can be proven up to the linear instability threshold only when the top and bottom boundaries of the fluid layer are insulating. Contrary to the well-known Rayleigh-Bénard convection set-up, therefore, energy stability theory does not exclude the possibility of subcritical instabilities against finite-amplitude perturbations.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Marangoni convection; nonlinear instability; variational methods

Exact Sequence Classification with Hardmax Transformers - Alcalde Zafra, Albert; Fantuzzi, Giovanni; Zuazua Iriondo, Enrique (2025)
We prove that hardmax attention transformers perfectly classify datasets of N labeled sequences in R^d, d≥ 2. Specifically, given N sequences with an arbitrary but finite length in R^d, we construct a transformer with O(N) blocks and O(Nd) parameters perfectly classifying this dataset. Our construction achieves the best complexity estimate to date, independent of the length of the sequences, by innovatively alternating feed-forward and self-attention layers and by capitalizing on the clustering effect inherent to the latter. Our novel constructive method also uses low-rank parameter matrices within the attention mechanism, a common practice in real-life transformer implementations. Consequently, our analysis holds twofold significance: it substantially advances the mathematical theory of transformers and it rigorously justifies their exceptional real-world performance in sequence classification task
https://cris.fau.de/converis/publicweb/Publication/334528458
Keywords: Transformers; Self-Attention Mechanism; Exact Classification; Theory of Deep Learning

Exploiting sparsity in the coefficient matching conditions in sum-of-squares programming using ADMM - Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis (IEEE Control Systems Letters, 2017)
This letter introduces an efficient first-order method based on the alternating direction method of multipliers (ADMM) to solve semidefinite programs arising from sum-of-squares (SOS) programming. We exploit the sparsity of the coefficient matching conditions when SOS programs are formulated in the usual monomial basis to reduce the computational cost of the ADMM algorithm. Each iteration of our algorithm requires one projection onto the positive semidefinite cone and the solution of multiple quadratic programs with closed-form solutions free of any matrix inversion. Our techniques are implemented in the open-source MATLAB solver SOSADMM. Numerical experiments on SOS problems arising from unconstrained polynomial minimization and from Lyapunov stability analysis for polynomial systems show speed-ups compared to the interior-point solver SeDuMi, and the first-order solver CDCS.
CRIS-Team Scopus Importer:2022-09-26
Keywords: ADMM; Large-scale problems; Sum-of-squares

Fast ADMM for homogeneous self-dual embedding of sparse SDPs - Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis; Goulart, Paul; Wynn, Andrew (IFAC-PapersOnLine, 2017)
We propose an efficient first-order method, based on the alternating direction method of multipliers (ADMM), to solve the homogeneous self-dual embedding problem for a primal-dual pair of semidefinite programs (SDPs) with chordal sparsity. Using a series of block eliminations, the per-iteration cost of our method is the same as applying a splitting method to the primal or dual alone. Moreover, our approach is more efficient than other first-order methods for generic sparse conic programs since we work with smaller semidefinite cones. In contrast to previous first-order methods that exploit chordal sparsity, our algorithm returns both primal and dual solutions when available, and a certificate of infeasibility otherwise. Our techniques are implemented in the open-source MATLAB solver CDCS. Numerical experiments on three sets of benchmark problems from the library SDPLIB show speed-ups compared to some common state-of-the-art software packages.
CRIS-Team Scopus Importer:2022-09-26
Keywords: chordal sparsity; Convex optimization; first-order methods; large-scale problems; semidefinite programs

Fast ADMM for semidefinite programs with chordal sparsity - Zheng, Yang; Papachristodoulou, Antonis; Goulart, Paul; Wynn, Andrew; et al. (Proceedings of the American Control Conference, 2017)
Many problems in control theory can be formulated as semidefinite programs (SDPs). For large-scale SDPs, it is important to exploit the inherent sparsity to improve scalability. This paper develops efficient first-order methods to solve SDPs with chordal sparsity based on the alternating direction method of multipliers (ADMM). We show that chordal decomposition can be applied to either the primal or the dual standard form of a sparse SDP, resulting in scaled versions of ADMM algorithms with the same computational cost. Each iteration of our algorithms consists of a projection on the product of small positive semidefinite cones, followed by a projection on an affine set, both of which can be carried out efficiently. Our techniques are implemented in CDCS, an open source add-on to MATLAB. Numerical experiments on large-scale sparse problems in SDPLIB and random SDPs with block-arrow sparse patterns show speedups compared to some common state-of-the-art software packages.
CRIS-Team Scopus Importer:2022-09-26

Fast ADMM for sum-of-squares programs using partial orthogonality - Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis (IEEETransactions on Automatic Control, 2019)
When sum-of-squares (SOS) programs are recast as semidefinite programs (SDPs) using the standard monomial basis, the constraint matrices in the SDP possess a structural property that we call partial orthogonality. In this paper, we leverage partial orthogonality to develop a fast first-order method, based on the alternating direction method of multipliers (ADMM), for the solution of the homogeneous self-dual embedding of SDPs describing SOS programs. Precisely, we show how a “diagonal plus low rank” structure implied by partial orthogonality can be exploited to project efficiently the iterates of a recent ADMM algorithm for generic conic programs onto the set defined by the affine constraints of the SDP. The resulting algorithm, implemented as a new package in the solver CDCS, is tested on a range of large-scale SOS programs arising from constrained polynomial optimization problems and from Lyapunov stability analysis of polynomial dynamical systems. These numerical experiments demonstrate the effectiveness of our approach compared to common state-of-the-art solvers.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Alternating direction method of multipliers (ADMM); Large-scale optimization; Sum-of-squares (SOS)

Finding extremal periodic orbits with polynomial optimization, with application to a nine-mode model of shear flow - Lakshmi, Mayur; Fantuzzi, Giovanni; Fernandez-Caballero, Jesus D.; Hwang, Yongyun; Chernyshenko, Sergei (SIAM Journal on Applied Dynamical Systems, 2020)
Tobasco, Goluskin, and Doering [Phys. Lett. A, 382 (2018), pp. 382–386] recently suggested that trajectories of ODE systems that optimize the infinite-time average of a certain observable can be localized using sublevel sets of a function that arise when bounding such averages using so-called auxiliary functions. In this paper we demonstrate that this idea is viable and allows for the computation of extremal unstable periodic orbits (UPOs) for polynomial ODE systems. First, we prove that polynomial optimization is guaranteed to produce auxiliary functions that yield near-sharp bounds on time averages, which is required in order to localize the extremal orbit accurately. Second, we show that points inside the relevant sublevel sets can be computed efficiently through direct nonlinear optimization. Such points provide good initial conditions for UPO computations. As a proof of concept, we then combine these methods with a single-shooting Newton–Raphson algorithm to study extremal UPOs for a nine-dimensional model of sinusoidally forced shear flow. We discover three previously unknown families of UPOs, one of which simultaneously minimizes the mean energy dissipation rate and maximizes the mean perturbation energy relative to the laminar state for Reynolds numbers approximately between 81.24 and 125.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Ergodic optimization; Periodic orbits; Polynomial optimization

Finding unstable periodic orbits: A hybrid approach with polynomial optimization - Lakshmi, Mayur V.; Fantuzzi, Giovanni; Chernyshenko, Sergei I.; Lasagna, Davide (Physica D-Nonlinear Phenomena, 2021)
We present a novel method to compute unstable periodic orbits (UPOs) that optimize the infinite-time average of a given quantity for polynomial ODE systems. The UPO search procedure relies on polynomial optimization to construct nonnegative polynomials whose sublevel sets approximately localize parts of the optimal UPO, and that can be used to implement a simple yet effective control strategy to reduce the UPO's instability. Precisely, we construct a family of controlled ODE systems, parameterized by a scalar k, such that the original ODE system is recovered for k=0 and such that the optimal orbit is less unstable, or even stabilized, for k>0. Periodic orbits for the controlled system can often be more easily converged with traditional methods, and numerical continuation in k allows one to recover optimal UPOs for the original system. The effectiveness of this approach is illustrated on three low-dimensional ODE systems with chaotic dynamics.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Auxiliary functions; Differential equations; Nonlinear dynamics; Periodic orbits; Polynomial optimization

Finite Element Approximation of the Hardy Constant - Della Pietra, Francesco; Fantuzzi, Giovanni; Ignat, Liviu I.; Masiello, Alba Lia; Paoli, Gloria; Zuazua Iriondo, Enrique (Journal of Convex Analysis, 2024)
We consider finite element approximations to the optimal constant for the Hardy inequality with exponent p = 2 in bounded domains of dimension n = 1 or n ≥ 3. For finite element spaces of piecewise linear and continuous functions on a mesh of size h, we prove that the approximate Hardy constant converges to the optimal Hardy constant at a rate proportional to 1/|log h|2. This result holds in dimension n = 1, in any dimension n ≥ 3 if the domain is the unit ball and the finite element discretization exploits the rotational symmetry of the problem, and in dimension n = 3 for general finite element discretizations of the unit ball. In the first two cases, our estimates show excellent quantitative agreement with values of the discrete Hardy constant obtained computationally.
CRIS-Team Scopus Importer:2024-04-12
Keywords: finite element method; Hardy constant; Hardy inequality

Finite element approximation of the Hardy constant - Della Pietra, Francesco; Fantuzzi, Giovanni; Ignat, Liviu I.; Masiello, Alba Lia; Paoli, Gloria; Zuazua Iriondo, Enrique (2024)
We consider finite element approximations to the optimal constant for the Hardy inequality with exponent p=2 in bounded domains of dimension n=1 or n≥ 3. For finite element spaces of piecewise linear and continuous functions on a mesh of size h, we prove that the approximate Hardy constant, S_h^n, converges to the optimal Hardy constant S^n no slower than O(1/h). We also show that the convergence is no faster than O(1/h^2) if n=1 or if n≥ 3, the domain is the unit ball, and the finite element discretization exploits the rotational symmetry of the problem. Our estimates are compared to exact values for S_h^n obtained computationally.<br
https://cris.fau.de/converis/publicweb/Publication/308553439

Global minimization of polynomial integral functionals - Fantuzzi, Giovanni; Fuentes, Federico (SIAM Journal on Scientific Computing, 2024)
We describe a “discretize-then-relax” strategy to globally minimize integral functionals over functions u in a Sobolev space subject to Dirichlet boundary conditions. The strategy applies whenever the integral functional depends polynomially on u and its derivatives, even if it is nonconvex. The “discretize” step uses a bounded finite element scheme to approximate the integral minimization problem with a convergent hierarchy of polynomial optimization problems over a compact feasible set, indexed by the decreasing size h of the finite element mesh. The “relax” step employs sparse moment-sum-of-squares relaxations to approximate each polynomial optimization problem with a hierarchy of convex semidefinite programs, indexed by an increasing relaxation order ω. We prove that, as ω tends to infinity and h tends to zero, solutions of such semidefinite programs provide approximate minimizers that converge in a suitable sense (including in certain Lp norms) to the global minimizer of the original integral functional if it is unique. We also report computational experiments showing that our numerical strategy works well even when technical conditions required by our theoretical analysis are not satisfie
Keywords: Global minimization; calculus of variations; finite-element method; convex relaxation; sparse polynomial optimization; moment-SOS hierarchy

Internal heating profiles for which downward conduction is impossible - Arslan, Ali; Fantuzzi, Giovanni; Craske, John; Wynn, Andrew (Journal of Fluid Mechanics, 2024)
We consider an internally heated fluid between parallel plates with fixed thermal fluxes. For a large class of heat sources that vary in the direction of gravity, we prove that ⟨δT⟩h≥σR−1/3−μ, where ⟨δT⟩h is the average temperature difference between the bottom and top plates, R is a 'flux' Rayleigh number and the constants σ,μ>0 depend on the geometric properties of the internal heating. This result implies that mean downward conduction (for which ⟨δT⟩h 0) is impossible for a range of Rayleigh numbers smaller than a critical value R0:=(σ/μ)3. The bound demonstrates that R0 depends on the heating distribution and can be made arbitrarily large by concentrating the heating near the bottom plate. However, for any given fixed heating profile of the class we consider, the corresponding value of R0 is always finite. This points to a fundamental difference between internally heated convection and its limiting case of Rayleigh-Bénard convection with fixed-flux boundary conditions, for which ⟨δT⟩h is known to be positive for all R.
CRIS-Team Scopus Importer:2024-09-27
Keywords: turbulent convection; variational methods

New bounds on the vertical heat transport for Bénard-Marangoni convection at infinite Prandtl number - Fantuzzi, Giovanni; Nobili, Camilla; Wynn, Andrew (Journal of Fluid Mechanics, 2019)
We prove a new rigorous upper bound on the vertical heat transport for Bénard-Marangoni Â convection of a two-or three-dimensional fluid layer with infinite Prandtl number. Precisely, for Marangoni number the Nusselt number is bounded asymptotically by. Key to our proof are a background temperature field with a hyperbolic profile near the fluid's surface and new estimates for the coupling between temperature and vertical velocity.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Marangoni convection; variational methods

Optimal bounds with semidefinite programming: An application to stress-driven shear flows - Wynn, Andrew; Fantuzzi, Giovanni (Physical Review E, 2016)
We introduce an innovative numerical technique based on convex optimization to solve a range of infinite-dimensional variational problems arising from the application of the background method to fluid flows. In contrast to most existing schemes, we do not consider the Euler-Lagrange equations for the minimizer. Instead, we use series expansions to formulate a finite-dimensional semidefinite program (SDP) whose solution converges to that of the original variational problem. Our formulation accounts for the influence of all modes in the expansion, and the feasible set of the SDP corresponds to a subset of the feasible set of the original problem. Moreover, SDPs can be easily formulated when the fluid is subject to imposed boundary fluxes, which pose a challenge for the traditional methods. We apply this technique to compute rigorous and near-optimal upper bounds on the dissipation coefficient for flows driven by a surface stress. We improve previous analytical bounds by more than 10 times and show that the bounds become independent of the domain aspect ratio in the limit of vanishing viscosity. We also confirm that the dissipation properties of stress-driven flows are similar to those of flows subject to a body force localized in a narrow layer near the surface. Finally, we show that SDP relaxations are an efficient method to investigate the energy stability of laminar flows driven by a surface stress.
CRIS-Team Scopus Importer:2022-09-26

Optimization with affine homogeneous quadratic integral inequality constraints - Fantuzzi, Giovanni; Wynn, Andrew; Goulart, Paul J.; Papachristodoulou, Antonis (IEEETransactions on Automatic Control, 2017)
We introduce a new technique to optimize a linear cost function subject to an affine homogeneous quadratic integral inequality, i.e., the requirement that a homogeneous quadratic integral functional affine in the optimization variables is nonnegative over a space of functions defined by homogeneous boundary conditions. Such problems arise in control and stability or input-to-state/output analysis of systems governed by partial differential equations (PDEs), particularly fluid dynamical systems. We derive outer approximations for the feasible set of a homogeneous quadratic integral inequality in terms of linear matrix inequalities (LMIs), and show that a convergent sequence of lower bounds for the optimal cost can be computed with a sequence of semidefinite programs (SDPs). We also obtain inner approximations in terms of LMIs and sum-of-squares constraints, so upper bounds for the optimal cost and strictly feasible points for the integral inequality can be computed with SDPs. We present QUINOPT, an open-source add-on to YALMIP to aid the formulation and solution of our SDPs, and demonstrate our techniques on problems arising from the stability analysis of PDEs.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Integral inequalities; Partial differential equations (PDEs); Semidefinite programming; Sum-ofsquares optimization

Rigorous bounds on the heat transport of rotating convection with Ekman pumping - Pachev, Benjamin; Whitehead, J. P.; Fantuzzi, Giovanni; Grooms, Ian (Journal of Mathematical Physics, 2020)
We establish rigorous upper bounds on the time-averaged heat transport for a model of rotating Rayleigh-Bénard convection between no-slip boundaries at infinite Prandtl numbers and with Ekman pumping. The analysis is based on the asymptotically reduced equations derived for rotationally constrained dynamics with no-slip boundaries, and hence, includes a lower order correction that accounts for the Ekman layer and corresponding Ekman pumping into the bulk. Using the auxiliary functional method, we find that, to leading order, the temporally averaged heat transport is bounded above as a function of the Rayleigh and Ekman numbers Ra and Ek according to Nu ≤ 0.3704Ra2Ek2. Dependent on the relative values of the thermal forcing represented by Ra and the effects of rotation represented by Ek, this bound is both an improvement on earlier rigorous upper bounds and provides a partial explanation of recent numerical and experimental results that were consistent yet surprising relative to the previously derived upper bound of Nu ≲ Ra3Ek4
CRIS-Team Scopus Importer:2022-09-26

Rigorous scaling laws for internally heated convection at infinite Prandtl number - Arslan, Ali; Fantuzzi, Giovanni; John, Craske; Wynn, Andrew (Journal of Mathematical Physics, 2023)
New bounds are proven on the mean vertical convective heat transport, ⟨wT⟩, for uniform internally heated (IH) convection in the limit of infinite Prandtl number. For fluid in a horizontally-periodic layer between isothermal boundaries, we show that ⟨wT⟩≤1/2−cR−2, where R is a nondimensional `flux' Rayleigh number quantifying the strength of internal heating and c=216. Then, ⟨wT⟩=0 corresponds to vertical heat transport by conduction alone, while ⟨wT⟩>0 represents the enhancement of vertical heat transport upwards due to convective motion. If, instead, the lower boundary is a thermal insulator, then we obtain ⟨wT⟩≤1/2−cR−4, with c≈0.0107. This result implies that the Nusselt number Nu, defined as the ratio of the total-to-conductive heat transport, satisfies Nu≲R4. Both bounds are obtained by combining the background method with a minimum principle for the fluid's temperature and with Hardy-Rellich inequalities to exploit the link between the vertical velocity and temperature. In both cases, power-law dependence on R improves the previously best-known bounds, which, although valid at both infinite and finite Prandtl numbers, approach the uniform bound exponentially with R.
Keywords: Heat transfer; Mathematical optimization; Auxiliary functions; Calculus of variations; Fluid mechanics; Natural convection

Semidefinite relaxation of a class of quadratic integral inequalities - Fantuzzi, Giovanni; Wynn, Andrew (2016 IEEE 55th Conference on Decision and Control, CDC 2016, 2016)
We propose a novel technique to solve optimization problems subject to a class of integral inequalities whose integrand is quadratic and homogeneous with respect to the dependent variables, and affine in the parameters. We assume that the dependent variables are subject to homogeneous boundary conditions. Specifically, we derive rigorous relaxations of such integral inequalities in terms of semidefinite constraints, so a strictly feasible and near-optimal point for the original problem can be computed using semidefinite programming. Simple examples arising from the stability analysis of partial differential equations illustrate the potential of our method compared to existing techniques.
CRIS-Team Scopus Importer:2022-09-26

Sharpness and non-sharpness of occupation measure bounds for integral variational problems - Fantuzzi, Giovanni; Tobasco, Ian (2024)
We analyze two recently proposed methods to establish a priori lower bounds on the minimum of general integral variational problems. The methods, which involve either 'occupation measures' [Korda et al., ch. 10 of Numerical Control: Part A, https://doi.org/10.1016/bs.hna.2021.12.010] or a 'pointwise dual relaxation' procedure [Chernyavsky et al., arXiv:2110.03079], are shown to produce the same lower bound under a coercivity hypothesis ensuring their strong duality. We then show by a minimax argument that the methods actually evaluate the minimum for classes of one-dimensional, scalar-valued, or convex multidimensional problems. For generic problems, however, we conjecture that these methods should fail to capture the minimum and produce non-sharp lower bounds. We explain why using two examples, the first of which is one-dimensional and scalar-valued with a non-convex constraint, and the second of which is multidimensional and non-convex in a different way. The latter example emphasizes the existence in multiple dimensions of nonlinear constraints on gradient fields that are ignored by occupation measures, but are built into the finer theory of gradient Young measures, which we review.
https://cris.fau.de/converis/publicweb/Publication/287615895

Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials - Zheng, Yang; Papachristodoulou, Antonis; et al. (Proceedings of the American Control Conference, 2019)
Optimization over non-negative polynomials is fundamental for nonlinear systems analysis and control. This work investigates the relation between three tractable relaxations for optimizing over sparse non-negative polynomials: sparse sum-of-squares (SSOS) optimization, diagonally dominant sum-of-squares (DSOS) optimization, and scaled diagonally dominant sum-of-squares (SDSOS) optimization. We prove that the set of SSOS polynomials, an inner approximation of the cone of SOS polynomials, strictly contains the spaces of sparse DSOS/SDSOS polynomials. For problems with sparse polynomials, therefore, SSOS optimization is less conservative than its DSOS/SDSOS counterparts. Numerical results for large-scale sparse polynomial optimization problems demonstrate this fact, and also that SSOS optimization can be faster than DSOS/SDSOS methods despite requiring the solution of semidefinite programs instead of less expensive linear/second-order cone programs.
CRIS-Team Scopus Importer:2022-09-26

Sum-of-squares chordal decomposition of polynomial matrix inequalities - Zheng, Yang; Fantuzzi, Giovanni (Mathematical Programming, 2021)
We prove decomposition theorems for sparse positive (semi)definite polynomial matrices that can be viewed as sparsity-exploiting versions of the Hilbert–Artin, Reznick, Putinar, and Putinar–Vasilescu Positivstellensätze. First, we establish that a polynomial matrix P(x) with chordal sparsity is positive semidefinite for all x∈ Rn if and only if there exists a sum-of-squares (SOS) polynomial σ(x) such that σP is a sum of sparse SOS matrices. Second, we show that setting σ(x)=(x12+⋯+xn2)ν for some integer ν suffices if P is homogeneous and positive definite globally. Third, we prove that if P is positive definite on a compact semialgebraic set K= x: g1(x) ≥ 0 , … , gm(x) ≥ 0 satisfying the Archimedean condition, then P(x) = S(x) + g1(x) S1(x) + ⋯ + gm(x) Sm(x) for matrices Si(x) that are sums of sparse SOS matrices. Finally, if K is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for (x12+⋯+xn2)νP(x) with some integer ν≥ 0 when P and g1, … , gm are homogeneous of even degree. Using these results, we find sparse SOS representation theorems for polynomials that are quadratic and correlatively sparse in a subset of variables, and we construct new convergent hierarchies of sparsity-exploiting SOS reformulations for convex optimization problems with large and sparse polynomial matrix inequalities. Numerical examples demonstrate that these hierarchies can have a significantly lower computational complexity than traditional ones.
CRIS-Team Scopus Importer:2022-09-26
Keywords: Chordal decomposition; Polynomial matrix inequalities; Polynomial optimization

The background method: Theory and computations - Fantuzzi, Giovanni; Arslan, Ali; Wynn, Andrew (Philosophical Transactions of the Royal Society A-Mathematical Physical and Engineering Sciences, 2022)
The background method is a widely used technique to bound mean properties of turbulent flows rigorously. This work reviews recent advances in the theoretical formulation and numerical implementation of the method. First, we describe how the background method can be formulated systematically within a broader 'auxiliary function' framework for bounding mean quantities, and explain how symmetries of the flow and constraints such as maximum principles can be exploited. All ideas are presented in a general setting and are illustrated on Rayleigh-Bénard convection between stress-free isothermal plates. Second, we review a semidefinite programming approach and a timestepping approach to optimizing bounds computationally, revealing that they are related to each other through convex duality and low-rank matrix factorization. Open questions and promising directions for further numerical analysis of the background method are also outlined. This article is part of the theme issue 'Mathematical problems in physical fluid dynamics (part 1)'.
CRIS-Team Scopus Importer:2022-09-26
Keywords: auxiliary functions; background method; bounds; semidefinite programming; variational methods

Uncertainty propagation for nonlinear dynamics: A polynomial optimization approach - Covella, Francesca; Fantuzzi, Giovanni (2023 American Control Conference (ACC), 2023)
We use Lyapunov-like functions and convex optimization to propagate uncertainty in the initial condition of nonlinear systems governed by ordinary differential equations. We consider the full nonlinear dynamics without approximation, producing rigorous bounds on the expected future value of a quantity of interest even when only limited statistics of the initial condition (e.g., mean and variance) are known. For dynamical systems evolving in compact sets, the best upper (lower) bound coincides with the largest (smallest) expectation among all initial state distributions consistent with the known statistics. For systems governed by polynomial equations and polynomial quantities of interest, one-sided estimates on the optimal bounds can be computed using tools from polynomial optimization and semidefinite programming. Moreover, these numerical bounds provably converge to the optimal ones in the compact case. We illustrate the approach on a van der Pol oscillator and on the Lorenz system in the chaotic regime.<br

Verification of some functional inequalities via polynomial optimization - Fantuzzi, Giovanni (IFAC-PapersOnLine, 2022)
Motivated by the application of Lyapunov methods to partial differential equations (PDEs), we study functional inequalities of the form f(I1(u), . . . , Ik(u))≥ 0 where f is a polynomial, u is any function satisfying prescribed constraints, and I1(u), . . . , Ik(u) are integral functionals whose integrands are polynomial in u, its derivatives, and the integration variable. We show that such functional inequalities can be strengthened into sufficient polynomial inequalities, which in principle can be checked via semidefinite programming using standard techniques for polynomial optimization. These sufficient conditions can be used also to optimize functionals with affine dependence on tunable parameters whilst ensuring their nonnegativity. Our approach relies on a measure-theoretic lifting of the original functional inequality, which extends both a recent moment relaxation strategy for PDE analysis and a dual approach to inequalities for integral functionals.
Created from Fastlane, Scopus look-up
Keywords: distributed parameter systems; Functional inequalities; Lyapunov methods; moment relaxations; partial differential equations; polynomial optimization