MISC

2006年1月

Minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities

JOURNAL OF GLOBAL OPTIMIZATION
  • JY Gotoh
  • ,
  • H Konno

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.

リンク情報
DOI
https://doi.org/10.1007/s10898-005-3883-8
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000234144900001&DestApp=WOS_CPL
ID情報
  • DOI : 10.1007/s10898-005-3883-8
  • ISSN : 0925-5001
  • Web of Science ID : WOS:000234144900001

エクスポート
BibTeX RIS