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
Academic Journal
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

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics