An inexact inverse iteration for large sparse eigenvalue problems

In this paper, we propose an inverse inexact iteration method for the computation of the eigenvalue with the smallest modulus and its associated eigenvector for a large sparse matrix. The linear systems of the traditional inverse iteration are solved with accuracy that depends on the eigenvalue with the second smallest modulus and iteration numbers. We prove that this approach preserves the linear convergence of inverse iteration. We also propose two practical formulas for the accuracy bound which are used in actual implementation. © 1997 John Wiley & Sons, Ltd.     

Inexact inverse subspace iteration for generalized eigenvalue problems

n this paper, we present an inexact inverse subspace iteration method for computing a few eigenpairs of the generalized eigenvalue problem Ax=λBx. We first formulate a version of inexact inverse subspace iteration in which the approximation from one step is used as an initial approximation for the next step. We then analyze the convergence property, which relates the accuracy in the inner iteration to the convergence rate of the outer iteration. In particular, the linear convergence property of the inverse subspace iteration is preserved. Numerical examples are given to demonstrate the theoretical results.     

A solution of the affine quadratic inverse eigenvalue problem

The quadratic inverse eigenvalue problem (QIEP) is to find the three matrices M,C, and K, given a set of numbers, closed under complex conjugations, such that these numbers become the eigenvalues of the quadratic pencil P(λ)=λ²M+λC+K. The affine inverse quadratic eigenvalue problem (AQIEP) is the QIEP with an additional constraint that the coefficient matrices belong to an affine family, that is, these matrices are linear combinations of substructured matrices. An affine family of matrices very often arise in vibration engineering modeling and analysis. Research on QIEP and AQIEP are still at developing stage. In this paper, we propose three methods and the associated mathematical theories for solving AQIEP: A Newton method, an alternating projections method, and a hybrid method combining the two. Validity of these methods are illustrated with results on numerical experiments on a spring-mass problem and comparisons are made with these three methods amongst themselves and with another Newton method developed by Elhay and Ram (2002) [12]. The results of our experiments show that the hybrid method takes much smaller number of iterations and converges faster than any of these methods.     

An inexact NE/SQP method for solving the nonlinear complementarity problem

In this paper, we present an extension to the NE/SQP method; the latter is a robust algorithm that we proposed for solving the nonlinear complementarity problem in an earlier article. In this extended version of NE/SQP, instead of exactly solving the quadratic program subproblems, approximate solutions are generated via an inexact rule.Under a proper choice for this rule, this inexact method is shown to inherit the same convergence properties of the original NE/SQP method. In addition to developing the convergence theory for the inexact method, we also present numerical results of the algorithm tested on two problems of varying size.     

Regularized Newton iteration method for a penetrable cavity with internal measurements in inverse scattering problem

In this paper, we consider the inverse scattering problem of determining the shape of a cavity with a penetrable inhomogeneous medium of compact support from one source and a knowledge of measurements placed on a curve inside the cavity. First, the boundary value problem of the partial differential equations can be transformed into an equivalent system of nonlinear and ill-posed integral equations for the unknown boundary. Then, we apply the regularized Newton iterative method to reconstruct the boundary and prove the injectivity for the linearized system. Finally, we present some numerical examples to show the feasibility of our method.     

A geometric theory for preconditioned inverse iteration applied to a subspace

The aim of this paper is to provide a convergence analysis for a preconditioned subspace iteration, which is designated to determine a modest number of the smallest eigenvalues and its corresponding invariant subspace of eigenvectors of a large, symmetric positive definite matrix. The algorithm is built upon a subspace implementation of preconditioned inverse iteration, i.e., the well-known inverse iteration procedure, where the associated system of linear equations is solved approximately by using a preconditioner. This step is followed by a Rayleigh-Ritz projection so that preconditioned inverse iteration is always applied to the Ritz vectors of the actual subspace of approximate eigenvectors. The given theory provides sharp convergence estimates for the Ritz values and is mainly built on arguments exploiting the geometry underlying preconditioned inverse iteration.     

On a recursive inverse eigenvalue problem

Let s ₁, ..., s _n be arbitrary complex scalars. It is required to construct an n × n normal matrix A such that s _i is an eigenvalue of the leading principal submatrix A _i , i = 1, 2, ..., n. It is shown that, along with the obvious diagonal solution diag(s ₁, ..., s _n ), this problem always admits a much more interesting nondiagonal solution A. As a rule, this solution is a dense matrix; with the diagonal solution, it shares the property that each submatrix A _i is itself a normal matrix, which implies interesting connections between the spectra of the neighboring submatrices A _i and A _{i + 1}.     

