Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

This note studies _A , a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A∈ℝ ^m×n , and (A), a variant of another condition number due to Ye [17] that also arises in complexity analyses of linear programming problems. We provide a new characterization of _A and relate _A and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln _A )=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between _A and (A), we show that the same bound holds for E(ln(A)). Received: September 1998 / Accepted: September 2000?Published online January 17, 2001     

Probabilistic Analysis of Condition Numbers for Linear Programming

In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is O(log n) otherwise. A similar bound applies for the log of the condition number C _R(A) introduced by Renegar (Ref. 2).     

On Representations Associated with Completely n-Positive Linear Maps on Pro-C^＊-Algebras

It is shown that an n × n matrix of continuous linear maps from a pro-C^＊-algebra A to L（H）, which verifies the condition of complete positivity, is of the form [V^＊TijФ（·）V]^n i,where Ф is a representation of A on a Hilbert space K, V is a bounded linear operator from H to K, and j=1,[Tij]^n i,j=1 is a positive element in the C^＊-algebra of all n×n matrices over the commutant of Ф（A） in L（K）. This generalizes a result of C. Y.Suen in Proc. Amer. Math. Soc., 112（3）, 1991, 709-712. Also, a covariant version of this construction is given.     

On the condition numbers associated with the polar factorization of a matrix

We are interested in the calculation of explicit formulae for the condition numbers of the two factors of the polar decomposition of a full rank real or complex m × n matrix A, where m ≥ n. We use a unified presentation that enables us to compute such condition numbers in the Frobenius norm, in cases where A is a square or a rectangular matrix subjected to real or complex perturbations. We denote by σ₁ (respectively σ _n) the largest (respectively smallest) singular value of A, and by K(A) = σ₁/σ _n the generalized condition number of A. Our main results are that the absolute condition number of the Hermitian polar factor is √2(1 + K(A)²)^1/2/(1 + K(A)) and that the absolute condition number of the unitary factor of a rectangular matrix is 1/σ _n. Copyright © 2000 John Wiley & Sons, Ltd.     

Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

A particular class of preconditioners for the conjugate gradient method and other iterative methods is proposed for the solution of linear systemsA _n,mx=b, whereA _n,m is ann×n positive definite block Toeplitz matrix withm×m Toeplitz blocks. In particular we propose a sparse preconditionerP _n,m such that the condition number of the preconditioned matrix turns out to be less than a suitable constant independent of bothn andm, even if the condition number ofA _n,m tends to . This leads to iterative methods which require a number of steps independent ofm andn in order to reduce the error by a given factor.     

Down-Up Algebras From Trees

It is shown that the global dimension of any n-ary down-up algebra A _n  = A(n,α, β,γ) is less than or equal to n + 2, and when γ _i  = 0 for all i (A _n is graded by total degree in the generators), then the global dimension of A _n is n + 2. Furthermore, a sufficient condition for A _n to be prime is given; when γ _i  = 0 for all i this condition is also necessary. An example is given to show that the condition is not always necessary.     

A weighted estimate for the square function on the unit ball in ℂ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We show that the Luzin area integral or the square function on the unit ball of ℂ ⁿ , regarded as an operator in the weighted space L ²(w) has a linear bound in terms of the invariant A ₂ characteristic of the weight. We show a dimension-free estimate for the “area-integral” associated with the weighted L ²(w) norm of the square function. We prove the equivalence of the classical and the invariant A ₂ classes.     

Domains of attraction of nonnormal operator-stable laws

A sequence of independent, identically distributed random vectors X₁, X₂, X₃,… is said to belong to the domain of attraction of a random vector Y is there exist linear operators A_n and constant vectors b_n such that A_n(X₁,…, X_n)+b_n converges in distribution to Y. We present a simple, necessary, and sufficient condition for the existence of such A_n, B_n in the case where Y has no normal component.     

Solution of large‐scale weighted least‐squares problems

A sequence of least‐squares problems of the form min_y∥G^1/2(A^T y?h)∥₂, where G is an n×n positive‐definite diagonal weight matrix, and A an m×n (m?n) sparse matrix with some dense columns; has many applications in linear programming, electrical networks, elliptic boundary value problems, and structural analysis. We suggest low‐rank correction preconditioners for such problems, and a mixed solver (a combination of a direct solver and an iterative solver). The numerical results show that our technique for selecting the low‐rank correction matrix is very effective. Copyright © 2002 John Wiley & Sons, Ltd.     

Convergence of the efficient sets

LetA _n,n=1, 2, ... be nonempty subsets of a linear metric spaceE andC _n, n=1, 2, ... convex cones ofE. We consider the efficient sets Min(A _n, C_n) and the aim of this paper is to show that under suitable conditions, the convergence ofA _n andC _n toA andC respectively, implies the convergence of Min(A _n,C _n) to Min(A, C). Several illustrative examples are given which clarify the results.     

Sur la convergence des processus ponctuels

Summary We give a necessary and sufficient condition for the convergence in law of simple point processes on ₊, for Skorokhod topology, in terms of their predictable compensatorsA ⁿ andA. The assumptions are thatA _t() is continuous in (,t) and meets some mild integrability condition. The condition is thatA ⁿ converges weakly toA in a suitable sense.     

Strict Semimonotonicity Property of Linear Transformations on Euclidean Jordan Algebras

