A fast interative method for solving regularized parameter identification problems in elliptic boundary value problems

We study the regularization method applied to the numerical identification of the diffusion coefficienta(x) within a linear two-point boundary value problem of 2nd order. For solving the corresponding regularized discrete nonlinear minimization problems the Gauss-Newton method is analyzed. We describe an effective way for performing one iteration step which requires to solve only two tridiagonal systems of equations.     

A coupled Newton iterative mixed finite element method for stationary conduction–convection problems

In this paper, a coupled Newton iterative mixed finite element method (MFEM) for solving the stationary conduction–convection problems in two dimension is given. In our method, the Newton iterative MFEM is used for solving all the equations of the conduction–convection problems. The stability and convergence analysis in H ¹-norm of ${u_h^n, T_h^n}$ and the L ²-norm of ${p_h^n}$ are derived. The theory analysis shows that our method is stable and have a good precision. Some numerical results are also given, which show that the coupled Newton iterative MFEM is highly efficient for the stationary conduction–convection problems.     

On the use of parallel processors for implicit Runge-Kutta methods

An iteration scheme, for solving the non-linear equations arising in the implementation of implicit Runge-Kutta methods, is proposed. This scheme is particularly suitable for parallel computation and can be applied to any method which has a coefficient matrixA with all eigenvalues real (and positive). For such methods, the efficiency of a modified Newton scheme may often be improved by the use of a similarity transformation ofA but, even when this is the case, the proposed scheme can have advantages for parallel computation. Numerical results illustrate this. The new scheme converges in a finite number of iterations when applied to linear systems of differential equations, achieving this by using the nilpotency of a strictly lower triangular matrixS ^?1 AS — Λ, with Λ a diagonal matrix. The scheme reduces to the modified Newton scheme whenS ^?1 AS is diagonal.A convergence result is obtained which is applicable to nonlinear stiff systems.     

Topology optimization of density type for a linear elastic body by using the second derivative of a KS function with respect to von Mises stress

This study demonstrates the use of Newton method to solve topology optimization problems of density type for linear elastic bodies to minimize the maximum von Mises stress. We use the Kreisselmeier–Steinhauser (KS) function with respect to von Mises stress as a cost function to avoid the non-differentiability of the maximum von Mises stress. For the design variable, we use a function defined in the domain of a linear elastic body with no restriction on the range and assume that a density is given by a sigmoid function of the function of design variable. The main aim of this study involves evaluating the second derivative of the KS function with respect to variation of the design variable and to propose an iterative scheme based on an H¹ Newton method as opposed to the H¹ gradient method that was presented in previous studies. The effectiveness of the scheme is demonstrated by numerical results for several linear elastic problems. The numerical results show that the speed of the proposed H¹ Newton method exceeds that of the H¹ gradient method.     

Modified online Newton step based on elementwise multiplication

The second-order method using a Newton step is a suitable technique in online learning to guarantee a regret bound. The large data are a challenge in the Newton method to store second-order matrices such as the hessian. In this article, we have proposed a modified online Newton step that stores first- and second-order matrices of dimension m (classes) by d (features). We have used elementwise arithmetic operations to maintain the size of matrices. The modified second-order matrix size results in faster computations. Also, the mistake rate is on par with respect to popular methods in the literature. The experimental outcome indicates that proposed method could be helpful to handle large multiclass datasets on common desktop machines using second-order method as the Newton step.     

Computation of the Hessian matrix in aerodynamic inverse design using continuous adjoint formulations

