On semi-infinite systems of linear inequalities

The ordered fieldR(M) consists of the realsR with a transcendentalM adjoined, which is larger than any realr ∈R. Given any semi-infinite matrix (s.i.m.) interpreted as linear inequalities:u ^tP_i≧c _i, ∀ _i ∈I, an arbitrary index set, it is also shown that the following are equivalent. (1) For every finiteJ ⊆I the systemu ^tP_i≧c _i,i ∈J is consistent, and (2) the s.i.m. has a solutionu ∈R(M) ⁿ. Some consequences for “duality gaps” are also given. These results were obtained as part of the activities of the Management Science Research Group and School of Urban and Public Affairs, Carnegie-Mellon University.     

On relaxation methods for systems of linear inequalities

In their classical papers Agmon and Motzkin and Schoenberg introduced a relaxation method to find a feasible solution for a system of linear inequalities. So far the method was believed to require infinitely many iterations on some problem instances since it could (depending on the dimension of the set of feasible soltions) converge asymptotically to a feasible solution, if one exists. Hence it could not be used to determine infeasibility.Using two lemma's basic to Khachian's polynomially bounded algorithm we can show that the relaxation method is finite in all cases and thus can handle infeasible systems as well. In spite of more refined stopping criteria the worst case behaviour of the relaxation method is not polynomially bounded as examplified by a class of problems constructed here.     

On nonnegative solutions of random systems of linear inequalities

The set of nonnegative solutions of a system of linear equations or inequalities is a convex polyhedron. If the coefficients of the system are chosen at random, the number of vertices of this polyhedron is a random variable. Its expected value, dependent on the probability distribution of the coefficients, which are assumed to be nonnegative throughout, is investigated, and a distribution-independent upper bound for this expected value is established.     

Irreducibly inconsistent systems of linear inequalities

Irreducibly inconsistent systems of linear inequalities are considered from the point of view of applying simplex-like methods for investigation.We give necessary and sufficient conditions, for a system to be irreducibly inconsistent, which can be found by applying a simplex algorithm. Next we consider general inconsistent systems. The simplex method can be used to identify irreducibly inconsistent subsystem. Such subsystems can give structural insight in the inconsistency and are used in trying to make the overall system consistent. This can be done in an easy way e.g. by right-hand side manipulations. Finally the problem of finding a ‘cheapest’ way of doing this can be formulated and solved as an extended linear program.     

On inequalities of Lyapunov for linear Hamiltonian systems on time scales

In this paper, we establish several new Lyapunov type inequalities for linear Hamiltonian systems on an arbitrary time scale T when the end-points are not necessarily usual zeroes, but rather, generalized zeroes, which generalize and improve all related existing ones including the continuous and discrete cases.     

Weak type inequalities for vector-valued martingales

We obtain weak versions of the Burkholder–Davis–Gundy inequalities for vector-valued martingales by employing the operator-valued martingale transform technique. These inequalities are closely related to the geometric properties of the underlying Banach space.     

On the non-polynomiality of the relaxation method for systems of linear inequalities

A class of linear programs is given in which the relaxation method for inequalities, under the same operating rules as Khacian's method, is not polynomial in the length of the input. This result holds for any value of the relaxation parameter.This research was supported in part by the D.G.E.S. (Quebec), the N.S.E.R.C. of Canada under grant A 4152, and the S.S.H.R.C. of Canada.     

Flexible solutions to systems of linear inequalities

In this paper we present two methods for calculating solutions to a system of linear inequalities which have certain prescribed distance properties to the constraints (referred to as flexibility properties). The first method (based on the calculation of the centre of an inscribed sphere, which is a well-known problem in linear programming) allows changes in the solution in any direction over a certain distance without becoming infeasible. The second method consists in the calculation of a solution with flexibility properties with respect to a prescribed coordinate system. It comprises an iterative procedure inside the area of feasible solutions using simple arithmetic operations. The major part of the paper will be devoted to the second method, since it is new and has attractive properties. Both methods are particularly applicable to the analysis of linear programming models with uncertain and inaccurate constraint parameters and in cases where operational adjustments are desired.     

Some preconditioners for systems of linear inequalities

We show that a combination of two simple preprocessing steps would generally improve the conditioning of a homogeneous system of linear inequalities. Our approach is based on a comparison among three different but related notions of conditioning for linear inequalities.     

On a class of discontinuous vector-valued functions and the associated quasi-variational inequalities

We study in detail a class of discontinuous vector-valued functions defined on a closed convex subset of Rn, which was introduced by B. Ricceri [7] and which is very useful in the theory of variational inequalities. The results are used to give a new proof for the existence theorem due to P. Cubiotti [3]. The proof allows us to have a better understanding of quasi-variational inequalities associated with the abovementioned class of functions.     

Fuzzification of linear systems of equalities and inequalities

Translated from Aktual'nye Voprosy Prikladnoi Matematiki, pp. 73–80, 1989.     

Iterative solution of inconsistent systems of linear inequalities

In 1980 S.P. Han proposed a finitely terminating (in exact arithmetic) algorithm for solving an inconsistent system of linear inequalities in a least squares sense. This algorithm uses a singular value decomposition of a submatrix of the problem matrix on each iteration, making it impractical for all but only smaller problems. In this paper we show that a modification of Han's algorithm allows us to introduce an iterative approximation to the singular value decomposition solution. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A discretization method for systems of linear inequalities

We investigate a method for approximating a convex domainCR ⁿ described by a (possibly infinite) set of linear inequalities. In contrast to other methods, the approximating domains (polyhedrons) lie insideC. We discuss applications to semi-infinite programming and present numerical examples.The paper was written at the Institut für Angewandte Mathematik, Universität Hamburg, Hamburg, West Germany. The author thanks Prof. U. Eckhardt, Dr. K. Roleff, and Prof. B. Werner for helpful discussions.     

Projecting systems of linear inequalities with binary variables

We investigate methods for projecting out 0–1 variables from a system of linear inequalities. After reviewing some special cases like monotone polyhedra and the satisfiability problem, we examine why Fourier elimination cannot be applied to the general case. Finally, we give a procedure based on disjunctive programming for solving the general case. We also discuss a simpler procedure applicable only under certain conditions.     

Riccati differential inequalities and dichotomies for linear systems

A general notion of dichotomy for linear differential systems is investigated. It is well known that a system x′=A(t)x in which the matrix A(t) is bounded and diagonally dominant by rows or columns has an invariant splitting of its solution space into two subspaces each uniformly asymptotically stable, one for increasing time and the other for decreasing time. Similar results are obtained here where the concept of diagonal dominance is weakened using Riccati inequalities.     

Lyapunov inequalities and stability for linear Hamiltonian systems

In this paper, we will establish several Lyapunov inequalities for linear Hamiltonian systems, which unite and generalize the most known ones. For planar linear Hamiltonian systems, the connection between Lyapunov inequalities and estimates of eigenvalues of stationary Dirac operators will be given, and some optimal stability criterion will be proved.