2
応用数学解説
文献あり

拘束系における汎関数の極小化とNewton法

324
0

【更新履歴】

  • 31Jan.2024: 「公式2」およびその説明に関し軽微な修正を行いました

はじめに

微分方程式を数値的に解く方法のひとつにgradient flowと呼ばれるものがあります。これは作用汎関数やエネルギー汎関数において、配位を勾配のマイナスの方向に数値的にフローさせて極小化することで微分方程式の解を求める方法です。様々な場面で使えると思いますが、例えば場の理論におけるトポロジカルで静的な解を求める際には大変有用ですManton

このような数値的な汎関数の極小化において拘束条件を課さなければならないことがあります。簡単な例が懸垂線です。懸垂線はひもを垂らしたときの形であり、重力下におけるひものエネルギーの極小化により導けます。しかし数値計算ではひもの長さを固定しないと望まない方向に配位がフローしてしまいます。

本記事では拘束の存在する汎関数の極小化問題をLagrangeの未定乗数法とNewton法により解く方法に関して記します。そして具体的に数値計算で懸垂線を求めます。

本記事では主にWashioを参考にしました。またLagrangeの未定乗数法は既知として、Newton法および2つの方法の融合に焦点を当てます。未定乗数法に関しては例えばLagrangeをご参照ください。

Newton法

Newton法 (Newton-Raphson法) とは方程式の解を求めるための方法ですHayakawa。いま
fl(u1,,un)=0    (l=1,,n)
の解を近似的に求めることにします。そのためにまずP0:(u10,u20,,un0)を適当に選びます。flの値をz方向として、z=fl(u1,,un)P0における接超平面のz=0でのuiの値で解を近似するのがNewton法です。方程式がn個あればu1,,unが一意に定まります。

以下これを図を用いて説明します。

1次元の場合

1次元のNewton法の概念図 1次元のNewton法の概念図

一次元の場合のNewton法が図1です。 最初にP0を適当に選びます。P0におけるz=f(x)の接線がz=0と交わる点をP1とします。これを繰り返しP2,P3,と続けると、良い初期値P0を選んでおけば真の解Psolに近づきます。

これを具体的に式にするのは簡単です。図1よりP0:x0P1:x1との関係が以下になるのはすぐにわかると思います:
f(x0)(x1x0)=f(x0)
この関係は任意のPkPk+1k=0,1,2,)で成立します。

多次元の場合

2次元のNewton法の概念図。青バツと緑バツがそれぞれ!FORMULA[24][36330951][0]の!FORMULA[25][35721894][0]における値。バツ印における接平面がそれぞれ!FORMULA[26][1100237917][0]。!FORMULA[27][1100237917][0]が交わる点が近似解!FORMULA[28][35721925][0]。赤点は正しい解。 2次元のNewton法の概念図。青バツと緑バツがそれぞれf,gP0における値。バツ印における接平面がそれぞれTf,TgTf,Tgが交わる点が近似解P1。赤点は正しい解。

2次元の場合が図2です。2つの拘束条件が存在するとして、それらを
f(x,y)=0 (図の青線),    g(x,y)=0 (図の緑線)
とします。まずP0:(x0,y0)を適当に選び、P0におけるz=fの接平面Tfz=0と交わる線をf(x,y)=0の近似解とします。同様にP0におけるz=gの接平面Tgz=0と交わる線をg(x,y)=0の近似解とします。これらが交わる点P1(オレンジ色の点)がf=0,g=0の近似解です。これを繰り返してP2,P3と続ければ、良い初期条件の場合真の解Psol(赤点)に近づきます。

この議論を多変数に拡張し式にします。改めて以下の拘束を解くことを考えます:
fl(u1,,un)=0    (l=1,,n)
flの高さをzとします。ここで
Fl(u1,,un,z):=fl(u1,,un)z
を定義すれば、あるlに対する拘束条件Fl=0が定めるn次元超曲面は
z=fl(u1,,un)Fl(ul,,)=0
で表されます。(n+1)次元中の点P~0:(u10,,un0,z=fl(u10,,un0))における超曲面Fl=0の超接平面を考えます。この平面上の点(u1,,un,z)は以下を満たします:
i=0nFlui|u0(uiui0)+Flz(zfl(u10,,un0))=0
これが成立するのは、Flの勾配が接超平面の法線ベクトルであり、また(u1u10,,unun0,zfl(u10,,un0))が接超平面上のベクトルであるため、これら2つのベクトルが直交することに拠ります。この超平面がz=0と交わる点の集合(つまりP~0を初期値としたときの近似解)をui1とします。Δui:=ui1ui0を定義すれば
(1)i=0nFlui|u0Δui+fl(u10,,un0)=0
が成立します。

