B.1.1 問題
次の最適化問題
を考えます注1.ここで,変数は
次元ベクトルで,関数
は目的関数です.また,
は
次元のベクトル値関数です.この問題のラグランジュ関数を
としたとき,Karush-Kuhn-Tucker(KKT)条件(最適性の一次の必要条件)は次式で与えられます:
ただし,,
,
です.ここで,相補性条件
を
(
)で置き換えたものを修正KKT条件と呼びます.
Nuorium Optimizerではバリヤペナルティ関数:
をメリット関数として採用します.ここで,はバリヤパラメ-タ,
はペナルティパラメ-タ,
は主双対項の考慮度合いを表すパラメータです.
非線形最適化問題に対する内点法では,「修正KKT条件を満たす点を求めて,修正KKT条件を更新する」という作業を逐次行います.この際に,メリット関数の一次近似
あるいは二次近似
の変化量が重要な手がかりとなります注2.次項以降で示すように,修正KKT条件を求める方法は複数存在します(直線探索を利用する方法・信頼領域を利用する方法).
この作業を通して,最終的に元来のKKT条件を満たす点を求めます.
注1)ここでは,説明の便宜上このような形式を考えますが,Nuorium Optimizerでは制約関数に上下限が存在する場合,等式条件,変数に上下限が存在する場合などの一般形を扱うことができます.また,制約条件が存在しない問題も扱うことができます.
上に戻る