多面体描画ツールglipoのご紹介

はじめに

本記事は数理最適化 Advent Calendar 202220日目の記事です。最近作った多面体の描画ツールglipoを紹介します。また、glipoの活用例として、線形相補性問題の多面体を眺めてみます。

glipo

glipoのサンプル動画

数理最適化erのみなさんは、実行可能領域の多面体がどんな形なのか、どんな特徴を持つのかに興味をお持ちかと思います。特に、出来合いの多面体を描画するだけでなく、形を動かしながら、良い特徴を持つ多面体を探しているのではないでしょうか?(簡単に解を計算できる、解の個数に特徴がある、など。)

一方で、三次元図形をただ描画するツールはあっても、インタラクティブに図形を動かせるツールは限られています。(私の知る限りgeogebraしかありません。)また、そのようなツールを使っても、数理計画問題で扱う形式の多面体をインタラクティブに動かすには、一手間も二手間もかかります。

glipoは数理最適化問題で扱う形式の多面体に特化して作成しやすいように設計された多面体作成ツールです。ぜひみなさんが扱っている多面体をglipoで可視化してみてください!そして良い特徴を持つ多面体を探してみてください!使い方はこちらからご確認ください。

では、glipoの活用例として、線形相補性問題の多面体を眺めてみます。

線形相補性問題

数理最適化erであっても、馴染みのない方がいらっしゃいますと思いますので、まずは線形相補性問題の定義を紹介します。

線形相補性問題(Linear Complementarity Problem; LCP)とは、以下で定義される数理最適化問題です。(この定義は表現力の高い形式で書かれており、一般的な定義とは異なることをご了承ください。)


 \displaystyle
\begin{align}
\begin{matrix}
\text{find} & x & \\
\text{subject to}
& y_{ij} = a_{ij}^\top x + b_{ij} \geq 0 & (1) \\
& \prod_{j} y_{ij} = 0 & (2)
\end{matrix}
\end{align}


ここで、i \in \{ 1, ..., n \}, j \in \{ 1, ..., m_i \}は添え字、 a_{ij} \in \mathbb{R}^{n}, b_{ij} \in \mathbb{R}は所与、 x \in \mathbb{R}^n, y_{ij} \in \mathbb{R}は変数です。

正確には、条件を満たす解を探す問題であり、「最適化」問題ではないです。ただ、最適化問題を含む広い問題クラスであることが知られています。LCPについては、以前に書いたこちらの記事も読んでいただけると嬉しいです。

(1)は実行可能性条件、(2)は相補性条件と呼ばれています。実行可能性条件を構成する制約式は線形ですので、これを満たす点の集合は多面体を構成しています。したがって、LCPとは、多面体の中で相補性条件を満たす点を探す問題となります。

ここで、相補性条件を幾何の言葉に置き換えておきます。相補性条件は、各 iに対して、 y_{i1}, ..., y_{i m_i}のいずれかが 0であることと同値です。これを幾何的に解釈すると、解が y_{i1} = a_{i1}^\top x + b_{i1} = 0, ..., y_{i m_i} = a_{i m_i}^\top x + b_{i m_i} = 0のいずれかの超平面上に乗っていることを意味しています。

したがって、LCPの解とは、多面体上の点のうち、すべての iのいずれかの超平面上にある点のことです。

LCPの多面体の可視化

言葉での説明だけでは分かりにくいと思いますので、早速glipoを使って、LCPの多面体を可視化し、どのような点がLCPの解になるのかを見てみましょう。 iは面の色で表しています。適当に多面体を作って、各面に色を付けてみます。(色を付ける機能はまだgithubには説明がありません。点を選択した状態で1,2,3の数字を選択することで変更できます。)

LCPの多面体の可視化

すべての色の面が重なっている点(赤点)がLCPの解です。このように、可視化することで理解が深まるということはよくあることかと思います。

解の個数の変化

glipoでは多面体の面を自由に移動できるので、面が移動したときに、解がどのように変化するのかを調べることができます。このメリットを使って、LCPの解の個数の変化を見てみましょう。LCPの面白い性質の一つに、(特殊な条件を除き、)面の傾き( a_{ij})を固定したときに、面の位置( b_{ij})をどんなに変えても、解の個数の偶奇は変わらない、というものがあります。例えば、特定の b_{ij}で解の個数が偶数(奇数)であるとすると、 b_{ij}をどんなふうに変えても、解の個数は偶数(奇数)となるのです。

先ほどのケースの続きで、このことを確かめてみましょう。(解がきれいに配置されるように位置を若干調整しています。これが気軽にできるのもglipoの良さ!)先ほどのケースでは解は7個でしたので、どんなに面の位置を変えても解の個数は奇数になるはずです。では、いろいろと試してみましょう。(時間の都合で一つの面しか動かせませんでした。。)

解の個数の変化

面の位置を移動すると、解が移動したり、消えたり、増えたりしますが、個数が奇数で保たれていることが見えました。さらに、解の変化の様子を見ていくことで、解の偶奇が変わらないのは、解が増える(減る)ときに、2個ずつ増える(減る)からだ、ということも分かりました。(実際、この性質の証明ではこの性質を使っています。)このようなことを確認できるのは、インタラクティブな描画ツールならではかと思います。

おわりに

数理最適化では他にも多面体を図示することで理解が深まるテーマがたくさんあります。特に、線形計画問題に対するシンプレックス法に関するテーマで力を発揮するのではと思います。シンプレックス法の挙動を確認したり、シンプレックス法(の特定のピボット規則)で最悪計算時間のインスタンスとして知られるKlee-Minty cubeなどを図示したりするなどです。みなさまの勉強・研究で役立つことがありましたら、とても幸せです。

おまけ

もともとglipoはLCPの多面体を見るために開発したツールでして、解の個数以外にもたくさんの性質をglipoを使って調べることができます。glipoで遊ぶおもちゃとして、いくつかネタを記載しておきます!

  • 任意の b_{ij}で実行可能解が存在する a_{ij}がある
  • 任意の b_{ij}で解が存在する a_{ij}がある
  • 任意の b_{ij}で解が唯一となる a_{ij}がある
  • 任意の b_{ij}で解が存在&個数が偶数となる a_{ij}がある