Motivated by the equivalence of the strict semimonotonicity property of the matrix A and the uniqueness of the solution to the linear complementarity problem LCP(A,q) for q∈R ₊ ⁿ , we study the strict semimonotonicity (SSM) property of linear transformations on Euclidean Jordan algebras. Specifically, we show that, under the copositive condition, the SSM property is equivalent to the uniqueness of the solution to LCP(L,q) for all q in the symmetric cone K. We give a characterization of the uniqueness of the solution to LCP(L,q) for a Z transformation on the Lorentz cone ℒ₊ ⁿ . We study also a matrix-induced transformation on the Lorentz space ℒ ⁿ .     

Sur l'interpolation des opérateurs maximaux monotones

On the Interpolation of Maximal Monotone Operators. We study here one way to extend to the maximal monotone case the results of linear interpolation, exposed bybalakrishnan in [2]. We obtain a necessary and sufficient condition of convergence for sequences(A ⁿ ) _n of maximal monotone operators on a real Hilbert spaceH.     

On automorphisms of finite Abelian <Emphasis Type="Italic">p</Emphasis>-groups

Let A be a finitely generated abelian group. We describe the automorphism group Aut(A) using the rank of A and its torsion part p-part A _p . For a finite abelian p-group A of type (k ₁, ..., k _n ), simple necessary and sufficient conditions for an n × n-matrix over integers to be associated with an automorphism of A are presented. Then, the automorphism group Aut(A) for a finite p-group A of type (k ₁, k ₂) is analyzed. This work has begin during the visit of the second author to the Faculty of Mathematics and Computer Science, Nicolaus Copernicus University during the period July 31–August 13, 2005. This visit was supported by the Nicolaus Copernicus University and a grant from Cnpq.     

Integrals and Banach spaces for finite order distributions

Let B _c denote the real-valued functions continuous on the extended real line and vanishing at −∞. Let B _r denote the functions that are left continuous, have a right limit at each point and vanish at −∞. Define A _c ⁿ to be the space of tempered distributions that are the nth distributional derivative of a unique function in B _c . Similarly with A _r ⁿ from B _r . A type of integral is defined on distributions in A _c ⁿ and A _r ⁿ . The multipliers are iterated integrals of functions of bounded variation. For each n ∈ ℕ, the spaces A _c ⁿ and A _r ⁿ are Banach spaces, Banach lattices and Banach algebras isometrically isomorphic to B _c and B _r , respectively. Under the ordering in this lattice, if a distribution is integrable then its absolute value is integrable. The dual space is isometrically isomorphic to the functions of bounded variation. The space A _c ¹ is the completion of the L ¹ functions in the Alexiewicz norm. The space A _r ¹ contains all finite signed Borel measures. Many of the usual properties of integrals hold: H?lder inequality, second mean value theorem, continuity in norm, linear change of variables, a convergence theorem.     

Revisit the Lovász Local Lemma

We provide a sufficient condition for showing that the probability of none of the events A ₁, A ₂,...,A _n occurs is positive. This condition explicitly involves the dependency digraph and the probabilities of the A _i's. Some applications are given.     

Feynman’s Operational Calculi: Decomposing Disentanglings

Let X be a Banach space and suppose that A ₁,…,A _n are noncommuting (that is, not necessarily commuting) elements in ℒ(X), the space of bounded linear operators on X. Further, for each i∈{1,…,n}, let μ _i be a continuous probability measure on ℬ([0,1]), the Borel class of [0,1]. Each such n-tuple of operator-measure pairs (A _i ,μ _i ), i=1,…,n, determines an operational calculus or disentangling map T_m1,...,mn{\mathcal{T}}_{\mu_{1},\dots,\mu_{n}} from a commutative Banach algebra \mathbbD(A₁,...,A_n){\mathbb{D}}(A_{1},\dots,A_{n}) of analytic functions, called the disentangling algebra , into the noncommutative Banach algebra ℒ(X). The disentanglings are the central processes of Feynman’s operational calculi.     

Primes in the semigroup of non-negative matrices

A matrix A in the semigroup N _n of non-negative n×nmatrices is prime if A is not monomial and A=BC,B CεN _n implies that either B or C is monomial. One necessary and another sufficient condition are given for a matrix in N _n to be prime. It is proved that every prime in N _n is completely decomposable.     

Semidifferentiable functions and necessary optimality conditions

We consider Lyapunov's equationPA+A ^T P+Q=0, whereQ is symmetric positive definite andA is in controllable companion form. We prove that a necessary and sufficient condition thatA be stable is that the first rowP ₁ of theP-matrix be a stablen–1 coefficient vector. This result is related to the minimum phase property of linear systems and is useful in designing robust controllers.     

On the uniqueness of promotion operators on tensor products of type <Emphasis Type="Italic">A</Emphasis> crystals

The affine Dynkin diagram of type A _n ⁽¹⁾ has a cyclic symmetry. The analogue of this Dynkin diagram automorphism on the level of crystals is called a promotion operator. In this paper we show that the only irreducible type A _n crystals which admit a promotion operator are the highest weight crystals indexed by rectangles. In addition we prove that on the tensor product of two type A _n crystals labeled by rectangles, there is a single connected promotion operator. We conjecture this to be true for an arbitrary number of tensor factors. Our results are in agreement with Kashiwara’s conjecture that all ‘good’ affine crystals are tensor products of Kirillov-Reshetikhin crystals.