A preconditioning technique for a class of PDE-constrained optimization problems

We investigate the use of a preconditioning technique for solving linear systems of saddle point type arising from the application of an inexact Gauss?CNewton scheme to PDE-constrained optimization problems with a hyperbolic constraint. The preconditioner is of block triangular form and involves diagonal perturbations of the (approximate) Hessian to insure nonsingularity and an approximate Schur complement. We establish some properties of the preconditioned saddle point systems and we present the results of numerical experiments illustrating the performance of the preconditioner on a model problem motivated by image registration.     

A meshless procedure for transient heat conduction in functionally graded materials

A meshless numerical procedure is developed for analyzing the transient heat conduction problem in non-homogeneous functionally graded materials. In the proposed method the time derivative of temperature is approximate by the finite difference. At each time step the original nonlinear boundary value problem is transform into a hierarchy of non-homogeneous linear problem by used the homotopy analysis method. In this method a sought solution is presented by using a finite expansion in Taylor series, which consecutive elements are solutions of series linear value problems defining differential deformations. Each of linear boundary value problems with the corresponding boundary conditions is solved by using the method of fundamental solutions and radial basis functions which are used for interpolation of the inhomogeneous term. The accuracy of the obtained approximate solution is controlled by the number of components of the Taylor series, while the convergence of the process is monitored by an additional parameter of the method. Numerical experiments demonstrate the efficiency and accuracy of the present scheme in the solution of the heat conduction problem in nonlinear functionally graded materials. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics

We investigate the use of sparse approximate inverse preconditioners for the iterative solution of linear systems with dense complex coefficient matrices arising in industrial electromagnetic problems. An approximate inverse is computed via a Frobenius norm approach with a prescribed nonzero pattern. Some strategies for determining the nonzero pattern of an approximate inverse are described. The results of numerical experiments suggest that sparse approximate inverse preconditioning is a viable approach for the solution of large-scale dense linear systems on parallel computers. This revised version was published online in August 2006 with corrections to the Cover Date.     

Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation

We study inexact subspace iteration for solving generalized non-Hermitian eigenvalue problems with spectral transformation, with focus on a few strategies that help accelerate preconditioned iterative solution of the linear systems of equations arising in this context. We provide new insights into a special type of preconditioner with “tuning” that has been studied for this algorithm applied to standard eigenvalue problems. Specifically, we propose an alternative way to use the tuned preconditioner to achieve similar performance for generalized problems, and we show that these performance improvements can also be obtained by solving an inexpensive least squares problem. In addition, we show that the cost of iterative solution of the linear systems can be further reduced by using deflation of converged Schur vectors, special starting vectors constructed from previously solved linear systems, and iterative linear solvers with subspace recycling. The effectiveness of these techniques is demonstrated by numerical experiments.     

Numerical solution of 3D problems of electromagnetic wave diffraction on a system of ideally conducting surfaces by the method of hypersingular integral equations

We construct a numerical method for solving problems of electromagnetic wave diffraction on a system of solid and thin objects based on the reduction of the problem to a boundary integral equation treated in the sense of the Hadamard finite value. For the construction of such an equation, we construct a numerical scheme on the basis of the method of piecewise continuous approximations and collocations. Unlike earlier known schemes, by using the below-suggested scheme, we have found approximate analytic expressions for the coefficients of the arising system of linear equations by isolating the leading part of the kernel of the integral operator. We present examples of solution of a number of model problems of the diffraction of electromagnetic waves by the suggested method.     

Validated Infeasible Interior-Point Predictor–Corrector Methods for Linear Programming

Many problems arising in practical applications lead to linear programming problems. Hence, they are fundamentally tractable. Recent interior-point methods can exploit problem structure to solve such problems very efficiently. Infeasible interior-point predictor–corrector methods using floating-point arithmetic sometimes compute an approximate solution with duality gap less than a given tolerance even when the problem may not have a solution. We present an efficient verification method for solving linear programming problems which computes a guaranteed enclosure of the optimal solution and which verifies the existence of the solution within the computed interval.     

A specialized primal-dual interior point method for the plastic truss layout optimization

We are concerned with solving linear programming problems arising in the plastic truss layout optimization. We follow the ground structure approach with all possible connections between the nodal points. For very dense ground structures, the solutions of such problems converge to the so-called generalized Michell trusses. Clearly, solving the problems for large nodal densities can be computationally prohibitive due to the resulting huge size of the optimization problems. A technique called member adding that has correspondence to column generation is used to produce a sequence of smaller sub-problems that ultimately approximate the original problem. Although these sub-problems are significantly smaller than the full formulation, they still remain large and require computationally efficient solution techniques. In this article, we present a special purpose primal-dual interior point method tuned to such problems. It exploits the algebraic structure of the problems to reduce the normal equations originating from the algorithm to much smaller linear equation systems. Moreover, these systems are solved using iterative methods. Finally, due to high degree of similarity among the sub-problems after preforming few member adding iterations, the method uses a warm-start strategy and achieves convergence within fewer interior point iterations. The efficiency and robustness of the method are demonstrated with several numerical experiments.     

A reliable algorithm for solving fourth-order boundary value problems

In this paper, we present an efficient numerical algorithm for approximate solutions of fourth-order boundary values problems with twopoint boundary conditions. The Adomian decomposition method and a modified form of this method are applied to construct the numerical solution. The scheme is tested on one linear problem and two nonlinear problems. The obtained results demonstrate the applicability and efficiency of the proposed scheme.     

Numerical treatment of singularly perturbed two point boundary value problems using initial-value method

