数理物理学の初歩的な問題の1つである最適化。 最適化とは、目的関数と呼ばれる関数の最大値または最小値と、その最適値が得られる入力変数の値を求める問題です。
多変数最適化問題は、制約条件があるため、より複雑になります。 ある関数gと定数cに対して、g(x,y,z)=cの形で表現できる制約を等式制約といい、この制約を満たす点の集合を実現可能集合といい、これをSとします。 例えば、単位円上のf(x,y)の最大値を求めよと言われた場合、単位円はx²+y²=1で定義されているので、g(x,y)=x²+y²となります。
このような問題を解く標準的な手法はラグランジュ乗数法です。
動機付けと導出
関数fは、fの偏微分が独立変数のそれぞれについてゼロであり、かつその点が鞍点ではないとき、ある点Pにおいて局所的な極値(最大または最小)を持ちます(この状況はここでは扱う必要がありません)。 これをコンパクトに書くと∇f=0となり、∇は勾配演算子を表します。
制約条件付き最適化においては、fが局所的な値を持つからといって、その値が変化することはありません。
しかしながら、制約付き最適化では、fが実現可能なセット上のある点で局所的な最大値または最小値を持つからといって、その点でfが実現可能なセット上で最適な値を取るとは限りません。
例として、次のような最適化問題を考えてみましょう。
勾配を書き出すことで、fは局所的な値をとることがわかります。 x=0、y=1のときにfが局所的な最小値を持つことがわかります。
さらに、次のようになります。 f(0,1)=0ですが、f(0,-1)=-4なので、(0,1)はf(x,y)の局所的な最小値ではありますが、単位円上のf(x,y)の最小値ではありません。
別の例として、単位円上でf(x,y)=yを最大化するとします。
この失敗の理由は、勾配は3次元空間の位置に対するf(x,y,z)の変化率を測定するものですが、我々は実行可能セットの位置に対するf(x,y,z)の変化率を測定したいからです。
最も自然なアプローチは、S の曲線を考えることです。 P を、f(P) が S において局所的に最適な値をとるが、∇f(P) が必ずしもゼロではない S の点とし、r(t) を、P を通過する S の任意の曲線のパラメータ化とします。
Sが曲線の場合。 とすると、r(t)はSのパラメータ化に過ぎません。 さらに、r(T)=P、r′(T)≠0とし、h′(T)=0となるようにh(t)=f(r(t))とします。 h′(t)を鎖の法則で展開してみましょう。
r(t)は常にSの中にあるので、速度ベクトルr′(t)は常にSの表面または曲線に接していなければなりません。なぜなら、もしr′(t)が表面に垂直な成分を持っていたら、つまり表面から外に向かっていたら、r(t)がSから離れる点があるからです。 これはPを通過するどんな曲線r(t)にも当てはまるので、∇f(P)はPにおける表面へのどんな接線ベクトルにも垂直であることがわかる。
逆もまた真なりで、r′(T)は決してゼロではなく、常にSに平行であるため、∇f(P)がSに垂直であれば、h′(T)=∇f(P)・r′(T)=0となります
しかし、実際に∇fがSに垂直な点を見つけるにはどうすればよいのでしょうか。 その答えは以下の通りです。 集合Sはg(x,y,z)=cとなる全ての点の集合、つまりSはgのレベルセットです。これは、S内の全ての点で∇gがSに垂直であることを意味し、fが最適値をとるS内の点では∇fと∇gが平行になることを意味します。 この定数λはラグランジュ未定乗数と呼ばれ、この方法の名前の由来となっています。 これで、fを最適化する問題は、この4つの方程式を解く4つの未知数x、y、z、λを見つけることで解決できます。
別の言い方をすると、現在の目標は関数を最適化することです。 今の私たちの目標は、∇(f-λg)=0となる場所を見つけることで、x, y, zに関する関数f-λgを制約なしに最適化することです。
もし、制約条件が複数あったらどうでしょうか。 今、g(x,y,z)=cとh(x,y,z)=dを条件として、f(x,y,x)を最適化しなければならないとします。 ここでは、次のようにします。 g(x,y,z)=cを条件とするfを最適化するには、制約のないf-λgを最適化するので、fをf-λgに置き換えることで最初の制約は解消され、あとはh(x,y,z)=dを条件とするf-λgを最適化することになります。
ここでいくつかの例を見てみましょう。
長方形の最大面積
ある周囲の長さに対して、その周囲の長さを持つ長方形の最大の面積は何でしょうか。 これはラグランジュ乗数の問題として定式化できます。 幅と高さをxとyとすると、g(x,y)=2x+2y=cに対して、f(x,y)=xyを最大化したいと考えます。 その結果、方程式系は次のようになります。
最初の2つの式から、すぐにx=yであることがわかります。 となり、長方形が正方形のときに最大の面積となります。
A (modified) Putnam problem
Putnam mathematical competition は、毎年12月に学部生を対象に行われる試験形式のコンペティションです。 学生は6時間で12の非常に難しい問題を解きます。 試験は非常に難しく、120点満点のところ、例年の平均点は0点か1点です。 今日は、2018年の試験から問題A3を(簡単にするためと著作権の問題を避けるために)修正したものを見てみましょう。
2つの問題があります。 1 つ目は、目的関数が非常に望ましくない特徴を持っていることです。それは余弦の和であり、三角関数の和は扱うのが難しい場合があります。 2つ目は、一見できるように見えても、制約関数を目的関数の中にきれいに明示的に表示する方法がないことです。 パットナム問題には、このような「罠」があることが多く、よく考えないと解決につながらないアプローチに時間を取られてしまいます。 三角恒等式が重視されがちな高校の数学大会の経験がある出場者にとっては、特に危険な罠です。
しかし、「g=0を条件にfを最大化せよ」という問題を見たら、すぐにラグランジュ乗数について考えるべきです。 それでは、方程式を立ててみましょう。
さて、三角恒等式を使って、制約を明示的に表すことができます。 二重角の公式を使って方程式系を書き換えます。
その結果は以下の通りです。
さて、各辺のサイン関数をキャンセルします。 そして、その方程式を加えます。
そして、これはλ=0であることを意味しています。 となりますので、ラグランジュ乗数の方程式によれば、これは次のことを意味します。
従って、w, x,y,zはすべてπ/2の整数倍です。 偶数のπ/2の整数倍の場合、ある整数kに対してm=2kとします。
ただし、mが奇数整数の場合は。 とすると、cos(mπ/2)=0となります。 つまり、制約式を満たす方法には3つの選択肢があることになります。 まず、w、x、y、zのすべてをπ/2の奇数整数倍、つまりk、l、m、nに設定することができます。
1行目は、制約式が満たされていることを示しています。
2行目は、制約式が満たされていることを示しており、2行目は、これらの値を目的関数にプラグインした結果で、-4となります。
2つ目の選択肢は、変数の2つをπ/2の奇数整数倍、たとえばkとlに設定し、残りの2つを偶数整数、たとえば2mと2n(mは偶数、nは奇数)に設定することです。 これを制約式に差し込むと、次のようになります。
従って、制約式は満たされます。 これらを目的関数に差し込んだ結果がこちらです。
バリエーションδρ(r)の任意の選択に対して、これが真であるためには。 括弧内の項はゼロでなければなりませんので。
しかし、この積分値はrでのポテンシャルに過ぎません。 積分は、導体内部の電荷によるrでの電位だけなので、この式の左辺は、導体内部の各点rでの全電位を与えます。 したがって、ρ(r)は導体内部の全電位を一定にする分布であることがわかります。
これは、導体の静電エネルギーが最大になる場合にも有効で、その場合、導体は不安定な平衡状態にあります。 実際には、不安定な平衡状態にある導体に遭遇することはありません。なぜなら、導体内の電子のランダムな熱運動により、金属導体では10-¹⁴秒のオーダーで、システムが不安定な平衡状態から安定した平衡状態へと急速に移行するからです。