2022-05-24T09:37:19Z
https://tsukuba.repo.nii.ac.jp/oai
oai:tsukuba.repo.nii.ac.jp:00000347
2022-04-27T08:23:19Z
3:2658:2659
Minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities
後藤, 順哉
今野, 浩
Gotoh, Junya
Konno, Hiroshi
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.
research report
2003
application/pdf
http://hdl.handle.net/2241/842
https://tsukuba.repo.nii.ac.jp/record/347/files/1.pdf
jpn
Institute of Socio-Economic Planning discussion paper series ~ no. 1065