In this paper, we describe an initial-value method for linear and nonlinear singularly perturbed boundary value problems in the interval [p,q]. For linear problems, the required approximate solution is obtained by solving the reduced problem and one initial-value problems directly deduced from the given problem. For nonlinear problems the original second-order nonlinear problem is linearized by using quasilinearization method. Then this linear problem is solved as previous method. The present method has been implemented on several linear and non-linear examples which approximate the exact solution. We also present the approximate and exact solutions graphically.     

On variational perturbations of control problems: Minimum-time problem and minimum-effort problem

In order to obtain numerical solutions for an abstract optimal control problem, one approximates the abstract operations in a computationally feasible manner. After having found an approximate optimal solution, the question is whether a sequence of these approximate optimal solutions converges to an optimal solution of the original problem. In this work, we are concerned with this type of convergence on the time-optimal control problem for a class of linear systems with distributed parameters and on the minimum-effort problem.     

A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

Two-Level preconditioned Krylov subspace methods for the solution of three-dimensional heterogeneous Helmholtz problems in seismics

In this paper we address the solution of three-dimensional heterogeneous Helmholtz problems discretized with compact fourth-order finite difference methods with application to acoustic waveform inversion in geophysics. In this setting, the numerical simulation of wave propagation phenomena requires the approximate solution of possibly very large linear systems of equations. We propose an iterative two-grid method where the coarse grid problem is solved inexactly. A single cycle of this method is used as a variable preconditioner for a flexible Krylov subspace method. Numerical results demonstrate the usefulness of the algorithm on a realistic three-dimensional application. The proposed numerical method allows us to solve wave propagation problems with single or multiple sources even at high frequencies on a reasonable number of cores of a distributed memory cluster.     

Sparse Approximations of the Schur Complement for Parallel Algebraic Hybrid Solvers in 3D

<正>In this paper we study the computational performance of variants of an algebraic additive Schwarz preconditioner for the Schur complement for the solution of large sparse linear systems.In earlier works,the local Schur complements were computed exactly using a sparse direct solver.The robustness of the preconditioner comes at the price of this memory and time intensive computation that is the main bottleneck of the approach for tackling huge problems.In this work we investigate the use of sparse approximation of the dense local Schur complements.These approximations are computed using a partial incomplete LU factorization.Such a numerical calculation is the core of the multi-level incomplete factorization such as the one implemented in pARMS. The numerical and computing performance of the new numerical scheme is illustrated on a set of large 3D convection-diffusion problems;preliminary experiments on linear systems arising from structural mechanics are also reported.     

Optimal discrete-valued control computation

In this paper, we consider an optimal control problem in which the control takes values from a discrete set and the state and control are subject to continuous inequality constraints. By introducing auxiliary controls and applying a time-scaling transformation, we transform this optimal control problem into an equivalent problem subject to additional linear and quadratic constraints. The feasible region defined by these additional constraints is disconnected, and thus standard optimization methods struggle to handle these constraints. We introduce a novel exact penalty function to penalize constraint violations, and then append this penalty function to the objective. This leads to an approximate optimal control problem that can be solved using standard software packages such as MISER. Convergence results show that when the penalty parameter is sufficiently large, any local solution of the approximate problem is also a local solution of the original problem. We conclude the paper with some numerical results for two difficult train control problems.     

Initial-Value Technique for Singularly Perturbed Boundary-Value Problems for Second-Order Ordinary Differential Equations Arising in Chemical Reactor Theory

An initial-value technique is presented for solving singularly perturbed two-point boundary-value problems for linear and semilinear second-order ordinary differential equations arising in chemical reactor theory. In this technique, the required approximate solution is obtained by combining solutions of two terminal-value problems and one initial-value problem which are obtained from the original boundary-value problem through asymptotic expansion procedures. Error estimates for approximate solutions are obtained. Numerical examples are presented to illustrate the present technique.     

An interior penalty method for a finite-dimensional linear complementarity problem in financial engineering

In this work we study an interior penalty method for a finite-dimensional large-scale linear complementarity problem (LCP) arising often from the discretization of stochastic optimal problems in financial engineering. In this approach, we approximate the LCP by a nonlinear algebraic equation containing a penalty term linked to the logarithmic barrier function for constrained optimization problems. We show that the penalty equation has a solution and establish a convergence theory for the approximate solutions. A smooth Newton method is proposed for solving the penalty equation and properties of the Jacobian matrix in the Newton method have been investigated. Numerical experimental results using three non-trivial test examples are presented to demonstrate the rates of convergence, efficiency and usefulness of the method for solving practical problems.     

A finite difference scheme for nonlinear ultra-parabolic equations

In this paper, our aim is to study a numerical method for an ultraparabolic equation with nonlinear source function. Mathematically, the bibliography on initial–boundary value problems for ultraparabolic equations is not extensive although the problems have many applications related to option pricing, multi-parameter Brownian motion, population dynamics and so forth. In this work, we present the approximate solution by virtue of finite difference scheme and Fourier series. For the nonlinear case, we use an iterative scheme by linear approximation to get the approximate solution and obtain error estimates. A numerical example is given to justify the theoretical analysis.     

Adaptive Arnoldi-Tikhonov regularization for image restoration

In the framework of the numerical solution of linear systems arising from image restoration, in this paper we present an adaptive approach based on the reordering of the image approximations obtained with the Arnoldi-Tikhonov method. The reordering results in a modified regularization operator, so that the corresponding regularization can be interpreted as problem dependent. Numerical experiments are presented.     

Error Estimation for Nonlinear Complementarity Problems via Linear Systems with Interval Data

For the nonlinear complementarity problem, we derive norm bounds for the error of an approximate solution, generalizing the known results for the linear case. Furthermore, we present a linear system with interval data, whose solution set contains the error of an approximate solution. We perform extensive numerical tests and compare the different approaches.