Continuous adjoint formulations for the computation of (first and) second order derivatives of the objective function governing inverse design problems in 2D inviscid flows are presented. These are prerequisites for the use of the very efficient exact Newton method. Four new formulations based on all possible combinations of the direct differentiation method and the continuous adjoint approach to compute the sensitivity derivatives of objective functions, constrained by the flow equations, are presented. They are compared in terms of the expected CPU cost to compute the Hessian of the objective function used in single-objective optimization problems with N degrees of freedom. The less costly among them was selected for further study and tested in inverse design problems solved by means of the Newton method. The selected approach, which will be referred to as the direct-adjoint one, since it performs direct differentiation for the gradient and, then, uses the adjoint approach to compute the Hessian, requires as many as N+2 equivalent flow solutions for each Newton step. The major part of the CPU cost (N equivalent flow solutions) is for the computation of the gradient but, fortunately, this task is directly amenable to parallelization. The method is used to reconstruct ducts or cascade airfoils for a known pressure distribution along their solid boundaries, at inviscid flow conditions. The examined cases aim at demonstrating the accuracy of the proposed method in computing the exact Hessian matrix as well as the efficiency of the exact Newton method as an optimization tool in aerodynamic design.     

The use of first and second derivatives in optical model parameter searches

This paper compares the efficiencies of standard minimization procedures in carrying out nuclear optical-model fits. It is shown that first-order perturbation theory permits computation of the gradient of x² more than five times as fast as is possible by difference methods. A linear approximation to the second-derivative matrix in terms of first derivatives of residuals is found to be very accurate in the neighborhood of minima; it provides a way of introducing second-derivative information that is significantly superior to the use of variable-metric algorithms. The resulting restricted-step Gauss-Newton procedures are shown to be about five times as fast as direct-search methods. The use of the methods of pseudo-inverses to “freeze” linear combinations of parameters poorly determined by the data is discussed.     

A polynomial newton method for linear programming

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at mostO(n ² m ² L) operations that there is no solution or, else, computes an exact solution in at mostO(n ³ m ² L) operations. The linear programming problem is treated as a parametrized feasibility problem and solved in at mostO(n ³ m ² L) operations.     

The stiffest designs of elastic plates: Vector optimization for two loading conditions

The paper deals with optimal design of linearly elastic plates of the Kelvin moduli being distributed according to a given pattern. The case of two loading conditions is discussed. The optimal plate is characterized by the minimum value of the weighted sum of the compliances corresponding to the two kinds of loads. The problem is reduced to the equilibrium problem of a hyperelastic mixture of properties expressed in terms of two stress fields. The stress-based formulation (P) is rearranged to the displacement-based form (P¹). The latter formulation turns out to be well-posed due to convexity of the relevant potential expressed in terms of strains. Due to monotonicity of the stress–strain relations the problem (P¹) is tractable by the finite element method, using special Newton’s solvers. Exemplary numerical results are presented delivering layouts of variation of elastic characteristics for selected values of the weighting factors corresponding to two kinds of loadings.     

Decentralized closed-loop parameter identification for multivariable processes from step responses

This paper presents a novel technique for on-line decentralized closed-loop parameter identification of multivariable processes from step responses. Based on simple sequential step tests, the coupled closed-loop n-inputs and n-outputs (n × n) multivariable process is decoupled equivalently into n² independent single open-loop processes with an unit step input signal acting on the n² transfer functions. By using virtual step response signals, the parameters of each element in the transfer function matrix can be directly identified by the well-developed least squares methods. The significance of the proposed method is that it relaxes most restrictions of existing multivariable process identification methods, it is universally applicable to closed-loop identification for cross-coupling multivariable processes. Simulation examples are given to show both effectiveness and practicality of the identification method for a wide range of multivariable processes.     

The continuous direct-adjoint approach for second order sensitivities in viscous aerodynamic inverse design problems

A novel continuous adjoint approach for the computation of the second order sensitivities of the objective function used in inverse design problems is proposed. In the framework of the Newton method, the proposed approach can be used to efficiently cope with inverse design problems in viscous flows, where the target is a given pressure distribution along the solid walls. It consists of two steps and will, thus, be referred to as the direct-adjoint approach. At the first step, the direct differentiation method is used to compute the first order sensitivities of the flow variables with respect to the design variables and build the gradient of the objective function. At the second step, the adjoint approach is used to compute the second order sensitivities. The final Hessian expression is free of field integrals and its computation requires the solution of N + 1 equivalent flow (system) solutions for N design variables. Since the CPU cost of using the Newton method, with exact gradient and Hessian data at each cycle, becomes prohibitively high, an approach that computes the exact Hessian only once and then updates it in an approximated manner through the BFGS formula, is used instead. The accuracy of the Hessian matrix components, computed using the direct-adjoint approach is demonstrated on the inverse design of a diffuser and a cascade airfoil.     

