Extending the mixed algebraic-analysis Fourier–Motzkin elimination method for classifying linear semi-infinite programmes

Motivated by a recent Basu–Martin–Ryan paper, we obtain a reduced primal-dual pair of a linear semi-infinite programming problem by applying an amended Fourier–Motzkin elimination method to the linear semi-infinite inequality system. The reduced primal-dual pair is equivalent to the original one in terms of consistency, optimal values and asymptotic consistency. Working with this reduced pair and reformulating a linear semi-infinite programme as a linear programme over a convex cone, we reproduce all the theorems that lead to the full eleven possible duality state classification theory. Establishing classification results with the Fourier–Motzkin method means that the two classification theorems for linear semi-infinite programming, 1969 and 1974, have been proved by new and exciting methods. We also show in this paper that the approach to study linear semi-infinite programming using Fourier–Motzkin elimination is not purely algebraic, it is mixed algebraic-analysis.     

γ-Active Constraints in Convex Semi-Infinite Programming

In this article, we extend the definition of γ-active constraints for linear semi-infinite programming to a definition applicable to convex semi-infinite programming, by two approaches. The first approach entails the use of the subdifferentials of the convex constraints at a point, while the second approach is based on the linearization of the convex inequality system by means of the convex conjugates of the defining functions. By both these methods, we manage to extend the results on γ-active constraints from the linear case to the convex case.     

Metric regularity of semi-infinite constraint systems

We obtain a formula for the modulus of metric regularity of a mapping defined by a semi-infinite system of equalities and inequalities. Based on this formula, we prove a theorem of Eckart-Young type for such set-valued infinite-dimensional mappings: given a metrically regular mapping F of this kind, the infimum of the norm of a linear function g such that F+g is not metrically regular is equal to the reciprocal to the modulus of regularity of F. The Lyusternik-Graves theorem gives a straightforward extension of these results to nonlinear systems. We also discuss the distance to infeasibility for homogeneous semi-infinite linear inequality systems. Dedicated to R. T. Rockafellar on his 70th Birthday Research partially supported by grants BFM2002-04114-C02 (01-02) from MCYT (Spain) and FEDER (E.U.), GV04B-648 and GRUPOS04/79 from Generalitat Valenciana (Spain), and Bancaja-UMH (Spain).     

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

Optimal feedback control for dynamic systems with state constraints: An exact penalty approach

In this paper, we consider a class of nonlinear dynamic systems with terminal state and continuous inequality constraints. Our aim is to design an optimal feedback controller that minimizes total system cost and ensures satisfaction of all constraints. We first formulate this problem as a semi-infinite optimization problem. We then show that by using a new exact penalty approach, this semi-infinite optimization problem can be converted into a sequence of nonlinear programming problems, each of which can be solved using standard gradient-based optimization methods. We conclude the paper by discussing applications of our work to glider control.     

Nonsmooth semi-infinite programming problems with mixed constraints

We consider a nonsmooth semi-infinite programming problem with a feasible set defined by inequality and equality constraints and a set constraint. First, we study some alternative theorems which involve linear and sublinear functions and a convex set and we propose several generalizations of them. Then, alternative theorems are applied to obtain, under different constraint qualifications, several necessary optimality conditions in the type of Fritz-John and Karush-Kuhn-Tucker.     

Outer approximation schemes for generalized semi-infinite variational inequality problems

We introduce and analyse outer approximation schemes for solving variational inequality problems in which the constraint set is as in generalized semi-infinite programming. We call these problems generalized semi-infinite variational inequality problems. First, we establish convergence results of our method under standard boundedness assumptions. Second, we use suitable Tikhonov-like regularizations for establishing convergence in the unbounded case.     

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.     

Topological stability of linear semi-infinite inequality systems

In this note, we analyze the relationship between the lower semicontinuity of the feasible set mapping for linear semi-infinite inequality systems and the so-called topological stability, which is held when the solution sets of all the systems obtained by sufficiently small perturbations of the data are homeomorphic to each other. This topological stability and its relation with the Mangasarian-Fromovitz constraints qualification have been studied deeply by Jongen et al. in Ref. 1. The main difference of our approach is that we are not assuming any kind of structure for the index set and, consequently, any particular property for the functional dependence between the inequalities and the associated indices. In addition, we deal with systems whose solution sets are not necessarily bounded.This work has been supported partially by the DGICYT of Spain, Grant PB93-0943, by Generalitat Valenciana, Grant GV-2219/94, and by IVEI, Grant 003/026.The authors would like to thank J. E. Martínez Legaz for his valuable comments.     

