数理計画法における離散凸性の研究

1.付値マトロイドの公理を拡張することにより,整数格子点上で定義され整数値をとる関数に対して,離散凸関数とでも呼ぶべき概念が得られることが,本研究の開始時に明らかになっていたが,連続世界の凸解析におけるルジャンドル変換の離散版を導入することによって,整数格子点上で定義された整数値関数に対して共役関数の概念を導入した.これによって,離散凸関数は,いわば表と裏(数理計画の用語では,primalとdual)の姿をもつことになった.離散凸関数の表の姿をM凸性,裏の姿をL凸性と名付け,M凸性を交換公理を拡張することにより特徴付け,L凸性を劣モジュラ性を拡張することにより特徴付けた.2.M凸関数の実効定義域は基多面体であるが,これを,一般化ポリマトロイドの場合に定式化し直した.基多面体と一般化ポリマトロイドは,ある意味で等価な概念であることは知られている事実であるから,これは一種の翻訳作業ということになるが,これによって,Camerini-Conforti-NaddefやFavati-Tardellaなどによる従来の関連研究との関係が明らかとなった.3.離散凸関数の最小化のアルゴリズムについて,ある程度の進展があった.L凸関数がFavati-Tardellaの考察した関数の族に含まれることが分かり,彼らのアルゴリズムによってL凸関数が最小化できる.ただし,これは楕円体法を基礎としているので,純粋に組合せ的とは言い難いアルゴリズムである.一方,M凸関数の最小化については,その性質を巧みに使った組合せ的なアルゴリズムを開発できた.このアルゴリズムの計算量や有効性については、今後,直ちに調べる予定である.

1.付値マトロイドの公理を拡張することにより,整数格子点上で定義され整数値をとる関数に対して,離散凸関数とでも呼ぶべき概念が得られることが,本研究の開始時に明らかになっていたが,連続世界の凸解析におけるルジャンドル変換の離散版を導入することによって,整数格子点上で定義された整数値関数に対して共役関数の概念を導入した.これによって,離散凸関数は,いわば表と裏(数理計画の用語では,primalとdual)の姿をもつことになった.離散凸関数の表の姿をM凸性,裏の姿をL凸性と名付け,M凸性を交換公理を拡張することにより特徴付け,L凸性を劣モジュラ性を拡張することにより特徴付けた.2.M凸関数の実効定義域は基多面体であるが,これを,一般化ポリマトロイドの場合に定式化し直した.基多面体と一般化ポリマトロイドは,ある意味で等価な概念であることは知られている事実であるから,これは一種の翻訳作業ということになるが,これによって,Camerini-Conforti-NaddefやFavati-Tardellaなどによる従来の関連研究との関係が明らかとなった.3.離散凸関数の最小化のアルゴリズムについて,ある程度の進展があった.L凸関数がFavati-Tardellaの考察した関数の族に含まれることが分かり,彼らのアルゴリズムによってL凸関数が最小化できる.ただし,これは楕円体法を基礎としているので,純粋に組合せ的とは言い難いアルゴリズムである.一方,M凸関数の最小化については,その性質を巧みに使った組合せ的なアルゴリズムを開発できた.このアルゴリズムの計算量や有効性については、今後,直ちに調べる予定である.