有向マトロイドの代数幾何的実現可能性解析とその離散最適化への展開

点击翻译按钮获取中文摘要

本研究では、昨年度に行ったSDP緩和を用いて解く手法を適用する手法を発展させ、以下の通りの研究を行った。1.有向マトロイドの実現可能性をPOPを解くことで判定する手法について、SDP緩和問題から得られる解をより安定させるための研究を行った。具体的にはスケーリングやSDP緩和をよりタイトなものとすることで、今までは求められていなかった有向マトロイドに対して、新たにその実現可能性を示した。2.POPの許容解を求めることで実現可能性を示す手法に加え、解が存在しないことを示す「実現不可能性」の立場からもPOPを用いたアプローチを行った。この手法は、SDP緩和問題の双対問題に着目したものであるが、これによって列挙された実現不可能な有向マトロイドは、今までのところすべて既存の手法である双二次最終多項式(BFP)によっても判別可能なものであることを確かめた。3.POPとして定式化された多項式系に着目し、興味深い有向マトロイドの例を列挙した。具体的には、(1)ランクが4の有向マトロイドで有理表現を持たないものを、3次元中の点の配置として得た。(2)従来から知られていた平面上の「Pappusの配置」を、一般のランクrの場合について拡張を行った。