Geometrically convergent projection method in matrix games

We propose a method which evaluates the solution of a matrix game. We reduce the problem of the search for the solution to a convex feasibility problem for which we present a method of projection onto an acute cone. The algorithm converges geometrically. At each iteration, we apply a combinatorial algorithm in order to evaluate the projection onto the standard simplex.     

Two-Phase Model Algorithm with Global Convergence for Nonlinear Programming

The family of feasible methods for minimization with nonlinear constraints includes the nonlinear projected gradient method, the generalized reduced gradient method (GRG), and many variants of the sequential gradient restoration algorithm (SGRA). Generally speaking, a particular iteration of any of these methods proceeds in two phases. In the restoration phase, feasibility is restored by means of the resolution of an auxiliary nonlinear problem, generally a nonlinear system of equations. In the minimization phase, optimality is improved by means of the consideration of the objective function, or its Lagrangian, on the tangent subspace to the constraints. In this paper, minimal assumptions are stated on the restoration phase and the minimization phase that ensure that the resulting algorithm is globally convergent. The key point is the possibility of comparing two successive nonfeasible iterates by means of a suitable merit function that combines feasibility and optimality. The merit function allows one to work with a high degree of infeasibility at the first iterations of the algorithm. Global convergence is proved and a particular implementation of the model algorithm is described.     

Alternating convex projection methods for discrete-time covariance control design

The problem of designing a controller for a linear, discretetime system is formulated as a problem of designing an appropriate plant-state covariance matrix. Closed-loop stability and multiple-output performance constraints are expressed geometrically as requirements that the covariance matrix lies in the intersection of some specified closed, convex sets in the space of symmetric matrices. We solve a covariance feasibility problem to determine the existence and compute a covariance matrix to satisty assignability and output-norm performance constraints. In addition, we can treat a covariance optimization problem to construct an assignable covariance matrix which satisfies output performance constraints and is as close as possible to a given desired covariance. We can also treat inconsistent constraints, where we look for an assignable covariance which best approximates desired but unachievable output performance objectives; we call this the infeasible covariance optimization problem. All these problems are of a convex nature, and alternating convex projection methods are proposed to solve them, exploiting the geometric formulation of the problem. To this end, analytical expressions for the projections onto the covariance assignability and the output covariance inequality constraint sets are derived. Finally, the problem of designing low-order dynamic controllers using alternating projections is discussed, and a numerical technique using alternating projections is suggested for a solution, although convergence of the algorithm is not guaranteed in this case. A control design example for a fighter aircraft model illustrates the method.This research was completed while the first author was with the Space Systems Control Laboratory at Purdue University. Support from the Army Research Office Grant ARO-29029-EG is gratefully acknowledged.     

An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem

We present an infeasible interior-point algorithm for symmetric linear complementarity problem based on modified Nesterov–Todd directions by using Euclidean Jordan algebras. The algorithm decreases the duality gap and the feasibility residual at the same rate. In this algorithm, we construct strictly feasible iterates for a sequence of perturbations of the given problem. Each main iteration of the algorithm consists of a feasibility step and a number of centring steps. The starting point in the first iteration is strictly feasible for a perturbed problem. The feasibility steps lead to a strictly feasible iterate for the next perturbed problem. By using centring steps for the new perturbed problem, a strictly feasible iterate is obtained to be close to the central path of the new perturbed problem. Furthermore, giving a complexity analysis of the algorithm, we derive the currently best-known iteration bound for infeasible interior-point methods.     

Inexact Interior-Point Method

In this paper, we introduce an inexact interior-point algorithm for a constrained system of equations. The formulation of the problem is quite general and includes nonlinear complementarity problems of various kinds. In our convergence theory, we interpret the inexact interior-point method as an inexact Newton method. This enables us to establish a global convergence theory for the proposed algorithm. Under the additional assumption of the invertibility of the Jacobian at the solution, the superlinear convergence of the iteration sequence is proved.     

Efficient numerical algorithm for solving the gravimetry problem of finding a lateral density in a layer: Parallel implementation

