On Finite Linear Systems Containing Strict Inequalities

This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.     

Motzkin predecomposable sets

We introduce and study the family of sets in a finite dimensional Euclidean space which can be written as the Minkowski sum of a compact and convex set and a convex cone (not necessarily closed). We establish several properties of the class of such sets, called Motzkin predecomposable, some of which hold also for the class of Motzkin decomposable sets (i.e., those for which the convex cone in the decomposition is requested to be closed), while others are specific of the new family.     

On the Stability of the Motzkin Representation of Closed Convex Sets

A set is called Motzkin decomposable when it can be expressed as the Minkowski sum of a compact convex set with a closed convex cone. This paper analyzes the continuity properties of the set-valued mapping associating to each couple $\left( C,D\right) $ formed by a compact convex set C and a closed convex cone D its Minkowski sum C?+?D. The continuity properties of other related mappings are also analyzed.     

Set Containment Characterization

Characterization of the containment of a polyhedral set in a closed halfspace, a key factor in generating knowledge-based support vector machine classifiers [7], is extended to the following: (i) containment of one polyhedral set in another; (ii) containment of a polyhedral set in a reverse-convex set defined by convex quadratic constraints; (iii) Containment of a general closed convex set, defined by convex constraints, in a reverse-convex set defined by convex nonlinear constraints. The first two characterizations can be determined in polynomial time by solving m linear programs for (i) and m convex quadratic programs for (ii), where m is the number of constraints defining the containing set. In (iii), m convex programs need to be solved in order to verify the characterization, where again m is the number of constraints defining the containing set. All polyhedral sets, like the knowledge sets of support vector machine classifiers, are characterized by the intersection of a finite number of closed halfspaces.     

Piecewise linear retractions by reflexion

The reflexion method of Motzkin and Schoenberg is used to generate a class of piecewise linear retractions from X to Y where X is the set of all points within a fixed distance of the convex polyhedral set Y.     

On Some Generalized Polyhedral Convex Constructions

Generalized polyhedral convex sets, generalized polyhedral convex functions on locally convex Hausdorff topological vector spaces, and the related constructions such as sum of sets, sum of functions, directional derivative, infimal convolution, normal cone, conjugate function, subdifferential are studied thoroughly in this paper. Among other things, we show how a generalized polyhedral convex set can be characterized through the finiteness of the number of its faces. In addition, it is proved that the infimal convolution of a generalized polyhedral convex function and a polyhedral convex function is a polyhedral convex function. The obtained results can be applied to scalar optimization problems described by generalized polyhedral convex sets and generalized polyhedral convex functions.     

A representation of convex semilinear sets

If F is an ordered field, a subset of n-space over F is said to be semilinear just in case it is a finite Boolean combination of translates of closed halfspaces, where a closed halfspace is the set of all points obeying a homogeneous weak linear inequality with coefficients from F. Andradas, Rubio, and Vélez have shown that closed (open) convex semilinear sets are finite intersections of translates of closed (open) halfspaces (an open halfspace is defined as before, but with a strict inequality). This paper represents arbitrary convex semilinear sets in a manner analogous to that of Andradas, Rubio, and Vélez.     

Voronoi cells via linear inequality systems

The theory and methods of linear algebra are a useful alternative to those of convex geometry in the framework of Voronoi cells and diagrams, which constitute basic tools of computational geometry. As shown by Voigt and Weis in 2010, the Voronoi cells of a given set of sites T, which provide a tesselation of the space called Voronoi diagram when T is finite, are solution sets of linear inequality systems indexed by T. This paper exploits systematically this fact in order to obtain geometrical information on Voronoi cells from sets associated with T (convex and conical hulls, tangent cones and the characteristic cones of their linear representations). The particular cases of T being a curve, a closed convex set and a discrete set are analyzed in detail. We also include conclusions on Voronoi diagrams of arbitrary sets.     

Normal Fans of Polyhedral Convex Sets

The normal fan of a polyhedral convex set in ? ⁿ is the collection of its normal cones. The structure of the normal fan reflects the geometry of that set. This paper reviews and studies properties about the normal fan. In particular, it investigates situations in which the normal fan of a polyhedral convex set refines, or is a subfan of, that of another set. It then applies these techniques in several examples. One of these concerns the face structure and normal manifold of the critical cone of a polyhedral convex set associated with a point in ? ⁿ . Another concerns how perturbation of the right hand side of the linear constraints defining such a set affects the normal fan and the face structure.     

On the cone of a finite dimensional compact convex set at a point

Four equivalent conditions for a convex cone in a Euclidean space to be an F_σ-set are given. Our result answers in the negative a recent open problem posed by Tam [5], characterizes the barrier cone of a convex set, and also provides an alternative proof for the known characterizations of the inner aperture of a convex set as given by Brønsted [2] and Larman [3].     

Isotone functions,dual cones,and networks

If the collection of all real-valued functions defined on a finite partially ordered set S of n elements is identified in the natural way with Rⁿ, it is obvious that the subset of functions that are isotone or order preserving with respect to the given partial order constitutes a closed, convex, polyhedral cone K in Rⁿ. The dual cone K^* of K is the set of all linear functionals that are nonpositive of K. This article identifies the important geometric properties of K, and characterizes a nonredundant set of defining equations and inequalities for K^* in terms of a special class of partitions of S into upper and lower sets. These defining constraints immediately imply a set of extreme rays spanning K and K^*. One of the characterizations of K^* involves feasibility conditions on flows in a network. These conditions are also used as a tool in analysis.     

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.     

Unique representation in convex sets by extraction of marked components

After introducing the basic concepts of extraction and marking for convex sets, the following marked representation theorem is established: Let C be a lineally closed convex set without lines, the face lattice of which satisfies some descending chain condition, and let μ be some marking on C. Then every point of C can be represented in unique way as a convex (nonnegative) linear combination of points (directions) of C which are μ-independent, and this representation can be determined by an algorithm of successive extractions. In particular, if C is a finite dimensional closed convex set without lines and μ marks extreme points (directions) only, then the marked representation theorem contains some well-known results of convex analysis as special cases, and it yields in the case where C is a polyhedral triangulation which extends available results on polytopes to the unbounded case. The triangulation of unbounded polyhedra then is applied to a certain class of parametric linear programs.     

Existence and sum decomposition of vertex polyhedral convex envelopes

Convex envelopes are a very useful tool in global optimization. However finding the exact convex envelope of a function is a difficult task in general. This task becomes considerably simpler in the case where the domain is a polyhedron and the convex envelope is vertex polyhedral, i.e., has a polyhedral epigraph whose vertices correspond to the vertices of the domain. A further simplification is possible when the convex envelope is sum decomposable, i.e., the convex envelope of a sum of functions coincides with the sum of the convex envelopes of the summands. In this paper we provide characterizations and sufficient conditions for the existence of a vertex polyhedral convex envelope. Our results extend and unify several results previously obtained for special cases of this problem. We then characterize sum decomposability of vertex polyhedral convex envelopes, and we show, among else, that the vertex polyhedral convex envelope of a sum of functions coincides with the sum of the vertex polyhedral convex envelopes of the summands if and only if the latter sum is vertex polyhedral.     

Best interpolation in seminorm with convex constraints

Implicit and explicit characterizations of the solutions to the following constrained best interpolation problem $$\min \left\{ {\left\| {Tx - z} \right\|:x \in C \cap A^{ - 1} d} \right\}$$ are presented. Here,T is a densely-defined, closed, linear mapping from a Hilbert spaceX to a Hilbert spaceY, A: X→Z is a continuous, linear mapping withZ a locally, convex linear topological space,C is a closed, convex set in the domain domT ofT, andd∈AC. For the case in whichC is a closed, convex cone, it is shown that the constrained best interpolation problem can generally be solved by finding the saddle points of a saddle function on the whole space, and, if the explicit characterization is applicable, then solving this problem is equivalent to solving an unconstrained minimization problem for a convex function.     

Characterizing robust set containments and solutions of uncertain linear programs without qualifications

Qualification-free dual characterizations are given for robust polyhedral set containments where a robust counterpart of an uncertain polyhedral set is contained in another polyhedral set or a polyhedral set is contained in a robust counterpart of an uncertain polyhedral set. These results are used to characterize robust solutions of uncertain linear programs, where the uncertainty is defined in terms of intervals or l₁-balls. The hidden separable sub-linearity of the robust counterparts allows qualification-free dual characterizations.     

Minimum Distance to the Complement of a Convex Set: Duality Result

The subject of this paper is to study the problem of the minimum distance to the complement of a convex set. Nirenberg has stated a duality theorem treating the minimum norm problem for a convex set. We state a duality result which presents some analogy with the Nirenberg theorem, and we apply this result to polyhedral convex sets. First, we assume that the polyhedral set is expressed as the intersection of some finite collection of m given half-spaces. We show that a global solution is determined by solving m convex programs. If the polyhedral set is expressed as the convex hull of a given finite set of extreme points, we show that a global minimum for a polyhedral norm is obtained by solving a finite number of linear programs.     

Characterizations of solution sets of convex vector minimization problems

Complete dual characterizations of the weak and proper optimal solution sets of an infinite dimensional convex vector minimization problem are given. The results are expressed in terms of subgradients, Lagrange multipliers and epigraphs of conjugate functions. A dual condition characterizing the containment of a closed convex set, defined by a cone-convex inequality, in a reverse-convex set, plays a key role in deriving the results. Simple Lagrange multiplier characterizations of the solution sets are also derived under a regularity condition. Numerical examples are given to illustrate the significance of the results.     

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.

     

Characterizations via linear scalarization of minimal and properly minimal elements

In this note we provide sufficient conditions that guarantee representations via linear scalarization of different types of properly minimal elements of a given set by means of a new separation statement for closed convex cones. Moreover, we also give conditions that ensure the proper minimality (in different senses) of the minimal points with respect to a convex ordering cone of a set.