Eq.(1)をfで書き直し、さらに行列表記にしましょう。Jacobian JP0を以下で定義します:
JP0:=(f1u1f1u2f1unf2u1f2u2f2unfnu1fnu2fnun)P0
P0の添字はどの要素もP0における値で評価していることを表しています。Δu
Δu:=u1u0,   u0:=(u10u20un0),   u1:=(u11u21un1)
とします。すなわちu0P0の座標値、u1P1の座標値です。さらに
fP0:=(f1f2fn)P0
とします。このときEq.(1)は行列表記で以下のように書けます:

多変数のNewton法

JP0Δu=fP0

各行がflの各l (1ln)に関する近似解を表しており、それらの連立方程式になっています。これを解くにはJP01を求めて両辺左からかければよいです。これにより
u1=u0JP01fP0
のように次の解の候補を作ることができます。この関係はもちろん任意のPkPk+1k=0,1,2,)で成立します。

Newton法とLagrangeの未定乗数法

Newton法を拘束条件付き多変数関数の極小化に適用します。以下Ref.Washioを参考にしています。

次の拘束条件付きの最小化問題:
minuf(u),   φl(u)=0   (l=1,,m)
を考えます。un次元ベクトルとします。前章ではfが拘束を表す関数でしたが、以下ではφが拘束を表しfは極小化する対象の関数であることに注意してください。