The paper is devoted to developing the new time- and memory-efficient algorithm BiCGSTABmem for solving the inverse gravimetry problem of determination of a variable density in a layer using the gravitational data. The problem is in solving the linear Fredholm integral equation of the first kind. After discretization of the domain and approximation of the integral operator, this problem is reduced to solving a large system of linear algebraic equations. It is shown that the matrix of coefficients is the Toeplitz-block-Toeplitz one in the case of the horizontal layer. For calculating and storing the elements of this matrix, we construct an efficient method, which significantly reduces the required memory and time. For the case of the curvilinear layer, we construct a method for approximating the parts of the matrix by a Toeplitz-block-Toeplitz one. This allows us to exploit the same efficient method for storing and processing the coefficient matrix in the case of a curvilinear layer. To solve the system of linear equations, we constructed the parallel algorithm on the basis of the stabilized biconjugated gradient method with using the Toeplitz-block-Toeplitz structure of the matrix. We implemented the BiCGSTAB and BiCGSTABmem algorithms for the Uran cluster supercomputer using the hybrid MPI + OpenMP technology. A model problem with synthetic data was solved for a large grid. It was shown that the new BiCGSTABmem algorithm reduces the computation time in comparison with the BiCGSTAB. Scalability of the parallel algorithm was studied.     

Iterative adaptive RBF methods for detection of edges in two-dimensional functions

Radial basis functions have gained popularity for many applications including numerical solution of partial differential equations, image processing, and machine learning. For these applications it is useful to have an algorithm which detects edges or sharp gradients and is based on the underlying basis functions. In our previous research, we proposed an iterative adaptive multiquadric radial basis function method for the detection of local jump discontinuities in one-dimensional problems. The iterative edge detection method is based on the observation that the absolute values of the expansion coefficients of multiquadric radial basis function approximation grow exponentially in the presence of a local jump discontinuity with fixed shape parameters but grow only linearly with vanishing shape parameters. The different growth rate allows us to accurately detect edges in the radial basis function approximation. In this work, we extend the one-dimensional iterative edge detection method to two-dimensional problems. We consider two approaches: the dimension-by-dimension technique and the global extension approach. In both cases, we use a rescaling method to avoid ill-conditioning of the interpolation matrix. The global extension approach is less efficient than the dimension-by-dimension approach, but is applicable to truly scattered two-dimensional points, whereas the dimension-by-dimension approach requires tensor product grids. Numerical examples using both approaches demonstrate that the two-dimensional iterative adaptive radial basis function method yields accurate results.     

Cost-efficient numerical algorithm for solving the linear inverse problem of finding a variable magnetization

The paper is devoted to developing an original cost-efficient algorithm for solving the inverse problem of finding a variable magnetization in a rectangular parallelepiped. The problem is ill-posed and is described by the integral Fredholm equation. It is shown that after discretization of the area and approximation of the integral operator, this problem is reduced to solving a system of linear algebraic equations with the Toeplitz-block-Toeplitz matrix. We have constructed the memory efficient variant of the stabilized biconjugate gradient method BiCGSTABmem. This optimized algorithm exploits the special structure of the matrix to reduce the memory requirements and computing time. The efficient implementation is developed for multicore CPU and GPU. A series of the model problems with synthetic and real magnetic data are solved. Investigation of efficiency and speedup of parallel algorithm is performed.     

广义耦合Sylvester矩阵方程的对称-反对称最小二乘解

本文主要研究极小残差问题‖(A1XB1+C1YD1A2XB2+C2YD2)-(M1M2)‖=min关于X对称-Y反对称解的迭代算法.本文首先给出等价于极小残差问题的规范方程,然后,提出求解此规范方程的对称-反对称解的迭代算法.在不考虑舍入误差的情况下,任取一个初始的对称-反对称矩阵对(X0,Y0),该算法都可以在有限步内求得该极小残差问题的对称-反对称解.最后讨论该问题的极小范数对称-反对称解.     

Optimization of Approximate Solution of Integral Equations of Several Variables

In this paper, we consider the problem of optimization of adaptive direct methods of operator equations. Adaptivity of a direct method is understood in the sense that the subspace on the basis of which it is constructed is chosen depending on the operator of the concrete equation (otherwise, nonadaptive direct method is then concerned), which would essentially let us increase the precision. For some classes of the second kind of Fredhlom integral equations with anisotropic smooth kernels we determine the exact order of the error of adaptive direct methods, and we also give an optimal algorithm. Received April 13, 2001, Accepted September 13, 2001     

