Bard-type Methods for the Linear Complementarity problem with symmetric positive Definite Matrices

In this paper, the authors develop two heuristic Block Bard-typemethods for solving linear complementarity problems with P-matrices.Two implementations of these algorithms for sparse symmetricP (positive definite) matrices without special structure aredescribed. A computational study of these methods is also presented,and shows that the heuristic methods are quite efficient forthe solution of large-scale linear complementarity problemswith such matrices.     

On the convergence of the block principal pivotal algorithm for the LCP

We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling.     

Computational complexity of LCPs associated with positive definite symmetric matrices

Murty in a recent paper has shown that the computational effort required to solve a linear complementarity problem (LCP), by either of the two well known complementary pivot methods is not bounded above by a polynomial in the size of the problem. In that paper, by constructing a class of LCPs—one of ordern forn 2—he has shown that to solve the problem of ordern, either of the two methods goes through 2 ⁿ pivot steps before termination.However that paper leaves it as an open question to show whether or not the same property holds if the matrix,M, in the LCP is positive definite and symmetric. The class of LCPs in whichM is positive definite and symmetric is of particular interest because of the special structure of the problems, and also because they appear in many practical applications.In this paper, we study the computational growth of each of the two methods to solve the LCP, (q, M), whenM is positive definite and symmetric and obtain similar results.This research is partially supported by Air Force Office of Scientific Research, Air Force Number AFOSR-78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation thereon.     

Positive definiteness in the numerical solution of Riccati differential equations

Summary. In this work we address the issue of integrating symmetric Riccati and Lyapunov matrix differential equations. In many cases -- typical in applications -- the solutions are positive definite matrices. Our goal is to study when and how this property is maintained for a numerically computed solution. There are two classes of solution methods: direct and indirect algorithms. The first class consists of the schemes resulting from direct discretization of the equations. The second class consists of algorithms which recover the solution by exploiting some special formulae that these solutions are known to satisfy. We show first that using a direct algorithm -- a one-step scheme or a strictly stable multistep scheme (explicit or implicit) -- limits the order of the numerical method to one if we want to guarantee that the computed solution stays positive definite. Then we show two ways to obtain positive definite higher order approximations by using indirect algorithms. The first is to apply a symplectic integrator to an associated Hamiltonian system. The other uses stepwise linearization. Received April 21, 1993     

An efficient algorithm for maximum entropy extension of block-circulant covariance matrices

This paper deals with maximum entropy completion of partially specified block-circulant matrices. Since positive definite symmetric circulants happen to be covariance matrices of stationary periodic processes, in particular of stationary reciprocal processes, this problem has applications in signal processing, in particular to image modeling. In fact it is strictly related to maximum likelihood estimation of bilateral AR-type representations of acausal signals subject to certain conditional independence constraints. The maximum entropy completion problem for block-circulant matrices has recently been solved by the authors, although leaving open the problem of an efficient computation of the solution. In this paper, we provide an efficient algorithm for computing its solution which compares very favorably with existing algorithms designed for positive definite matrix extension problems. The proposed algorithm benefits from the analysis of the relationship between our problem and the band-extension problem for block-Toeplitz matrices also developed in this paper.     

关于线性系统解的对称性算法的强稳定性的探索

关于线性方程解的算法方面,本文在对称非奇异矩阵类和对称正定矩阵类上给出了强稳定性算法.     

A note on a quadratic formulation for linear complementarity problems

In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known.     

Proximal point algorithm with Schur decomposition on the cone of symmetric semidefinite positive matrices

In this work, we propose a proximal algorithm for unconstrained optimization on the cone of symmetric semidefinite positive matrices. It appears to be the first in the proximal class on the set of methods that convert a Symmetric Definite Positive Optimization in Nonlinear Optimization. It replaces the main iteration of the conceptual proximal point algorithm by a sequence of nonlinear programming problems on the cone of diagonal definite positive matrices that has the structure of the positive orthant of the Euclidian vector space. We are motivated by results of the classical proximal algorithm extended to Riemannian manifolds with nonpositive sectional curvature. An important example of such a manifold is the space of symmetric definite positive matrices, where the metrics is given by the Hessian of the standard barrier function −lndet(X). Observing the obvious fact that proximal algorithms do not depend on the geodesics, we apply those ideas to develop a proximal point algorithm for convex functions in this Riemannian metric.     

A matrix-splitting method for symmetric affine second-order cone complementarity problems

The affine second-order cone complementarity problem (SOCCP) is a wide class of problems that contains the linear complementarity problem (LCP) as a special case. The purpose of this paper is to propose an iterative method for the symmetric affine SOCCP that is based on the idea of matrix splitting. Matrix-splitting methods have originally been developed for the solution of the system of linear equations and have subsequently been extended to the LCP and the affine variational inequality problem. In this paper, we first give conditions under which the matrix-splitting method converges to a solution of the affine SOCCP. We then present, as a particular realization of the matrix-splitting method, the block successive overrelaxation (SOR) method for the affine SOCCP involving a positive definite matrix, and propose an efficient method for solving subproblems. Finally, we report some numerical results with the proposed algorithm, where promising results are obtained especially for problems with sparse matrices.     

Basic-set algorithm for a generalized linear complementarity problem

In this paper, the authors develop a new direct method for the solution of a BLCP, that is, a linear complementarity problem (LCP) with upper bounds, when its matrix is a symmetric or an unsymmetricP-matrix. The convergence of the algorithm is established by extending Murty's principal pivoting method to an LCP which is equivalent to the BLCP. Computational experience with large-scale BLCPs shows that the basic-set method can solve efficiently large-scale BLCPs with a symmetric or an unsymmetricP-matrix.     