Lagrangeの未定乗数法に従い
f~(u,λ):=f(u)+l=1mλlφl(u)
を導入します。λm次元ベクトルです。そして極小化条件
f~u=0,   f~λ=0(f~u,f~λはそれぞれf~ui,f~λl(i=1,,n; l=1,,m)のなすベクトルを表す)
を前章のNewton法に従い解くことを考えます。ここでFk (k=1,,n,n+1,,n+m)
Fk:={f~ukz(k=1,,n)f~λkz(k=n+1,,n+m)
とします。また
u~:=(u1unλ1λm)
を導入します。前章の議論に従いFk(u1,,un,λ,z)=0の解をNewton法で求めます。P~0
P~0:(u10,,un0,λ10,,λm0,z=f~/u~k)
とすると、P~0におけるFk=0の接超平面は、(u11,,un1,λ11,,λn1,z)をこの接平面上の点とし、またΔu~:=u~1u~0として
Fku~Δu~+Fkz(zf~u~k)=0
で表されます。よってこれがz=0と交わるときΔu~
Fku~Δu~=f~u~k
を満たします。これをk=1,,nn+1,,mにわけて書き直します:

  • k=1,,nのとき
    2f~uiujΔuj+2f~uiλlΔλl=ui(f+λlφl)(2fuiuj+λl2φluiuj)Δuj+φlukΔλl=ui(f+λlφl)
  • n+1,,mのとき
    u~k(f~λl)Δu~k=f~λlφluiΔui=φl

ここで繰り返し登場する添字は和を取るものとします。またi,j1,,nl1,,mk1,,n+mまで走るものとします。

上の下線を引いた2式を数値計算で扱いやすいように行列表記すれば以下のようになりますWashio

Newton法による拘束条件付き多変数関数の極小化

(ABBT0)(ΔuΔλ)=(rurλ),{A:=2fu2+(2φu2)λ,B:=φu,Δu:=u1u0,   Δλ:=λ1λ0{ru:=(fu+(φu)λ),rλ:=φ
ここでuによる微分は以下で定義される:
fu:=(fu1fun),   2fu2:=(2fu1u12fu1un2funu12funun),   φu:=(φu1φun),   2φu2:=(2φu1u12φu1un2φunu12φunun)
BTの転置記号はφ/uuの足に作用する。また
φuλ:=φluλl,   2φu2λ:=2φlu2λl,   φuΔλ:=φluΔλl
である。

公式2を(Δu,Δλ)に関して解いて
(u1λ1)=(u0λ0)+(ABBT0)1(rurλ)
を計算すれば次の解が求まります。ru,rλのノルムは収束の指標であり、これがゼロになるとフローは止まり真の解付近に到達します。

具体的な数値計算

2変数関数の拘束付き極小化

まずは2変数関数の拘束付き極値問題を前章の式を用いて数値的に解いてみます。問題はRef.Problemからお借りしました。

2変数関数の拘束付き極小化問題

f(x,y)=(x1)2+y3の極値をg(x,y)=x2y3=0の拘束のもとで求めよ

解析的な計算はProblemを御覧ください。非自明な極値は
(x,y)=(1/2,1/43)
です。一方初期条件(x0,y0,λ0)=(2,3,4)から公式2を用いて数値的に計算すると
iterationxyλ02.03.04.010.546218491.932773113.13445378151260520.337704241.29481212.40906171824368430.344962250.886857241.887902676971421680.50.629960520.999999999924751490.50.629960521.0
となります。iterationとは公式2を何回繰り返したかを表す数字です。iterationが9回で本計算の計算精度の範囲において収束します。1/43=0.62996052...であり計算は正しいです。λ=1も正しい値です。

懸垂線の計算

次にエネルギーの極小化により懸垂線を数値的に求めます。この場合の拘束条件はひもの長さを固定することに対応します。

懸垂線と拘束条件つき変分法

まず懸垂線における変分法について述べます。詳細は省いて説明するので、馴染みのない方は例えばCatenaryをご参照ください。

x-y座標において懸垂線をu(x)で表します。このとき極小化したいuの汎関数であるエネルギーf(u)
f(u):=ρgx0x1dx u(x)1+u2(x)
ですCatenaryρ,gはそれぞれひもの線密度と重力加速度です。ここでは簡単のためρg=1とします。拘束条件はひもの長さをLに固定する条件であり
x0x1dx1+u2(x)=L
で与えられます。Lagrangeの未定乗数法を用いて拘束条件付きの変分問題を解きます。それにはf~
f~(u;λ):=x0x1dxu(x)1+u2(x)λ(x0x1dx1+u2(x)L)
で定義し、これがδyδλの変分(λに関しては微分)がゼロとなる条件を解けばよいです。

数値計算を行うため空間を離散化します。空間をN1等分し、uui (i=0,,N1)とします。こうすれば上記変分は変数u0,u1,,uN1,λの多変数関数f(u0,u1,,uN1,λ)の極小化と等価です。以下の量を導入します:
u=(u0u1uN1),   f(u):=Δxi=0N2(uiλ)1+(ui+1ui12Δx)2,   φ(u):=Δxi=0N21+ui2L
fは極小化する目的関数、φは拘束条件、Δxは最近接の2点の間隔です。計算に関係ないfの定数項は落としました。この表式では微分に関してΔxの2次の精度である一方、積分に関して0次なのですが、これで議論を進めます。

あとはf/u,2f/u2(およびfφとした量)を上の表式を用いて構成し、公式2を繰り返し計算すればよいです。これらの量の構成は単純ですがちょっと長いので、Appendixに具体的な表式のみ掲載しておきます。

計算結果: 長さに拘束をかけない場合

まず拘束をかけないとどうなるか見ておきます。

ひもの長さに拘束をかけない場合のひもの形状のiteration依存性。空間の離散化に関し!FORMULA[165][1241914709][0]を400分割している。 ひもの長さに拘束をかけない場合のひもの形状のiteration依存性。空間の離散化に関し20x20を400分割している。

図3がひもの形状のiteration依存性です。一番下の青線が初期関数であり放物線y=7/40x2+10に設定しています。また境界条件として(±20,80)uの値を固定しています。これを極小化のアルゴリズムであるAdamAdamを用いてフローさせています(パラメータ:lr=0.005,β1=0.9,β2=0.999)。iterationが進むごとに平坦になり、最終的には平らになります。下図のようにエネルギーはiterationが進むごとに小さくなります。

図3のひものエネルギーのiteration依存性。 図3のひものエネルギーのiteration依存性。

端を(±20,80)に固定した場合、まっすぐにピンと張ったひものエネルギーは80×40=3200であり、実際その辺りにエネルギーが収束しています。長さを固定しないと長さの違うひもの関数空間までサーチして極小を見つけようとするため、懸垂線には行き着かないのだと思います。

計算結果: 拘束をかけた場合

一方公式2を用いてひもの長さに拘束をかけて計算すると下図のようになります。

ひもの長さに拘束をかけた場合のひもの形状のiteration依存性。空間の離散化に関し!FORMULA[172][1241914709][0]を400分割している。 ひもの長さに拘束をかけた場合のひもの形状のiteration依存性。空間の離散化に関し20x20を400分割している。

紫の線が初期条件であり、図1と同じ放物線に設定しています。この放物線の長さは図のスケールで148.98です。これと同じ長さを持ち端点を(±20,80)に固定した懸垂線が正しい解であり、灰色の太線がそれです。だいたい3回程度のiterationで概形は正しい懸垂線に到達します。またひもの長さの拘束されるべき値からの誤差はiteration16回目以降で106より小さくなります。このことから拘束は正しく機能していることがわかります。

エネルギーのiteration依存性は以下のようになります:
図5のひものエネルギーのiteration依存性。 図5のひものエネルギーのiteration依存性。

エネルギーは単調に減少し、だいたいiteration回数が10回で一定になります。非常に速く収束しています。

Mathematicaで計算すると、初期の放物線のエネルギーは6487、また正しい解である懸垂線のエネルギーは6476です。本計算の初期のエネルギーはだいたい良いですが、最終的に安定した後のエネルギーは6441なので、けっこう差があります。図5をよく見ると少し真の解から計算結果がずれているのが問題なのかもしれません。またはコードに問題があるかもしれません。まあでも定性的・半定量的には問題ない結果かと思います。

Newton法はiteration回数に対し非常に速く収束します。ただAdam等の陽的なminimizationと比較して、iteration毎に空間の分割数分の行と列を持つ行列の逆行列計算が必要なので、計算量は単純には比較できません。

もう少し歪な初期条件から始めても正しい形状を得ます:
図5よりも歪な初期状態からフローさせた計算。計算条件は初期条件以外図5と同じ。 図5よりも歪な初期状態からフローさせた計算。計算条件は初期条件以外図5と同じ。

計算条件は初期条件(紫の線)以外図5と同じです。この場合でもiterationが3回程度でひもの形状はほぼ正しい懸垂線に到達します。またひもの長さもiterationが13回以降では誤差が106を下回り、正しく拘束がかかっています。エネルギーはiteration=0で6520、iteration10回目以降で6459で落ち着きます。一方正しい初期のエネルギーは6525、解となる懸垂線のエネルギーは6497です。やはり最終的に到達するエネルギーは正しいものより低い値になります。

図7の初期条件より更に歪んだ初期条件を与えると往々にして収束せず計算が発散して破綻します。極小化の数値計算では不安定性は頻繁に見られる現象であり気を遣う点ですWashio。またそもそもNewton法では初期条件が悪ければ収束は保証されません。ある程度良い初期条件を選ぶことは大切です。

まとめ

本記事では拘束の存在する汎関数の極小化問題を、Lagrangeの未定乗数法とNewton法により解く方法に関して述べました。多変数の場合のNewton法および未定乗数法におけるNewton法の定式化に関して記したのち、その応用として数値計算により懸垂線を求めました。この方法において、初期条件と不安定性に気を配れば、数値計算により拘束系における汎関数の極小化問題をうまく解くことができます。

Newton法+Lagrange未定乗数法で懸垂線を計算するコードをGistにアップロードしましたCode。PythonでコーディングしJupyter Notebookとして保存してあります。各セルを上から順番に実行すれば図5・6が描画されます。よろしければご参照ください。
(※本コードの正しさは保証できません。何らかの別用途に利用される場合ご自身で確認・修正されることをおすすめします)

おしまい。



Appendix: f/u等の懸垂線における表式

まずf,φを以下で定義します:
f=driui1+((ui+1ui1)/2dr)2   (dim.2),φ=dri1+((ui+1ui1)/2dr)2   (dim.1)
drは本文のΔxです。dim.nは長さのn乗の次元を持つことを意味します。dr, uiはdim. 1です。

表式の簡単化のため次の量を定義しておきます:
gi:=1+{(ui+1ui1)/2dr}2   (dim.0),hi:=(ui+1ui1)/2dr   (dim.0),α:=1/(2dr)   (dim.1)

以上の準備のもと、計算に必要な量は以下のようになります:

  • f/ui (dim. 1)
    fui=dr(gi+α(ui1hi1/gi1ui+1hi+1/gi+1))

  • 2f/uiuj (dim. 0)
    2fuiuj=αdr{δi,j+1hjgjδi,j1hjgj+δi,j1hj1gj1uj1δi,jhj12gj13α+uj1δi,jαgj1+uj1δi,j2hj12gj13αuj1δi,j2αgj1δi,j+1hj+1gj+1+δi,j+2uj+1hj+12gj+13αδi,j+2uj+11gj+1αδi,juj+1hj+12gj+13α+δi,juj+1αgj+1}

  • φ/ui (dim. 0)
    φui=αdr{hi1gi1hi+1gi+1}

  • 2φ/ui2 (dim. -1)
    2φuiuj=α2dr[δi,j{hj12gj13+1gj1}+δi,j2{hj12gi131gj1}+δi,j+2{hj+12gj+131gj+1}+δi,j{hj+12gi+13+1gj+1}]

以上。

参考文献

投稿日:2024130
更新日:2024223
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

bisaitama
bisaitama
143
66878

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. Newton法
  3. 1次元の場合
  4. 多次元の場合
  5. Newton法とLagrangeの未定乗数法
  6. 具体的な数値計算
  7. 2変数関数の拘束付き極小化
  8. 懸垂線の計算
  9. 計算結果: 拘束をかけた場合
  10. まとめ
  11. Appendix: f/u等の懸垂線における表式
  12. 参考文献