Primal-dual row-action method for convex programming

We present a primal-dual row-action method for the minimization of a convex function subject to general convex constraints. Constraints are used one at a time, no changes are made in the constraint functions and their Jacobian matrix (thus, the row-action nature of the algorithm), and at each iteration a subproblem is solved consisting of minimization of the objective function subject to one or two linear equations. The algorithm generates two sequences: one of them, called primal, converges to the solution of the problem; the other one, called dual, approximates a vector of optimal KKT multipliers for the problem. We prove convergence of the primal sequence for general convex constraints. In the case of linear constraints, we prove that the primal sequence converges at least linearly and obtain as a consequence the convergence of the dual sequence.The research of the first author was partially supported by CNPq Grant No. 301280/86.     

A fast multiscale solver for modified Hammerstein equations

This paper presents a fast solver, called the multilevel augmentation method, for modified nonlinear Hammerstein equations. When we utilize the method to solve a large scale problem, most of components of the solution can be computed directly, and lower frequency components can be obtained by solving a fixed low-order algebraic nonlinear system. The advantage of using the algorithm to modified equations is that it leads to reduce the cost of numerical integrations greatly. The optimal error estimate of the method is established and the nearly linear computational complexity is proved. Finally, numerical examples are presented to confirm the theoretical results and illustrate the efficiency of the method.     

An algorithm for the finite difference approximation of derivatives with arbitrary degree and order of accuracy

In this paper, we introduce an algorithm and a computer code for numerical differentiation of discrete functions. The algorithm presented is suitable for calculating derivatives of any degree with any arbitrary order of accuracy over all the known function sampling points. The algorithm introduced avoids the labour of preliminary differencing and is in fact more convenient than using the tabulated finite difference formulas, in particular when the derivatives are required with high approximation accuracy. Moreover, the given Matlab computer code can be implemented to solve boundary-value ordinary and partial differential equations with high numerical accuracy. The numerical technique is based on the undetermined coefficient method in conjunction with Taylor’s expansion. To avoid the difficulty of solving a system of linear equations, an explicit closed form equation for the weighting coefficients is derived in terms of the elementary symmetric functions. This is done by using an explicit closed formula for the Vandermonde matrix inverse. Moreover, the code is designed to give a unified approximation order throughout the given domain. A numerical differentiation example is used to investigate the validity and feasibility of the algorithm and the code. It is found that the method and the code work properly for any degree of derivative and any order of accuracy.     

A Constrained Optimization Approach for LCP

In this paper, LCP is converted to an equivalent nonsmooth nonlinear equation system H(x,y) = 0 by using the famous NCP function-Fischer-Burmeister function. Note that some equations in H(x, y) = 0 are nonsmooth and nonlinear hence difficult to solve while the others are linear hence easy to solve. Then we further convert the nonlinear equation system H(x, y) = 0 to an optimization problem with linear equality constraints. After that we study the conditions under which the K-T points of the optimization problem are the solutions of the original LCP and propose a method to solve the optimization problem. In this algorithm, the search direction is obtained by solving a strict convex programming at each iterative point, However, our algorithm is essentially different from traditional SQP method. The global convergence of the method is proved under mild conditions. In addition, we can prove that the algorithm is convergent superlinearly under the conditions: M is P0 matrix and the limit point is a strict complementarity solution of LCP. Preliminary numerical experiments are reported with this method.     

Matrix valued adaptive cross approximation

A new variant of the Adaptive Cross Approximation (ACA) for approximation of dense block matrices is presented. This algorithm can be applied to matrices arising from the Boundary Element Methods (BEM) for elliptic or Maxwell systems of partial differential equations. The usual interpolation property of the ACA is generalised for the matrix valued case. Some numerical examples demonstrate the efficiency of the new method. The main example will be the electromagnetic scattering problem, that is, the exterior boundary value problem for the Maxwell system. Here, we will show that the matrix valued ACA method works well for high order BEM, and the corresponding high rate of convergence is preserved. Another example shows the efficiency of the new method in comparison with the standard technique, whilst approximating the smoothed version of the matrix valued fundamental solution of the time harmonic Maxwell system. Copyright © 2016 John Wiley & Sons, Ltd.     

