Abstract
本論文では、確率的目的関数と決定論的等式制約をもつ非線形最適化問題を考察する。信頼領域型 確率的逐次二次計画法（Trust-Region Stochastic Sequential Quadratic Programming; TR-SSQP）手法を提案し、一次および二次の
\epsilon-停留点を同定するための、その高確率反復計算量の評価（iteration complexity bounds）を確立する。提案アルゴリズムでは、目的関数値、勾配、ヘッセ行列の厳密な値は直接は利用できないと仮定するが、ゼロ次、一次、二次の確率的オラクルによりそれらを推定可能であるとする。ゼロ次オラクルに対する部分指数型の裾（サブ指数）ノイズ（すなわち軽い裾）を仮定し、主として一次停留性に焦点を当てた、既存の SSQP 手法に関する計算量研究と比較して、本解析は、ゼロ次オラクルにおけるバイアス（文献では既約（irreducible）とも呼ばれる）および重い裾（heavy-tailed）ノイズを扱うことができ、さらに二次停留性への解析を大きく拡張する。重い裾のノイズ条件の下では、我々の SSQP 手法が軽い裾ノイズ設定と同じ高確率の一次反復計算量評価を達成し、加えて有望な二次反復計算量評価も示すことを明らかにする。具体的には、本手法は、高確率で一次の
\epsilon-停留点を
\mathcal{O}(\epsilon^{-2}) 回の反復で、二次の
\epsilon-停留点を
\mathcal{O}(\epsilon^{-3}) 回の反復で同定する。ここで、
\epsilon は推定におけるバイアスの大きさ（すなわち既約ノイズ）によって定まる定数によって下から抑えられている必要がある。理論的な知見を検証し、CUTEst ベンチマークのテストセットにおいて本手法の実用的な性能を評価する。
