Investigating the Newton–Raphson basins of attraction in the restricted three-body problem with modified Newtonian gravity

The planar circular restricted three-body problem with modified Newtonian gravity is used in order to determine the Newton–Raphson basins of attraction associated with the equilibrium points. The evolution of the position of the five Lagrange points is monitored when the value of the power p of the gravitational potential of the second primary varies in predefined intervals. The regions on the configuration (x, y) plane occupied by the basins of attraction are revealed using the multivariate version of the Newton–Raphson iterative scheme. The correlations between the basins of convergence of the equilibrium points and the corresponding number of iterations needed for obtaining the desired accuracy are also illustrated. We conduct a thorough and systematic numerical investigation by demonstrating how the dynamical quantity p influences the shape as well as the geometry of the basins of attractions. Our results strongly suggest that the power p is indeed a very influential parameter in both cases of weaker or stronger Newtonian gravity.     

Monotone convergence of Newton-like methods for M-matrix algebraic Riccati equations

For the algebraic Riccati equation whose four coefficient matrices form a nonsingular M-matrix or an irreducible singular M-matrix K, the minimal nonnegative solution can be found by Newton’s method and the doubling algorithm. When the two diagonal blocks of the matrix K have both large and small diagonal entries, the doubling algorithm often requires many more iterations than Newton’s method. In those cases, Newton’s method may be more efficient than the doubling algorithm. This has motivated us to study Newton-like methods that have higher-order convergence and are not much more expensive each iteration. We find that the Chebyshev method of order three and a two-step modified Chebyshev method of order four can be more efficient than Newton’s method. For the Riccati equation, these two Newton-like methods are actually special cases of the Newton–Shamanskii method. We show that, starting with zero initial guess or some other suitable initial guess, the sequence generated by the Newton–Shamanskii method converges monotonically to the minimal nonnegative solution.We also explain that the Newton-like methods can be used to great advantage when solving some Riccati equations involving a parameter.     

A Priori Estimations of a Global Homotopy Residue Continuation Method

This work is concerned with the a priori estimations of a global homotopy residue continuation method starting from a disjoint initial guess. Explicit conditions ensuring the quadratic convergence of the underlying Newton–Raphson algorithm are proved.     

Fast implicit schemes for the Fokker–Planck–Landau equation

We propose new implicit schemes to solve the homogeneous and isotropic Fokker–Planck–Landau equation. These schemes have conservation and entropy properties. Moreover, they allow for large time steps (of the order of the physical relaxation time), contrary to usual explicit schemes. We use in particular fast linear Krylov solvers like the GMRES method. These schemes allow an important gain in terms of CPU time, with the same accuracy as explicit schemes. This work is a first step to the development of fast implicit schemes to solve more realistic kinetic models. To cite this article: M. Lemou, L. Mieussens, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Computation of equilibrium measures

We present a new way of computing equilibrium measures numerically, based on the Riemann–Hilbert formulation. For equilibrium measures whose support is a single interval, the simple algorithm consists of a Newton–Raphson iteration where each step only involves fast cosine transforms. The approach is then generalized for multiple intervals.     

Numerical simulation of two-dimensional Bingham fluid flow by semismooth Newton methods

This paper is devoted to the numerical simulation of two-dimensional stationary Bingham fluid flow by semismooth Newton methods. We analyze the modeling variational inequality of the second kind, considering both Dirichlet and stress-free boundary conditions. A family of Tikhonov regularized problems is proposed and the convergence of the regularized solutions to the original one is verified. By using Fenchel’s duality, optimality systems which characterize the original and regularized solutions are obtained. The regularized optimality systems are discretized using a finite element method with (cross-grid P₁)-Q₀ elements for the velocity and pressure, respectively. A semismooth Newton algorithm is proposed in order to solve the discretized optimality systems. Using an additional relaxation, a descent direction is constructed from each semismooth Newton iteration. Local superlinear convergence of the method is also proved. Finally, we perform numerical experiments in order to investigate the behavior and efficiency of the method.     

Recursive Marginal Quantization of the Euler Scheme of a Diffusion Process

Abstract

We propose a new approach to quantize the marginals of the discrete Euler diffusion process. The method is built recursively and involves the conditional distribution of the marginals of the discrete Euler process. Analytically, the method raises several questions like the analysis of the induced quadratic quantization error between the marginals of the Euler process and the proposed quantizations. We show in particular that at every discretization step t_k of the Euler scheme, this error is bounded by the cumulative quantization errors induced by the Euler operator, from times t₀ = 0 to time t_k. For numerics, we restrict our analysis to the one-dimensional setting and show how to compute the optimal grids using a Newton–Raphson algorithm. We then propose a closed formula for the companion weights and the transition probabilities associated to the proposed quantizations. This allows us to quantize in particular diffusion processes in local volatility models by reducing dramatically the computational complexity of the search of optimal quantizers while increasing their computational precision with respect to the algorithms commonly proposed in this framework. Numerical tests are carried out for the Brownian motion and for the pricing of European options in a local volatility model. A comparison with the Monte Carlo simulations shows that the proposed method may sometimes be more efficient (w.r.t. both computational precision and time complexity) than the Monte Carlo method.     

