Search

Many problems in engineering can be understood as controlling the bifurcation structure of a given device. For example, one may wish to delay the onset of instability, or bring forward a bifurcation to enable rapid switching between states. We propose a numerical technique for controlling the bifurcation diagram of a nonlinear partial differential equation by varying the shape of the domain. Specifically, we are able to delay or advance a given branch point to a target parameter value. The algorithm consists of solving a shape optimization problem constrained by an augmented system of equations, the Moore--Spence system, that characterize the location of the branch points. Numerical experiments on the Allen--Cahn, Navier--Stokes, and hyperelasticity equations demonstrate the effectiveness of this technique in a wide range of settings., 20 pages, 11 figures

We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a $k$-edge-connected graph $G=(V,E)$ and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to $G$ makes the graph $(k+1)$-edge-connected. If $k$ is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP) -- i.e., $G$ is a spanning tree -- for which significant progress has been achieved recently, leading to approximation factors below $1.5$ (the currently best factor is $1.458$). However, advances on TAP did not carry over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain the first approximation factor below $2$ for CAP by presenting a $1.91$-approximation algorithm based on a method that is disjoint from recent advances for TAP. We first bridge the gap between TAP and CAP, by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below $1.5$, based on a new analysis technique. Through these ingredients, we obtain a $1.393$-approximation algorithm for CAP, and therefore also TAP. This leads to the currently best approximation result for both problems in a unified way, by significantly improving on the above-mentioned $1.91$-approximation for CAP and also the previously best approximation factor of $1.458$ for TAP by Grandoni, Kalaitzis, and Zenklusen (STOC 2018). Additionally, a feature we inherit from recent TAP advances is that our approach can deal with the weighted setting when the ratio between the largest to smallest cost on extra links is bounded, in which case we obtain approximation factors below $1.5$.

This work is a follow-up and a complement to arXiv:1912.08899 [math.OC] for solving polynomial optimization problems (POPs). The chordal-TSSOS hierarchy that we propose is a new sparse moment-SOS framework based on term-sparsity and chordal extension. By exploiting term-sparsity of the input polynomials we obtain a two-level hierarchy of semidefinite programming relaxations. The novelty and distinguishing feature of such relaxations is to obtain quasi block-diagonal matrices obtained in an iterative procedure that performs chordal extension of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Various numerical examples demonstrate the efficiency and the scalability of this new hierarchy for both unconstrained and constrained POPs. The two hierarchies are complementary. While the former TSSOS arXiv:1912.08899 [math.OC] has a theoretical convergence guarantee, the chordal-TSSOS has superior performance but lacks this theoretical guarantee., 29 pages, 14 tables, 5 figures. arXiv admin note: text overlap with arXiv:1912.08899

In this paper, we develop convergence analysis of a modified line search method for objective functions whose value is computed with noise and whose gradient estimates are inexact and possibly random. The noise is assumed to be bounded in absolute value without any additional assumptions. We extend the framework based on stochastic methods from [Cartis and Scheinberg, 2018] which was developed to provide analysis of a standard line search method with exact function values and random gradients to the case of noisy functions. We introduce two alternative conditions on the gradient which when satisfied with some sufficiently large probability at each iteration, guarantees convergence properties of the line search method. We derive expected complexity bounds to reach a near optimal neighborhood for convex, strongly convex and nonconvex functions. The exact dependence of the convergence neighborhood on the noise is specified., Comment: 30 pages. arXiv admin note: text overlap with arXiv:1905.01332

This paper examines mean field linear-quadratic-Gaussian (LQG) social optimum control with volatility-uncertain common noise. The diffusion terms in the dynamics of agents contain an unknown volatility process driven by a common noise. We apply a robust optimization approach in which all agents view volatility uncertainty as an adversarial player. Based on the principle of person-by-person optimality and a two-step-duality technique for stochastic variational analysis, we construct an auxiliary optimal control problem for a representative agent. Through solving this problem combined with a consistent mean field approximation, we design a set of decentralized strategies, which are further shown to be asymptotically social optimal by perturbation analysis.

In this paper we give an algorithm to round the floating point output of a semidefinite programming solver to a solution over the rationals or a quadratic extension of the rationals. We apply this to get sharp bounds for packing problems, and we use these sharp bounds to prove that certain optimal packing configurations are unique up to rotations. In particular, we show that the configuration coming from the $\mathsf{E}_8$ root lattice is the unique optimal code with minimal angular distance $\pi/3$ on the hemisphere in $\mathbb R^8$, and we prove that the three-point bound for the $(3, 8, \vartheta)$-spherical code, where $\vartheta$ is such that $\cos \vartheta = (2\sqrt{2}-1)/7$, is sharp by rounding to $\mathbb Q[\sqrt{2}]$. We also use our machinery to compute sharp upper bounds on the number of spheres that can be packed into a larger sphere., Comment: 24 pages

