最適解の連続性(その1)

　今、が連続で、xについて厳密に凹なnumerical functionであるとする。なお、で、S、Θはコンパクト集合とする。
　このとき、次の問題を考える：

　

ここで、は連続で、任意のsとθに対して空ではないコンパクトになる対応とする。
　Maximum Theoremを用いれば、最適解は上の連続な関数であることがわかる。

　では、次のような問題についてはどうだろうか。ここでは、最適化にあたって、measurable functionを選択するという問題を考えている：

　

ここで、は確率変数で、μはそれに対応する確率測度。Eは全集合。fはについても連続であるとする。は、s,θを所与として、各が実現したとき、制約が必ず満たされるmeasurable functionの集合を現す。については、上記の問題と同様の仮定をする。

　このとき、解が一意のmeasurable functionで、かつそれがについて連続となるにはどういう仮定が必要だろうか？今このことについて、時間があるときに考えております。

目的関数のarugmentの数と最適化処理速度向上

　今、コンパクト集合があって、が連続で、(y,z)に関して厳密に凹な関数であるとする。このとき、次の問題を空間の分割(discretization)を使って、各xについて最適化を行う解を求めたいという状況にあるとする：

　

　さらに、何らかの事情で、この問題を次のように分解して解かなければならないとする：

　

「凸計画問題の分解」と同じ議論を展開すれば、カッコの中はyの厳密な凹関数であることがいえる。

　まず、yの最適化についてはBinary Searchを使えば良いことがわかる。
　では、他にできることはあるだろうか。例えば、xとfの何らかの関係性が仮定されているとしたらどうだろうか。もし、zのargumentがなくてfがxの厳密な増加関数であるなら、は厳密な増加関数であることがいえ、この単調性を使って、関数fの評価の回数を減らすことが可能。しかし、今はzというargumentがあるため、このような単調性を保証するには、さらに何らかの仮定が必要になる。一般論として、fのargumentが増えるほど単調性を導出することが難しくなる。したがって、数値計算がそれだけbrute forceなやり方に近づいてしまうことになる。

凸計画問題の分解

　を連続で厳密な凹関数であるとする。また、をコンパクトな凸集合とする。以下の目的のため、のxについてのsectionをと表記する。すなわち、

　

仮定より、G(x)が空集合とならない任意のxについて、G(x)はコンパクトな凸集合となる。

　このとき、



で定義されるは連続で厳密な凹関数となるだろうか。

　答えは、"YES"。連続性についてはMaximum Theoremを使えば一発。厳密に凹であることを示すには、まずi=1,2について、をがのときのargmaxというペアとして定義する。このとき、任意のに対して、

　
　

で定義されるペアについて、Gが凸集合なので、が成立する。このとき、

　

n次元ユークリッド空間への拡張は容易に行えるはず。

最大値最小値の定理の拡張

　Topologistの興味をそそる定理の一つに、次のものがある：

If f is a numerical function defined and continuous on a space X, and if K is compact subset of X, then f attains the value in K. Similarly, f attains the value .

ここで"numerical function"とは、fがXから実空間への写像であることを意味する。


　この定理を、generalized numerical function に拡張することはできないだろうか。

　自分の答えは、"YES, WE CAN!"である。議論は以下のステップからなる。

1. 上の位相を定義する。
　以下の３種類の集合からなる集合族を考える：
(a) 上の開集合。
(b) とという形の区間を一つ含む上のある開集合のunion。
(c) とという形の区間を一つ含む上のある開集合のunion。

　すると、上のを含む最も小さい(から生成された)位相を定義することができる（詳しいことは省略）。

2. 位相空間上では、single-valued function f の値が+∞や-∞となる点においても連続である。
　例として、となる点における連続性について考える。位相の定義から、{-∞}の点を含む開集合は必ず[-∞,a)(for some )という区間を含む。fが-∞や+∞となる点以外では連続であることから、X上の適当な開集合が存在して、そのfによる写像（集合）が[-∞,a)に含まれることになる。

　そこで、上記の定理を次のように書き直す：

If f is a generalized numerical function defined and continuous on a space X, and if K is compact subset of X, then f attains the value in K. Similarly, f attains the value .

3. 2.より、任意のコンパクト集合K⊂Xに対し、は閉集合である。
　コンパクト集合Kは閉集合。閉集合を連続な写像で移した先の集合も閉集合だから。

4. 上のどのような点に対しても、それに収束するような上の点列が存在する。また、上の収束する点列の収束先は上に属する。

5. f は関数であるので、上の任意の点に対して、K上のある点（場合によっては複数の点）が対応する。

よって、supもinfもK上の点で達成可能。


上の議論の4.,5.あたりが遠回りな気がする（汗）