On Linear Inequality Systems with Smooth Coefficients

A linear inequality system with infinitely many constraints is polynomial [analytical] if its index set is a compact interval of the real line and all its coefficients are polynomial [analytical] functions of the index on this interval. This paper provides sufficient conditions for a given closed convex set to be the solution set of a certain polynomial or at least analytical system.The authors are indebted to Dr. J. M. Almira for valuable comments and suggestions.     

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.     

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.

     

On the stability of linear systems with an exact constraint set

This paper deals with the stability of the intersection of a given set with the solution, , of a given linear system whose coefficients can be arbitrarily perturbed. In the optimization context, the fixed constraint set X can be the solution set of the (possibly nonlinear) system formed by all the exact constraints (e.g., the sign constraints), a discrete subset of (as or { 0,1} ⁿ , as it happens in integer or Boolean programming) as well as the intersection of both kind of sets. Conditions are given for the intersection to remain nonempty (or empty) under sufficiently small perturbations of the data. Research supported by Fondecyt Grant 1020(7020)-646. Research supported by DGES and FEDER, Grant BFM2002-04114-C02-01     

Locally Farkas-Minkowski linear inequality systems

This paper introduces thelocally Farkas-Minkowski (LFM) linear inequality systems in a finite dimensional Euclidean space. These systems are those ones that satisfy that any consequence of the system that is active at some solution point is also a consequence of some finite subsystem. This class includes the Farkas-Minkowski systems and verifies most of the properties that these systems possess. Moreover, it contains the locally polyhedral systems, which are the natural external representation of quasi-polyhedral sets. TheLFM systems appear to be the natural external representation of closed convex sets. A characterization based on their properties under the union of systems is provided. In linear semi-infinite programming, theLFM property is the more general constraint qualification such that the Karush-Kuhn-Tucker condition characterizes the optimal points. Furthermore, the pair of Haar dual problems has no duality gap.     

Motzkin decomposition of closed convex sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. This paper provides five characterizations of the larger class of closed convex sets in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed in the paper. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed.     

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.     

Estimating reachable sets for two-dimensional linear discrete systems

We are concerned with the problem of estimating the reachable set for a two-dimensional linear discrete-time system with bounded controls. Different approaches are adopted depending on whether the system matrix has real or complex eigenvalues. For the complex eigenvalue case, the quasiperiodic nature of minimum time trajectories is exploited in developing a simple, but often accurate, procedure. For the real eigenvalue case, over estimates of reachable sets can be trivially obtained using a decomposition method.The second author was supported by funds supplied by the John M. Bennett Faculty Fellowship, Trinity University, San Antonio, Texas.     

Methods of Chebyshev points of convex sets and their applications

Chebyshev points of bounded convex sets, search algorithms for them, and various applications to convex programming are considered for simple approximations of reachable sets, optimal control, global optimization of additive functions on convex polyhedra, and integer programming. The problem of searching for Chebyshev points in multicriteria models of development and operation of electric power systems is considered.     

A Dual Parametrization Method for Convex Semi-Infinite Programming

We formulate convex semi-infinite programming problems in a functional analytic setting and derive optimality conditions and several duality results, based on which we develop a computational framework for solving convex semi-infinite programs.     

Approximate solution of a class of singular control problems

A class of singular control problems involving amplitude constraints on the controls is examined. IfL is the space of control functionsU, the control constraint setS can be identified with the unit ball inL . Now, for anyn (1, ), an analogous problem may be set up withL ⁿ forU and the unit ball inL ⁿ forS. This modified problem is necessarily nonsingular for controllable systems. It is shown that, by takingn sufficiently large, the solution to the modified problem also solves the original problem arbitrarily closely (in a sense made precise). Behavior asn is investigated.This research was supported by the Science Research Council of Great Britain and the Commonwealth Fund (Harkness Fellowship).     

On the connectedness of the solution set to linear complementarity systems

This paper establishes sufficient conditions for the connectedness of nontrivial subsets of the solution set to linear complementarity systems with special structure. Connectedness may be important to investigate stability and sensitivity questions, parametric problems, and for extending a Lemke-type method to a new class of problems. Such a property may help in analyzing the structure of the feasible region by checking the explicitly given matrices of the resulting conditions. From the point of view of geometry, the question is how to analyze the combined geometrical object consisting of a Riemannian manifold, a pointed cone, and level sets determined by linear inequalities.This paper has been mainly prepared while the author was visiting the Department of Mathematics at the University of Pisa. This research was partialy supported by the Hungarian National Research Foundation, Grant No. OTKA-2568.     

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.     

Characterization and computation of control invariant sets for linear impulsive control systems

