Column sufficient tensors and tensor complementarity problems

Stimulated by the study of sufficient matrices in linear complementarity problems, we study column sufficient tensors and tensor complementarity problems. Column sufficient tensors constitute a wide range of tensors that include positive semi-definite tensors as special cases. The inheritance property and invariant property of column sufficient tensors are presented. Then, various spectral properties of symmetric column sufficient tensors are given. It is proved that all H-eigenvalues of an even-order symmetric column sufficient tensor are nonnegative, and all its Z-eigenvalues are nonnegative even in the odd order case. After that, a new subclass of column sufficient tensors and the handicap of tensors are defined. We prove that a tensor belongs to the subclass if and only if its handicap is a finite number. Moreover, several optimization models that are equivalent with the handicap of tensors are presented. Finally, as an application of column sufficient tensors, several results on tensor complementarity problems are established.     

Solvability of monotone tensor complementarity problems

The tensor complementarity problem is a special instance in the class of nonlinear complementarity problems, which has many applications in multi-person noncooperative games, hypergraph clustering problems and traffic equilibrium problems. Two most important research issues are how to identify the solvability and how to solve such a problem via analyzing the structure of the involved tensor. In this paper, based on the concept of monotone mappings, we introduce a new class of structured tensors ...     

Strictly semi-positive tensors and the boundedness of tensor complementarity problems

In this paper, we present the boundedness of solution set of tensor complementarity problem defined by a strictly semi-positive tensor. For strictly semi-positive tensor, we prove that all \(H^+(Z^+)\)-eigenvalues of each principal sub-tensor are positive. We define two new constants associated with \(H^+(Z^+)\)-eigenvalues of a strictly semi-positive tensor. With the help of these two constants, we establish upper bounds of an important quantity whose positivity is a necessary and sufficient condition for a general tensor to be a strictly semi-positive tensor. The monotonicity and boundedness of such a quantity are established too.     

随机R0张量互补问题的投影Levenberg-Marquardt方法

本文考虑一类离散型随机$R_0$张量互补问题,利用Fischer-Burmeister函数将问题转化为约束优化问题,并用投影Levenberg-Marquardt方法对其进行了求解。在一般的条件下得到了该方法的全局收敛性,相关的数值实验表明了该方法的有效性。     

A multilevel iterative method for symmetric,positive definite linear complementarity problems

A fast iterative method for the solution of large, sparse, symmetric, positive definite linear complementarity problems is presented. The iterations reduce to linear iterations in a neighborhood of the solution if the problem is nondegenerate. The variational setting of the method guarantees global convergence.As an application, we consider a discretization of a Dirichlet obstacle problem by triangular linear finite elements. In contrast to usual iterative methods, the observed rate of convergence does not deteriorate with step size.The results presented here were announced at the XI. International Symposium on Mathematical Programming, Bonn, August 1982.     

A modified modulus method for symmetric positive‐definite linear complementarity problems

By reformulating the linear complementarity problem into a new equivalent fixed‐point equation, we deduce a modified modulus method, which is a generalization of the classical one. Convergence for this new method and the optima of the parameter involved are analyzed. Then, an inexact iteration process for this new method is presented, which adopts some kind of iterative methods for determining an approximate solution to each system of linear equations involved in the outer iteration. Global convergence for this inexact modulus method and two specific implementations for the inner iterations are discussed. Numerical results show that our new methods are more efficient than the classical one under suitable conditions. Copyright © 2008 John Wiley & Sons, Ltd.     

Coxeter图的正定性

用线性代数的方法证明了李代数中正定的Coxeter图仅是Aι，Bι，Dι，Eι，F4和Gz六种类型。     

Positive definite metric spaces

Magnitude is a numerical invariant of finite metric spaces, recently introduced by Leinster, which is analogous in precise senses to the cardinality of finite sets or the Euler characteristic of topological spaces. It has been extended to infinite metric spaces in several a priori distinct ways. This paper develops the theory of a class of metric spaces, positive definite metric spaces, for which magnitude is more tractable than in general. Positive definiteness is a generalization of the classical property of negative type for a metric space, which is known to hold for many interesting classes of spaces. It is proved that all the proposed definitions of magnitude coincide for compact positive definite metric spaces and further results are proved about the behavior of magnitude as a function of such spaces. Finally, some facts about the magnitude of compact subsets of $\ell _p^n$ for $p \le 2$ are proved, generalizing results of Leinster for $p=1,2$ using properties of these spaces which are somewhat stronger than positive definiteness.     

Positive definite distributions and normed spaces

We answer a question of Alex Koldobsky. We show that for each −∞<p<2 and each n?3−p there is a normed space X of dimension n which embeds in Ls if and only if −n<s?p.     

Estimations on upper and lower bounds of solutions to a class of tensor complementarity problems

We introduce a class of structured tensors, called generalized row strictly diagonally dominant tensors, and discuss some relationships between it and several classes of structured tensors, including nonnegative tensors, Btensors, and strictly copositive tensors. In particular, we give estimations on upper and lower bounds of solutions to the tensor complementarity problem (TCP) when the involved tensor is a generalized row strictly diagonally dominant tensor with all positive diagonal entries. The main advantage of the results obtained in this paper is that both bounds we obtained depend only on the tensor and constant vector involved in the TCP;and hence, they are very easy to calculate.     