Quadratic Finite Element Approximations of the Monge-Amp��re Equation

We prove several new results of the C ⁰ finite element method introduced in (S.C.?Brenner et al., Math. Comput. 80:1979?C1995, 2011) for the fully nonlinear Monge-Ampère equation. These include the convergence of quadratic finite element approximations, W ^2,p quasi-optimal error estimates, localized pointwise error estimates, and convergence of Newton??s method with explicit dependence on the discretization parameter. Numerical experiments are presented which back up the theoretical results.     

Box-Splitting strategies for the interval Gauss-Seidel step in a global optimization method

We consider an algorithm for computing verified enclosures for all global minimizersx ^* and for the global minimum valuef ^*=f(x ^*) of a twice continuously differentiable functionf:? ⁿ →→ within a box [x]∈I→. Our algorithm incorporates the interval Gauss-Seidel step applied to the problem of finding the zeros of the gradient off. Here, we have to deal with the gaps produced by the extended interval division. It is possible to use different box-splitting strategies for handling these gaps, producing different numbers of subboxes. We present results concerning the impact of these strategies on the interval Gauss-Seidel step and therefore on our global optimization method. First, we give an overview of some of the techniques used in our algorithm, and we describe the modifications improving the efficiency of the interval Gauss-Seidel step by applying a special box-splitting strategy. Then, we have a look on special preconditioners for the Gauss-Seidel step, and we investigate the corresponding results for different splitting strategies. Test results for standard global optimization problems are discussed for different variants of our method in its portable PASCAL-XSC implementation. These results demonstrate that there are many cases in which the splitting strategy is more important for the efficiency of the algorithm than the use of preconditioners.     

Improving the Van de Vel Root-Finding method

The Van de Vel Method for solving a single nonlinear equation consists in a succession of quasi-Newton steps, each with a coefficientm ^* that approximates the multiplicitym. Before every other step,m ^* is extrapolated by a δ²-process to a better estimate ofm. In the improved method,m ^* is extrapolated each and every step after the first; as a result, the efficiency is improved from 1.554 to 1.618. It is also shown that convergence of Van de Vel's Method is actually of order \(\left( {1 + \sqrt 2 } \right)\) instead of the presumed value 2.     

Design and analysis of optimization methods for subdivision surface fitting

We present a complete framework for computing a subdivision surface to approximate unorganized point sample data, which is a separable nonlinear least squares problem. We study the convergence and stability of three geometrically-motivated optimization schemes and reveal their intrinsic relations with standard methods for constrained nonlinear optimization. A commonly-used method in graphics, called point distance minimization, is shown to use a variant of the gradient descent step and thus has only linear convergence. The second method, called tangent distance minimization, which is well-known in computer vision, is shown to use the Gauss-Newton step, and thus demonstrates near quadratic convergence for zero residual problems but may not converge otherwise. Finally, we show that an optimization scheme called squared distance minimization, recently proposed by Pottmann et al., can be derived from the Newton method. Hence, with proper regularization, tangent distance minimization and squared distance minimization are more efficient than point distance minimization. We also investigate the effects of two step size control methods -- Levenberg-Marquardt regularization and the Armijo rule -- on the convergence stability and efficiency of the above optimization schemes.     

Optimization methods for scattered data approximation with subdivision surfaces