We propose a novel learning-based framework for image reconstruction particularly designed for training without ground truth data, which has three major building blocks: energy-based learning, a patch-based Wasserstein loss functional, and shared prior learning. In energy-based learning, the parameters of an energy functional composed of a learned data fidelity term and a data-driven regularizer are computed in a mean-field optimal control problem. In the absence of ground truth data, we change the loss functional to a patch-based Wasserstein functional, in which local statistics of the output images are compared to uncorrupted reference patches. Finally, in shared prior learning, both aforementioned optimal control problems are optimized simultaneously with shared learned parameters of the regularizer to further enhance unsupervised image reconstruction. We derive several time discretization schemes of the gradient flow and verify their consistency in terms of Mosco convergence. In numerous numerical experiments, we demonstrate that the proposed method generates state-of-the-art results for various image reconstruction applications--even if no ground truth images are available for training., 37 pages, 19 figures

This paper presents an accelerated composite gradient (ACG) variant, referred to as the AC-ACG method, for solving nonconvex smooth composite minimization problems. As opposed to well-known ACG variants that are either based on a known Lipschitz gradient constant or a sequence of maximum observed curvatures, the current one is based on the average of all past observed curvatures. More specifically, AC-ACG uses a positive multiple of the average of all observed curvatures until the previous iteration as a way to estimate the "function curvature" at the current point and then two resolvent evaluations to compute the next iterate. In contrast to other variable Lipschitz estimation variants, e.g., the ones based on the maximum curvature, AC-ACG always accepts the aforementioned iterate regardless how poor the Lipschitz estimation turns out to be. Finally, computational results are presented to illustrate the efficiency of AC-ACG on both randomly generated and real-world problem instances., 28 pages

We introduce iterative methods named TriCG and TriMR for solving symmetric quasi-definite systems based on the orthogonal tridiagonalization process proposed by Saunders, Simon and Yip in 1988. TriCG and TriMR are tantamount to preconditioned Block-CG and Block-MINRES with two right-hand sides in which the two approximate solutions are summed at each iteration, but require less storage and work per iteration. We evaluate the performance of TriCG and TriMR on linear systems generated from the SuiteSparse Matrix Collection and from discretized and stablized Stokes equations. We compare TriCG and TriMR with SYMMLQ and MINRES, the recommended Krylov methods for symmetric and indefinite systems. In all our experiments, TriCG and TriMR terminate earlier than SYMMLQ and MINRES on a residual-based stopping condition with an improvement of up to 50% in terms of number of iterations. They also terminate more reliably than Block-CG and Block-MINRES. Experiments in quadruple and octuple precision suggest that loss of orthogonality in the basis vectors is significantly less pronounced in TriCG and TriMR than in Block-CG and Block-MINRES., Comment: 24 pages, 12 figures

We present a backward diffusion flow (i.e. a backward-in-time stochastic differential equation) whose marginal distribution at any (earlier) time is equal to the smoothing distribution when the terminal state (at a latter time) is distributed according to the filtering distribution. This is a novel interpretation of the smoothing solution in terms of a nonlinear diffusion (stochastic) flow. This solution contrasts with, and complements, the (backward) deterministic flow of probability distributions (viz. a type of Kushner smoothing equation) studied in a number of prior works. A number of corollaries of our main result are given including a derivation of the time-reversal of a stochastic differential equation, and an immediate derivation of the classical Rauch-Tung-Striebel smoothing equations in the linear setting.

We introduce BELLA, a locally superlinearly convergent Bregman forward-backward splitting method for minimizing the sum of two nonconvex functions, one of which satisfies a relative smoothness condition and the other one is possibly nonsmooth. A key tool of our methodology is the Bregman forward-backward envelope (BFBE), an exact and continuous penalty function with favorable first- and second-order properties, which enjoys a nonlinear error bound when the objective function satisfies a Lojasiewicz-type property. The proposed algorithm is of linesearch type over the BFBE along user-defined update directions and converges subsequentially to stationary points and globally under the Kurdyka-Lojasiewicz condition. Moreover, when the update directions are superlinear in the sense of Facchinei and Pang [Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I, Springer, New York, 2003], owing to the given nonlinear error bound unit stepsize is eventually always accepted and the algorithm attains superlinear convergence rates even when the limit point is a nonisolated minimum.