On reduced convex QP formulations of monotone LCPs

Techniques for transforming convex quadratic programs (QPs) into monotone linear complementarity problems (LCPs) and vice versa are well known. We describe a class of LCPs for which a reduced QP formulation – one that has fewer constraints than the “standard” QP formulation – is available. We mention several instances of this class, including the known case in which the coefficient matrix in the LCP is symmetric. Received: May 2000 / Accepted: February 22, 2001?Published online April 12, 2001     

On finite termination of an iterative method for linear complementarity problems

Based on a well-known reformulation of the linear complementarity problem (LCP) as a nondifferentiable system of nonlinear equations, a Newton-type method will be described for the solution of LCPs. Under certain assumptions, it will be shown that this method has a finite termination property, i.e., if an iterate is sufficiently close to a solution of LCP, the method finds this solution in one step. This result will be applied to a recently proposed algorithm by Harker and Pang in order to prove that their algorithm also has the finite termination property.     

Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

A sequential LCP method for bilevel linear programming

In this paper, we discuss an SLCP algorithm for the solution of Bilevel Linear Programs (BLP) which consists of solving a sequence of Linear Complementarity Problems (LCP) by using a hybrid enumerative method. This latter algorithm incorporates a number of procedures that reduce substantially the search for a solution of the LCP or for showing that the LCP has no solution. Computational experience with the SLCP algorithm shows that it performs quite well for the solution of small- and medium-scale BLPs with sparse structure. Furthermore, the algorithm is shown to be more efficient than a branch-and-bound method for solving the same problems.     

An iterative scheme for variational inequalities

In this paper we introduce and study a general iterative scheme for the numerical solution of finite dimensional variational inequalities. This iterative scheme not only contains, as special cases the projection, linear approximation and relaxation methods but also induces new algorithms. Then, we show that under appropriate assumptions the proposed iterative scheme converges by establishing contraction estimates involving a sequence of norms in Eⁿ induced by symmetric positive definite matrices G_m. Thus, in contrast to the above mentioned methods, this technique allows the possibility of adjusting the norm at each step of the algorithm. This flexibility will generally yield convergence under weaker assumptions.     

Some n by dn linear complementarity problems

The purpose of this paper is to study some recent applications of the n by dn LCP solvable by a parametric principal pivoting algorithm (PPP algorithm). Often, the LCPs arising from these applications give rise to large systems of linear equations which can be solved fairly efficiently by exploiting their special structures. First, it is shown that by analyzing the n by dn LCP we could study the problem of solving a system of equations and the (nonlinear) complementarity problem when the function involved is separable. Next, we examine conditions under which the PPP algorithm is applicable to a general LCP, and then present examples of LCPs arising from various applications satisfying the conditions; included among them is the n by dn LCP with a certain $\text{P}$-property. Finally we study a special class of n by dn LCPs which do not possess the $\text{P}$-property but to which the PPP algorithm is still applicable; a major application of this class of problems is a certain economic spatial equilibrium model with piecewise linear prices.     

关于实方阵的几个问题

本文讨论如下内容：１．把有关对称正定（半正定）的一些性质推广到广义正定（半正定）。２．给定ｘ∈Ｒｍ×ｍ，∧为对角阵，求ＡＸ＝ｘ∧在对称半正定矩阵类中解存在的充要条件及一般形式，并讨论了对任意给定的对称正定（半正定）矩阵Ａ，在上述解的集合中求得Ａ，使得     

Computing the matrix geometric mean: Riemannian versus Euclidean conditioning,implementation techniques,and a Riemannian BFGS method

This paper addresses the problem of computing the Riemannian center of mass of a collection of symmetric positive definite matrices. We show in detail that the condition number of the Riemannian Hessian of the underlying optimization problem is never very ill conditioned in practice, which explains why the Riemannian steepest descent approach has been observed to perform well. We also show theoretically and empirically that this property is not shared by the Euclidean Hessian. We then present a limited‐memory Riemannian BFGS method to handle this computational task. We also provide methods to produce efficient numerical representations of geometric objects that are required for Riemannian optimization methods on the manifold of symmetric positive definite matrices. Through empirical results and a computational complexity analysis, we demonstrate the robust behavior of the limited‐memory Riemannian BFGS method and the efficiency of our implementation when compared to state‐of‐the‐art algorithms.     

特殊五对角与七对角对称正定矩阵的一类反问题

针对线性代数方程组Ax=b,利用矩阵分解的思想,构造一类特殊五对角与七对角对称正定阵的矩阵分解,获得这类矩阵反问题解存在的充要条件和通解表达式.最后,给出了具体算法与数值算例.     

Multilevel approaches for FSAI preconditioning

Factorized sparse approximate inverse (FSAI) preconditioners are robust algorithms for symmetric positive matrices, which are particularly attractive in a parallel computational environment because of their inherent and almost perfect scalability. Their parallel degree is even redundant with respect to the actual capabilities of the current computational architectures. In this work, we present two new approaches for FSAI preconditioners with the aim of improving the algorithm effectiveness by adding some sequentiality to the native formulation. The first one, denoted as block tridiagonal FSAI, is based on a block tridiagonal factorization strategy, whereas the second one, domain decomposition FSAI, is built by reordering the matrix graph according to a multilevel k‐way partitioning method followed by a bandwidth minimization algorithm. We test these preconditioners by solving a set of symmetric positive definite problems arising from different engineering applications. The results are evaluated in terms of performance, scalability, and robustness, showing that both strategies lead to faster convergent schemes regarding the number of iterations and total computational time in comparison with the native FSAI with no significant loss in the algorithmic parallel degree.