A well-known theorem of Rabin yields a dimensional lower bound on the width of complete polynomial proofs of a system of linear algebraic inequalities. In this note we investigate a practically motivated class of systems where the same lower bound can be obtained on the width of almost all (noncomplete) linear proofs. The proof of our result is based on the Helly Theorem.
We investigate solution sets of a special kind of linear inequality systems. In particular, we derive characterizations of these sets in terms of minimal solution sets. The studied inequalities emerge as information inequalities in the context of Bayesian networks. This allows to deduce structural properties of Bayesian networks, which is important within causal inference.
Necessary and sufficient conditions are formulated for checking robust stability of an uncertain polynomial matrix. Various stability regions and uncertainty models are handled in a unified way. The conditions, stemming from a general optimization methodology similar to the one used in -analysis, are expressed as a rank-one LMI, a non-convex problem frequently arising in robust control. Convex relaxations of the problem yield tractable sufficient LMI conditions for robust stability of uncertain...
Dado un Problema de Programación Semi-Infinita, si se puede obtener una representación finita del conjunto factible, pueden aplicarse para resolver el problema los métodos de programación con restricciones finitas.En la primera parte se caracterizan los sistemas lineales infinitos que pueden ser reducidos a un sistema finito equivalente, dándose además condiciones suficientes y métodos para efectuar tal reducción. En la segunda parte se establecen diferentes procedimientos de obtención de la representación...
Let and for . Max-algebra is an analogue of linear algebra developed on the pair of operations extended to matrices and vectors. The system of equations and inequalities have each been studied in the literature. We consider a problem consisting of these two systems and present necessary and sufficient conditions for its solvability. We also develop a polynomial algorithm for solving max-linear program whose constraints are max-linear equations and inequalities.
A problem of finding a system of proportionally located parallel supporting hyperplanes of a family of connected compact sets is analyzed. A special attention is paid to finding a common supporting halfspace. An existence theorem is proved and a method of solution is proposed.