The paper studies the open-loop saddle point and the open-loop lower and upper values, as well as their relationship for two-person zero-sum stochastic linear-quadratic (LQ, for short) differential games with deterministic coefficients. It derives a necessary condition for the finiteness of the open-loop lower and upper values and a sufficient condition for the existence of an open-loop saddle point. It turns out that under the sufficient condition, a strongly regular solution to the associated Riccati equation uniquely exists, in terms of which a closed-loop representation is further established for the open-loop saddle point. Examples are presented to show that the finiteness of the open-loop lower and upper values does not ensure the existence of an open-loop saddle point in general. But for the classical deterministic LQ game, these two issues are equivalent and both imply the solvability of the Riccati equation, for which an explicit representation of the solution is obtained., Comment: 26 pages

We study a class of countably infinite linear programs (CILPs) whose feasible sets are bounded subsets of appropriately defined spaces of measures. The optimal value, optimal points, and minimal points of these CILPs can be approximated by solving finite-dimensional linear programs. We show how to construct finite-dimensional programs that lead to approximations with easy-to-evaluate error bounds, and we prove that the errors converge to zero as the size of the finite-dimensional programs approaches that of the original problem. We discuss the use of our methods in the computation of the stationary distributions, occupation measures, and exit distributions of Markov chains. Read More:https://epubs.siam.org/doi/10.1137/19M1268847 &nbsp

We give a sufficient condition for exponential stability of a network of lossless telegrapher's equations, coupled by linear time-varying boundary conditions. The sufficient conditions is in terms of dissipativity of the couplings, which is natural for instance in the context of microwave circuits. Exponential stability is with respect to any $L^p$-norm, $1\leq p\leq\infty$. This also yields a sufficient condition for exponential stability to a special class of linear time-varying difference delay systems which is quite explicit and tractable. One ingredient of the proof is that $L^p$ exponential stability for such difference delay systems is independent of $p$, thereby reproving in a simpler way some results from [3]., Comment: To be published in SIAM Journal on Mathematical Analysis, most probably 2021

We introduce new parametrized classes of shape admissible domains in R^n , n $\ge$ 2, and prove that they are compact with respect to the convergence in the sense of characteristic functions, the Hausdorff sense, the sense of compacts and the weak convergence of their boundary volumes. The domains in these classes are bounded ($\epsilon$, $\infty$)-domains with possibly fractal boundaries that can have parts of any non-uniform Hausdorff dimension greater or equal to n -- 1 and less than n. We prove the existence of optimal shapes in such classes for maximum energy dissipation in the framework of linear acous-tics. A by-product of our proof is the result that the class of bounded ($\epsilon$, $\infty$)-domains with fixed $\epsilon$ is stable under Hausdorff convergence. An additional and related result is the Mosco convergence of Robin-type energy functionals on converging domains.

In statistical decision theory involving a single decision-maker, an information structure is said to be better than another one if for any cost function involving a hidden state variable and an action variable which is restricted to be conditionally independent from the state given some measurement, the solution value under the former is not worse than that under the latter. For finite spaces, a theorem due to Blackwell leads to a complete characterization on when one information structure is better than another. For stochastic games, in general, such an ordering is not possible since additional information can lead to equilibria perturbations with positive or negative values to a player. However, for zero-sum games in a finite probability space, P\k{e}ski introduced a complete characterization of ordering of information structures. In this paper, we obtain an infinite dimensional (standard Borel) generalization of P\k{e}ski's result. A corollary is that more information cannot hurt a decision maker taking part in a zero-sum game. We establish two supporting results which are essential and explicit though modest improvements on prior literature: (i) a partial converse to Blackwell's ordering in the standard Borel setup and (ii) an existence result for equilibria in zero-sum games with incomplete information., Comment: To appear in SIAM Journal on Control and Optimization. A short conference version appeared at the 2020 IEEE International Symposium on Information Theory

An optimal ergodic control problem (EC problem, for short) is investigated for a linear stochastic differential equation with quadratic cost functional. Constant nonhomogeneous terms, not all zero, appear in the state equation, which lead to the asymptotic limit of the state non-zero. Under the stabilizability condition, for any (admissible) closed-loop strategy, an invariant measure is proved to exist, which makes the ergodic cost functional well-defined and the EC problem well-formulated. Sufficient conditions, including those allowing the weighting matrices of cost functional to be indefinite, are introduced for finiteness and solvability for the EC problem. Some comparisons are made between the solvability of EC problem and the closed-loop solvability of stochastic linear quadratic optimal control problem in the infinite horizon. Regularized EC problem is introduced to be used to obtain the optimal value of the EC problem.

We study compressible and incompressible nonlinear elasticity variational problems in a general context. Our main result gives a sufficient condition for an equilibrium to be a global energy minimizer, in terms of convexity properties of the pressure in the deformed configuration. We also provide a convex relaxation of the problem together with its dual formulation, based on measure-valued mappings, which coincides with the original problem under our condition., Comment: 17 pages