Combining Binary Search and Newton′s Method to Compute Real Roots for a Class of Real Functions

We generalize a hybrid algorithm of binary search and Newton′s method to compute real roots for a class of real functions. We show that the algorithm computes a root inside (0, R] with error ϵ in O(log log(R/ϵ)) time, where one function evaluation or one arithmetic operation counts for one unit of time. This work is based on Smale′s criterion for using Newton′s method and Renegar′s result of approximating roots of polynomials.     

High-order Newton-penalty algorithms

Recent efforts in differentiable non-linear programming have been focused on interior point methods, akin to penalty and barrier algorithms. In this paper, we address the classical equality constrained program solved using the simple quadratic loss penalty function/algorithm. The suggestion to use extrapolations to track the differentiable trajectory associated with penalized subproblems goes back to the classic monograph of Fiacco & McCormick. This idea was further developed by Gould who obtained a two-steps quadratically convergent algorithm using prediction steps and Newton correction. Dussault interpreted the prediction step as a combined extrapolation with respect to the penalty parameter and the residual of the first order optimality conditions. Extrapolation with respect to the residual coincides with a Newton step.We explore here higher-order extrapolations, thus higher-order Newton-like methods. We first consider high-order variants of the Newton–Raphson method applied to non-linear systems of equations. Next, we obtain improved asymptotic convergence results for the quadratic loss penalty algorithm by using high-order extrapolation steps.     

An exact Block–Newton algorithm for solving fluid–structure interaction problems

In this Note, we introduce a partitioned Newton based method for solving nonlinear coupled systems arising in the numerical approximation of fluid–structure interaction problems. The originality of this Schur–Newton algorithm lies in the exact Jacobians evaluation involving the fluid–structure linearized subsystems which are here fully developed. To cite this article: M.Á. Fernández, M. Moubachir, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

A robust and informative method for solving large-scale power flow problems

Solving power flow problems is essential for the reliable and efficient operation of an electric power network. However, current software for solving these problems have questionable robustness due to the limitations of the solution methods used. These methods are typically based on the Newton–Raphson method combined with switching heuristics for handling generator reactive power limits and voltage regulation. Among the limitations are the requirement of a good initial solution estimate, the inability to handle near rank-deficient Jacobian matrices, and the convergence issues that may arise due to conflicts between the switching heuristics and the Newton–Raphson process. These limitations are addressed by reformulating the power flow problem and using robust optimization techniques. In particular, the problem is formulated as a constrained optimization problem in which the objective function incorporates prior knowledge about power flow solutions, and solved using an augmented Lagrangian algorithm. The prior information included in the objective adds convexity to the problem, guiding iterates towards physically meaningful solutions, and helps the algorithm handle near rank-deficient Jacobian matrices as well as poor initial solution estimates. To eliminate the negative effects of using switching heuristics, generator reactive power limits and voltage regulation are modeled with complementarity constraints, and these are handled using smooth approximations of the Fischer–Burmeister function. Furthermore, when no solution exists, the new method is able to provide sensitivity information that aids an operator on how best to alter the system. The proposed method has been extensively tested on real power flow networks of up to 58k buses.     

A new class of polynomial primal–dual methods for linear and semidefinite optimization

