整凸関数におけるL拡張可能性に関する一考察

DOI

書誌事項

タイトル別名
  • A study on L-extendability of integrally convex functions

説明

<p>整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とし，その準備となる証明を行った．具体的には，まず，半整数格子点上で整凸関数と同様の性質を持つ関数，半整凸関数を新たに定義する．そして，整凸関数が半整凸関数に緩和できる条件や，半整凸関数がL凸性を満たす条件を調べる．さらに，これらを利用することで，整凸関数がL拡張可能である条件を明らかにするための方向性を示す．</p>

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390015333244489088
  • DOI
    10.11517/pjsai.jsai2023.0_2j4gs102
  • ISSN
    27587347
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