We present a method for scattered data approximation with subdivision surfaces which actually uses the true representation of the limit surface as a linear combination of smooth basis functions associated with the control vertices. A robust and fast algorithm for exact closest point search on Loop surfaces which combines Newton iteration and non-linear minimization is used for parameterizing the samples. Based on this we perform unconditionally convergent parameter correction to optimize the approximation with respect to the L² metric, and thus we make a well-established scattered data fitting technique which has been available before only for B-spline surfaces, applicable to subdivision surfaces. We also adapt the recently discovered local second order squared distance function approximant to the parameter correction setup. Further we exploit the fact that the control mesh of a subdivision surface can have arbitrary connectivity to reduce the L^∞ error up to a certain user-defined tolerance by adaptively restructuring the control mesh. Combining the presented algorithms we describe a complete procedure which is able to produce high-quality approximations of complex, detailed models.     

A locally optimized reordering algorithm and its application to a parallel sparse linear system solver

A coarse-grain parallel solver for systems of linear algebraic equations with general sparse matrices by Gaussian elimination is discussed. Before the factorization two other steps are performed. A reordering algorithm is used during the first step in order to obtain a permuted matrix with as many zero elements under the main diagonal as possible. During the second step the reordered matrix is partitioned into blocks for asynchronous parallel processing (normally the number of blocks is equal to the number of processors). It is possible to obtain blocks with nearly the same number of rows, because there is no requirement to produce square diagonal blocks. The first step is much more important than the second one and has a significant influence on the performance of the solver. A straightforward implementation of the reordering algorithm will result inO(n ²) operations. By using binary trees this cost can be reduced toO(NZ logn), whereNZ is the number of non-zero elements in the matrix andn is its order (normallyNZ is much smaller thann ²). Some experiments on parallel computers with shared memory have been performed. The results show that a solver based on the proposed reordering performs better than another solver based on a cheaper (but at the same time rather crude) reordering whose cost is onlyO(NZ) operations.     

Algebraic approach to the interval linear static identification,tolerance, and control problems,or one more application of kaucher arithmetic

In this paper, theidentification problem, thetolerance problem, and thecontrol problem are treated for the interval linear equation Ax=b. These problems require computing an inner approximation of theunited solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, of thetolerable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, and of thecontrollable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?b ∈ b)(Ax ∈b)} respectively. Analgebraic approach to their solution is developed in which the initial problem is replaced by that of finding analgebraic solution of some auxiliary interval linear system in Kaucher extended interval arithmetic. The algebraic approach is proved almost always to give inclusion-maximal inner interval estimates of the solutionsets considered. We investigate basic properties of the algebraic solutions to the interval linear systems and propose a number of numerical methods to compute them. In particular, we present the simple and fastsubdifferential Newton method, prove its convergence and discuss numerical experiments.     

Parameter estimation in complicated rational functions

An extension of the previously proposed method [Dimitrov S.D. & Kamenski D.I. (1991) Computers Chem. Engng 15, 657] for unconstrained parameter estimation in models, expressed as the ratio of any linear functions of the unknown parameters, is described. The results from simulated and real data show that the method provides non-local convergence properties. Also, it is superior to the Gauss-Newton and Marquardt algorithms with respect to sensitivity to the initial parameter estimates.     

On tensor approximation of Green iterations for Kohn-Sham equations

In the present paper we discuss efficient rank-structured tensor approximation methods for 3D integral transforms representing the Green iterations for the Kohn-Sham equation. We analyse the local convergence of the Newton iteration to solve the Green’s function integral formulation of the Kohn-Sham model in electronic structure calculations. We prove the low-separation rank approximations for the arising discrete convolving kernels given by the Coulomb and Yukawa potentials 1/|x|, and e ^?λ|x|/|x|, respectively, with $x \in {\mathbb{R}}^{d} $ . Complexity analysis of the nonlinear iteration with truncation to the fixed Kronecker tensor-product format is presented. Our method has linear scaling in the univariate problem size. Numerical illustrations demostrate uniform exponential convergence of tensor approximations in the orthogonal Tucker and canonical formats.