On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

Stable monotone variational inequalities

Variational inequalities associated with monotone operators (possibly nonlinear and multivalued) and convex sets (possibly unbounded) are studied in reflexive Banach spaces. A variety of results are given which relate to a stability concept involving a natural parameter. These include characterizations useful as criteria for stable existence of solutions and also several characterizations of surjectivity. The monotone complementarity problem is covered as a special case, and the results are sharpened for linear monotone complementarity and for generalized linear programming.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 at the University of Wisconsin - Madison and by the National Science Foundation under Grant No. DMS-8405179 at the University of Illinois at Urbana-Champaign.     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

Morita equivalence of quasi-primal algebras and sheaves

In this paper, we show that two quasi-primal algebras are Morita equivalent if and only if their inverse semigroups of inner automorphisms are isomorphic, and if they have the same one-element subalgebras. The proof of this statement uses the representation theory of algebras by sections in sheaves.Presented by H. P. Gumm.     

Locally finitely presented categories of sheaves

Let A be a locally finitely presented Grothendieck category. It is shown that a class of localizations of A in the sense of Bousfield is again locally finitely presented. The criterion is applied to torsion-free classes in A, sheaves and separated presheaves on a generalized ringed space, and representations of partially ordered sets.     

Locally strong endomorphisms of paths

We determine the number of locally strong endomorphisms of directed and undirected paths—direction here is in the sense of a bipartite graph from one partition set to the other. This is done by the investigation of congruence classes, leading to the concept of a complete folding, which is used to characterize locally strong endomorphisms of paths. A congruence belongs to a locally strong endomorphism if and only if the number l of congruence classes divides the length of the original path and the points of the path are folded completely into the l classes, starting from 0 to l and then back to 0, then again back to l and so on. It turns out that for paths locally strong endomorphisms form a monoid if and only if the length of the path is prime or equal to 4 in the undirected case and in the directed case also if the length is 8. Finally some algebraic properties of these monoids are described.     

General recurrence and ladder relations of hypergeometric-type functions

A method for the explicit construction of general linear sum rules involving hypergeometric-type functions and their derivatives of any order is developed. This method only requires the knowledge of the coefficients of the differential equation that they satisfy, namely the hypergeometric-type differential equation. Special attention is paid to the differential-recurrence or ladder relations and to the fundamental three-term recurrence formulas. Most recurrence and ladder relations published in the literature for numerous special functions including the classical orthogonal polynomials, are instances of these sum rules. Moreover, an extension of the method to the generalized hypergeometric-type functions is also described, allowing us to obtain explicit ladder operators for the radial wave functions of multidimensional hydrogen-like atoms, where the varying parameter is the dimensionality.     

Artin-Schelter regular algebras and categories

Motivated by constructions in the representation theory of finite dimensional algebras we generalize the notion of Artin-Schelter regular algebras of dimension n to algebras and categories to include Auslander algebras and a graded analogue for infinite representation type. A generalized Artin-Schelter regular algebra or a category of dimension n is shown to have common properties with the classical Artin-Schelter regular algebras. In particular, when they admit a duality, then they satisfy Serre duality formulas and the -category of nice sets of simple objects of maximal projective dimension n is a finite length Frobenius category.     

Flat covers in abelian and in non-abelian categories

A general existence theorem for flat covers in (e.g., quasi-abelian) locally finitely presented categories is obtained from an additive Ramsey type theorem. In the abelian case, it is shown that flat covers always exist. Applications to categories of separated presheaves or sheaves, localizations of Bousfield type, torsion-free classes of finite type, and categories of filtered objects or complexes, are given.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

Homotopy method for solving variational inequalities with bounded box constraints

In this paper, using the Gabriel–Moré smoothing function of the median function, a smooth homotopy method for solving nonsmooth equation reformulation of bounded box constrained variational inequality problem VIP(l,u,F$l,u,F$) is given. Without any monotonicity condition on the defining map F$F$, for starting point chosen almost everywhere in Rⁿ$R^n$, existence and convergence of the homotopy pathway are proven. Nevertheless, it is also proven that, if the starting point is chosen to be an interior point of the box, the proposed homotopy method can also serve as an interior point method.     

Ideals,radicals, and structure of additive categories

Simple and semisimple additive categories are studied. We prove, for example, that an artinian additive category is (semi)simple iff it is Morita equivalent to a division ring(oid). Semiprimitive additive categories (that is, those with zero radical) are those which admit anoether full, faithful functor into a category of modules over a division ringoid.     

Homotopy method for solving ball-constrained variational inequalities

In this paper, we present a smoothing homotopy method for solving ball-constrained variational inequalities by utilizing a similar Chen-Harker-Kanzow-Smale function to smooth Robinson’s normal equation. Without any monotonicity condition on the defining map F, for the starting point chosen almost everywhere in Rⁿ, the existence and convergence of the homotopy pathway are proven. Numerical experiments illustrate that the method is feasible and effective.     

On cone of nonsymmetric positive semidefinite matrices

In this paper, we analyze and characterize the cone of nonsymmetric positive semidefinite matrices (NS-psd). Firstly, we study basic properties of the geometry of the NS-psd cone and show that it is a hyperbolic but not homogeneous cone. Secondly, we prove that the NS-psd cone is a maximal convex subcone of P₀-matrix cone which is not convex. But the interior of the NS-psd cone is not a maximal convex subcone of P-matrix cone. As the byproducts, some new sufficient and necessary conditions for a nonsymmetric matrix to be positive semidefinite are given. Finally, we present some properties of metric projection onto the NS-psd cone.     

A predictor-corrector smoothing Newton method for symmetric cone complementarity problems

In this paper, we present a predictor-corrector smoothing Newton method for solving nonlinear symmetric cone complementarity problems (SCCP) based on the symmetrically perturbed smoothing function. Under a mild assumption, the solution set of the problem concerned is just nonempty, we show that the proposed algorithm is globally and locally quadratic convergent. Also, the algorithm finds a maximally complementary solution to the SCCP. Numerical results for second order cone complementarity problems (SOCCP), a special case of SCCP, show that the proposed algorithm is effective.     

A family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations

In this paper, we propose a family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations. They come from two modified conjugate gradient methods [W.Y. Cheng, A two term PRP based descent Method, Numer. Funct. Anal. Optim. 28 (2007) 1217–1230; L. Zhang, W.J. Zhou, D.H. Li, A descent modified Polak–Ribiére–Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal. 26 (2006) 629–640] recently proposed for unconstrained optimization problems. Under appropriate conditions, the global convergence of the proposed method is established. Preliminary numerical results show that the proposed method is promising.     

Laplacian energy of a graph

Let G be a graph with n vertices and m edges. Let λ₁, λ₂, … , λ_n be the eigenvalues of the adjacency matrix of G, and let μ₁, μ₂, … , μ_n be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences.