Search

It is well known that finite-dimensional polyhedral convex sets can be generated by finitely many points and finitely many directions. Representation formulas in this spirit are obtained for convex polyhedra and generalized convex polyhedra in locally convex Hausdorff topological vector spaces. Our results develop those of X. Y. Zheng (Set-Valued Anal., Vol. 17, 2009, 389-408), which were established in a Banach space setting. Applications of the representation formulas to proving solution existence theorems for generalized linear programming problems and generalized linear vector optimization problems are shown.

Let ωnπ and ωnt&h denote the convex polytope of n×n centrosymmetric doubly substochastic matrices and the convex polytope of n×n symmetric and Hankel-symmetric doubly substochastic matrices, respec...

Let ωn,k denote the convex polytope of doubly substochastic matrices with sub-defect k. Let h(A) and l(A) denote the maximum and minimum diagonals of A∈ωn,k respectively. In this paper, we study th...

A complete, elementary analysis is presented for second-order difference equations xn=g(xn-1,xn-2) where g is strictly monotone and convex in the first quadrant. It is shown that the dynamics of any such equation partitions the phase space into two basins of attraction, one of which is bounded and convex (possibly empty). In the case of two non-empty basins, each point on their common boundary corresponds to an asymptotically 2-periodic solution. The results and examples presented complement previous studies of second-order equations in the literature.

Invertibility of all convex combinations of A and I is equivalent to the real eigenvalues of A, if any, being positive. Invertibility of all matrices whose rows are convex combinations of the respective rows of A and I is equivalent to A having positive principal minors (i.e. being a P-matrix). These results are extended by considering convex combinations of higher powers of A and of their rows. The invertibility of matrices in these convex hulls is associated with the eigenvalues of A lying in open sectors of the right-half plane and provides a general context for the theory of matrices with P-matrix powers.

Given a weighted simple graph, the minimum weighted maximal matching MWMM problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings the maximal matching polytope in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.

The problem of covering a convex 3D polytope by the minimal number of congruent spheres is reduced to a sequence of problems of minimising sphere radius when fixing the number of the spheres. We form a mathematical model of the problem using the Voronoi polytopes. Characteristics of the model are investigated. Extrema are attained at the vertices of the Voronoi polytopes constructed for sphere centres. To search for local minima, a modification of the Zoutendijk feasible directions method in a combination with random search is developed. Some numerical results for a cube and a non-regular octahedron are obtained.

We provide a counterexample to the remark in Lohne and Schrage [An algorithm to solve polyhedral convex set optimization problems, Optimization 62 (2013), pp. 131-141] that every solution of a polyhedral convex set optimization problem is a pre-solution. A correct statement is that every solution of a polyhedral convex set optimization problem obtained by the algorithm SetOpt is a pre-solution. We also show that every finite infimizer and hence every solution of a polyhedral convex set optimization problem contains a pre-solution.

The H-unistochastic matrices are a special class of symmetric bistochastic matrices obtained by taking the square of the absolute value of each entry of a Hermitian unitary matrix. We examine the geometric relationship of the convex hull of the n by n H-unistochastic matrices relative to the larger convex set of n by n symmetric bistochastic matrices. We show that any line segment in the convex set of the n by n symmetric bistochastic matrices which passes through the centroid of this convex set must spend at least two-thirds of its length in the convex hull of the n by n H-unistochastic matrices when n is either three or four and we prove a partial result for higher n. A class of completely positive linear maps, called the self-dual doubly stochastic maps, is useful for studying this problem. Some results on self-dual doubly stochastic maps are given including a self-dual version of the Laudau–Streater theorem.

SummaryThe problem of geometric realization for convex polyhedra, which satisfy certain desirable properties, has received quite a bit of attention lately. Interest, mainly, has been on polyhedral representations where either all of the vertex coordinates are small integers, or all of the edge lengths are integers, or all of the edges are tangent to a sphere. In general, it is not easy to construct a convex polyhedron satisfying any of those criteria. We introduce a remarkable polyhedron that satisfies all of them.

