Tracking the solution of time-varying variational inequalities is an important problem with applications in game theory, optimization, and machine learning. Existing work considers time-varying games or time-varying optimization problems. For strongly convex optimization problems or strongly monotone games, these results provide tracking guarantees under the assumption that the variation of the time-varying problem is restrained, that is, problems with a sublinear solution path. In this work we extend existing results in two ways: In our first result, we provide tracking bounds for (1) variational inequalities with a sublinear solution path but not necessarily monotone functions, and (2) for periodic time-varying variational inequalities that do not necessarily have a sublinear solution path-length. Our second main contribution is an extensive study of the convergence behavior and trajectory of discrete dynamical systems of periodic time-varying VI. We show that these systems can exhibit provably chaotic behavior or can converge to the solution. Finally, we illustrate our theoretical results with experiments.
相關內容
Incorporating probabilistic terms in mathematical models is crucial for capturing and quantifying uncertainties of real-world systems. However, stochastic models typically require large computational resources to produce meaningful statistics. For such reason, the development of reduction techniques becomes essential for enabling efficient and scalable simulations of complex scenarios while quantifying the underlying uncertainties. In this work, we study the accuracy of Polynomial Chaos (PC) surrogate expansion of the probability space on a bifurcating phenomena in fluid dynamics, namely the Coand\u{a} effect. In particular, we propose a novel non-deterministic approach to generic bifurcation problems, where the stochastic setting gives a different perspective on the non-uniqueness of the solution, also avoiding expensive simulations for many instances of the parameter. Thus, starting from the formulation of the Spectral Stochastic Finite Element Method (SSFEM), we extend the methodology to deal with solutions of a bifurcating problem, by working with a perturbed version of the deterministic model. We discuss the link between the deterministic and the stochastic bifurcation diagram, highlighting the surprising capability of PC polynomials coefficients of giving insights on the deterministic solution manifold.
A proof of optimal-order error estimates is given for the full discretization of the Cahn--Hilliard equation with Cahn--Hilliard-type dynamic boundary conditions in a smooth domain. The numerical method combines a linear bulk--surface finite element discretization in space and linearly implicit backward difference formulae of order 1 to 5 in time. Optimal-order error estimates are proven. The error estimates are based on a consistency and stability analysis in an abstract framework, based on energy estimates exploiting the anti-symmetric structure of the second-order system.
We consider the following problem in computational geometry: given, in the d-dimensional real space, a set of points marked as positive and a set of points marked as negative, such that the convex hull of the positive set does not intersect the negative set, find K hyperplanes that separate, if possible, all the positive points from the negative ones. That is, we search for a convex polyhedron with at most K faces, containing all the positive points and no negative point. The problem is known in the literature for pure convex polyhedral approximation; our interest stems from its possible applications in constraint learning, where points are feasible or infeasible solutions of a Mixed Integer Program, and the K hyperplanes are linear constraints to be found. We cast the problem as an optimization one, minimizing the number of negative points inside the convex polyhedron, whenever exact separation cannot be achieved. We introduce models inspired by support vector machines and we design two mathematical programming formulations with binary variables. We exploit Dantzig-Wolfe decomposition to obtain extended formulations, and we devise column generation algorithms with ad-hoc pricing routines. We compare computing time and separation error values obtained by all our approaches on synthetic datasets, with number of points from hundreds up to a few thousands, showing our approaches to perform better than existing ones from the literature. Furthermore, we observe that key computational differences arise, depending on whether the budget K is sufficient to completely separate the positive points from the negative ones or not. On 8-dimensional instances (and over), existing convex hull algorithms become computational inapplicable, while our algorithms allow to identify good convex hull approximations in minutes of computation.
The mathematical formulation of sign-changing problems involves a linear second-order partial differential equation in the divergence form, where the coefficient can assume positive and negative values in different subdomains. These problems find their physical background in negative-index metamaterials, either as inclusions embedded into common materials as the matrix or vice versa. In this paper, we propose a numerical method based on the constraint energy minimizing generalized multiscale finite element method (CEM-GMsFEM) specifically designed for sign-changing problems. The construction of auxiliary spaces in the original CEM-GMsFEM is tailored to accommodate the sign-changing setting. The numerical results demonstrate the effectiveness of the proposed method in handling sophisticated coefficient profiles and the robustness of coefficient contrast ratios. Under several technical assumptions and by applying the \texttt{T}-coercivity theory, we establish the inf-sup stability and provide an a priori error estimate for the proposed method.
We address the challenge of estimating the hyperuniformity exponent $\alpha$ of a spatial point process, given only one realization of it. Assuming that the structure factor $S$ of the point process follows a vanishing power law at the origin (the typical case of a hyperuniform point process), this exponent is defined as the slope near the origin of $\log S$. Our estimator is built upon the (expanding window) asymptotic variance of some wavelet transforms of the point process. By combining several scales and several wavelets, we develop a multi-scale, multi-taper estimator $\widehat{\alpha}$. We analyze its asymptotic behavior, proving its consistency under various settings, and enabling the construction of asymptotic confidence intervals for $\alpha$ when $\alpha < d$ and under Brillinger mixing. This construction is derived from a multivariate central limit theorem where the normalisations are non-standard and vary among the components. We also present a non-asymptotic deviation inequality providing insights into the influence of tapers on the bias-variance trade-off of $\widehat{\alpha}$. Finally, we investigate the performance of $\widehat{\alpha}$ through simulations, and we apply our method to the analysis of hyperuniformity in a real dataset of marine algae.
A bottleneck of sufficient dimension reduction (SDR) in the modern era is that, among numerous methods, only the sliced inverse regression (SIR) is generally applicable under the high-dimensional settings. The higher-order inverse regression methods, which form a major family of SDR methods that are superior to SIR in the population level, suffer from the dimensionality of their intermediate matrix-valued parameters that have an excessive number of columns. In this paper, we propose the generic idea of using a small subset of columns of the matrix-valued parameter for SDR estimation, which breaks the convention of using the ambient matrix for the higher-order inverse regression methods. With the aid of a quick column selection procedure, we then generalize these methods as well as their ensembles towards sparsity under the ultrahigh-dimensional settings, in a uniform manner that resembles sparse SIR and without additional assumptions. This is the first promising attempt in the literature to free the higher-order inverse regression methods from their dimensionality, which facilitates the applicability of SDR. The gain of column selection with respect to SDR estimation efficiency is also studied under the fixed-dimensional settings. Simulation studies and a real data example are provided at the end.
Sharpness is an almost generic assumption in continuous optimization that bounds the distance from minima by objective function suboptimality. It facilitates the acceleration of first-order methods through restarts. However, sharpness involves problem-specific constants that are typically unknown, and restart schemes typically reduce convergence rates. Moreover, these schemes are challenging to apply in the presence of noise or with approximate model classes (e.g., in compressive imaging or learning problems), and they generally assume that the first-order method used produces feasible iterates. We consider the assumption of approximate sharpness, a generalization of sharpness that incorporates an unknown constant perturbation to the objective function error. This constant offers greater robustness (e.g., with respect to noise or relaxation of model classes) for finding approximate minimizers. By employing a new type of search over the unknown constants, we design a restart scheme that applies to general first-order methods and does not require the first-order method to produce feasible iterates. Our scheme maintains the same convergence rate as when the constants are known. The convergence rates we achieve for various first-order methods match the optimal rates or improve on previously established rates for a wide range of problems. We showcase our restart scheme in several examples and highlight potential future applications and developments of our framework and theory.
We present a new algorithm for solving linear-quadratic regulator (LQR) problems with linear equality constraints, also known as constrained LQR (CLQR) problems. Our method's sequential runtime is linear in the number of stages and constraints, and its parallel runtime is logarithmic in the number of stages. The main technical contribution of this paper is the derivation of parallelizable techniques for eliminating the linear equality constraints while preserving the standard positive (semi-)definiteness requirements of LQR problems.
Spectral analysis of open surfaces is gaining momentum for studying surface morphology in engineering, computer graphics, and medical domains. This analysis is enabled using proper parameterization approaches on the target analysis domain. In this paper, we propose the usage of customizable parameterization coordinates that allow mapping open surfaces into oblate or prolate hemispheroidal surfaces. For this, we proposed the usage of Tutte, conformal, area-preserving, and balanced mappings for parameterizing any given simply connected open surface onto an optimal hemispheroid. The hemispheroidal harmonic bases were introduced to spectrally expand these parametric surfaces by generalizing the known hemispherical ones. This approach uses the radius of the hemispheroid as a degree of freedom to control the size of the parameterization domain of the open surfaces while providing numerically stable basis functions. Several open surfaces have been tested using different mapping combinations. We also propose optimization-based mappings to serve various applications on the reconstruction problem. Altogether, our work provides an effective way to represent and analyze simply connected open surfaces.
We set up, at the abstract Hilbert space setting, the general question on when an inverse linear problem induced by an operator of Friedrichs type admits solutions belonging to (the closure of) the Krylov subspace associated to such operator. Such Krylov solvability of abstract Friedrichs systems allows to predict when, for concrete differential inverse problems, truncation algorithms can or cannot reproduce the exact solutions in terms of approximants from the Krylov subspace.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191