We introduce a mean field game model for pedestrians moving in a given domain and choosing their trajectories so as to minimize a cost including a penalization on the difference between their own velocity and that of the other agents they meet. We prove existence of an equilibrium in a Lagrangian setting by using its variational structure, and then study its properties and regularity.

We analyze an optimal trade execution problem in a financial market with stochastic liquidity. To this end we set up a limit order book model in which both order book depth and resilience evolve randomly in time. Trading is allowed in both directions and at discrete points in time. We derive an explicit recursion that, under certain structural assumptions, characterizes minimal execution costs. We also discuss several qualitative aspects of optimal strategies, such as existence of profitable round trips or closing the position in one go, and compare our findings with the literature., Comment: 39 pages; to appear in SIAM J. Financial Math

We consider robust pricing and hedging for options written on multiple assets given market option prices for the individual assets. The resulting problem is called the multi-marginal martingale optimal transport problem. We propose two numerical methods to solve such problems: using discretisation and linear programming applied to the primal side and using penalisation and deep neural networks optimisation applied to the dual side. We prove convergence for our methods and compare their numerical performance. We show how adding further information about call option prices at additional maturities can be incorporated and narrows down the no-arbitrage pricing bounds. Finally, we obtain structural results for the case of the payoff given by a weighted sum of covariances between the assets., Comment: Forthcoming in SIAM Journal on Financial Mathematics

The computation of free energies is a common issue in statistical physics. A natural technique to compute such high-dimensional integrals is to resort to Monte Carlo simulations. However, these techniques generally suffer from a high variance in the low temperature regime, because the expectation is often dominated by high values corresponding to rare system trajectories. A standard way to reduce the variance of the estimator is to modify the drift of the dynamics with a control enhancing the probability of rare events, leading to so-called importance sampling estimators. In theory, the optimal control leads to a zero-variance estimator; it is, however, defined implicitly and computing it is of the same difficulty as the original problem. We propose here a general strategy to build approximate optimal controls in the small temperature limit for diffusion processes, with the first goal to reduce the variance of free energy Monte Carlo estimators. Our construction builds upon low noise asymptotics by expanding the optimal control around the instanton, which is the path describing most likely fluctuations at low temperature. This technique not only helps reducing variance, but it is also interesting as a theoretical tool since it differs from usual small temperature expansions (WKB ansatz). As a complementary consequence of our expansion, we provide a perturbative formula for computing the free energy in the small temperature regime, which refines the now standard Freidlin--Wentzell asymptotics. We compute this expansion explicitly for lower orders, and explain how our strategy can be extended to an arbitrary order of accuracy. We support our findings with illustrative numerical examples.

International audience; We consider a continuous time stochastic optimal control problem under both equality and inequality constraints on the expectation of some functionals of the controlled process. Under a qualification condition, we show that the problem is in duality with an optimization problem involving the Lagrange multiplier associated with the constraints. Then by convex analysis techniques, we provide a general existence result and some a priori estimation of the dual optimizers. We further provide a necessary and sufficient optimality condition for the initial constrained control problem. The same results are also obtained for a discrete time constrained control problem. Moreover, under additional regularity conditions, it is proved that the discrete time control problem converges to the continuous time problem, possibly with a convergence rate. This convergence result can be used to obtain numerical algorithms to approximate the continuous time control problem, which we illustrate by two simple numerical examples.

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, different clusterings of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically different solutions. We are interested in applications in which one clustering has to be transformed into another; e.g., when a gradual transition from an old solution to a new one is required. In this paper, we devise methods for constructing such a transition based on linear programming and network theory. We use a so-called clustering-difference graph to model the desired transformation and provide methods for decomposing the graph into a sequence of elementary moves that accomplishes the transformation. These moves are equivalent to the edge directions, or circuits, of the underlying partition polytopes. Therefore, in addition to a conceptually new metric for measuring the distance between clusterings, we provide new bounds on the circuit diameter of these partition polytopes.

We consider a distributionally robust Partially Observable Markov Decision Process (DR-POMDP), where the distribution of the transition-observation probabilities is unknown at the beginning of each decision period, but their realizations can be inferred using side information at the end of each period after an action being taken. We build an ambiguity set of the joint distribution using bounded moments via conic constraints and seek an optimal policy to maximize the worst-case (minimum) reward for any distribution in the set. We show that the value function of DR-POMDP is piecewise linear convex with respect to the belief state and propose a heuristic search value iteration method for obtaining lower and upper bounds of the value function. We conduct numerical studies and demonstrate the computational performance of our approach via testing instances of a dynamic epidemic control problem. Our results show that DR-POMDP can produce more robust policies under misspecified distributions of transition-observation probabilities as compared to POMDP, but has less costly solutions than robust POMDP. The DR-POMDP policies are also insensitive to varying parameter in the ambiguity set and to noise added to the true transition-observation probability values obtained at the end of each decision period.

