TITLE

# Algorithms for the Frame of a Finitely Generated Unbounded Polyhedron

AUTHOR(S)
Dulá, José H.; López, Francisco J.
PUB. DATE
January 2006
SOURCE
INFORMS Journal on Computing;Winter2006, Vol. 18 Issue 1, p97
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
Consider two finite sets A and V of points in m-dimensional space. The convex hull of A and the conical hull of V can be combined to create a finitely generated unbounded polyhedron. We explore the geometry of these polyhedral sets to design, implement, test, and compare two different algorithms for finding the frame, a minimal-cardinality subset of A and V , that generates the same polyhedron. One algorithm is a naive approach based on the direct application of the definition of these sets. The second algorithm is based on different principles erecting the frame geometrically one element at a time. Testing indicates that the second algorithm is faster with the difference becoming increasingly dramatic as the cardinality of the sets A and V increases and frame density decreases.
ACCESSION #
20371578

## Related Articles

• Adaptive FEM and a posteriori error control for stationary coupled bulk-surface PDEs. Eigel, Martin; Müller, Rüdiger // PAMM: Proceedings in Applied Mathematics & Mechanics;Oct2016, Vol. 16 Issue 1, p755

We consider a system of two coupled elliptic equations, one defined on a bulk domain and the other one on the boundary surface. The numerical error of the finite element solution can be controlled by a residual a posteriori error estimator which takes into account the approximation errors due to...

• Global infimum of strictly convex quadratic functions with bounded perturbations. Hoang Xuan Phu; Vo Minh Pho // Mathematical Methods of Operations Research;Oct2010, Vol. 72 Issue 2, p327

The problem of minimizing $${\tilde f=f+p}$$ over some convex subset of a Euclidean space is investigated, where f( x) = x Ax + b x is strictly convex and | p| is only assumed to be bounded by some positive number s. It is shown that the function $${\tilde f}$$ is strictly outer ?-convex for any...

• Closedness of a Convex Cone and Application by Means of the End Set of a Convex Set. Hu, Hui; Wang, Qing // Journal of Optimization Theory & Applications;Dec2011, Vol. 151 Issue 3, p633

This article presents new conditions that ensure the closedness of a convex cone in terms of the end set and the extent of its generator. The results significantly extend the classic condition. The new closedness conditions are utilized to obtain a simple formula of the least global error bound...

• On degeneracy in linear programming and related problems. George, Karen; Osborae, M. R. // Annals of Operations Research;1993, Vol. 46/47 Issue 1-4, p343

Methods related to Wolfe's recursive method for the resolution of degeneracy in linear programming are discussed, and a nonrecursive variant which works with probability one suggested. Numerical results for both nondegenerate problems and problems constructed to have degenerate optima are...

• A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527

In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch...

• DCA based algorithms for multiple sequence alignment (MSA). Le Thi, Hoai; Pham Dinh, Tao; Belghiti, Moulay // Central European Journal of Operations Research;Sep2014, Vol. 22 Issue 3, p501

In the last years many techniques in bioinformatics have been developed for the central and complex problem of optimally aligning biological sequences. In this paper we propose a new optimization approach based on DC (Difference of Convex functions) programming and DC Algorithm (DCA) for the...

• A regularized simplex method. Fábián, Csaba; Eretnek, Krisztián; Papp, Olga // Central European Journal of Operations Research;Dec2015, Vol. 23 Issue 4, p877

In case of a special problem class, the simplex method can be implemented as a cutting-plane method that approximates a polyhedral convex objective function. In this paper we consider a regularized version of this cutting-plane method, and interpret the resulting procedure as a regularized...

• A SUPERLINEARLY CONVERGENT ALGORITHM FOR ONE-DIMENSIONAL CONSTRAINED MINIMIZATION PROBLEMS WITH CONVEX FUNCTIONS. Mifflin, Robert // Mathematics of Operations Research;May83, Vol. 8 Issue 2, p185

This paper presents a globally and superlinearly convergent algorithm for solving one-dimensional constrained minimization problems involving (not necessarily smooth) convex functions. The constraint is handled by what can be interpreted as a new type of penalty method. The algorithm does not...

• ON THE EQUIVALENCE BETWEEN SOME DISCRETE AND CONTINUOUS OPTIMIZATION PROBLEMS. Tardella, Fabio // Annals of Operations Research;1990, Vol. 25 Issue 1-4, p291

The simplex algorithm for linear programming is based on the well-known equivalence between the problem of maximizing a linear function Æ’ on a polyhedron P and the problem of maximizing Æ’ over the set VP of all vertices of P. The equivalence between these two problems is also exploited...

Share