1．は　じ　め　に

　離散凸解析とは，整数格子点上で定義された離散凸関数の理論体系である．数学的な理論である離散凸解析は一見，本会で扱われる研究分野とは余り関係ないように見えるかもしれないが，意外と身近な存在である．歴史をたどると，離散凸解析はマトロイド理論を基にして発展しており，1960年代以降に盛んに行われたグラフ理論による回路網解析の研究^(1)～(4)と深いつながりがある．実際，離散凸解析の理論が1990年代に室田によって提唱されたきっかけの一つは，回路網を含む線形システムに対する新たな解析手法の研究である⁽⁵⁾．本稿では，読者の皆さんに，離散凸解析の理論をより身近に感じてもらうことを目指し，オークション・画像処理・物流という様々な研究分野と離散凸解析とのつながりについて解説する．

　その名前から分かるように，離散凸解析は凸解析の離散版と位置付けられる．連続変数に関する最適化の分野では，集合や関数に対する凸性が良い性質であると認識されており，凸集合・凸関数に関する理論体系が凸解析である⁽⁶⁾．凸解析の理論は，連続最適化問題のアルゴリズム構築における数学的な基盤をなすとともに，多彩な研究分野において応用されている．

　一方，離散凸解析は整数変数に関する最適化問題に対する理論体系である^(7)～(10)．離散凸解析では，凸関数と凸関数の2種類の離散凸関数を軸に理論が構築され，離散凸関数に関する最適化問題に対して様々なアルゴリズムが提案されている．その結果，離散凸性を持つ離散最適化問題は「解きやすい」問題であると認識されている．また，離散凸解析の応用先は現在，工学・情報科学・経済学などの様々な分野へ広がりつつある．

　本稿では，離散凸解析における基本的な問題である「凸関数の最小化」を取り上げ，この問題を通じて離散凸解析と他分野とのつながりを説明する．まず，凸関数の定義を述べた後に，その最小化に関する基本的な定理とアルゴリズムを紹介する．その後，様々な研究分野で現れる凸関数最小化の例として，

 （ⅰ）オークションにおける均衡価格の計算

 （ⅱ）画像処理におけるエネルギー最小化

 （ⅲ）物流における最小費用フローの計算