Wenjia JingYau Mathematical Sciences Center, Tsinghua University, No 1. Tsinghua Yuan, Beijing 100084, ChinaPanagiotis E. SouganidisDepartment of Mathematics, The University of Chicago, 5734 S. University Ave., Chicago, IL 60637, USAHung V. TranDepartment of Mathematics, University of Wisconsin at Madison, 480 Lincoln Drive, Madison, WI 53706, USA
Analysis of PDEsOptimization and ControlProbabilitymathscidoc:2206.03012
Discrete and Continuous Dynamical Systems - S, 11, (5), 915-939, 2018.10
We study the averaging of fronts moving with positive oscillatory normal velocity, which is periodic in space and stationary ergodic in time. The problem can be formulated as the homogenization of coercive level set Hamilton-Jacobi equations with spatio-temporal oscillations. To overcome the difficulties due to the oscillations in time and the linear growth of the Hamiltonian, we first study the long time averaged behavior of the associated reachable sets using geometric arguments. The results are new for higher than one dimensions even in the space-time periodic setting.
The focus of this work is on rigorous mathematical analysis of the topological derivative based detection algorithms for the localization of an elastic inclusion of vanishing characteristic size. A filtered quadratic misfit is considered, and the performance of the topological derivative imaging functional resulting therefrom is analyzed. Our analysis reveals that the imaging functional may not attain its maximum at the location of the inclusion. Moreover, the resolution of the image is below the diffraction limit. Both phenomena are due to the coupling of pressure and shear waves propagating with different wave speeds and polarization directions. A novel imaging functional based on the weighted Helmholtz decomposition of the topological derivative is, therefore, introduced. It is thereby substantiated that the maximum of the imaging functional is attained at the location of the inclusion and the resolution is enhanced and proves to be the diffraction limit. Finally, we investigate the stability of the proposed imaging functionals with respect to measurement and medium noises.
Habib AmmariDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceThomas BoulierDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceJosselin GarnierLaboratoire de Probabilités et Modèles Aléatoires & Laboratoire Jacques-Louis Lions, Université Paris VII, 75205, Paris Cedex 13, FranceWenjia JingDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceHyeonbae KangDepartment of Mathematics, Inha University, Incheon, 402-751, KoreaHan WangDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, France
Analysis of PDEsMathematical PhysicsNumerical Analysis and Scientific ComputingOptimization and Controlmathscidoc:2206.03006
Foundations of Computational Mathematics, 14, 27-62, 2013.9
The aim of this paper is to provide a fast and efficient procedure for (real-time) target identification in imaging based on matching on a dictionary of precomputed generalized polarization tensors (GPTs). The approach is based on some important properties of the GPTs and new invariants. A new shape representation is given and numerically tested in the presence of measurement noise. The stability and resolution of the proposed identification algorithm is numerically quantified. We compare the proposed GPT-based shape representation with a moment-based one.
Chenchen MouDepartment of Mathematics, City University of Hong Kong, Hong Kong, ChinaXianjin YangYau Mathematical Sciences Center, Tsinghua University, Haidian District, Beijing, 100084, China; Beijing Institute of Mathematical Sciences and Applications, Huairou District, Beijing, 101408, ChinaChao ZhouDepartment of Mathematics and Risk Management Institute, National University of Singapore, Singapore
Numerical Analysis and Scientific ComputingOptimization and Controlmathscidoc:2206.25007
Journal of Computational Physics, 460, (1), 111188, 2022.7
In this article, we propose two numerical methods, the Gaussian Process (GP) method and the Fourier Features (FF) algorithm, to solve mean field games (MFGs). The GP algorithm approximates the solution of a MFG with maximum a posteriori probability estimators of GPs conditioned on the partial differential equation (PDE) system of the MFG at a finite number of sample points. The main bottleneck of the GP method is to compute the inverse of a square gram matrix, whose size is proportional to the number of sample points. To improve the performance, we introduce the FF method, whose insight comes from the recent trend of approximating positive definite kernels with random Fourier features. The FF algorithm seeks approximated solutions in the space generated by sampled Fourier features. In the FF method, the size of the matrix to be inverted depends only on the number of Fourier features selected, which is much less than the size of sample points. Hence, the FF method reduces the precomputation time, saves the memory, and achieves comparable accuracy to the GP method. We give the existence and the convergence proofs for both algorithms. The convergence argument of the GP method does not depend on any monotonicity condition, which suggests the potential applications of the GP method to solve MFGs with non-monotone couplings in future work. We show the efficacy of our algorithms through experiments on a stationary MFG with a non-local coupling and on a time-dependent planning problem. We believe that the FF method can also serve as an alternative algorithm to solve general PDEs.
Ruichen JiangDepartment of Electronic Engineering, Tsinghua University, Beijing 100084, ChinaYa-Feng LiuState Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, ChinaChenglong BaoYau Mathematical Sciences Center, Tsinghua University, Beijing 100084, ChinaBo JiangSchool of Mathematical Sciences, Key Laboratory for NSLSCS of Jiangsu Province, Nanjing Normal University, Nanjing 210023, China
The multiple-input multiple-output (MIMO) detection problem, a fundamental problem in modern digital communications, is to detect a vector of transmitted symbols from the noisy outputs of a fading MIMO channel. The maximum likelihood detector can be formulated as a complex least-squares problem with discrete variables, which is NP-hard in general. Various semidefinite relaxation (SDR) methods have been proposed in the literature to solve the problem due to their polynomial-time worst-case complexity and good detection error rate performance. In this paper, we consider two popular classes of SDR-based detectors and study the conditions under which the SDRs are tight and the relationship between different SDR models. For the enhanced complex and real SDRs proposed recently by Lu et al., we refine their analysis and derive the necessary and sufficient condition for the complex SDR to be tight, as well as a necessary condition for the real SDR to be tight. In contrast, we also show that another SDR proposed by Mobasher et al. is not tight with high probability under mild conditions. Moreover, we establish a general theorem that shows the equivalence between two subsets of positive semidefinite matrices in different dimensions by exploiting a special "separable" structure in the constraints. Our theorem recovers two existing equivalence results of SDRs defined in different settings and has the potential to find other applications due to its generality.
Yuhao ZhouDepartment of Computer Science and Technology, Tsinghua University, ChinaChenglong BaoYau Mathematical Sciences Center, Tsinghua University, China and Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, ChinaChao DingInstitute of Applied Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, ChinaJun ZhuDepartment of Computer Science and Technology, Tsinghua University, China
This paper is devoted to studying an augmented Lagrangian method for solving a class of manifold optimization problems, which have nonsmooth objective functions and non-negative constraints. Under the constant positive linear dependence condition on manifolds, we show that the proposed method converges to a stationary point of the nonsmooth manifold optimization problem. Moreover, we propose a globalized semismooth Newton method to solve the augmented Lagrangian subproblem on manifolds efficiently. The local superlinear convergence of the manifold semismooth Newton method is also established under some suitable conditions. We also prove that the semismoothness on submanifolds can be inherited from that in the ambient manifold. Finally, numerical experiments on compressed modes and (constrained) sparse principal component analysis illustrate the advantages of the proposed method.
Kurdyka–Łojasiewicz (KL) exponent plays an important role in estimating the convergence rate of many contemporary first-order methods. In particular, a KL exponent of 1/2 for a suitable potential function is related to local linear convergence. Nevertheless, KL exponent is in general extremely hard to estimate. In this paper, we show under mild assumptions that KL exponent is preserved via inf-projection. Inf-projection is a fundamental operation that is ubiquitous when reformulating optimization problems via the lift-and-project approach. By studying its operation on KL exponent, we show that the KL exponent is 1/2 for several important convex optimization models, including some semidefinite-programming-representable functions and some functions that involve C2-cone reducible structures, under conditions such as strict complementarity. Our results are applicable to concrete optimization models such as group-fused Lasso and overlapping group Lasso. In addition, for nonconvex models, we show that the KL exponent of many difference-of-convex functions can be derived from that of their natural majorant functions, and the KL exponent of the Bregman envelope of a function is the same as that of the function itself. Finally, we estimate the KL exponent of the sum of the least squares function and the indicator function of the set of matrices
of rank at most k.
Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W-tensors, which not only extends thewell-studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory.We then show that finding the maximum H-eigenvalue of an even-order symmetric W-tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing themaximumH-eigenvalue of W-tensors and is based on a new structured sums-of-squares decomposition result for a nonnegative polynomial induced by W-tensors. Numerical experiments illustrate
that the proposed algorithm can successfully find the maximum H-eigenvalue of W-tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H-eigenvalues of large-size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state-of-the-art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z-tensors,whose order may be even or odd.
In this paper, we study, for the first time, nonconvex minimax separable quadratic optimization problems with multiple separable quadratic constraints and their second-order cone programming (SOCP) relaxations. Under suitable conditions, we establish exact SOCP relaxation for minimax nonconvex separable quadratic programs. We show that various important classes of specially structured minimax quadratic optimization problems admit exact SOCP relaxations under easily verifiable conditions. These classes include some minimax extended trust-region problems, minimax uniform quadratic optimization problems, max dispersion problems, and some robust quadratic optimization problems under bounded data uncertainty. The present work shows that nonconvex minimax separable quadratic problems with quadratic constraints, which contain a hidden closed and convex epigraphical set, exhibit exact SOCP relaxations.