We give a triangulation for Wright's 2(n)-ray algorithm to compute solutions of nonlinear equations. According to measures of efficiency of triangulations, it is better than any other available triangulation for t...
详细信息
We give a triangulation for Wright's 2(n)-ray algorithm to compute solutions of nonlinear equations. According to measures of efficiency of triangulations, it is better than any other available triangulation for the 2(n)-ray algorithm. (C) 1997 Academic Press.
Sparse representations has become an important topic in recent years. It consists in representing, say, a signal (vector) as a linear combination of as few as possible components (vectors) from a redundant basis (of t...
详细信息
Sparse representations has become an important topic in recent years. It consists in representing, say, a signal (vector) as a linear combination of as few as possible components (vectors) from a redundant basis (of the vector space). This is usually performed, either iteratively (adding a component at a time), or globally (selecting simultaneously all the needed components). We consider a specific algorithm, that we obtain as a fixedpoint algorithm, but that can also be seen as an iteratively reweighted least-squares algorithm. We analyze it thoroughly and show that it converges to the global optimum. We detail the proof in the real case and indicate how to extend it to the complex case. We illustrate the result with some easily reproducible toy simulations, that further illustrate the potential tracking properties of the proposed algorithm.
We consider the recent algorithms for computing fixedpoints or zeros of continuous functions fromRn to itself that are based on tracing piecewise-linear paths in triangulations. We investigate the possible savings th...
详细信息
We consider the recent algorithms for computing fixedpoints or zeros of continuous functions fromRn to itself that are based on tracing piecewise-linear paths in triangulations. We investigate the possible savings that arise when these fixed-point algorithms with their usual triangulations are applied to computing zeros of functionsf with special structure:f is either piecewise-linear in certain variables, separable, or has Jacobian with small bandwidth. Each of these structures leads to a property we call modularity; the algorithmic path within a simplex can be continued into an adjacent simplex without a function evaluation or linear programming pivot. Modularity also arises without any special structure onf from the linearity of the function that is deformed *** the case thatf is separable we show that the path generated by Kojima's algorithm with the homotopyH2 coincides with the path generated by the standard restart algorithm of Merrill when the usual triangulations are employed. The extra function evaluations and linear programming steps required by the standard algorithm can be avoided by exploiting modularity.
The exact homotopy path when seeking the minimum of a convex function is monotonic in the homotopy parameter. This monotonicity is not inherited by the piecewise linear approximations to such paths produced by fixed-p...
详细信息
The exact homotopy path when seeking the minimum of a convex function is monotonic in the homotopy parameter. This monotonicity is not inherited by the piecewise linear approximations to such paths produced by fixed-point algorithms.
It is well known that the Newton method may not converge when the initial guess does not belong to a specific quadratic convergence region. We propose a family of new variants of the Newton method with the potential a...
详细信息
It is well known that the Newton method may not converge when the initial guess does not belong to a specific quadratic convergence region. We propose a family of new variants of the Newton method with the potential advantage of having a larger convergence region as well as more desirable properties near a solution. We prove quadratic convergence of the new family, and provide specific bounds for the asymptotic error constant. We illustrate the advantages of the new methods by means of test problems, including two and six variable polynomial systems, as well as a challenging signal processing example. We present a numerical experimental methodology which uses a large number of randomized initial guesses for a number of methods from the new family, in turn providing advice as to which of the methods employed is preferable to use in a particular search domain.
Imposing equilibrium restrictions provides substantial gains in the estimation of dynamic discrete games. Estimation algorithms imposing these restrictions have different merits and limitations. algorithms that guaran...
详细信息
Imposing equilibrium restrictions provides substantial gains in the estimation of dynamic discrete games. Estimation algorithms imposing these restrictions have different merits and limitations. algorithms that guarantee local convergence typically require the approximation of high-dimensional Jacobians. Alternatively, the Nested Pseudo-Likelihood (NPL) algorithm is a fixed-point iterative procedure, which avoids the computation of these matrices, but-in games-may fail to converge to the consistent NPL estimator. In order to better capture the effect of iterating the NPL algorithm in finite samples, we study the asymptotic properties of this algorithm for data generating processes that are in a neighborhood of the NPL fixed-point stability threshold. We find that there are always samples for which the algorithm fails to converge, and this introduces a selection bias. We also propose a spectral algorithm to compute the NPL estimator. This algorithm satisfies local convergence and avoids the approximation of Jacobian matrices. We present simulation evidence and an empirical application illustrating our theoretical results and the good properties of the spectral algorithm.
The adjoint mode of Algorithmic Differentiation (AD) is particularly attractive for computing gradients. However, this mode needs to use the intermediate values of the original simulation in reverse order at a cost th...
详细信息
The adjoint mode of Algorithmic Differentiation (AD) is particularly attractive for computing gradients. However, this mode needs to use the intermediate values of the original simulation in reverse order at a cost that increases with the length of the simulation. AD research looks for strategies to reduce this cost, for instance by taking advantage of the structure of the given program. In this work, we consider on one hand the frequent case of fixed-point loops for which several authors have proposed adapted adjoint strategies. Among these strategies, we select the one introduced by B. Christianson. We specify further the selected method and we describe the way we implemented it inside the AD tool Tapenade. Experiments on a medium-size application shows a major reduction of the memory needed to store trajectories. On the other hand, we study checkpointing in the case of MPI parallel programs with point-to- point communications. We propose techniques to apply checkpointing to these programs. We provide proof of correctness of our techniques and we experiment them on representative CFD codes. This work was sponsored by the European project "AboutFlow".
In this paper, we propose an approach for computing invariant sets of discrete-time nonlinear systems by lifting the nonlinear dynamics into a higher dimensional linear model. In particular, we focus on the maximal ad...
详细信息
In this paper, we propose an approach for computing invariant sets of discrete-time nonlinear systems by lifting the nonlinear dynamics into a higher dimensional linear model. In particular, we focus on the maximal admissible invariant set contained in some given constraint set. For special types of nonlinear systems, which can be exactly immersed into higher dimensional linear systems with state transformations, invariant sets of the original nonlinear system can be characterized using the higher dimensional linear representation. For general nonlinear systems without the immersibility property, approximate immersions are defined in a local region within some tolerance and linear approximations are computed by leveraging the fixed-point iteration technique for invariant sets. Given the bound on the mismatch between the linear approximation and the original system, we provide an invariant inner approximation of the maximal admissible invariant set by a tightening procedure. (c) 2022 Elsevier Ltd. All rights reserved.
暂无评论