Year 2011,
Volume: 1 Issue: 2, 117 - 128, 04.07.2011
Abstract
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
Keywords
References
- 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.
Year 2011,
Volume: 1 Issue: 2, 117 - 128, 04.07.2011
Abstract
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
Keywords
References
- 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.
There are 16 citations in total.
Details
| Primary Language | English |
|---|---|
| Journal Section | Articles |
| Authors | |
| Publication Date | July 4, 2011 |
| Published in Issue | Year 2011 Volume: 1 Issue: 2 |
