[2J4-GS-1] 基礎・理論

[2J4-GS-1-02] 整凸関数におけるL拡張可能性に関する一考察

〇横山 健¹、木村 慧¹、横尾 真¹ (1. 九州大学)

キーワード：離散凸解析、整凸関数、L拡張可能性、半整数緩和

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