We propose and analyze variational source conditions (VSC) for the Tikhonov regularization method with Lp-norm penalties for a general ill-posed operator equation in a Banach space. Our analysis is based on the use of the celebrated Littlewood-Paley theory and the concept of (Rademacher) R-boundedness. On the basis of these two analytical tools, we validate the proposed VSC under a conditional stability estimate and a regularity requirement of the true solution in terms of Triebel-Lizorkin-type spaces. In the final part of the paper, the developed theory is applied to an inverse elliptic problem with measure data for the reconstruction of possibly unbounded diffusion coefficients in the Lp-setting. By means of VSC, convergence rates for the associated Tikhonov regularization with Lp-norm penalties are obtained.

International audience; We numerically investigate, and improve upon, a computational approach originally introduced in [Cottereau, IJNME 2013] which aims at evaluating the effective coefficient of a medium modelled by a highly oscillatory coefficient. This computational approach is based on a Arlequin type coupling. It combines the original fine-scale description of the medium (modelled by an oscillatory coefficient) with an effective description (modelled by a constant coefficient) and optimizes upon the coefficient of the effective medium to best fit the response of the actual heterogeneous medium using a purely homogeneous medium. We present here a mathematical formalization of the approach along with various improvements of the algorithms, in order to obtain a procedure as efficient as possible. Representative numerical results demonstrate the added value of our approach in comparison to the original approach.

We investigate the dynamic stability of the indirect utility process associated with a (possibly suboptimal) trading strategy under perturbations of the market. Establishing the reverse conjugacy characterizations first, we prove continuity and first-order convergence of the indirect-utility process under simultaneous perturbations of the finite variation and martingale parts of the return of the risky asset., 34 pages, preliminary version

Nonconvex optimal-control problems governed by evolution problems in infinite-dimensional spaces (as e.g. parabolic boundary-value problems) needs a continuous (and possibly also smooth) extension on some (preferably convex) compactification, called relaxation, to guarantee existence of their solutions and to facilitate analysis by relatively conventional tools. When the control is valued in some subsets of Lebesgue spaces, the usual extensions are either too coarse (allowing in fact only very restricted nonlinearities) or too fine (being nonmetrizable). To overcome these drawbacks, a compromising convex compactification is here devised, combining classical techniques for Young measures with Choquet theory. This is applied to parabolic optimal control problems as far as existence and optimality conditions concerns.

Recently, in a series of papers [32,38,39,41], the ratio of $\ell_1$ and $\ell_2$ norms was proposed as a sparsity inducing function for noiseless compressed sensing. In this paper, we further study properties of such model in the noiseless setting, and propose an algorithm for minimizing $\ell_1$/$\ell_2$ subject to noise in the measurements. Specifically, we show that the extended objective function (the sum of the objective and the indicator function of the constraint set) of the model in [32] satisfies the Kurdyka-Lojasiewicz (KL) property with exponent 1/2; this allows us to establish linear convergence of the algorithm proposed in [39, Eq. 11] under mild assumptions. We next extend the $\ell_1$/$\ell_2$ model to handle compressed sensing problems with noise. We establish the solution existence for some of these models under the spherical section property [37,44], and extend the algorithm in [39, Eq. 11] by incorporating moving-balls-approximation techniques [4] for solving these problems. We prove the subsequential convergence of our algorithm under mild conditions, and establish global convergence of the whole sequence generated by our algorithm by imposing additional KL and differentiability assumptions on a specially constructed potential function. Finally, we perform numerical experiments on robust compressed sensing and basis pursuit denoising with residual error measured by $ \ell_2 $ norm or Lorentzian norm via solving the corresponding $\ell_1$/$\ell_2$ models by our algorithm. Our numerical simulations show that our algorithm is able to recover the original sparse vectors with reasonable accuracy.

Controlling the shape and position of moving and pinned droplets on a solid surface is an important feature often found in microfluidic applications. In this work, we consider a well investigated phase field model including contact line dynamics as the state system for an (open-loop) optimal control problem. Here the spatially and temporally changeable contact angles between droplet and solid are considered as the control variables. We consider a suitable, energy stable, time discrete version of the state equation in our optimal control problem. We discuss regularity of the solution to the time discrete state equation and its continuity and differentiability properties. Furthermore, we show existence of solutions and state first order optimality conditions to the optimal control problem. We illustrate our results by actively pushing a droplet uphill against gravity in an optimal way.

