A note about linear inequality systems and duality

The optimization of a linear function on a closed convex set,F, can be stated as a linear semi-infinite program, sinceF is the solution set of (usually) infinite linear inequality systems, the so-called linear representations ofF. The duality properties of these programs are analyzed when the linear representation ofF ranges in some well known classes of linear inequality systems. This paper provides propositions on the duality diagrams of Farkas-Minkowski, canonically closed, compact and closed systems. Converse statements are also given.

---

Zusammenfassung Die Optimierung einer linearen Funktion auf einer konvexen abgeschlossenen MengeF kann als semi-infinites lineares Programm aufgefaßt werden, daF als Durchschnitt (unendlich) vieler Halbräume dargestellt werden kann. Es werden Dualitätseigenschaften dieser Programme untersucht, wobei von verschiedenen linearen Darstellungen fürF ausgegangen wird. Die Arbeit enthält Sätze über Dualitätsbeziehungen von Farkas-Minkowski, kanonisch abgeschlossene, kompakte und abgeschlossene Systeme. Es werden auch umgekehrte Beziehungen angegeben.

     

Locally polyhedral linear inequality systems

Linear systems of an arbitrary number of inequalities provide external representations for the closed convex sets in the Euclidean space. In particular, the locally polyhedral systems introduced in this paper are the natural linear representation for quasipolyhedral sets (those subsets of the Euclidean space whose nonempty intersections with polytopes are polytopes). For these systems the geometrical properties of the solution set are investigated, and their extreme points and edges are characterized. The class of locally polyhedral systems includes the quasipolyhedral systems, introduced by Marchi, Puente, and Vera de Serio in order to generalize the Weyl property of finite linear inequality systems.     

Reachable and controllable sets for two-dimensional,linear, discrete-time systems

We consider two-dimensional discrete-time linear systems with constrained controls. We propose a simple polynomial time procedure to give an exact external representation of theN-step reachable set and controllable set. The bounding hyperplanes are explicitly derived in terms of the data of the problem. By using a result in computational geometry, all the calculations are made in polynomial time in contrast to classical methods. The limit case asN is also investigated.     

Directional End of a Convex Set: Theory and Applications

A point of a convex set belongs to its end in a given direction when this direction is not feasible at that point. This paper analyzes the properties of the directional end of general convex sets and closed convex sets (for which the directional ends are connected by arcs) as well as the relationship between the directional end and certain concepts on the illumination of convex bodies. The paper includes applications of the directional end to the theory of linear systems.     

Unicity in linear optimization

This paper deals with the conditions for the uniqueness of the optimal solution of an optimization problem for which the objective function is linear and the feasible set is a closed convex set in a finite-dimensional space. Some of these conditions, such as strong unicity andw-unicity (a new transition concept), involve only the feasible set. Others are related to the properties of the chosen linear representation. To some extent, the paper surveys the literature about unicity and strong unicity in linear semi-infinite programming.This work was partially supported by the DGICYT of Spain, Grant PS90-0158, by the Bulgarian Ministry of Education and Science, Grant MM-408/94, and by the EC Commission, Grant CIPA-3510PL929132.     

A class of linear differential dynamical systems with fuzzy matrices

This paper investigates the first order linear fuzzy differential dynamical systems with fuzzy matrices. We use a complex number representation of the α-level sets of the fuzzy system, and obtain the solution by employing such representation. It is applicable to practical computations and has also some implications for the theory of fuzzy differential equations. We then present some properties of the 2-dimensional dynamical systems and their phase portraits. Some examples are considered to show the richness of the theory and we can clearly see that new behaviors appear. We finally present some conclusions and new directions for further research in the area of fuzzy dynamical systems.     

Analytical Linear Inequality Systems and Optimization

In many interesting semi-infinite programming problems, all the constraints are linear inequalities whose coefficients are analytical functions of a one-dimensional parameter. This paper shows that significant geometrical information on the feasible set of these problems can be obtained directly from the given coefficient functions. One of these geometrical properties gives rise to a general purification scheme for linear semi-infinite programs equipped with so-called analytical constraint systems. It is also shown that the solution sets of such kind of consistent systems form a transition class between polyhedral convex sets and closed convex sets in the Euclidean space of the unknowns.     

