arXiv cs.LG

逐次ミニマックス最適化によるバイレベル最適化の解法

Solving bilevel optimization via sequential minimax optimization

http://arxiv.org/abs/2511.07398v1


この記事では、制約付きバイレベル最適化問題を解決するための逐次ミニマックス最適化(SMO)手法を提案しています。下位レベルは滑らかでない凸最適化問題であり、上位レベルは非凸最適化問題かもしれません。具体的には、SMOは、バイレベル最適化問題に対して修正された拡張ラグランジアンとペナルティ方式のハイブリッドを用いて得られる一連のミニマックスサブ問題を解決するために第一種の手法を適用します。適切な条件の下で、SMOが凸および強凸の下位レベル目的関数に対して epsilon-KKT解を求める際の操作の複雑さを$O( epsilon^{-7} ext{log} epsilon^{-1})$や$O( epsilon^{-6} ext{log} epsilon^{-1})$と確立しました。この結果は、以前の最良の操作複雑さを epsilon^{-1}倍改善します。初期の数値結果は、最近開発された第一種ペナルティ手法と比較して、顕著に優れた計算性能を示しています。