Numerical analysis of a quadratic matrix equation

The quadratic matrix equation AX²+ BX + C = 0in n x nmatricesarises in applications and is of intrinsic interest as oneof the simplest nonlinear matrix equations. We give a completecharacterization of solutions in terms of the generalized Schurdecomposition and describe and compare various numerical solutiontechniques. In particular, we give a thorough treatment offunctional iteration methods based on Bernoulli’s method.Other methods considered include Newton’s method with exact line searches, symbolic solution and continued fractions.We show that functional iteration applied to the quadraticmatrix equation can provide an efficient way to solve the associated quadratic eigenvalue problem (²A + B + C)x = 0.     

一类特殊二次分配问题的线性化求解新方法

许多抽象于实际的二次分配问题，其流矩阵与距离矩阵中有很多零元素，求解该类二次分配问题时，可通过先行利用零元素的信息减小问题规模，缩短计算时间．以二次分配问题的线性化模型为基础，提出了一种求解流矩阵与距离矩阵中同时存在大量零元素的二次分配问题新方法，不仅从理论上证明了方法的可行性，而且从实验的角度说明了该方法比以往方法更加优越．     

Noncentral matrix quadratic forms of the skew elliptical variables

In this paper, the noncentral matrix quadratic forms of the skew elliptical variables are studied. A family of the matrix variate noncentral generalized Dirichlet distributions is introduced as the extension of the noncentral Wishart distributions, the Dirichlet distributions and the noncentral generalized Dirichlet distributions. Main distributional properties are investigated. These include probability density and closure property under linear transformation and marginalization, the joint distribution of the sub-matrices of the matrix quadratic forms in the skew elliptical variables and the moment generating functions and Bartlett's decomposition of the matrix quadratic forms in the skew normal variables. Two versions of the noncentral Cochran's Theorem for the matrix variate skew normal distributions are obtained, providing sufficient and necessary conditions for the quadratic forms in the skew normal variables to have the matrix variate noncentral generalized Dirichlet distributions. Applications include the properties of the least squares estimation in multivariate linear model and the robustness property of the Wilk's likelihood ratio statistic in the family of the matrix variate skew elliptical distributions.     

Vector space of linearizations for the quadratic two-parameter matrix polynomial

Given a quadratic two-parameter matrix polynomial Q(λ,?μ), we develop a systematic approach to generating a vector space of linear two-parameter matrix polynomials. The purpose for constructing this vector space is that potential linearizations of Q(λ,?μ) lie in it. Then, we identify a set of linearizations and describe their constructions. Finally, we determine a class of linearizations for a quadratic two-parameter eigenvalue problem.     

Solvability of quadratic matrix equations

Solvability conditions are studied in this paper for a quadratic matrix Riccati equation arising in studies of the Chapman-Enskog projection for a Cauchy problem and a mixed problem for momentum approximations of kinetic equations. The structure of the matrix equation permits one to formulate necessary and sufficient solvability conditions in terms of eigenvectors and associated vectors for the matrix composed from the coefficients.     

A unified framework for the numerical solution of general quadratic matrix equations

^** Email: vassilios.tsachouridis{at}ieee.org^*** Email: N.karcanias{at}city.ac.uk^**** Email: ixp{at}le.ac.uk Algebraic quadratic equations are special cases of a singlegeneralized algebraic quadratic matrix equation (GQME). Thispaper focuses on the numerical solution of the GQME using probability-1homotopy methods. A synoptic review of these methods and theirapplication to algebraic matrix equations is provided as background.A large variety of analysis and design problems in systems andcontrol are reported as special cases of the presented frameworkand some of them are illustrated via numerical examples fromthe literature.     

The homogeneous projective transformation of general quadratic matrix equations

^** Email: vassilios.tsachouridis{at}ieee.org^*** Email: basil.kouvaritakis{at}eng.ox.ac.uk Algebraic quadratic equations are a special case of a singlegeneralized algebraic quadratic matrix equation (GQME). Hence,the importance of that equation in science and engineering isevident. This paper focus on the study of solutions of thatGQME and a unified framework for the characterization and identificationof solutions at infinity and of finite solutions of generalquadratic algebraic matrix equations is presented. The analysisis based on the concept of homogeneous projective transformationfor general polynomial systems (Morgan, 1986). In addition,a numerical error analysis for the computed solutions is providedfor the assessment of numerical accuracy, stability and conditioningof the computed solutions. The proposed framework is independentof any numerical method and therefore it can be used along withvarious possible numerical methods for the GQME solution, especiallymatrix flow-based algorithms (Chu, 1994) (e.g. continuation/homotopy,Morgan, 1989).     

The Wiener maximum quadratic assignment problem

We investigate a special case of the maximum quadratic assignment problem where one matrix is a product matrix and the other matrix is the distance matrix of a one-dimensional point set. We show that this special case, which we call the Wiener maximum quadratic assignment problem, is NP-hard in the ordinary sense and solvable in pseudo-polynomial time.Our approach also yields a polynomial time solution for the following problem from chemical graph theory: find a tree that maximizes the Wiener index among all trees with a prescribed degree sequence. This settles an open problem from the literature.     

一类二次矩阵方程的条件数和后向误差

主要讨论一类二次矩阵方程X^2-EX-F=0的条件数和后向误差,其中E是一个对角矩阵,F是一个M矩阵.这类二次矩阵方程来源于Markov链的噪声Wiener-Hopf问题.实际问题中人们感兴趣的是它的M矩阵的解.应用Rice创立的基于Frobenius范数下的条件数理论,导出此类二次矩阵方程的M矩阵解的条件数的显式表达式.同时,也给出近似解的后向误差的定义以及一个可计算的表达式.最后,通过数值例子验证理论结果是有效的.     