Solution structures of tensor complementarity problem

We introduce two new types of tensors called the strictly semimonotone tensor and the range column sufficient tensor and explore their structure properties. Based on the obtained results, we make a characterization to the solution of tensor complementarity problem.     

Positive definite probability densities and probability distributions

In the first short survey article [H.-J. Rossberg,Wiss. Z. Karl Marx Univ.,37, 366–374 (1988)] the author indicated that positive definite probability densities deserve attention and that the investigation of this class leads to serious new mathematical problems. Later [R. Riedel and H.-J. Rossberg,Metrika, (submitted for publication)] it turned out that it is worthwhile to consider an even larger class of distribution functions, namely those having characteristic function f≥0; they were first briefly considered in [P. Lévy,C. R. Acad. Sci.,265, 249–252 (1967)]. We survey the basic ideas and the present state of the developing new theory; moreover, we formulate open problems. Some new results are proved. For the sake of brevity we do not enter into a discussion of continuation problems and limit theorems; for these subjects see [H.-J. Rossberg,Appendix to Gnedenko B. W., Einführung in die Wahrscheinlichkeitstheorie, 9th ed., Akademie-Verlag, Berlin (1991)], [H.-J. Rossberg,Math. Nachr.,141, 227–232 (1989)], and [H.-J. Rossberg,Lect. Notes Math.,1412, 296–308 (1989)]. Proceedings of the Seminar on Stability Problems for Stochastic Models, Moscow, 1993.     

Positive definite functions and stable random vectors

We say that a random vector X = (X ₁, …, X _n ) in ℝ ⁿ is an n-dimensional version of a random variable Y if, for any a ∈ ℝ ⁿ , the random variables Σa _i X _i and γ(a)Y are identically distributed, where γ: ℝ ⁿ → [0,∞) is called the standard of X. An old problem is to characterize those functions γ that can appear as the standard of an n-dimensional version. In this paper, we prove the conjecture of Lisitsky that every standard must be the norm of a space that embeds in L ₀. This result is almost optimal, as the norm of any finite-dimensional subspace of L _p with p ∈ (0, 2] is the standard of an n-dimensional version (p-stable random vector) by the classical result of P. Lèvy. An equivalent formulation is that if a function of the form f(‖ · ‖ _K ) is positive definite on ℝ ⁿ , where K is an origin symmetric star body in ℝ ⁿ and f: ℝ → ℝ is an even continuous function, then either the space (ℝ ⁿ , ‖·‖ _K ) embeds in L ₀ or f is a constant function. Combined with known facts about embedding in L ₀, this result leads to several generalizations of the solution of Schoenberg’s problem on positive definite functions.     

Positive definite Hermitian matrices and reproducing kernels

Some quadratic identities associated with positive definite Hermitian matrices are derived by use of the theory of reproducing kernels. For example, the following identity is obtained: Let{A_j}^m_j=1 be N × N positive definite Hermitian matrices. Then, for any complex vector x ∈ $\text{C}$^N, we have the identity

$\text{x}{}^1\text{∑}\text{j=}\text{1}\text{m}\text{A}{}^{-1}{}_{\mathrm{j}}{}^{-1}\text{x = min}\text{∑}\text{j=}\text{1}\text{m}\text{x}{}^1{}_{\mathrm{j}}\text{A}{}_{\mathrm{j}}\text{x}{}_{\mathrm{j}}$

. The minimum is taken here over all the decompositions x =∑^m_j=1x_j. This identity gives, in a sense, a precise converse for an inequality which was derived by T. Ando. Moreover, this paper shows that the sum of two reproducing kernels is naturally related to the harmonic-arithmetic-mean inequality for matrices and also that the geometric-arithmetic-mean inequality for matrices can be naturally interpreted in terms of tensor-product spaces.     

Tensor eigenvalue complementarity problems

This paper studies tensor eigenvalue complementarity problems. Basic properties of standard and complementarity tensor eigenvalues are discussed. We formulate tensor eigenvalue complementarity problems as constrained polynomial optimization. When one tensor is strictly copositive, the complementarity eigenvalues can be computed by solving polynomial optimization with normalization by strict copositivity. When no tensor is strictly copositive, we formulate the tensor eigenvalue complementarity problem equivalently as polynomial optimization by a randomization process. The complementarity eigenvalues can be computed sequentially. The formulated polynomial optimization can be solved by Lasserre’s hierarchy of semidefinite relaxations. We show that it has finite convergence for generic tensors. Numerical experiments are presented to show the efficiency of proposed methods.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

Quadratic programming problems and related linear complementarity problems

This paper investigates the general quadratic programming problem, i.e., the problem of finding the minimum of a quadratic function subject to linear constraints. In the case where, over the set of feasible points, the objective function is bounded from below, this problem can be solved by the minimization of a linear function, subject to the solution set of a linear complementarity problem, representing the Kuhn-Tucker conditions of the quadratic problem.To detect in the quadratic problem the unboundedness from below of the objective function, necessary and sufficient conditions are derived. It is shown that, when these conditions are applied, the general quadratic programming problem becomes equivalent to the investigation of an appropriately formulated linear complementarity problem.This research was supported by the Hungarian Research Foundation, Grant No. OTKA/1044.