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 ℒ ⁿ .     

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.     

Construction of a linear Pfaff system of Fuchsian type with algebraic manifold of singularities

We present a constructive proof of the existence of a two-dimensional completely integrable Fuchsian Pfaff system on CP ⁿ with four singular surfaces forming a pencil, with 2-step solvable monodromy group, and with fundamental solution matrix realizing a given homomorphism.     

Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix

The plain Newton-min algorithm to solve the linear complementarity problem (LCP for short) can be viewed as a semismooth Newton algorithm without globalization technique to solve the system of piecewise linear equations min(x, Mx + q) = 0, which is equivalent to the LCP. When M is an M-matrix of order n, the algorithm is known to converge in at most n iterations. We show in this paper that this result no longer holds when M is a P-matrix of order ≥ 3, since then the algorithm may cycle. P-matrices are interesting since they are those ensuring the existence and uniqueness of the solution to the LCP for an arbitrary q. Incidentally, convergence occurs for a P-matrix of order 1 or 2.     

The distance spectrum of the path Pn and The First Distance Eigenvector of Connected Graphs

Forumulas are given for all of the eigenvalues and eigenvectors of the distance matrix of the path P_n on n vertices. It is shown that P_n has the maximum distance spectral radius among all connected graphs of order n, and an ordering property of the entries of the Perron-Frobenius eigenvector is presented.     

Closed geodesics in compact nilmanifolds

We study the density of closed geodesics property on 2-step nilmanifolds Γ\N, where N is a simply connected 2-step nilpotent Lie group with a left invariant Riemannian metric and Lie algebra ?, and Γ is a lattice in N. We show the density of closedgeodesics property holds for quotients of singular, simply connected, 2-step nilpotent Lie groups N which are constructed using irreducible representations of the compact Lie group SU(2). Received: 8 November 2000 / Revised version: 9 April 2001     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

A-priori upper bounds for the set covering problem

A matrix M∈R^n×n is said to be a column sufficient matrix if the solution set of LCP(M,q) is convex for every q∈Rⁿ. In a recent article, Qin et al. (Optim. Lett. 3:265–276, 2009) studied the concept of column sufficiency property in Euclidean Jordan algebras. In this paper, we make a further study of this concept and prove numerous results relating column sufficiency with the Z and Lypaunov-like properties. We also study this property for some special linear transformations.     

On a class of order pick strategies in paternosters

We study the travel time needed to pick n items in a paternoster, operating under the m-step strategy. This means that the paternoster chooses the shortest route among the ones that change direction at most once, and after collecting at most m items. For random pick positions, we find the distribution and moments of the travel time, provided n>2m. It appears that, already for m=2, the m-step strategy is very close to optimal, and better than the nearest item heuristic.     

A Characterization of Positive Matrices

It is shown that an n-by-n matrix has a strictly dominant positive eigenvalue with positive left and right eigenvectors and this property is inherited by principle submatrices if and only if it is entry-wise positive. This limits the extent to which attractive Perron-Frobenius properities may be generalized outside the positive matrices.Mathematics Subject Classification (2000): 15A48     

A continuation method for linear complementarity problems with P 0 matrix

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.     

Accelerated conjugate direction methods for unconstrained optimization

A family of accelerated conjugate direction methods, corresponding to the Broyden family of quasi-Newton methods, is described. It is shown thatall members of the family generate the same sequence of points approximating the optimum and the same sequence of search directions, provided only that each direction vector is normalized before the stepsize to be taken in that direction is determined.With minimal restrictions on how the stepsize is determined (sufficient only for convergence), the accelerated methods applied to the optimization of a function ofn variables are shown to have an (n+1)-step quadratic rate of convergence. Furthermore, the information needed to generate an accelerating step can be stored in a singlen-vector, rather than the usualn×n symmetric matrix, without changing the theoretical order of convergence.The relationships between this family of methods and existing conjugate direction methods are discussed, and numerical experience with two members of the family is presented.This research was sponsored by the United States Army under Contract No. DAAG29-75-C-0024.The author gratefully acknowledges the valuable assistance of Julia H. Gray, of the Mathematics Research Center, University of Wisconsin, Madison, who painstakingly programmed these methods and obtained the computational results.     