In this article we give, for an arbitrary continuous function which is linear on the octants of an explicit representation in terms of a max–min expression. Moreover, we also consider its representation as the difference of two sublinear functions and determine minimal representations in the sense of Pallaschke and Urbanski [D. Pallaschke and R. Urbanski, Pairs of Compact Convex Sets – Fractional Arithmetic with Convex Sets, Vol. 548, Mathematics and its Applications, Kluwer Academic Publishers, Dordrecht, 2002].

In this article we consider a separation technique proposed in J. Grzybowski, D. Pallaschke, and R. Urbanski (A pre-classification and the separation law for closed bounded convex sets, Optim. Method Softw. 20(2005), pp. 219–229) for separating two convex sets A and B with another convex set C. We prove that in a finite dimension C can be chosen as the Clarke subdifferential at the origin of , where pA , pB denotes the support functions of A and B respectively.

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem. 1This article is dedicated to the memory of Professor Alex Rubinov.

A genetic programming method for solving inverse scattering problems involving cylindrical targets composed of either homogeneous or inhomogeneous dielectrics is presented. Specifically, a tree-shaped chromosome is used to combine convex polygons using either Boolean operations (for homogeneous targets) or an overlapping scheme (for inhomogeneous targets). Convex polygons residing in the terminal nodes of the tree are represented as the convex hull of a variable length list of points. Genetic programming then optimizes the geometry and topology of the target along with all material values. Results show that the method is accurate for a broad class of scattering targets.

In this paper, we determine the cardinality of various subsets of the family of all minimal pairs of compact convex subsets of n (Theorems 2.1 and 2.8). Furthermore, we express minimality properties of a pair of closed bounded convex sets in set-theoretical terms (Theorem 3.3).