A stability analysis of the jacobi matrix inverse eigenvalue problem

In this paper, we give a perturbation bound for the solution of the Jacobi matrix inverse eigenvalue problem.China State Major Key Project for Basic Researches.     

Modulus‐based matrix splitting iteration methods for linear complementarity problems

For the large sparse linear complementarity problems, by reformulating them as implicit fixed‐point equations based on splittings of the system matrices, we establish a class of modulus‐based matrix splitting iteration methods and prove their convergence when the system matrices are positive‐definite matrices and H₊‐matrices. These results naturally present convergence conditions for the symmetric positive‐definite matrices and the M‐matrices. Numerical results show that the modulus‐based relaxation methods are superior to the projected relaxation methods as well as the modified modulus method in computing efficiency. Copyright © 2009 John Wiley & Sons, Ltd.     

A Lipschitzian error bound for monotone symmetric cone linear complementarity problem

We first discuss some properties of the solution set of a monotone symmetric cone linear complementarity problem (SCLCP), and then consider the limiting behaviour of a sequence of strictly feasible solutions within a wide neighbourhood of central trajectory for the monotone SCLCP. Under assumptions of strict complementarity and Slater’s condition, we provide four different characterizations of a Lipschitzian error bound for the monotone SCLCP in general Euclidean Jordan algebras. Thanks to the observation that a pair of primal-dual convex quadratic symmetric cone programming (CQSCP) problems can be exactly formulated as the monotone SCLCP, thus we obtain the same error bound results for CQSCP as a by-product.     

Modified modulus‐based matrix splitting iteration methods for linear complementarity problems

For solving the large sparse linear complementarity problems, we establish modified modulus‐based matrix splitting iteration methods and present the convergence analysis when the system matrices are H₊‐matrices. The optima of parameters involved under some scopes are also analyzed. Numerical results show that in computing efficiency, our new methods are superior to classical modulus‐based matrix splitting iteration methods under suitable conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

Reconstruction for a class of the inverse transmission eigenvalue problem

The authors present a constructive algorithm for the numerical solution to a class of the inverse transmission eigenvalue problem. The numerical experiments are provided to demonstrate the efficiency of our algorithms by a numerical example.     

A two-step modulus-based multisplitting iteration method for the nonlinear complementarity problem

In this paper, we construct a two-step modulus-based multisplitting iteration method based on multiple splittings of the system matrix for the nonlinear complementarity problem. And we prove its convergence when the system matrix is an $H$-matrix with positive diagonal elements. Numerical experiments show that the proposed method is efficient.     

Constructive methods for spectra with three nonzero elements in the nonnegative inverse eigenvalue problem

We present and compare three constructive methods for realizing nonreal spectra with three nonzero elements in the nonnegative inverse eigenvalue problem. We also provide some necessary conditions for realizability and numerical examples. In particular, we utilize the companion matrix.     

A modified SQP-filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.     

On the gradient-projection method for solving the nonsymmetric linear complementarity problem

The Levitin-Poljak gradient-projection method is applied to solve the linear complementarity problem with a nonsymmetric matrixM, which is either a positive-semidefinite matrix or aP-matrix. Further-more, if the quadratic functionx ^T(Mx + q) is pseudoconvex on the feasible region {x R ⁿ |Mx + q 0,x0}, then the gradient-projection method generates a sequence converging to a solution, provided that the problem has a solution. For the case when the matrixM is aP-matrix and the solution is nondegenerate, the gradient-projection method is finite.This work is based on the author's PhD Dissertation, which was supported by NSF Grant No. MCS-79-01066 at the University of Wisconsin, Madison, Wisconsin.The author would like to thank Professor O. L. Mangasarian for his guidance of the dissertation.     

一类二次规划逆问题的交替方向数值方法

考虑求解一类二次规划逆问题的交替方向数值算法．首先给出矩阵变量子问题解的显示表达式,而后构造了两个求解向量变量子问题近似解的数值算法,其中一个算法基于不动点原理,另一算法则应用半光滑牛顿法．数值实验表明,所提出的算法能够快速高效地求解二次规划逆问题．     

Predictor-corrector method for nonlinear complementarity problem

Recently, Ye et al. proved that the predictor-corrector method proposed by Mizuno et al. maintains -iteration complexity while exhibiting the quadratic convergence of the dual gap to zero under very mild conditions. This impressive result becomes the best-known in the interior point methods. In this paper, we modify the predictor-corrector method and then extend it to solving the nonlinear complementarity problem. We prove that the new method has a -iteration complexity while maintaining the quadratic asymptotic convergence.