A quasi-Newton method can be obtained from a method of conjugate directions

In a recent paper McCormick and Ritter consider two classes of algorithms, namely methods of conjugate directions and quasi-Newton methods, for the problem of minimizing a function ofn variablesF(x). They show that the former methods possess ann-step superlinear rate of convergence while the latter are every step superlinear and therefore inherently superior. In this paper a simple and computationally inexpensive modification of a method of conjugate directions is presented. It is shown that the modified method is a quasi-Newton method and is thus every step superlinearly convergent. It is also shown that under certain assumptions on the second derivatives ofF the rate of convergence of the modified method isn-step quadratic.This work was supported by the National Research Council of Canada under Research Grant A8189.     

Perturbed Markov Chains with Damping Component

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter ε. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems for n-step transition probabilities, as well as ergodic theorems in triangular array mode.

     

Reflecting the pascal matrix about its main antidiagonal

Let B denote either of two varieties of order n Pascal matrix, i.e., one whose entries are the binomial coefficients. Let B_R denote the reflection of B about its main antidiagonal. The matrix B is always invertible modulo n; our main result asserts that B^-1 ≡ B^R mod n if and only if n is prime. In the course of motivating this result we encounter and highlight some of the difficulties with the matrix exponential under modular arithmetic. We then use our main result to extend the "Fibonacci diagonal" property of Pascal matrices.     

Weighted Positivity of Second Order Elliptic Systems

Integral inequalities that concern the weighted positivity of a differential operator have important applications in qualitative theory of elliptic boundary value problems. Despite the power of these inequalities, however, it is far from clear which operators have this property. In this paper, we study weighted integral inequalities for general second order elliptic systems in ℝ ⁿ (n ≥ 3) and prove that, with a weight, smooth and positive homogeneous of order 2–n, the system is weighted positive only if the weight is the fundamental matrix of the system, possibly multiplied by a semi-positive definite constant matrix.      

A power penalty method for linear complementarity problems

We propose a power penalty approach to a linear complementarity problem (LCP) in Rⁿ based on approximating the LCP by a nonlinear equation. We prove that the solution to this equation converges to that of the LCP at an exponential rate when the penalty parameter tends to infinity.     

Estimates on binomial sums of partition functions

Let p(n) denote the partition function and define where p(0)= 1. We prove that p(n,k) is unimodal and satisfies for fixed n≥ 1 and all 1≤k≤n. This result has an interesting application: the minimal dimension of a faithful module for a k-step nilpotent Lie algebra of dimension n is bounded by p(n,k) and hence by , independently of k. So far only the bound n ^{n −1} was known. We will also prove that for n≥ 1 and . Received: 17 December 1999     

Projection method for unconstrained optimization

A method of conjugate directions, the projection method, for solving unconstrained minimization problems is presented. Under the assumption of uniform strict convexity, the method is shown to converge to the global minimizer of the unconstrained problem and to have an (n – 1)-step superlinear rate of convergence. With a Lipschitz condition on the second derivatives, the rate of convergence is shown to be a modifiedn-step quadratic one.This research was supported in part by the Army Research Office, Contract No. DAHC 19-69-C-0017, and the Office of Naval Research, Contract No. N00014-71-C-0116(NR-047-099).     

n-step mingling inequalities: new facets for the mixed-integer knapsack set

The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi (Math Program 120(2):313–346, 2009) are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamtürk and Günlük (Math Program 123(2):315–338, 2010) are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n?=?2, we extend the results of Atamtürk and Günlük on facet-defining properties of 2-step mingling inequalities. For n ≥ 3, we present new facets for the mixed integer knapsack set. As a special case we also derive conditions under which the n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets.