It is needed to solve generalized eigenvalue problems (GEP) in many applications, such as the numerical simulation of vibration analysis, quantum mechanics, electronic structure, etc. The subspace iteration is a kind of widely used algorithm to solve eigenvalue problems. To solve the generalized eigenvalue problem, one kind of subspace iteration method, Chebyshev-Davidson algorithm, is proposed recently. In Chebyshev-Davidson algorithm, the Chebyshev polynomial filter technique is incorporated in the subspace iteration. In this paper, based on Chebyshev-Davidson algorithm, a new subspace iteration algorithm is constructed. In the new algorithm, the Chebyshev filter and inexact Rayleigh quotient iteration techniques are combined together to enlarge the subspace in the iteration. Numerical results of a vibration analysis problem show that the number of iteration and computing time of the proposed algorithm is much less than that of the Chebyshev-Davidson algorithm and some typical GEP solution algorithms. Furthermore, the new algorithm is more stable and reliable than the Chebyshev-Davidson algorithm in the numerical results.
The ability to continuously acquire new knowledge and skills is crucial for autonomous agents. Existing methods are typically based on either fixed-size models that struggle to learn a large number of diverse behaviors, or growing-size models that scale poorly with the number of tasks. In this work, we aim to strike a better balance between an agent's size and performance by designing a method that grows adaptively depending on the task sequence. We introduce Continual Subspace of Policies (CSP), a new approach that incrementally builds a subspace of policies for training a reinforcement learning agent on a sequence of tasks. The subspace's high expressivity allows CSP to perform well for many different tasks while growing sublinearly with the number of tasks. Our method does not suffer from forgetting and displays positive transfer to new tasks. CSP outperforms a number of popular baselines on a wide range of scenarios from two challenging domains, Brax (locomotion) and Continual World (manipulation).
In this paper we present an active-set method for the solution of $\ell_1$-regularized convex quadratic optimization problems. It is derived by combining a proximal method of multipliers (PMM) strategy with a standard semismooth Newton method (SSN). The resulting linear systems are solved using a Krylov-subspace method, accelerated by certain general-purpose preconditioners which are shown to be optimal with respect to the proximal parameters. Practical efficiency is further improved by warm-starting the algorithm using a proximal alternating direction method of multipliers. We show that the outer PMM achieves global convergence under mere feasibility assumptions. Under additional standard assumptions, the PMM scheme achieves global linear and local superlinear convergence. The SSN scheme is locally superlinearly convergent, assuming that its associated linear systems are solved accurately enough, and globally convergent under certain additional regularity assumptions. We provide numerical evidence to demonstrate the effectiveness of the approach by comparing it against OSQP and IP-PMM (an ADMM and a regularized IPM solver, respectively) on several elastic-net linear regression and $L^1$-regularized PDE-constrained optimization problems.
Solving analytically intractable partial differential equations (PDEs) that involve at least one variable defined on an unbounded domain arises in numerous physical applications. Accurately solving unbounded domain PDEs requires efficient numerical methods that can resolve the dependence of the PDE on the unbounded variable over at least several orders of magnitude. We propose a solution to such problems by combining two classes of numerical methods: (i) adaptive spectral methods and (ii) physics-informed neural networks (PINNs). The numerical approach that we develop takes advantage of the ability of physics-informed neural networks to easily implement high-order numerical schemes to efficiently solve PDEs and extrapolate numerical solutions at any point in space and time. We then show how recently introduced adaptive techniques for spectral methods can be integrated into PINN-based PDE solvers to obtain numerical solutions of unbounded domain problems that cannot be efficiently approximated by standard PINNs. Through a number of examples, we demonstrate the advantages of the proposed spectrally adapted PINNs in solving PDEs and estimating model parameters from noisy observations in unbounded domains.
This paper presents the Residual QPAS Subspace method (ResQPASS) method that solves large-scale least-squares problem with bound constraints on the variables. The problem is solved by creating a series of small problems with increasing size by projecting on the basis residuals. Each projected problem is solved by the QPAS method that is warm-started with a working set and the solution of the previous problem. The method coincides with conjugate gradients (CG) applied to the normal equations when none of the constraints is active. When only a few constraints are active the method converges, after a few initial iterations, as the CG method. We develop a convergence theory that links the convergence with Krylov subspaces. We also present an efficient implementation where the matrix factorizations using QR are updated over the inner and outer iterations.
In this paper we consider the generalized inverse iteration for computing ground states of the Gross-Pitaevskii eigenvector problem (GPE). For that we prove explicit linear convergence rates that depend on the maximum eigenvalue in magnitude of a weighted linear eigenvalue problem. Furthermore, we show that this eigenvalue can be bounded by the first spectral gap of a linearized Gross-Pitaevskii operator, recovering the same rates as for linear eigenvector problems. With this we establish the first local convergence result for the basic inverse iteration for the GPE without damping. We also show how our findings directly generalize to extended inverse iterations, such as the Gradient Flow Discrete Normalized (GFDN) proposed in [W. Bao, Q. Du, SIAM J. Sci. Comput., 25 (2004)] or the damped inverse iteration suggested in [P. Henning, D. Peterseim, SIAM J. Numer. Anal., 53 (2020)]. Our analysis also reveals why the inverse iteration for the GPE does not react favourably to spectral shifts. This empirical observation can now be explained with a blow-up of a weighting function that crucially contributes to the convergence rates. Our findings are illustrated by numerical experiments.
The non-greedy algorithm for $L_1$-norm PCA proposed in \cite{nie2011robust} is revisited and its convergence properties are studied. The algorithm is first interpreted as a conditional subgradient or an alternating maximization method. By treating it as a conditional subgradient, the iterative points generated by the algorithm will not change in finitely many steps under a certain full-rank assumption; such an assumption can be removed when the projection dimension is one. By treating the algorithm as an alternating maximization, it is proved that the objective value will not change after at most $\left\lceil \frac{F^{\max}}{\tau_0} \right\rceil$ steps. The stopping point satisfies certain optimality conditions. Then, a variant algorithm with improved convergence properties is studied. The iterative points generated by the algorithm will not change after at most $\left\lceil \frac{2F^{\max}}{\tau} \right\rceil$ steps and the stopping point also satisfies certain optimality conditions given a small enough $\tau$. Similar finite-step convergence is also established for a slight modification of the PAMe proposed in \cite{wang2021linear} very recently under a full-rank assumption. Such an assumption can also be removed when the projection dimension is one.
Uncertain fractional differential equation (UFDE) is a kind of differential equation about uncertain process. As an significant mathematical tool to describe the evolution process of dynamic system, UFDE is better than the ordinary differential equation with integer derivatives because of its hereditability and memorability characteristics. However, in most instances, the precise analytical solutions of UFDE is difficult to obtain due to the complex form of the UFDE itself. Up to now, there is not plenty of researches about the numerical method of UFDE, as for the existing numerical algorithms, their accuracy is also not high. In this research, derive from the interval weighting method, a class of fractional adams method is innovatively proposed to solve UFDE. Meanwhile, such fractional adams method extends the traditional predictor-corrector method to higher order cases. The stability and truncation error limit of the improved algorithm are analyzed and deduced. As the application, several numerical simulations (including $\alpha$-path, extreme value and the first hitting time of the UFDE) are provided to manifest the higher accuracy and efficiency of the proposed numerical method.
The Sinkhorn algorithm is the most popular method for solving the entropy minimization problem called the Schr\"odinger problem: in the non-degenerate cases, the latter admits a unique solution towards which the algorithm converges linearly. Here, motivated by recent applications of the Schr\"odinger problem with respect to structured stochastic processes (such as increasing ones), we study the Sinkhorn algorithm in degenerate cases where it might happen that no solution exist at all. We show that in this case, the algorithm ultimately alternates between two limit points. Moreover, these limit points can be used to compute the solution of a relaxed version of the Schr\"odinger problem, which appears as the $\Gamma$-limit of a problem where the marginal constraints are replaced by asymptotically large marginal penalizations, exactly in the spirit of the so-called unbalanced optimal transport. Finally, our work focuses on the support of the solution of the relaxed problem, giving its typical shape and designing a procedure to compute it quickly. We showcase promising numerical applications related to a model used in cell biology.
In this paper, a numerical method is proposed to calculate the eigenvalues of the Zakharov-Shabat system based on Chebyshev polynomials. A mapping in the form of tanh(ax) is constructed according to the asymptotic of the potential function for the Zakharov-Shabat eigenvalue problem. The mapping could distribute Chebyshev nodes very well considering the gradient for the potential function. Using Chebyshev polynomials,tanh(ax) mapping and Chebyshev nodes, the Zakharov-Shabat eigenvalue problem is transformed into a matrix eigenvalue problem, and then solved by the QR algorithm. This method has good convergence for Satsuma-Yajima potential, and the convergence speed is faster than the fourier collocation method. This method is not only suitable for simple potential functions, but also converges quickly for complex Y-shape potential. This method can also be further extended to solve other linear eigenvalue problems.
Unsupervised domain adaptation has recently emerged as an effective paradigm for generalizing deep neural networks to new target domains. However, there is still enormous potential to be tapped to reach the fully supervised performance. In this paper, we present a novel active learning strategy to assist knowledge transfer in the target domain, dubbed active domain adaptation. We start from an observation that energy-based models exhibit free energy biases when training (source) and test (target) data come from different distributions. Inspired by this inherent mechanism, we empirically reveal that a simple yet efficient energy-based sampling strategy sheds light on selecting the most valuable target samples than existing approaches requiring particular architectures or computation of the distances. Our algorithm, Energy-based Active Domain Adaptation (EADA), queries groups of targe data that incorporate both domain characteristic and instance uncertainty into every selection round. Meanwhile, by aligning the free energy of target data compact around the source domain via a regularization term, domain gap can be implicitly diminished. Through extensive experiments, we show that EADA surpasses state-of-the-art methods on well-known challenging benchmarks with substantial improvements, making it a useful option in the open world. Code is available at //github.com/BIT-DA/EADA.