In this article, we present an efficient algorithm to determine the convex hull of a finite planar set using the idea of the Method of Orienting Curves (introduced by Phu in Zur Losung einer regula...

For the n-dimensional golden search method used to solve a constrained optimization problem with a bounded closed convex feasible set X in the n-dimensional Euclidean space, one can evaluate the number of computations of the objective values. This evaluation requires, however, a search for a lower bound for the volume of X which is based on elementary geometrical facts. In this connection, one can observe that the closedness condition with respect to X need not be assumed. If we apply the obtained results to an n-simplex S for which every vertex has distance h to the being opposite bounding hyperplane, then S turns out to be a bounded convex set with minimal volume.

We give two generalized Moreau–Rockafellar-type results for the sum of a convex function with a composition of convex functions in separated locally convex spaces. Then we equivalently characterize the stable strong duality for composed convex optimization problems through two new regularity conditions, which also guarantee two formulae of the subdifferential of the mentioned sum of functions. We also treat some special cases, rediscovering older results in the literature. A discussion on the topological assumptions for the vector function used in the composition closes this article.

Several authors have introduced sequential relaxation techniques-based on linear and/or semi-definite programming-to generate the convex hull of 0-1 integer points in a polytope in at most n steps. In this paper, we introduce a sequential relaxation technique, which is based on p-order cone programming (1≤p≤∞). We prove that our technique generates the convex hull of 0-1 solutions asymptotically. In addition, we show that our method generalizes and subsumes several existing methods. For example, when p=∞, our method corresponds to the well-known procedure of Lovasz and Schrijver based on linear programming. Although the p-order cone programs in general sacrifice some strength compared to the analogous linear and semi-definite programs, we show that for p=2 they enjoy a better theoretical iteration complexity. Computational considerations of our technique are discussed.

We refine the reverse convex approach to binary programs into a piecewise convex maximization problem with only two pieces. As a vital lead, we address the multiknapsack problem. The results of computational experiments are presented in contrast with the best known solutions found by heuristics and by the reverse convex approach.

In this paper, some sufficient conditions are derived for nonsmooth r-invexity with respect to Clarke's generalized directional derivatives. Some notions including nearly convex-like mappings and nearly convex sets are used to obtain the results.

The article describes an interior-point method for minimizing a smooth strictly convex function f: Rn → R, , on the convex hull P of m points in Rn . The algorithm uses barycentric coordinates for representing points in P and generates points in P with positive coordinates. In particular, the algorithm can be used to compute the orthogonal projection of a point xc∈ Rn to P. § Dedicated to the memory of Prof. Dr. Franti[sbreve]ek No[zbreve]i[cbreve]ka.

In this paper, we show that the Newton polytope of an observation Y from a two-dimensional hidden Markov model (2D HMM) lies in a three-dimensional subspace of its ambient eight-dimensional space, whose vertices correspond to the most likely explanations ("hidden" states) for Y given the model. For each Newton polytope, there exists a set of "essential" vertices, which form a skeleton for the polytope. All observations in the same orbit (identical under translations, rotations, and transpositions) have the same Newton polytope. Our main conjecture is that the maximal number of vertices of any Newton polytope is of order n 2.

We study the geometrical properties of the convex semi-infinite systems and their solution sets. Our main focus is on those systems enjoying the so-called locally Farkas-Minkowski property. The article provides convex counterparts of some results already proven for linear systems, pointing out the main differences, and finding sufficient conditions for their fulfilment.

We consider the k-cycle polytope which is the convex hull of the incidence vectors of simple cycles of fixed length k in a complete undirected graph. We summarize the previous results of Kovalev, Maurras, Nguyen and Vaxes (Maurras, J.-F., Kovalev, M.M. and Vaxes, Y., 2003, On the convex hull of the 3-cycle of the complete graph. Pesquisa Operacional, 23, 99–109; Maurras, J.-F. and Nguyen, V.H., 2000, The k-cycle polytope: 2. facets, Technical Report 359, Laboratoire d’Informatique de Marseille (LIM), Universite de la Mediterranee; Maurras, J.-F. and Nguyen, V.H., 2001, On the linear description of the k-cycle polytope. International Transactions in Operational Research, 8 673–692 and Maurras, J.-F. and Nguyen, V.H., 2002, On the linear description of the 3-cycle polytope. European Journal of Operational Research, 137, 310–325.), and present new facet classes for the 3-cycle polytope along with a matroid approach to prove that a supporting inequality induces facet. We generalize the regular path inequaliti...

The Sylvester (d+2)-points problem deals with the probability S(K) that d + 2 random points taken from a convex compact subset K of are not the vertices of any convex polytope and asks for which sets S(K) is minimal or maximal. While it is known that ellipsoids are the only minimizers of S(K), the problem of the maximum is still open, unless d = 2. In this article we study generalizations of S(K), which include the Busemann functional – appearing in the formula for the volume of a convex set in terms of the areas of its central sections – and a functional introduced by Bourgain, Meyer, Milman and Pajor in connection with the local theory of Banach spaces. We also show that for these more general functionals ellipsoids are the only minimizers and, in the two-dimensional case, triangles (or parallelograms, in the symmetric case) are maximizers.

This article deals with the problem of packing convex polytopes into a parallelepiped of minimal height. It is assumed that the polytopes are oriented, i.e. rotations are not permitted. A mathematical model of the problem is developed and peculiarities of them are addressed. Based on these peculiarities an exact method to compute local optimal solutions is constructed. This method uses a special modification of the Simplex method. Some examples are also given.

The problem of robust quadratic stabilization for a class of uncertain linear dynamic systems with time-delays in both state and control is discussed in this paper. The uncertain time-delay systems under consideration are described by state differential equations with unknown-but-bounded uncertain parameters that are confined into convex polyhedrons. A new necessary and sufficient condition for the existence of quadratically stabilizing control law and the corresponding synthesis method are derived, the results are given in terms of a set of linear matrix inequalities (LMIs). Finally, numerical examples are presented to demonstrate the effectiveness of the obtained results.

Recursive analytical formulation for calculating the insphere in an irregular convex polyhedron has been developed. Emphasis has been placed on using coordinate geometry so that the geometric theories can be used without much modification. The results have been compared with some simple geometries for which the analytical results are well known. In all cases the results are matched with analytical results up to eight decimal places. The result for one irregular prism is also presented.

Suppose $\langle A_i, \vec{c}_i \rangle$ are planar (convex) H-polyhedra, that is, (unknown variable A_i) \in \mathbb{R}^{n_i \times 2}$ and $\vec{c}_i \in \mathbb{R}^{n_i}$. Let (unknown variable P_i) = \{ \vec{x} \in \mathbb{R}^2 \mid A_i\vec{x} \leq \vec{c}_i \}$ and (unknown variable n) = n_1 + n_2$. We present an (unknown variable O)(n \log n)$ algorithm for calculating an H-polyhedron $\langle A, \vec{c} \rangle$ with the smallest (unknown variable P) = \{ \vec{x} \in \mathbb{R}^2 \mid A\vec{x} \leq \vec{c} \}$ such that (unknown variable P)_1 \cup P_2 \subseteq P$.

In our previous work, a concept "attractive region in strategy investigation" was proposed and it was proven that existence of these "attractive regions" is the essential and sufficient condition for reducing uncertainty. These "attractive regions" can be formed by active inputs based on sensory feedback or by passive inputs from constraints. The "attractive regions" were found and successfully used in three-dimension robotic assembly without force sensors and flexible wrist. Here the concept is successfully used in another important area, part orientation, which is also an essential step in manufacture. The main contribution of this paper includes: (1) the motion region of a general polygon with a flat parallel jaw gripper or a pushing fence is formed by attractive regions, (2) through use of these attractive regions, the algorithm to orient a polygon from arbitrary orientation to a unique orientation without feedback can be deduced straightforward, (3) the motion region of a general convex polyhedron wi...

Let M be the set of all p × q matrices with nonnegative entries and fixed marginals. A matrix in M is an extreme if it cannot be expressed as a convex combination of two distinct matrices in M. Several procedures in categorical data analysis depend on the enumeration of all extremes with given marginals. The problem can be formulated as finding all vertices of a convex polytope for which an efficient algorithm has been developed recently. Because of its general applicability, however, this algorithm does not take advantage of the special combinatorial features inherent in our problem. Here we present an efficient algorithm that does use these features. These extremes have important applications in categorical data analysis in statistics and in the study of probability measures on product spaces with given marginals in mathematics.

We consider the problem of finding minima of convex functions under convex inequality constraints as well as the problem of finding Nash equilibria in n -person constant sum games. We prove that both problems can be solved by algorithms whose basic principles consist of representing the original problems as infinite systems of convex inequalities which, in turn, can be approached by outer projection techniques. Experiments showing how one of these algorithms behaves in test cases are presented and, in context, we describe a numerical method for computing subgradients of convex functions.

We propose to approximate the rank-one convex hull of a function in terms of the maximum number of “levels” permitted in the construction and approximation of the associated laminates. Although this approximation is not new, its understanding in terms of laminates of a maximum number of levels leads to the establishment of an exponential error estimate.

We give a parametrization for crystal bases of Demazure modules as a set of lattice points in some convex polytope and we also describe explicitly the extremal vectors as solutions of some system of linear equations.

This paper describes two new, mathematical programming-based approaches for evaluating general, one- and two-sidedp-variate normal probabilities where the variance-covariance matrix (of arbitrary structure) is singular with rankr(r

The monomial initial ideals of a graded polynomial ideal are in bijection with the vertices of a convex polytope known as the state polytope of the ideal. The Gröbner fan of the ideal is the normal fan of its state polytope. In this paper we present a software system called TiGERS (Toric Gröbner bases Enumeration by Reverse Search) for computing the Gröbner fan of a toric ideal by enumerating the edge graph of its state polytope. The key contributions are an inexpensive algorithm for local change of Gröbner bases in toric ideals and the identification of a reverse search tree on the vertices of the state polytope. Using these ideas we obtain a combinatorial Gröbner walk procedure for toric ideals. TiGERS has been used to compute state polytopes with over 200,000 vertices.

This paper presents a new fast algorithm to compute the twodimensional inclusion test of a point in the convex hull of a set of points, without computing the convex hull. The algorithm is based on the classification of the points in octants of the plane. This classification step for each point requires only simple test operations, and makes the algorithm run in at worst, O(ns). For point sets larger than 11 points, the proposed algorithm is faster than other known approaches. The paper includes a practical evaluation of the algorithm, comparing it with several previously known approaches.

We continue the study, begun by the first author, of linear-invariant families in . We obtain the unexpected result that the Cayley transform (the analogue of the half-plane mapping in the complex plane) does not give the maximum or minimum distortion among all mappings of the unit ball of n≥ 2, onto convex domains. In addition a result analogous to that of Pommerenke that a linear invariant family has order 1 (the smallest possible order) if and only if it consists of convex mappings of the disk does not hold for the ball in n≥ 2. Finally, we extend these ideas to the polydisk in . The theory for this case bears some similarity to the theory for the ball but there are some striking differences as well. For example it is true that the family of convex holomorphic mappings of the polydisk in has minimum order (which is nin this case) but it is not true that for n>1 every linear-invariant family of minimum order consists of convex mappings.

It is well-known that the solution set of an interval linear equation system is a union of convex polyhedra the number of which increases, in general, exponentially with the problem size. As a consequence, the problem of finding the interval hull of the solution set is NP-hard as J. Rohn and V. Kreinovich proved in [13]. The purpose of this paper is to show that the solution set analysis can be simplified substantially provided the rank of the error matrix is restricted even if the assumption of interval character of data errors is replaced by a more general one. Especially, in the case of a rank-one error matrix we have to look into at most two convex subsets. Besides, a dual approach to describing the solution set is discussed. The original version of this approach was suggested in [7].

Let q be a complex number with The q-numerical range of an n× ncomplex matrix Ais defined by Nakazato gave a complete description for the q-numerical range of normal matrices. We refine his result, and consider its extension to convex matrices, i.e., matrices Afor which W(1:A) equals to the convex hull of the spectrum of A.

Separation theorem is a basic theorem of convex analysis and convex programming. Its applicability to nonlinear programming methods depends on whether we can also describe a separating hyperplane of two or more convex sets. In this article the results obtained for two convex polytopes are extended to the case of two convex polyhedra, to the case of a convex polytope and a convex polyhedron, and further to the case of a finite number of convex polyhedral sets. In the courbe of solving the problem it was derived also an implicit representation of the convex hull of a finite number of collvex polyhedral sets and a simple necessary and sufficient condition for the emptiness of the intersection of the interiors of two n-dimensional convex polyhedral sets

We consider the difference equation where the coefficients bi are functions of the parameter vector p belonging to a convex polytope P in the parameter space. The purpose of this paper is to present general conditions for oscillation of all solutions of the difference equation for each p in P, which involve only the vertices of P. The oscillation property is established using Ladas theorem and testing positivity of vertex polynomials via the Modified Routh Array

A calculation of all separating hyperplanes of two convex polyhedral sets (polytopes and polyhedra), which are for them also the supporting ones, is dealt with in this article. In the theory of optimization this means of find all linear objective functions, which attain simultaneously their minimum over one and their maximum over the other one of two feasible sets. The feasible sets, which are described by a finite number of linear inequalities, can be bounded or unbounded, but they can have at most boundary points in common. Using the derived theory we try to find an approximate solution of a special nonlinear programming problem.

This paper describes computational experience obtained in the development of the Irs code, which uses the reverse search technique to solve the vertex enumeration/convex hull problem for d-dimensional convex polyhedra. We give empirical results showing improvements obtained by the use of lexicographic perturbation, lifting, and integer pivoting. We also give some indication of the cost of using extended precision arithmetic and illustrate the use of the estimation function of Irs.The empirical results are obtained by running various versions of the program on a set of well-known non-trivial polyhedra: cut, configuration, cyclic, Kuhn-Quandt, and metric polytopes.

We define here the counterpart of Jensen convex and anti-convex sets of real numbers for the case of languages. We investigate the existence of languages consisting only of strings in which a set of symbols is convex or anti-convex, as well as the place of such languages in Chomsky hierarchy. Local convexity is also briefly investigated.

A calculation of all hyperplanes, which are supporting simultaneously for two convex polyhedral sets lying in the same halfspace (corresponding to such hyperplane) is dealt with in this article. In the theory of optimization this means to find every linear objective function, which attains the same maximum (or minimum) simultaneously over two feasible sets. The feasible sets are described by a finite number of linear inequalities, can be bounded or unbounded, and none of them can be a subset of the other one. Using the derived theory we try to find an approximate solution of a special nonlinear programming problem.

The divide-and-conquer algorithm for constructing three-dimensional convex hulls is implemented in a numerically robust manner. The approach taken here is a topology-oriented approach, in which the topological consistency is considered more important than the result of numerical computation. This is the first implementation of the divide-and-conquer algorithm for the three-dimensional convex hull using the topology-oriented approach. Implementation details are described together with computational experiments.