We propose a new class of primal–dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large-update method for LO based on the new search direction has a polynomial complexity of O(n^4/(4+ρ)log(n/ε)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. If ρ=0, our results reproduce the well-known complexity of the standard primal–dual Newton method for LO. At each iteration, our algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented.     

The Adjoint Newton Algorithm for Large-Scale Unconstrained Optimization in Meteorology Applications

A new algorithm is presented for carrying out large-scale unconstrained optimization required in variational data assimilation using the Newton method. The algorithm is referred to as the adjoint Newton algorithm. The adjoint Newton algorithm is based on the first- and second-order adjoint techniques allowing us to obtain the Newton line search direction by integrating a tangent linear equations model backwards in time (starting from a final condition with negative time steps). The error present in approximating the Hessian (the matrix of second-order derivatives) of the cost function with respect to the control variables in the quasi-Newton type algorithm is thus completely eliminated, while the storage problem related to the Hessian no longer exists since the explicit Hessian is not required in this algorithm. The adjoint Newton algorithm is applied to three one-dimensional models and to a two-dimensional limited-area shallow water equations model with both model generated and First Global Geophysical Experiment data. We compare the performance of the adjoint Newton algorithm with that of truncated Newton, adjoint truncated Newton, and LBFGS methods. Our numerical tests indicate that the adjoint Newton algorithm is very efficient and could find the minima within three or four iterations for problems tested here. In the case of the two-dimensional shallow water equations model, the adjoint Newton algorithm improves upon the efficiencies of the truncated Newton and LBFGS methods by a factor of at least 14 in terms of the CPU time required to satisfy the same convergence criterion.The Newton, truncated Newton and LBFGS methods are general purpose unconstrained minimization methods. The adjoint Newton algorithm is only useful for optimal control problems where the model equations serve as strong constraints and their corresponding tangent linear model may be integrated backwards in time. When the backwards integration of the tangent linear model is ill-posed in the sense of Hadamard, the adjoint Newton algorithm may not work. Thus, the adjoint Newton algorithm must be used with some caution. A possible solution to avoid the current weakness of the adjoint Newton algorithm is proposed.     

Newton‐ vs. Multilevel‐Newton method in the FEM

In this presentation it is shown that in implicit finite element computations based on material models of evolutionary type the resulting system of non‐linear equations is usually not solved by means of the classical Newton‐Raphson method which is frequently stated. It is emphasized that the so‐called Multilevel‐Newton algorithm yields the known local and global schemes of stress or internal variables and nodal displacement computations. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Backward–forward algorithms for structured monotone inclusions in Hilbert spaces

In this paper, we study the backward–forward algorithm as a splitting method to solve structured monotone inclusions, and convex minimization problems in Hilbert spaces. It has a natural link with the forward–backward algorithm and has the same computational complexity, since it involves the same basic blocks, but organized differently. Surprisingly enough, this kind of iteration arises when studying the time discretization of the regularized Newton method for maximally monotone operators. First, we show that these two methods enjoy remarkable involutive relations, which go far beyond the evident inversion of the order in which the forward and backward steps are applied. Next, we establish several convergence properties for both methods, some of which were unknown even for the forward–backward algorithm. This brings further insight into this well-known scheme. Finally, we specialize our results to structured convex minimization problems, the gradient-projection algorithms, and give a numerical illustration of theoretical interest.     

Automatic Differentiation to Facilitate Maximum Likelihood Estimation in Nonlinear Random Effects Models

Maximum likelihood estimation in random effects models for non-Gaussian data is a computationally challenging task that currently receives much attention. This article shows that the estimation process can be facilitated by the use of automatic differentiation, which is a technique for exact numerical differentiation of functions represented as computer programs. Automatic differentiation is applied to an approximation of the likelihood function, obtained by using either Laplace's method of integration or importance sampling. The approach is applied to generalized linear mixed models. The computational speed is high compared to the Monte Carlo EM algorithm and the Monte Carlo Newton–Raphson method.     

Extending the QCR method to general mixed-integer programs

Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) into an equivalent program, with a convex objective function. Such a reformulation can be solved by a standard solver that uses a branch and bound algorithm. We prove that our reformulation is the best one within a convex reformulation scheme, from the continuous relaxation point of view. This reformulation, that we call MIQCR (Mixed Integer Quadratic Convex Reformulation), is based on the solution of an SDP relaxation of (MQP). Computational experiences are carried out with instances of (MQP) including one equality constraint or one inequality constraint. The results show that most of the considered instances with up to 40 variables can be solved in 1?h of CPU time by a standard solver.     

Smoothing Levenberg–Marquardt method for general nonlinear complementarity problems under local error bound

By using the F–B function and smoothing technique to convert the nonlinear complementarity problems to smoothing nonlinear systems, and introducing perturbation parameter μ_k into the smoothing Newton equation, we present a new smoothing Levenberg–Marquardt method for general nonlinear complementarity problems. For general mapping F, not necessarily a P₀ function, the algorithm has global convergence. Each accumulation point of the iterative sequence is at least a stationary point of the problem. Under the local error bound condition, which is much weaker than nonsingularity assumption or the strictly complementarity condition, we get the local superlinear convergence. Under some proper condition, quadratic convergence is also obtained.     

Logspline Density Estimation for Censored Data

Abstract

Logspline density estimation is developed for data that may be right censored, left censored, or interval censored. A fully automatic method, which involves the maximum likelihood method and may involve stepwise knot deletion and either the Akaike information criterion (AIC) or Bayesian information criterion (BIC), is used to determine the estimate. In solving the maximum likelihood equations, the Newton–Raphson method is augmented by occasional searches in the direction of steepest ascent. Also, a user interface based on S is described for obtaining estimates of the density function, distribution function, and quantile function and for generating a random sample from the fitted distribution.     

One‐level Newton–Krylov–Schwarz algorithm for unsteady non‐linear radiation diffusion problem

In this paper, we present a parallel Newton–Krylov–Schwarz (NKS)‐based non‐linearly implicit algorithm for the numerical solution of the unsteady non‐linear multimaterial radiation diffusion problem in two‐dimensional space. A robust solver technology is required for handling the high non‐linearity and large jumps in material coefficients typically associated with simulations of radiation diffusion phenomena. We show numerically that NKS converges well even with rather large inflow flux boundary conditions. We observe that the approach is non‐linearly scalable, but not linearly scalable in terms of iteration numbers. However, CPU time is more important than the iteration numbers, and our numerical experiments show that the algorithm is CPU‐time‐scalable even without a coarse space given that the mesh is fine enough. This makes the algorithm potentially more attractive than multilevel methods, especially on unstructured grids, where course grids are often not easy to construct. Copyright © 2004 John Wiley & Sons, Ltd.