Semi-Conjugate Direction Methods for Real Positive Definite Systems

In this preliminary work, left and right conjugate direction vectors are defined for nonsymmetric, nonsingular matrices A and some properties of these vectors are studied. A left conjugate direction (LCD) method for solving nonsymmetric systems of linear equations is proposed. The method has no breakdown for real positive definite systems. The method reduces to the usual conjugate gradient method when A is symmetric positive definite. A finite termination property of the semi-conjugate direction method is shown, providing a new simple proof of the finite termination property of conjugate gradient methods. The new method is well defined for all nonsingular M-matrices. Some techniques for overcoming breakdown are suggested for general nonsymmetric A. The connection between the semi-conjugate direction method and LU decomposition is established. The semi-conjugate direction method is successfully applied to solve some sample linear systems arising from linear partial differential equations, with attractive convergence rates. Some numerical experiments show the benefits of this method in comparison to well-known methods. This revised version was published online in July 2006 with corrections to the Cover Date.     

On strong and total Lagrange duality for convex optimization problems

We give some necessary and sufficient conditions which completely characterize the strong and total Lagrange duality, respectively, for convex optimization problems in separated locally convex spaces. We also prove similar statements for the problems obtained by perturbing the objective functions of the primal problems by arbitrary linear functionals. In the particular case when we deal with convex optimization problems having infinitely many convex inequalities as constraints the conditions we work with turn into the so-called Farkas-Minkowski and locally Farkas-Minkowski conditions for systems of convex inequalities, recently used in the literature. Moreover, we show that our new results extend some existing ones in the literature.     

Consistency of a linear system of inequalities

We show that a consistency check of a linear system of inequalitiesAxb reduces to check whetherQb0 for a certain matrixQ. It is a direct consequence of the Farkas-Minkowski theorem. Thus, when one has to check consistency for different values ofb, one need not run a numerical algorithm for eachb.On leave at the Electronics Research Laboratory of the University of California at Berkeley in a CNRS/NSF Exchange Program.     

On common linear copositive Lyapunov functions for pairs of stable positive linear systems

We study the common linear copositive Lyapunov functions of positive linear systems. Firstly, we present a theorem on pairs of second order positive linear systems, and give another proof of this theorem by means of properties of geometry. Based on the process of the proof, we extended the results to a finite number of second order positive linear systems. Then we extend this result to third order systems. Finally, for higher order systems, we give some results on common linear copositive Lyapunov functions.     

A characterization of constant-time linear control systems satisfying the Pontryagin maximum principle

Using the subdifferential, we extend the main characterization of Banach linear systems satisfying the Pontryagin maximum principle, given in our previous paper (Ref. 1), to the case whenF andX are locally convex spaces and the norm ofF is replaced by an arbitrary continuous convex functionalh onF.     

A Finite Field Framework for Modeling,Analysis and Control of Finite State Automata

In this paper, we address the modeling, analysis and control of finite state automata, which represent a standard class of discrete event systems. As opposed to graph theoretical methods, we consider an algebraic framework that resides on the finite field <formula form="inline">${\Op F}_2$</formula> which is defined on a set of two elements with the operations addition and multiplication, both carried out modulo 2. The key characteristic of the model is its functional completeness in the sense that it is capable of describing most of the finite state automata in use, including non-deterministic and partially defined automata. Starting from a graphical representation of an automaton and applying techniques from Boolean algebra, we derive the transition relation of our finite field model. For cases in which the transition relation is linear, we develop means for treating the main issues in the analysis of the cyclic behavior of automata. This involves the computation of the elementary divisor polynomials of the system dynamics, and the periods of these polynomials, which are shown to completely determine the cyclic structure of the state space of the underlying linear system. Dealing with non-autonomous linear systems with inputs, we use the notion of feedback in order to specify a desired cyclic behavior of the automaton in the closed loop. The computation of an appropriate state feedback is achieved by introducing an image domain and adopting the well-established polynomial matrix method to linear discrete systems over the finite field <formula form="inline">${\Op F}_2$</formula>. Examples illustrate the main steps of our method.     

Estimation of Time Varying Linear Systems

