離散凸解析の研究

离散凸分析研究

• 批准号: 09874046
• 负责人: 室田 一雄
• 金额: $ 0.64万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09874046/
• 关键词: 離散最適化; 凸解析; マトロイド; アルゴリズム; 双対定理

マトロイドの公理を拡張することにより,整数格子点上で定義された整数値をとる関数に対して離散凸関数とでも呼ぶべき概念が得られることが,本研究の開始時に明らかになっていた.連続世界の凸解析におけるルジャンドル変換の離散版を導入することによって,整数格子点上で定義された整数値関数に対して共役関数の概念が定義され,これによって,離散凸関数はM凸性,L凸性といういわば表と裏(数理計画の用語ではprimalとdual)の姿をもつ,M凸性は交換公理の拡張により,また,L凸性は劣モジュラ性の拡張により特徴付けられる.本研究では,以下の結果を得た.1.L凸集合の多面体的な特徴付けを与えた.とくに,L凸集合が三角不等式を満たす距離関数と同等であることを示した.これは,M凸集合が劣モジュラ不等式を満たす集合関数と同等であるという(既知の)事実に対応する結果である.M凸関数の実効定義域は基多面体であるが,これを,一般化ポリマトロイドの場合に定式化し直したものはM^〓凸関数と呼ばれる(M凸関数の射影がM^〓凸関数である).これに共役な操作(制限)をL凸関数に施したものをL^〓凸関数と名付け,その性質を調べた.これによって,従来の関連研究との関係が明らかとなった.とくに,L^〓凸関数がFavati-Tardellaによる整凸関数に一致すること,離散中点凸性により特徴付けられることを示した.3.M凸関数,L凸関数に関する離散双対定理の原証明は,M凸関数に対して構成的に最適双対変数を与え,L凸関数に対してはその共役をとるという形であった.本研究では,M凸関数とL凸関数に関して,独立に多面体的な別証明を見いだした.その結果,整多面体と離散凸関数の関係が明確になった.

在这项研究开始时就很清楚，通过扩展拟阵公理，对于采用整数网格点上定义的整数值的函数，可以得到一个可以称为离散凸函数的概念。连续世界凸分析中的勒让德变换，对于整数网格点上定义的整数值函数定义了共轭函数的概念，由此离散凸函数具有M凸性，即所谓的L凸性表M-凸性，其形式为back（数学规划术语中的原数和对偶），其特征在于交换公理的扩展，L-凸性的特征在于子模性的扩展。 1.L凸集合的获得。特别地，我们证明了 L 凸集等价于满足三角不等式的距离函数，这意味着 M 凸集等价于满足子模不等式的集合函数。这确实是一个相应的结果。M凸函数的有效域是基多面体，但在广义多拟阵的情况下重新表述的称为M^〓凸函数（M凸函数的投影）。是M^〓凸函数）。我们通过对L凸函数应用共轭运算（限制）来命名L凸函数，并研究其性质。结果，与先前相关研究的关系变得清晰。特别是，L凸函数^〓凸函数为法瓦蒂-塔我们证明它对应于 rdella 的良凸函数，并且具有离散中点凸性 3。M 凸函数和 L 凸函数的离散对偶定理的原始证明对于 M 凸函数是构造性的。最优双变量好吧，对于一个L-凸函数，我们取了它的共轭。在这项研究中，我们找到了M-凸函数和L-凸函数的另一个独立的多面体证明。由此，我们发现了多面体和离散多面体凸之间的关系功能已经明确。