矢部　博、八巻　直一：非線形計画法

概要

本書は非線形計画法の基本から実際までをまとめた教科書である。

使ってみて

最近はこの関係に疎いのでまだ読みこめていないが、 以前の成書では明らかにされていなかった各種の技法が解説されている。 たとえば、大規模問題で準ニュートン法を適用する場合に問題となる記憶容量の増大について、 これを抑えるための方法が 2.7 項で解説されている。

内容の一例

Maratos 効果 (マラトス効果) について述べられている。 これは、逐次二次計画法（SQP 法、sequential quadratic programming method) における現象である。 SQP 法では局所的に速い収束を達成するためにはステップを大きく取らなければならないが、 大域的収束性を同時に達成するために解の近くでステップが小さくなってしまうことをいう。 二次計画問題で非線形制約条件を線形化することが Maratos 効果の一因となっている。

Maratos 効果が起こってしまう例をこの本から引用する。なお、この後出てくるメリット関数とは、 直線探索の評価関数をいう。このメリット関数として `l_1` 型正確なペナルティ関数をそのまま用いている。 正確なペナルティ関数とは、ペナルティパラメータを固定したまま、 変換された無制約最小化問題を１回解くだけでもとの問題の解が得られるような関数である。

さて、例は次の通りである

`x_1^2 + x_2^2 = 1` のもとで `-x_1 + 10(x_1^2 + x_2^2 - 1) ` を `mathbbx = (x_1, x_2)` について最小化せよ。

SQP では、次のように解く。`k` 回目の反復における近似解と行列をそれぞれ、 `mathbbx_k = (cos theta, sin theta)^T, B_k = nabla_x^2L(mathbbx^**, mathbbmu^**) = I` とする。ここで、`mathbbx_k`は実行可能解であり、 近似行列`B_k`は最適解におけるラグランジュ関数のヘッセ行列に一致する。 `Delta mathbbx_k=(d_1, d_2)^T` としたとき、QP 部分問題は `d_1 cos theta = d_2 sin theta = 0` のもとで

`1/2(d_1^2 + d_2^2) + d_1(-1+20 cos theta) + 20 d_2 sin theta` を `(d_1, d_2)` について最小化せよ

となる。これを解いて得られる探索方向`Delta mathbbx_k ` と ` mathbbx_k + Delta mathbbx_k`は

`Delta mathbbx_k = ((sin^2 theta), (-sintheta cos theta)), mathbbx + Delta mathbbx_k = ((cos^2 theta + sin^2 theta), (-sintheta - sin theta cos theta)), `

であるので、`mathbbx_k` におけるメリット関数値と`mathbbx_k + Delta mathbbx_k` におけるメリット関数値はそれぞれ

`P(mathbbx_k; rho) = -cos theta`

`P(mathbbx_k + Delta mathbbx_k; rho) = -cos theta + (9 + rho) sin^2 theta`

となる。二つの式を比較すると、`rho >= 0` なので、`theta = 0` でない限り

`P(mathbbx_k + Delta mathbbx_k ; rho) = P(mathbbx_k ; rho)`

が成り立ち、近似解が十分に最適解に近くても `alpha_k = 1` に対してメリット関数は減少しない。 したがって、直線探索において `alpha_k = 1` が作用されず、その結果超１次収束性が保証されない。

理論的にはさまざまな対応策は提起されている。しかし、この本での結論は、 実際の問題では Maratos 効果が起こることはほとんどないことから、 `l_1` 型正確なペナルティ関数をメリット関数にそのまま用いてもよさそう、ということである。

ささいなこと

印刷されている書体では、著者の一人の姓は、八卷直一となっている。

数式の記述

数式記述は ASCIIMathML を、 数式表記は MathJax を用いている。

書誌情報

まりんきょ学問所 ＞ コンピュータの部屋 ＞ コンピュータの本 ＞ 矢部　博、八巻　直一：非線形計画法