Impulsive control systems are suitable to describe and control a venue of real-life problems, going from disease treatment to aerospace guidance. The main characteristic of such systems is that they evolve freely in-between impulsive actions, which makes it difficult to guarantee its permanence in a given state-space region. In this work, we develop a method for characterizing and computing approximations to the maximal control invariant sets for linear impulsive control systems, which can be explicitly used to formulate a set-based model predictive controller. We approach this task using a tractable and non-conservative characterization of the admissible state sets, namely the states whose free response remains within given constraints, emerging from a spectrahedron representation of such sets for systems with rational eigenvalues. The so-obtained impulsive control invariant set is then explicitly used as a terminal set of a predictive controller, which guarantees the feasibly asymptotic convergence to a target set containing the invariant set. Necessary conditions under which an arbitrary target set contains an impulsive control invariant set (and moreover, an impulsive control equilibrium set) are also provided, while the controller performance are tested by means of two simulation examples.     

On characterizing the solution sets of pseudolinear programs

This paper provides several new and simple characterizations of the solution sets of pseudolinear programs. By means of the basic properties of pseudolinearity, the solution set of a pseudolinear program is characterized, for instance, by the equality that , for each feasible pointx, where is in the solution set. As a consequence, we give characterizations of both the solution set and the boundedness of the solution set of a linear fractional program.     

On the boundedness of outer polyhedral estimates for reachable sets of linear systems

New properties of outer polyhedral (parallelepipedal) estimates for reachable sets of linear differential systems are studied. For systems with a stable matrix, it is determined what the orientation matrices are for which the estimates possessing the generalized semigroup property are bounded/unbounded on an infinite time interval. In particular, criteria are found (formulated in terms of the eigenvalues of the system’s matrix and the properties of bounding sets) that guarantee for previously mentioned tangent estimates and estimates with a constant orientation matrix that either there are initial orientation matrices for which the corresponding estimate tubes are bounded or all these tubes are unbounded. For linear stationary systems, a system of ordinary differential equations and algebraic relations is derived that determines estimates with constant orientation matrices for reachable sets that have no generalized semigroup property but are tangent and also bounded if the matrix of the system is stable.     

Saturation in Linear Optimization

In a solvable linear optimization problem, a constraint is saturated if it is binding at a certain optimal solution and it is weakly saturated if it is binding at a proper subset of the optimal set. Nonsaturation and weak saturation can be seen as redundancy phenomena in the sense that the elimination of a finite number of these constraints preserves the value of the given problem. We consider also the effect of sufficiently small perturbations of the cost coefficients in the classification of a given constraint as either saturated or nonsaturated.     

Exact analytical inversion of TSK fuzzy systems with singleton and linear consequents

In literature, exact inversion methods for TSK fuzzy systems exist only for the systems with singleton consequents. These methods have binding limitations such as strong triangular partitioning, monotonic rule bases and/or invertibility check. These extra limitations lessen the modeling capabilities of the TSK fuzzy systems. In this study, an exact analytical inversion method for TSK fuzzy systems with singleton and linear consequents is presented. The only limitation of the proposed method is that the inversion variable should be represented by piecewise linear membership functions (PWL-MFs). In this case, the universe of discourse of the inversion variable is divided into specific regions in which only one linear piece exists for each PWL-MF at most. In the proposed method, the analytical formulation of TSK fuzzy system is expressed in terms of the inversion variable by using linear equations of PWL-MFs. Thus, the fuzzy system output in any region can be obtained by using the appropriate parameters of the linear equations of PWL-MFs defined within the related region. This expression provides a way to obtain linear and quadratic equations in terms of the inversion variable for TSK fuzzy systems with singleton and linear consequents, respectively. So, it becomes very easy to find exact inverse solutions for each region by using explicit analytical solutions for linear or quadratic equations. The proposed inversion method has been illustrated through simulation examples.     

Discretization methods for the solution of semi-infinite programming problems

In the first part of this paper, we prove the convergence of a class of discretization methods for the solution of nonlinear semi-infinite programming problems, which includes known methods for linear problems as special cases. In the second part, we modify and study this type of algorithms for linear problems and suggest a specific method which requires the solution of a quadratic programming problem at each iteration. With this algorithm, satisfactory results can also be obtained for a number of singular problems. We demonstrate the performance of the algorithm by several numerical examples of multivariate Chebyshev approximation problems.     

A new result in the theory and computation of the least-norm solution of a linear program

By perturbing properly a linear program to a separable quadratic program, it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overrelaxation) algorithms. The main result of this paper gives an effective computational criterion to check whether the solutions of the perturbed quadratic programs provide the least-norm solution of the original linear program.This research was sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based upon work supported by the National Science Foundation, Grant Nos. DCR-84-20963 and DMS-82-109050, and by the Italian National Research Council (CNR).The author wishes to thank Professor O. L. Mangasarian for his helpful comments which helped to improve the paper.