A generalization of the inertia theorem for quadratic matrix polynomials

We show that the inertia of a quadratic matrix polynomial is determined in terms of the inertia of its coefficient matrices if the leading coefficient is Hermitian and nonsingular, the constant term is Hermitian, and the real part of the coefficient matrix of the first degree term is definite. In particular, we prove that the number of zero eigenvalues of such a matrix polynomial is the same as the number of zero eigenvalues of its constant term. We also give some new results for the case where the real part of the coefficient matrix of the first degree term is semidefinite.     

A numerically stable least squares solution to the quadratic programming problem

The strictly convex quadratic programming problem is transformed to the least distance problem — finding the solution of minimum norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method, an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult problems.      

On active-set methods for the quadratic programming problem

The active-set Newton method developed earlier by the authors for mixed complementarity problems is applied to solving the quadratic programming problem with a positive definite matrix of the objective function. A theoretical justification is given to the fact that the method is guaranteed to find the exact solution in a finite number of steps. Numerical results indicate that this approach is competitive with other available methods for quadratic programming problems.     

Generating equations approach for quadratic matrix equations

We show how Van Loan's method for annulling the (2,1) block of skew‐Hamiltonian matrices by symplectic‐orthogonal similarity transformation generalizes to general matrices and provides a numerical algorithm for solving the general quadratic matrix equation: For skew‐Hamiltonian matrices we find their canonical form under a similarity transformation and find the class of all symplectic‐orthogonal similarity transformations for annulling the (2,1) block and simultaneously bringing the (1,1) block to Hessenberg form. We present a structure‐preserving algorithm for the solution of continuous‐time algebraic Riccati equation. Unlike other methods in the literature, the final transformed Hamiltonian matrix is not in Hamiltonian–Schur form. Three applications are presented: (a) for a special system of partial differential equations of second order for a single unknown function, we obtain the matrix of partial derivatives of second order of the unknown function by only algebraic operations and differentiation of functions; (b) for a similar transformation of a complex matrix into a symmetric (and three‐diagonal) one by applying only finite algebraic transformations; and (c) for finite‐step reduction of the eigenvalues–eigenvectors problem of a Hermitian matrix to the eigenvalues– eigenvectors problem of a real symmetric matrix of the same dimension. Copyright © 1999 John Wiley & Sons, Ltd.     

Nonnegative definite matrices and their applications to matrix quadratic programming problems

In this paper, the concept that a matrix is nonnegative definite over a subspace and the tool of generalized inverse are used to express a general form of matrix quadratic programming. Several fundamental conclusions are obtained. An application to the common penalty method for handling constrained minimization problem is given.     

Equivalent conditions for noncentral generalized Laplacianness and independence of matrix quadratic forms

Let Y be an n×p multivariate normal random matrix with general covariance Σ_Y and W be a symmetric matrix. In the present article, the property that a matrix quadratic form Y^′WY is distributed as a difference of two independent (noncentral) Wishart random matrices is called the (noncentral) generalized Laplacianness (GL). Then a set of algebraic results are obtained which will give the necessary and sufficient conditions for the (noncentral) GL of a matrix quadratic form. Further, two extensions of Cochran’s theorem concerning the (noncentral) GL and independence of a family of matrix quadratic forms are developed.     

Nonnegative definite matrices and their applications to matrix quadratic programming problems

In this paper, the concept that a matrix is nonnegative definite over a subspace and the tool of generalized inverse are used to express a general form of matrix quadratic programming. Several fundamental conclusions are obtained. An application to the common penalty method for handling constrained minimization problem is given.     

Isolated solutions of quadratic matrix equations

We study the solutions X to the quadratic operator equation XBX+XA?DX?C=0 via the invariant subspace structure of an associated operator matrix. We translate a theorem of R.G. Douglas and C. Pearcy into a characterization of the isolated solutions to the matrix equation XBX+XA?DX?C=0, and we discuss conditions which ensure that the equation has a unique solution.     

On duality gap in binary quadratic programming

We investigate in this paper the duality gap between the binary quadratic optimization problem and its semidefinite programming relaxation. We show that the duality gap can be underestimated by ${\xi_{r+1}\delta^2}$ , where ?? is the distance between {?1, 1} ⁿ and certain affine subspace, and ?? _r+1 is the smallest positive eigenvalue of a perturbed matrix. We also establish the connection between the computation of ?? and the cell enumeration of hyperplane arrangement in discrete geometry.     

Linearly convergent descent methods for the unconstrained minimization of convex quadratic splines

We propose two linearly convergent descent methods for finding a minimizer of a convex quadratic spline and establish global error estimates for the iterates. One application of such descent methods is to solve convex quadratic programs, since they can be reformulated as problems of unconstrained minimization of convex quadratic splines. In particular, we derive several new linearly convergent algorthms for solving convex quadratic programs. These algorithms could be classified as row-action methods, matrix-splitting methods, and Newton-type methods.     

Numerical analysis for the quadratic matrix equations from a modification of fixed‐point type

In this paper, we study the quadratic matrix equations. To improve the application of iterative schemes, we use a transform of the quadratic matrix equation into an equivalent fixed‐point equation. Then, we consider an iterative process of Chebyshev‐type to solve this equation. We prove that this iterative scheme is more efficient than Newton's method. Moreover, we obtain a local convergence result for this iterative scheme. We finish showing, by an application to noisy Wiener‐Hopf problems, that the iterative process considered is computationally more efficient than Newton's method.