逐次線形二次計画法

逐次線形二次計画法 (SLQP) の概要

逐次線形二次計画法（Sequential Linear-Quadratic Programming、SLQP）は、非線形計画問題に対する効果的な解法の一つです。これは、目的関数と制約条件を微分可能な二種類の関数に近似し、反復的に解を見つける方法です。SLQPは、逐次二次計画法（SQP）と類似していますが、解法のアプローチにおいていくつかの重要な違いがあります。

SLQPとSQPの違い

SLQPの反復における解法は次の二つの部分問題を解くことで構成されています：

• - 一つ目は、制約条件を考慮した線形計画問題（LP）
• - 二つ目は、最適解を求める等式制約付き二次計画問題（EQP）

対照的に、SQPでは各反復で解決すべき部分問題は、目的関数が二次関数で制約条件が線形式となる二次計画問題です。このように、SLQPは複数の問題を解決することで、特に大規模な最適化問題に対して扱いやすい特性を持っています。

基本的なアルゴリズム

SLQPを用いた非線形計画問題の一般的な形は、次のように定義されます：

最小化:
$$\min_x f(x)$$
制約条件:
$$b(x) \geq 0$$
$$c(x) = 0$$

ここで、$f(x)$は目的関数、$b(x)$と$c(x)$はそれぞれ不等式制約と等式制約を示しています。この問題に対するラグランジュ関数は以下のように構成されます：

$$\mathcal{L}(x, \lambda, \sigma) = f(x) - \lambda^T b(x) - \sigma^T c(x)$$

ここで、$\lambda$は不等式制約のラグランジュ乗数、$\sigma$は等式制約のラグランジュ乗数を示しています。

LPフェーズ

逐次線形二次計画法では、最初に線形計画フェーズを通じて、次の線形問題を解決します：

最小化:
$$\min_d f(x_k) +
abla f(x_k)^T d$$
制約条件:
$$b(x_k) +
abla b(x_k)^T d \geq 0$$
$$c(x_k) +
abla c(x_k)^T d = 0$$

このフェーズでは、最適解$ d_{LP}^* $に対する有効制約が特定され、その結果得られるベクトル$b_A$と$c_A$が次の段階に影響を与えます。

EQPフェーズ

次にETP（等式制約付き二次計画）フェーズでは、探索方向$d_k$を決定するために次の等式制約付き二次計画問題を解きます：

最小化:
$$\min_d f(x_k) +
abla f(x_k)^T d + \frac{1}{2} d^T
abla_{xx}^2 L(x_k, \lambda_k, \sigma_k) d$$
制約条件:
$$b_{A_k}(x_k) +
abla b_{A_k}(x_k)^T d = 0$$
$$c_{A_k}(x_k) +
abla c_{A_k}(x_k)^T d = 0$$

EQPフェーズでは、目的函数の定数項は省略されることが一般的です。最適化のプロセスにおいて、SLQPは反復的に問題設定を更新し、新たな解を導出します。このような手法は、現実世界の様々な最適化問題に応用され、効率的な解決を提案します。

効率性

SLQPが特に注目される理由の一つは、問題を複数の段階に分解することによって大規模な最適化問題でも比較的スムーズに扱える点です。この特性により、SLQPは数理最適化の分野での応用が広がっています。加えて、準ニュートン法とも関連しているため、様々な最適化戦略に統合できる柔軟性を持っています。

参考文献

• - Jorge Nocedal; Stephen J. Wright (2006). Numerical Optimization. Springer.

もう一度検索