[1F3-GS-1] 基礎・理論：

[1F3-GS-1-02] 混合整数線形計画の逆問題におけるSuboptimality損失と予測損失の等価性

〇北岡 旦¹、江藤 力¹ (1. 日本電気株式会社)

キーワード：数理最適化、逆最適化、組合せ最適化

この論文は多目的最適化に対する逆最適化問題(IOP)を扱う．この問題は例えばシフトスケジューリングでどの観点を重要視しているかを見つける問題である．従来の手法だと，凸計画のIOPに対する効率的な解法は存在するが，混合整数線形計画(MILP)における逆問題には，2乗誤差，つまり，予測損失を0にする効率的な方法が存在しなかった．本論文では，MILPにおける予測損失を効果的に最小化するために，suboptimality損失の劣勾配が消滅すること予測誤差が消滅することが同値であることを示し，凸であるSuboptimality損失の最小化問題に帰着せせる．これにより，MILPにおいて，kを射影劣勾配法の更新回数としたとき，あるγ,ε>0が存在して，殆ど至る所の真の重みで，真の重みと学習の重みの誤差をO(exp(-γk^1/2 +(1/ε²)log k ))で評価できることと有限回の更新で予測損失を消滅できることを示す．数値実験でもこれらを確認する．