Based on kernel and wavelet estimators of the evolutionary spectrum and cross-spectrum we propose nonlinear wavelet estimators of the time varying coefficients of a linear system, whose input and output are locally stationary processes, in the sense of Dahlhaus (1997). We obtain large sample properties of these estimators, present some simulated examples and derive results on the L ₂-risk for the wavelet threshold estimators, assuming that the coefficients belong to some smoothness class. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the convergence of general stationary iterative methods for range‐Hermitian singular linear systems

General stationary iterative methods with a singular matrix M for solving range‐Hermitian singular linear systems are presented, some convergence conditions and the representation of the solution are also given. It can be verified that the general Ortega–Plemmons theorem and Keller theorem for the singular matrix M still hold. Furthermore, the singular matrix M can act as a good preconditioner for solving range‐Hermitian linear systems. Numerical results have demonstrated the effectiveness of the general stationary iterations and the singular preconditioner M. Copyright © 2009 John Wiley & Sons, Ltd.     

Multi-segmental representations and approximation of set-valued functions with 1D images

In this work univariate set-valued functions (SVFs, multifunctions) with 1D compact sets as images are considered. For such a continuous SFV of bounded variation (CBV multifunction), we show that the boundaries of its graph are continuous, and inherit the continuity properties of the SVF. Based on these results we introduce a special class of representations of CBV multifunctions with a finite number of ‘holes’ in their graphs. Each such representation is a finite union of SVFs with compact convex images having boundaries with continuity properties as those of the represented SVF. With the help of these representations, positive linear operators are adapted to SVFs. For specific positive approximation operators error estimates are obtained in terms of the continuity properties of the approximated multifunction.     

Infinite-dimensional linear groups with restrictions on subgroups that are not soluble <Emphasis Type="Italic">A</Emphasis><Subscript>3</Subscript>-groups

We are concerned with infinite-dimensional locally soluble linear groups of infinite central dimension that are not soluble A₃-groups and all of whose proper subgroups, which are not soluble A₃-groups, have finite central dimension. The structure of groups in this class is described. The case of infinite-dimensional locally nilpotent linear groups satisfying the specified conditions is treated separately. A similar problem is solved for infinite-dimensional locally soluble linear groups of infinite fundamental dimension that are not soluble A₃-groups and all of whose proper subgroups, which are not soluble A₃-groups, have finite fundamental dimension. __________ Translated from Algebra i Logika, Vol. 46, No. 5, pp. 548–559, September–October, 2007.     

On the Attainable Sets of Control Systems with p-Integrable Controls

It is well known that, for a control system, under suitable assumptions, the closure of the attainable set does not change if we consider p-integrable controls for different p. This is an interesting problem and has not been studied in depth, whether or not the attainable set changes when p changes. We show that, for a linear system, the attainable sets may be different for different p. In the two-dimensional case, we prove that the number of indices for which the attainable sets change is finite. Moreover, we show that, for a class of systems, the attainable sets are the same, when the time duration is large enough.     

On Locally Finite Modules

This paper is devoted to the study of locally finite modules M, i.e., modules whose finitely generated submodules are finite (as sets). In particular, we study rings which have faithful locally finite modules, for example, the polynomial rings ℤ[x] and F[x], where F is a finite field. Our results generalize the properties of Abelian torsion groups and the ring of integers. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 14, Algebra, 2004.     

Stability in disjunctive linear optimization I: continuity of the feasible set

The aim of this paper is to study the continuous dependence of the feasible set of a disjunctive semi-infinite linear optimization problem on all involved parameters (matrix and right-hand side). The feasible set of such an optimization problem is the union of (a. possible infinite number of) convex sets, which each is described by a finite or an infinite number of strict and non-strict linear inequalities. We derive necessary and sufficient conditions for the upper- and lower-semi-continuity, and the closedness of the feasible-set-mapping Z Especially, the compactness of the boundary of the feasible set and the closedness of Z are equivalent to the upper-semi-continuity of Zwhile the lower semi-continuity of Z is equivalent to a certain constraint qualification. This constraint qualification is a strengthened kind of Slater condition, rrom tuese investigations, we derive known results in parametric semi-infinite optimization and parametric integer programming.