DETERMINATION OF EDGES OF A CONVEX POLYTOPE

Yıl 2011, Cilt: 1 Sayı: 2, 117 - 128, 04.07.2011

Taner Büyükköroğlu

Öz

In this paper, the problem of determination of the edges of a convex polytope is considered. It is shown that this problem is equivalent to the standard linear programming problem and therefore can be solved by the simplex method. Further, for a special type of polytopes which are an affine transformation of a box we show that extremal points determine edges

Anahtar Kelimeler

-

Teorik Bilimler

Öz

Bu çalışmada, konveks bir politopun kenarlarının belirlenmesi problemi ele alınmıştır. Bu problemin, simpleks yöntemiyle çözülebilen bir standart lineer programlama problemine denk olduğu gösterilmiştir. Ayrıca, bir kutunun afin dönüşüm altındaki görüntüsü olan özel politoplar için uç noktaların, politopun kenarlarını belirlediği gösterilmiştir

Anahtar Kelimeler

Politoplar, Uç nokta, Kenar, Kenar Teoremi

Kaynakça

• Barmish, B.R. (1994). New Tools for Robustness of Linear Systems, MacMillan, New York.
• Bartlett, A.C., Hollot, C.V. and Huang, L. (1988). Root locations of an entire polytope of polynomials: It suffices to check the edges, Mathematics of Control, Signals and Systems 1, 61-71.
• Bhattacharyya, S.P., Chapellat, H. and Keel, L.H. (1995). Robust Control: The Parametric Approach , Prentice Hall, New Jersey.
• Dullá, J.H., Helgason, R.V. and Hickman, B.L. (1992). Preprocessing schemes and a solution method for the convex hull problem in multidimensional space, in: O. Balci (ed.), Computer Science and Operations Research: New Developments in their Interfaces, Pergamon, Oxford.
• Dullá, J.H. and Helgason, R.V. (1996). A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space, European Journal of Operational Re- search 92, 352-367.
• Fukuda, K. (2004). From the zonotope construction to the Minkowski addition of convex polytopes, Journal of Symbolic Computation 38, No. 4, 1261-1272.
• Grünbaum, B. (2003). Convex Polytopes, Springer, New York.
• Murty, K.G. (2009). A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes, Optim. Lett., 3, No. 2, 211-237.
• Papadimitriou, C.H. and Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexi- ty, Dover, New York.
• Pujara, L.R. and Bollepalli, B.S. (1994). On the geometry and stability of a polytope generated by a finite set of polynomials, American Control Conference, Baltimore, 236-237.
• Rockafellar, R.T. (1970). Convex Analysis, Princeton Univ. Press, Princeton NJ.
• Rosen, J.B., Xue, G.L. and Philips, A.T. (1992). Efficient computation of extreme points of convex hulls in R North-Holland, Amsterdam, 267-292.
• Stoer, J. and Witzgall, C. (1970). Convexity and Optimization in Finite Dimensions, Springer-Verlag, Berlin.
• Wallace, S.W. and Wets, R.J.B. (1995). Preprocessing in stochastic programming: The case of capaci- tated networks, ORSA Journal on Computing, 7, No. 1, 44-62.
• Wets, R.J.B. and Witzgall, C. (1967). Algorithms for frames and linearity spaces of cones, Journal of Research of the National Bureau of Standards, B Mathematics and Mathematical Physics , 71B, 1-7.
• Ziegler, G.M. (2006). Lectures on Polytopes, Springer.