適応的ステップサイズを用いた制約付き最適化のためのランダム化実行可能性手法

TL;DR（結論）

多数の凸関数が交差する複雑な制約条件下での最適化において、計算コストの高い射影操作を回避しつつ、ランダム化された実行可能性更新と適応的ステップサイズを統合した新しいアルゴリズムを提案しました。 強凸かつ平滑な目的関数に対しては任意の許容誤差までの線形収束を証明し、非平滑な凸関数の場合には問題固有のパラメータを一切必要としない「パラメータフリー」な設定で、理論的に最適な収束レートを達成することを数学的に実証しました。 二次制約付き二次計画問題（QCQP）やサポートベクターマシン（SVM）を用いた数値実験により、提案手法は既存の最先端アルゴリズムと比較して、ハイパーパラメータの調整なしに優れた計算効率と制約遵守能力を発揮することが確認されました。

なぜこの問題か

現代の意思決定プロセスにおいて、制約付き最適化問題は機械学習、金融工学、エネルギーシステム、制御理論など、多岐にわたる分野で中心的な役割を果たしています。例えば、機械学習ではモデルの公平性や堅牢性を確保するために複雑な制約を課す必要があり、金融分野では予算やリスクの限界を考慮したポートフォリオ最適化が求められます。これらの制約は通常、複数の凸関数の下位レベル集合の共通部分として表現されますが、制約の数（$m$）が膨大になると、制約集合全体への射影を計算するためのコストが指数関数的に増大し、実用的な時間内での解決が困難になります。 既存の手法であるADMM（交互方向乗数法）やペナルティ法、バリア関数法などは、大規模な問題に対して一定の成果を上げてきましたが、いくつかの重大な欠点があります。第一に、これらの手法は収束性能を左右するハイパーパラメータの調整に極めて敏感であり、適切な設定を見つけるために膨大な試行錯誤を必要とします。第二に、各反復ステップで複雑な副問題を解く必要があるため、計算リソースの消費が激しく、リアルタイム性が求められるアプリケーションには不向きです。…

核心：何を提案したのか

本論文の核心的な提案は、ランダム化された実行可能性更新（Randomized Feasibility Updates）と、最新の適応的ステップサイズ決定スキーム（DoWGやT-DoWGなど）を統合した、新しい制約付き最適化フレームワークです。この手法の最大の特徴は、射影が容易な単純な集合（集合 $Y$）と、多数の関数の共通部分からなる射影が困難な複雑な集合（集合 $X$）を明確に区別して扱う点にあります。具体的には、各反復においてすべての制約条件を一度に評価するのではなく、ランダムに選択された一部の制約のみを用いて実行可能性を段階的に確保する「ランダム化実行可能性アルゴリズム」を採用しています。これにより、大規模な制約集合に対する計算負荷を劇的に軽減することに成功しました。…

続きはログイン/プランで閲覧できます。