Necessary optimality conditions for nonsmooth generalized semi-infinite programming problems

This paper is devoted to the study of nonsmooth generalized semi-infinite programming problems in which the index set of the inequality constraints depends on the decision vector and all emerging functions are assumed to be locally Lipschitz. We introduce a constraint qualification which is based on the Mordukhovich subdifferential. Then, we derive a Fritz–John type necessary optimality condition. Finally, interrelations between the new and the existing constraint qualifications such as the Mangasarian–Fromovitz, linear independent, and the Slater are investigated.     

Robust linear semi-infinite programming duality under uncertainty

In this paper, we propose a duality theory for semi-infinite linear programming problems under uncertainty in the constraint functions, the objective function, or both, within the framework of robust optimization. We present robust duality by establishing strong duality between the robust counterpart of an uncertain semi-infinite linear program and the optimistic counterpart of its uncertain Lagrangian dual. We show that robust duality holds whenever a robust moment cone is closed and convex. We then establish that the closed-convex robust moment cone condition in the case of constraint-wise uncertainty is in fact necessary and sufficient for robust duality. In other words, the robust moment cone is closed and convex if and only if robust duality holds for every linear objective function of the program. In the case of uncertain problems with affinely parameterized data uncertainty, we establish that robust duality is easily satisfied under a Slater type constraint qualification. Consequently, we derive robust forms of the Farkas lemma for systems of uncertain semi-infinite linear inequalities.     

Spline smoothing under constraints on derivatives

An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.     

一类具有闭环极点约束的不确定线性系统的保性能控制

主要研究了闭环系统的极点约束在一个给定圆盘中的保性能控制问题,基于线性矩阵不等式处理方法给出了状态反馈控制器存在的充要条件,并利用线性矩阵不等式的解给出了保性能控制器的设计方法,得到一个状态反馈控制器,使得对所有允许的不确定性闭环系统稳定,并且闭环性能指标值不超过某个确定的上界.最后以数值例子验证了结果的正确性.     

Theorems on the dimension of convex sets

This paper gives theorems on the dimension of solution sets of semi-infinite systems of linear inequalities. As an application, some results of Clark and Williams are generalized.     

Duality for nonsmooth semi-infinite programming problems

This paper deals with nonsmooth semi-infinite programming problem which in recent years has become an important field of active research in mathematical programming. A semi-infinite programming problem is characterized by an infinite number of inequality constraints. We formulate Wolfe as well as Mond-Weir type duals for the nonsmooth semi-infinite programming problem and establish weak, strong and strict converse duality theorems relating the problem and the dual problems. To the best of our knowledge such results have not been done till now.     

Farkas’ lemma for separable sublinear inequalities without qualifications

We show that the celebrated Farkas lemma for linear inequality systems continues to hold for separable sublinear inequality systems. As a consequence, we establish a qualification-free characterization of optimality for separable sublinear programming problems which include classes of robust linear programming problems. We also deduce that the Lagrangian duality always holds for these programming problems without qualifications.     

One-Parameter Families of Feasible Sets in Semi-infinite Optimization

Feasible sets in semi-infinite optimization are basically defined by means of infinitely many inequality constraints. We consider one-parameter families of such sets. In particular, all defin-ing functions - including those defining the index set of the inequality constraints - will depend on a parameter. We note that a semi-infinite problem is a two-level problem in the sense that a point is feasible if and only if all global minimizers of a corresponding marginal function are nonnegative. For a quite natural class of mappings we characterize changes in the global topological structure of the corresponding feasible set as the parameter varies. As long as the index set (-mapping) of the inequality constraints is lower semicontinuous, all changes in topology are those which generically appear in one-parameter sets defined by finitely many constraints. In the case, however, that some component of the mentioned index set is born (or vanishes), the topological change is of global nature and is not controllable. In fact, the change might be as drastic as that when adding or deleting an (arbitrary) inequality constraint.     

Nonnegative solvability of linear equations in certain ordered rings

In the integers and in certain densely ordered rings that are not fields, projections of the solution set of finitely many homogeneous weak linear inequalities may be defined by finitely many congruence inequalities, where a congruence inequality combines a weak inequality with a system of congruences. These results extend well-known facts about systems of weak linear inequalities over ordered fields and imply corresponding analogues of Farkas' Lemma on nonnegative solvability of systems of linear equations.