Truncated Newton method for sparse unconstrained optimization using automatic differentiation

When solving large complex optimization problems, the user is faced with three major problems. These are (i) the cost in human time in obtaining accurate expressions for the derivatives involved; (ii) the need to store second derivative information; and (iii), of lessening importance, the time taken to solve the problem on the computer. For many problems, a significant part of the latter can be attributed to solving Newton-like equations. In the algorithm described, the equations are solved using a conjugate direction method that only needs the Hessian at the current point when it is multiplied by a trial vector. In this paper, we present a method that finds this product using automatic differentiation while only requiring vector storage. The method takes advantage of any sparsity in the Hessian matrix and computes exact derivatives. It avoids the complexity of symbolic differentiation, the inaccuracy of numerical differentiation, the labor of finding analytic derivatives, and the need for matrix store. When far from a minimum, an accurate solution to the Newton equations is not justified, so an approximate solution is obtained by using a version of Dembo and Steihaug's truncated Newton algorithm (Ref. 1).This paper was presented at the SIAM National Meeting, Boston, Massachusetts, 1986.     

三维电阻抗成像的体积元方法的数值模拟和分析

电阻抗成像是一类椭圆方程反问题,本文在三维区域上对其进行数值模拟和分析.对于椭圆方程Neumann边值正问题,本文提出了四面体单元上的一类对称体积元格式,并证明了格式的半正定性及解的存在性;引入单元形状矩阵的概念,简化了系数矩阵的计算;提出了对电阻率进行拼接逼近的方法来降低反问题求解规模,使之与正问题的求解规模相匹配;导出了误差泛函的Jacobi矩阵的计算公式,利用体积元格式的对称性和特殊的电流基向量,将每次迭代中需要求解的正问题的个数降到最低.一系列数值实验的结果验证了数学模型的可靠性和算法的可行性.本文所提出的这些方法,已成功应用于三维电阻抗成像的实际数值模拟.     

A shift-splitting hierarchical identification method for solving Lyapunov matrix equations

In the present paper, we propose a hierarchical identification method (SSHI) for solving Lyapunov matrix equations, which is based on the symmetry and skew-symmetry splitting of the coefficient matrix. We prove that the iterative algorithm consistently converges to the true solution for any initial values with some conditions, and illustrate that the rate of convergence of the iterative solution can be enhanced by choosing the convergence factors appropriately. Furthermore, we show that the method adopted can be easily extended to study iterative solutions of other matrix equations, such as Sylvester matrix equations. Finally, we test the algorithms and show their effectiveness using numerical examples.     

A CLASS OF FACTORIZATION UPDATE ALGORITHM FOR SOLVING SYSTEMS OF SPARSE NONLINEAR EQUATIONS

ＡＣＬＡＳＳＯＦＦＡＣＴＯＲＩＺＡＴＩＯＮＵＰＤＡＴＥＡＬＧＯＲＩＴＨＭＦＯＲＳＯＬＶＩＮＧＳＹＳＴＥＭＳＯＦＳＰＡＲＳＥＮＯＮＬＩＮＥＡＲＥＱＵＡＴＩＯＮＳＢＡＩＺＨＯＮＧＺＨＩ（ＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔａｔｉｏｎａｌＭａｔｈｅｍａｔｉｃ...     

用Uzawa型算法解抛物方程右端反问题

用Ｕｚａｗａ型算法解抛物方程右端反问题杨余飞，周叔子（湖南大学应用数学系）ＳＯＷＩＮＧＴＨＥＩＮＶＥＲＳＥＰＲＯＢＬＥＭＯＮＴＨＥＲＩＧＨＴＨＡＮＤＴＥＲＭＯＦＭＲＡＢＯＬＩＣＥＱＵＡＴＩＯＮＳＢＹＵＺＡＷ＇ＳＡＬＧＯＲＩＴＨＭ￥ＹａｎｇＹｕ－ｆｅｉ...