2006年1月
Minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities
JOURNAL OF GLOBAL OPTIMIZATION
- ,
- 巻
- 34
- 号
- 1
- 開始ページ
- 1
- 終了ページ
- 14
- 記述言語
- 英語
- 掲載種別
- DOI
- 10.1007/s10898-005-3883-8
- 出版者・発行元
- SPRINGER
In this paper, we will propose algorithms for calculating a minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities. If we know all vertices of the polytope and its cardinality is not very large, we can solve the problem in an efficient manner by a number of existent algorithms. However, when the polytope is defined by linear inequalities, these algorithms may not work since the cardinality of vertices may be huge. Based on a fact that vertices determining an ellipsoid are only a fraction of these vertices, we propose algorithms which iteratively calculate an ellipsoid which covers a subset of vertices. Numerical experiment shows that these algorithms perform well for polytopes of dimension up to seven.
- リンク情報
- ID情報
-
- DOI : 10.1007/s10898-005-3883-8
- ISSN : 0925-5001
- Web of Science ID : WOS:000234144900001