Yıl 2011,
Cilt: 1 Sayı: 2, 117 - 128, 04.07.2011
Ö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
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.
Yıl 2011,
Cilt: 1 Sayı: 2, 117 - 128, 04.07.2011
Ö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
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.
Toplam 16 adet kaynakça vardır.
Ayrıntılar
| Birincil Dil | İngilizce |
|---|---|
| Bölüm | Araştırma Makalesi |
| Yazarlar | |
| Yayımlanma Tarihi | 4 Temmuz 2011 |
| Yayımlandığı Sayı | Yıl 2011 Cilt: 1 Sayı: 2 |