Recently, there has been a surge of interest in designing variants of the classical Newton-CG in which the Hessian of a (strongly) convex function is replaced by suitable approximations. This is mainly motivated by large-scale finite-sum minimization problems that arise in many machine learning applications. Going beyond convexity, inexact Hessian information has also been recently considered in the context of algorithms such as trust-region or (adaptive) cubic regularization for general non-convex problems. Here, we do that for Newton-MR, which extends the application range of the classical Newton-CG beyond convexity to invex problems. Unlike the convergence analysis of Newton-CG, which relies on spectrum preserving Hessian approximations in the sense of L\"{o}wner partial order, our work here draws from matrix perturbation theory to estimate the distance between the subspaces underlying the exact and approximate Hessian matrices. Numerical experiments demonstrate a great degree of resilience to such Hessian approximations, amounting to a highly efficient algorithm in large-scale problems., Comment: 32 pages, 10 figures

This paper studies the problem of maximizing the sum of traces of matrix quadratic forms on a product of Stiefel manifolds. This orthogonal trace-sum maximization (OTSM) problem generalizes many interesting problems such as generalized canonical correlation analysis (CCA), Procrustes analysis, and cryo-electron microscopy of the Nobel prize fame. For these applications finding global solutions is highly desirable but it has been unclear how to find even a stationary point, let alone testing its global optimality. Through a close inspection of Ky Fan's classical result (1949) on the variational formulation of the sum of largest eigenvalues of a symmetric matrix, and a semidefinite programming (SDP) relaxation of the latter, we first provide a simple method to certify global optimality of a given stationary point of OTSM. This method only requires testing whether a symmetric matrix is positive semidefinite. A by-product of this analysis is an unexpected strong duality between Shapiro-Botha (1988) and Zhang-Singer (2017). After showing that a popular algorithm for generalized CCA and Procrustes analysis may generate oscillating iterates, we propose a simple fix that provably guarantees convergence to a stationary point. The combination of our algorithm and certificate reveals novel global optima of various instances of OTSM., 37 pages, 3 figures

We propose a computational approach to estimate the stability domain of quadratic-bilinear reduced-order models (ROMs), which are low-dimensional approximations of large-scale dynamical systems. For nonlinear ROMs, it is not only important to show that the origin is locally asymptotically stable, but also to quantify if the operative range of the ROM is included in the region of convergence. While accuracy and structure preservation remain the main focus of development for nonlinear ROMs, computational methods that go beyond the existing highly conservative analytical results have been lacking thus far. In this work, for a given quadratic Lyapunov function, we first derive an analytical estimate of the stability domain, which is rather conservative but can be evaluated efficiently. With the goal to enlarge this estimate, we provide an optimal ellipsoidal estimate of the stability domain by solving a convex optimization problem. This provides us with valuable information about stability properties of the ROM, an important aspect of predictive simulation. We do not assume a specific ROM method, so a particular appeal is that the approach is applicable to quadratic-bilinear models obtained via data-driven approaches, where ROM stability properties cannot - per definition - be derived from the full-order model. Numerical results for a LQG-balanced ROM of Burgers' equation, a proper orthogonal decomposition ROM of FitzHugh-Nagumo, and a non-intrusive ROM of Burgers' equation demonstrate the scalability and quantitative advantages of the proposed approach. The optimization-based estimates of the stability domain are found to be up to four orders of magnitude less conservative than analytical estimates., 16 pages, 6 figures

A linear control system with quadratic cost functional over infinite time horizon is considered without assuming controllability/stabilizability condition and the global integrability condition for the nonhomogeneous term of the state equation and the weight functions in the linear terms in the running cost rate function. Classical approaches do not apply for such kind of problems. Existence and non-existence of overtaking optimal controls in various cases are established. Some concrete examples are presented. These results show that the overtaking optimality approach can be used to solve some of the above-mentioned problems and at the same time, the limitation of this approach is also revealed.

Motivated by the problem of bounding the number of iterations of the Simplex algorithm we investigate the possible lengths of monotone paths followed by the Simplex method inside the oriented graphs of polyhedra (oriented by the objective function). We consider both the shortest and the longest monotone paths and estimate the monotone diameter and height of polyhedra. Our analysis applies to transportation polytopes, matroid polytopes, matching polytopes, shortest-path polytopes, and the TSP, among others. We begin by showing that combinatorial cubes have monotone and Bland pivot height bounded by their dimension and that in fact all monotone paths of zonotopes are no larger than the number of edge directions of the zonotope. We later use this to show that several polytopes have polynomial-size pivot height, for all pivot rules. In contrast, we show that many well-known combinatorial polytopes have exponentially-long monotone paths. Surprisingly, for some famous pivot rules, e.g., greatest improvement and steepest edge, these same polytopes have polynomial-size simplex paths., Comment: 24 pages, 8 figures

Computing the stationary distributions of a continuous-time Markov chain (CTMC) involves solving a set of linear equations. In most cases of interest, the number of equations is infinite or too large, and the equations cannot be solved analytically or numerically. Several approximation schemes overcome this issue by truncating the state space to a manageable size. In this review, we first give a comprehensive theoretical account of the stationary distributions and their relation to the long-term behaviour of CTMCs that is readily accessible to non-experts and free of irreducibility assumptions made in standard texts. We then review truncation-based approximation schemes for CTMCs with infinite state spaces paying particular attention to the schemes' convergence and the errors they introduce, and we illustrate their performance with an example of a stochastic reaction network of relevance in biology and chemistry. We conclude by elaborating on computational trade-offs associated with error control and several open questions. &nbsp

We prove a small-gain theorem for interconnections of $n$ nonlinear heterogeneous input-to-state stable (ISS) control systems of a general nature, covering partial, delay and ordinary differential equations. Furthermore, for the same class of control systems, we derive small-gain theorems for asymptotic gain, uniform global stability and weak input-to-state stability properties. We show that our technique is applicable for different formulations of ISS property (summation, maximum, semimaximum) and discuss tightness of achieved small-gain theorems. Finally, we introduce variations of uniform asymptotic gain and uniform limit properties, which are particularly useful for small-gain arguments and characterize ISS in terms of these notions., Accepted to SICON, 2021

Smooth convex minimization over the unit trace-norm ball is an important optimization problem in machine learning, signal processing, statistics and other fields, that underlies many tasks in which one wishes to recover a low-rank matrix given certain measurements. While first-order methods for convex optimization enjoy optimal convergence rates, they require in worst-case to compute a full-rank SVD on each iteration, in order to compute the projection onto the trace-norm ball. These full-rank SVD computations however prohibit the application of such methods to large problems. A simple and natural heuristic to reduce the computational cost is to approximate the projection using only a low-rank SVD. This raises the question if, and under what conditions, this simple heuristic can indeed result in provable convergence to the optimal solution. In this paper we show that any optimal solution is a center of a Euclid. ball inside-which the projected-gradient mapping admits rank that is at most the multiplicity of the largest singular value of the gradient vector. Moreover, the radius of the ball scales with the spectral gap of this gradient vector. We show how this readily implies the local convergence (i.e., from a "warm-start" initialization) of standard first-order methods, using only low-rank SVD computations. We also quantify the effect of "over-parameterization", i.e., using SVD computations with higher rank, on the radius of this ball, showing it can increase dramatically with moderately larger rank. We extend our results also to the setting of optimization with trace-norm regularization and optimization over bounded-trace positive semidefinite matrices. Our theoretical investigation is supported by concrete empirical evidence that demonstrates the \textit{correct} convergence of first-order methods with low-rank projections on real-world datasets., Accepted to SIAM Journal on Optimization (SIOPT)

We discuss a topology optimization problem for an elastoplastic medium. The distribution of material in a region is optimized with respect to a given target functional taking into account compliance. The incremental elastoplastic problem serves as state constraint. We prove that the topology optimization problem admits a solution. First-order optimality conditions are obtained by considering a regularized problem and passing to the limit.

This paper presents smoothing schemes for obtaining approximate stationary points of unconstrained or linearly-constrained composite nonconvex-concave min-max (and hence nonsmooth) problems by applying well-known algorithms to composite smooth approximations of the original problems. More specifically, in the unconstrained (resp. constrained) case, approximate stationary points of the original problem are obtained by applying, to its composite smooth approximation, an accelerated inexact proximal point (resp. quadratic penalty) method presented in a previous paper by the authors. Iteration complexity bounds for both smoothing schemes are also established. Finally, numerical results are given to demonstrate the efficiency of the unconstrained smoothing scheme.

In this work, we present a novel approach for solving stochastic shape optimization problems. Our method is the extension of the classical stochastic gradient method to infinite-dimensional shape manifolds. We prove convergence of the method on Riemannian manifolds and then make the connection to shape spaces. The method is demonstrated on a model shape optimization problem from interface identification. Uncertainty arises in the form of a random partial differential equation, where underlying probability distributions of the random coefficients and inputs are assumed to be known. We verify some conditions for convergence for the model problem and demonstrate the method numerically.

In this paper, we study an optimal control problem for a macroscopic mechanical tumour model based on the phase field approach. The model couples a Cahn--Hilliard type equation to a system of linear elasticity and a reaction-diffusion equation for a nutrient concentration. By taking advantage of previous analytical well-posedness results established by the authors, we seek optimal controls in the form of a boundary nutrient supply, as well as concentrations of cytotoxic and antiangiogenic drugs that minimise a cost functional involving mechanical stresses. Special attention is given to sparsity effects, where with the inclusion of convex non-differentiable regularisation terms to the cost functional, we can infer from the first-order optimality conditions that the optimal drug concentrations can vanish on certain time intervals., 26 pages

We re-visit the classical problem of optimal payment of dividends and determine the degree to which the diffusion approximation serves as a valid approximation of the classical risk model for this problem. Our results parallel some of those in B\"auerle (2004), but we obtain sharper results because we use a different technique for obtaining them. Specifically, B\"auerle (2004) uses probabilistic techniques and relies on convergence in distribution of the underlying processes. By contrast, we use comparison results from the theory of differential equations, and these methods allow us to determine the rate of convergence of the value functions in question.

In this paper, we provide the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regular conditions. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 2016, 158(1-2): 363-381]. However, due to the non-convexity and non-compactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regular condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS.

In recent years, the success of the Koopman operator in dynamical systems analysis has also fueled the development of Koopman operator-based control frameworks. In order to preserve the relatively low data requirements for an approximation via Dynamic Mode Decomposition, a quantization approach was recently proposed in [Peitz \& Klus, Automatica 106, 2019]. This way, control of nonlinear dynamical systems can be realized by means of switched systems techniques, using only a finite set of autonomous Koopman operator-based reduced models. These individual systems can be approximated very efficiently from data. The main idea is to transform a control system into a set of autonomous systems for which the optimal switching sequence has to be computed. In this article, we extend these results to continuous control inputs using relaxation. This way, we combine the advantages of the data efficiency of approximating a finite set of autonomous systems with continuous controls. We show that when using the Koopman generator, this relaxation --- realized by linear interpolation between two operators --- does not introduce any error for control affine systems. This allows us to control high-dimensional nonlinear systems using bilinear, low-dimensional surrogate models. The efficiency of the proposed approach is demonstrated using several examples with increasing complexity, from the Duffing oscillator to the chaotic fluidic pinball., 22 pages, 9 Figures

We propose a methodology for studying the performance of common splitting methods through semidefinite programming. We prove tightness of the methodology and demonstrate its value by presenting two applications of it. First, we use the methodology as a tool for computer-assisted proofs to prove tight analytical contraction factors for Douglas--Rachford splitting that are likely too complicated for a human to find bare-handed. Second, we use the methodology as an algorithmic tool to computationally select the optimal splitting method parameters by solving a series of semidefinite programs., Comment: Published in the SIAM Journal on Optimization

In this paper we establish an observability inequality for the heat equation with bounded potentials on the whole space. Roughly speaking, such a kind of inequality says that the total energy of solutions can be controlled by the energy localized in a subdomain, which is equidistributed over the whole space. The proof of this inequality is mainly adapted from the parabolic frequency function method, which plays an important role in proving the unique continuation property for solutions of parabolic equations. As an immediate application, we show that the null controllability holds for the heat equation with bounded potentials on the whole space., Comment: Welcome for any comment

We address the variational formulation of the risk-sensitive reward problem for non-degenerate diffusions on $\mathbb{R}^d$ controlled through the drift. We establish a variational formula on the whole space and also show that the risk-sensitive value equals the generalized principal eigenvalue of the semilinear operator. This can be viewed as a controlled version of the variational formulas for principal eigenvalues of diffusion operators arising in large deviations. We also revisit the average risk-sensitive minimization problem and by employing a gradient estimate developed in this paper, we extend earlier results to unbounded drifts and running costs., Comment: 29 pages

Let $X,Y$ be Banach spaces, $(S_t)_{t \geq 0}$ a $C_0$-semigroup on $X$, $-A$ the corresponding infinitesimal generator on $X$, $C$ a bounded linear operator from $X$ to $Y$, and $T > 0$. We consider the system \[ \dot{x}(t) = -Ax(t), \quad y(t) = Cx(t) \quad t\in (0,T], \quad x(0) = x_0 \in X. \] We provide sufficient conditions such that this system satisfies a final state observability estimate in $L_r ((0,T) ; Y)$, $r \in [1,\infty]$. These sufficient conditions are given by an uncertainty relation and a dissipation estimate. Our approach unifies and generalizes the respective advantages from earlier results obtained in the context of Hilbert spaces. As an application we consider the example where $A$ is an elliptic operator in $L_p(\mathbb{R}^d)$ for $1