佐藤 寛之

スライドショーには JavaScript が必要です。

講演者：佐藤寛之（東京理科大学）
題　目：リーマン多様体上の最適化の数理
日　時：2016年3月10日(木) 18:00-
場　所：早稲田大学西早稲田キャンパス63号館 4階 420教室

オープニング

司会：では、そろそろ時間になりましたので始めさせていただきたいと思います。カウントすると今日は13回目だそうです。13回目の数理人セミナーは、理科大の佐藤さんにお願いしました。相原さん経由でお願いをしていただきました。相原さんにご紹介いただきたいと思います。
相原：簡単にご紹介させていただきます。佐藤先生は、もともとは京都大学御出身で、京都大の岩井先生の研究室にいたんですけれども、2013年の11月に早期に学位を取られまして、ただ岩井先生が退官されたので中村先生のところで学位を取られました。その後、学振のPDを2014年3月までやられて、4月から理科大の工学部経営工学科の助教に着任されました。
　研究内容としては、この後お話があると思いますけれども、リーマン多様体上の最適化問題を専門とされていまして、ただ最適化手法はもちろんなんですけれども、そういう多様体上の最適化手法を通して数値線形代数におけるいろんな問題に対するアルゴリズムですね、特異値分解とか同時対角化とか、そういったものに対する計算アルゴリズムへ応用しようという研究をされています。
佐藤：大変、丁寧なご紹介をありがとうございます。東京理科大学の佐藤寛之と申します。よろしくお願いいたします。本日は、このような貴重な機会を与えていただきまして、山中先生、それからご紹介いただいた相原先生をはじめとして、世話人の先生方、本日お集まりいただきました皆様、本当にありがとうございます。

講演

　それでは、早速、今、ご紹介いただいたようにリーマン多様体上の最適化ということを研究しておりますので、その概要からちょっと突っ込んだところまで、それから応用例を幾つかご紹介させていただこうと思います。
　まずリーマン多様体なんですが、これは微分幾何学における基本的な対象です。先ほどご紹介いただいた私の所属しておりました岩井先生の研究室は、微分幾何を使って力学系の研究をしようという研究室でして、それで微分幾何にはもちろん興味を自分自身持っておりましたし、さらに最適化自体にも実は興味があって、その研究室自体は最適化の研究室ではないんですけれども、岩井先生に最適化にもちょっと興味があるんですということを言いましたら、こういう幾何学と最適化を合わせたような話が最近出てきているよということを2009年ぐらいに教えていただきまして、そこからこういう話をいろいろ勉強しつつ研究しています。

　講演内容ですが、まず最初にその多様体についての簡単な話と、その上の最適化とはどういうことなのかというところをお話しします。
　さらに、幾何学的な量がいろいろ出てきますので、これを簡単に解説しまして、さらに球面という簡単な多様体の例においてそういう幾何学的な量がどうなっているかというところをご紹介します。
　その後にもうちょっと深く入っていって、最適化の中でも特に共役勾配法と呼ばれる手法についてリーマン多様体上ではどうなっているかというお話です。
　最後に、応用例がいろいろとありますので、多様体上の最適化問題として定式化される例をいろいろとご紹介いたします。

　では最初に、多様体上の最適化ですが、まず多様体の前にユークリッド空間の最適化について簡単にご説明をします。

　今回考えますのは、このような制約条件なしの最適化問題です。これは目的関数と呼ばれる $f$ という $x$ の関数をユークリッド空間全体で $x$ を探すことで最小になるようなところを見つけようという問題です。こういう無制約の最適化問題に対しては、最急降下法であるとかニュートン法、それから共役勾配法と呼ばれる方法などいろいろとあります。これは後ほどもう少し詳しく説明します。
　こういった方法というのは、いずれも直線探索法と呼ばれる最適化手法の枠組みに入っているものでして、その直線探索を使ったアルゴリズムの一般的な形をここに書きました。
　初期点をまずユークリッド空間の中で選びまして、そこから反復に入るんですけれども、各反復においては、点 $x_k$ が得られているとしましたら、その点から探索方向と呼ばれるベクトル $\eta_k$ 、それからステップ幅と呼ばれる正の実数 $t_k$ を求めまして、次の点を今いる点から探索方向にステップ幅倍だけ進んだ点として計算します。

　これを図にしましたらこういう感じになるんですが、例えば初期点 $x_0$ というのをここに適当に取りました。ここから探索方向、どの方向に探していこうかということで、 $\eta_0$ というのを何らかの方法で求めます。それは後ほど説明します。
　求めましたら、このベクトルが定義する水色の直線上で次の点を探します。どれぐらい進んだところが目的関数を小さくするかということで、十分小さくするような点が見つかったらこれを次の点 $x_1$ とします。あとは反復ですので、また探索方向 $\eta_1$ をこの点において計算しまして次の点を探して、ということを繰り返して、最適解、つまり目的関数を最小にするような図の $x_*$ という点に収束していくような点列をつくっていく、これが直線探索法です。

　では、探索方向を実際どう求めるのかというところですが、 $\nabla f$ 、それから $\nabla^2 f$ というのをそれぞれ目的関数 $f$ の勾配、ヘッセ行列としましたら、最急降下法と呼ばれる方法では探索方向を $-\nabla f(x_k)$ 、つまり今いる点における目的関数の勾配の逆方向ということで探します。すなわち、目的関数を最も減少させるような方向に直線を伸ばして、その上で次の点を探そうということです。
　ニュートン法と呼ばれる方法でしたら、 $\eta_k$ というのをこのような $\eta$ についてのニュートン方程式と呼ばれる線形方程式の解として計算をします。これの意味は、目的関数 $f$ を点 $x_k$ において 2 次近似しまして、その近似された 2 次関数を最小にするような $\eta$ というのを求めているということです。
　それから、これは特に詳しく後ほど説明しますが、共役勾配法という方法でしたら、最初の探索方向は最急降下方法と一致するんですけれども、それより後の探索方向は、その点における勾配の逆方向だけではなくて、1 つ前の探索方向 $\eta_k$ を適当なスカラー $\beta_{k+1}$ 倍だけしたものを加えて、それを次の探索方向にします。ではこの $\beta_{k+1}$ をどういうふうに計算するかというところは、いろいろと提案されているので詳しく後ほど紹介します。
　これがユークリッド空間の最適化なんですが、これを多様体上に持っていこうということで、動機づけのために簡単な例を 1 つご紹介します。

　 $A$ を $n$ 次実対称行列としまして、このような最適化問題を考えます。すなわち、レイリー商関数を最小化するという問題です。 $x=0$ ではもちろんこれは定義されませんので、ユークリッド空間全体から原点 $0$ を除いたような空間において、 $x$ を自由に動かして $f$ を最小化しましょうということです。よく知られているように、この $f$ を最小にするような $x$ というのは、行列 $A$ の最小固有値に属する固有ベクトルだということで、これは固有値問題、特に最小固有値を求めるという問題と等価であるということになっています。
　では、これは原点 $0$ は抜かれてはいますが無制約の問題ですので、ニュートン法を適用できるかということで先ほどのニュートン方程式を解いてみますと、実は点 $x$ が $f$ の停留点でないとき、ここで停留点であるための必要十分条件は $x$ が $A$ の固有ベクトルになっているということなんですが、そうでないときには点 $x$ においてニュートン方程式を解いた解、すなわちニュートン方向、これが $\eta=x$ ということで、今いる点をあらわすベクトル $x$ と一致してしまいます。したがいまして、点 $x$ にいるときにニュートン方向が $x$ として求まるので、次の点は $x+x$ で $2x$ 、その次の点は $2x+2x$ で $4x$ ということで、1 つの直線上でどんどん点列がつくられてしまいますので、これでは一般には停留点には到達できない、すなわち固有ベクトルに収束するような点列は得られないということで、この問題に対してはニュートン法は失敗をしてしまいます。
　じゃあ、ちょっと見方を変えましょうということで、この $f$ をよく見ますと、 $x$ をスカラー倍しましても、分母分子でそのスカラー倍のところが 2 次と 2 次なのでキャンセルされますから、実はこの目的関数値というのは $x$ の方向だけに依存していて、 $x$ のノルムには依存せずに決まるということがわかります。

　そこで、 $x$ のノルムを 1 に固定するということを考えます。そうしますと、この分母が 1 ということで、このような簡単な関数になって、そのかわりにこういう制約条件がついてしまいます。制約条件がついてしまいますと、先ほどのニュートン法はそのままでは適用できなくなりますので、目的関数は簡単になったけれども制約条件がついてしまうということでちょっと困ったことになるんですが、さらに見方を変えまして、このような $x$ 全体というのは結局、単位球面上に乗っているというふうに考えられますので、ここで単位球面というのを $S^{n-1}$ という記号で書くことにしまして、この青い制約条件をこういう赤い制約条件に書きかえてやります。そうしますと、実はこの球面というのは多様体の最も簡単な例の 1 つなんですが、この「多様体の上の」、ほかに制約条件もなくなっていますので、「無制約の」最適化問題というふうにみなすことができます。
　ということで、ニュートン法を普通はユークリッド空間で考えるわけですけれども、これを多様体上にあらかじめ拡張しておいて、多様体上のニュートン法というものをここに適用すれば実際にいいアルゴリズムが得られると期待される。スライドには書いていないんですけれども、実際この球面上の最適化問題に多様体上のニュートン法を適用しますと、それは実はレイリー商反復法と全く同じアルゴリズムになるということが証明されています。そういうわけで、既存のほかの分野での手法、今の場合ですと、数値線形代数の分野で知られているアルゴリズムと多様体上のニュートン法は実は等価であると、こういったことがありまして、そうするとこれはニュートン法ですから、一般に局所的な 2 次収束性を持つとかそういうことが証明できますので、そういったことは実はレイリー商反復でも成り立つということが、多様体上の最適化という観点からわかったりもする。それはちょっと余談にはなりますが、そういった形で多様体上の最適化問題というのは、こういうところに例えばあらわれるということであります。

　では、多様体、多様体と言っているんですけれども、定義をここに書いておきました。そうすると、少しややこしい定義なんですけれども、今日は大ざっぱなところで、この厳密な定義というのはそんなに必要にはなってきませんので、集合 $M$ の各点の近傍がユークリッド空間と同相であるときにこの $M$ のことを多様体と呼びます。つまり、局所的にはユークリッド空間と同一視できるような集合ということです。すなわち、3 次元空間の中の 2 次元の滑らかな曲面の概念を一般化したようなものになっています。なので、イメージとしては、まさにこの 3 次元空間の中の滑らかな曲面を想像していただけると、今日の話はわかりやすいかと思います。
　特に、タイトルにリーマン多様体とあるんですが、この多様体 $M$ の各点における接空間と呼ばれるベクトル空間に内積が与えられているとき、 $M$ のことを特にリーマン多様体といいます。これも後ほどもう少し詳しくご説明をします。

　リーマン多様体の例としましては、例えば $n-1$ 次元の球面、これは先ほど紹介しましたが、これは多様体ですし、直交行列全体ということで直交群、これも多様体の例になります。それから、 $p$ を $n$ 以下の整数としまして、シュティーフェル多様体と呼ばれるこのような $n \times p$ の縦長の列直交行列全体というものもあります。これは $p=1$ にしましたら、 $n \times 1$ の直交行列全体ということで球面に一致しますし、 $p=n$ の場合は、この直交群に一致するということで、球面と直交群を特別な場合として含むような多様体、これがシュティーフェル多様体であります。
　それからほかにもありまして、実射影空間というものがあります。これは、 $\mathbb R^n$ の中の原点を通る直線全体というものです。すなわち、射影空間の一つ一つの点というのは、 $\mathbb R^n$ の中の原点を通る直線になっています。直線を点として持つような多様体が射影空間です。それから、これをもうちょっと一般化しまして、 $\mathbb R^n$ の中の $p$ 次元の部分空間全体というものも多様体になっています。これはグラスマン多様体と呼ばれます。これも $p=1$ にしますと、1 次元の部分空間ということは原点を通る直線ですから、グラスマン多様体でこの $p$ を $1$ にした場合というのは、ちょうど実射影空間になっているということで、グラスマン多様体の特別な場合が射影空間となっています。
　ここでちょっとすき間をあけているのは、この 3 つとこの下の 2 つにはちょっと違いがありまして、この上の 3 つというのは、いずれも自然に外側の空間、球面でしたら $\mathbb R^n$ の中に入っていますよとかそういうことなんですが、こういう外側の空間というのが自然に定義される。ところが下の空間ですと、これは一つ一つの点が直線であったり部分空間であったりということですから、外側の空間というのはそう簡単には定義できないということで、そういう違いがあるんですけれども、埋め込める多様体と埋め込めない多様体といういい方をします。
　外側の空間がわからないようなこういう抽象的な多様体があるわけですが、こういったものも統一して理論としては扱えます。想像しやすいのはこういう外側の空間があるものなんですが、実際の理論としては、こういうちょっと抽象的なものも一緒に扱えるという話をしていくということです。

　では多様体上の最適化ってどういうふうにやるのかということなんですが、まずユークリッド空間の場合の探索方向、これは多様体 $M$ の考えている点における接ベクトルとして選びましょう。後ほど図をお見せします。ユークリッド空間の更新式ではこういう直線探索というのをやっていたんですが、これも多様体上では一般にはできません。まずこの和が定義されているとは限りませんし、仮に外側の空間でこういう和が定義されていたとしても、これは直線探索ですから、多様体というのは一般に曲がっているものを考えていますので、この直線というのは多様体からはみ出ていますから、こうやって次の点を決めようとしてもこれは多様体の上に乗っていないということで、これはできない。ということで、直線のかわりに曲線を考えます。多様体 $M$ の上で今考えている点 $x_k$ から探索方向 $\eta_k$ の方向に伸びるような曲線を考えまして、この曲線の上で次の点を探しましょうということです。そのためには、レトラクションと呼ばれる写像が必要になってくるんですが、これは後ほど定義しますが、こういう写像がありましたら、こういうふうに多様体上の曲線を定義できて、これで次の点を計算するということになっています。

　図をお見せする前に、その $R$ という、レトラクションというものを使えばアルゴリズムは一般的な枠組みとしてこういうふうに書けます。ほとんどユークリッド空間の場合と同じで、初期点を選びまして、ここは反復なんですけれども、探索方向は接ベクトルとして選んで、それからステップ幅を計算して次の点をこういう曲線の上で計算します。

　これは図をお見せしたほうが早いと思います。点 $x_0$ という多様体上の点があったとしまして、多様体上の点が初期点として与えられたとして、このときにこの点におけるこの多様体の接ベクトルとして探索方向を求めます。そうしましたら、この探索方向ベクトルに接するような曲線を考えまして、この曲線の上で次の点を探します。そうしたら後は反復なので、またこの点で接ベクトルとしてこの探索方向を計算する。そうして探索をどんどん進めていく。そして最適解に収束していくような点列をつくりましょうということになっています。

Ａ：素朴な疑問なんですけれども、ユークリッド空間の場合には探索方向というのは、その関数の降下方向を選べばいいというのは、アイデアとしてわかるんですけれども、多様体上で接ベクトルを選ぶというその根拠というか理由というのは何でしょうか。
佐藤：そうですね。接ベクトル以外に探索方向をあらわすうまい概念が自然にはないと思います。一般の多様体でしたら。どの方向に探そうかといったときに……。
Ａ：それは実際の例えば計算のしやすさとか、そういうものまで考慮すると後々になって接ベクトルというのが扱いやすいということがあるとか。
佐藤：というのもありますし、抽象的な多様体でしたらそもそも「接していなくてもいいので、はみ出るようなベクトルを考えたい」といった場合に、そもそも外側の空間がないということがあるので、そうしますともう接ベクトル以外に考えられる幾何学的な対象というのが自然には定義できないと思います。
Ａ：わかりました。
佐藤：ありがとうございます。

　その接ベクトルとして選ぶ探索方向なんですが、どう計算するかといったときに、最急降下法でしたらやっぱりユークリッド空間と同じように関数の勾配の逆方向にするということなんですが、この ${\rm grad}$ というのは多様体上の勾配ということで、通常のユークリッド空間の場合の勾配とはちょっと違う幾何学的な曲がりぐあいを反映した量になっています。それから共役勾配法でしたら、やっぱり最初の探索方向は $-{\rm grad} f$ なんですが、じゃあそれより後の探索方向はというと、勾配の逆方向に 1 つ前の探索方向を何倍かして加えるということで、実はこれにも、多様体ならではの問題というのがあります。それは何かというと、こちらは $x_{k+1}$ というところでの接ベクトルなんですが、この $\eta_k$ というのは 1 つ前の点、 $x_k$ での接ベクトルということで違う接空間に入ってきますので、このままでは足せないということで、そういう問題もあったりします。これが今日のメインのお話ということになってきます。

　ここまではざっとした多様体上の最適化のお話でして、ほかにも幾何学的な量が出てきますので、簡単にご紹介をします。

　まず、さっきから接空間と何回か言っているんですが、これは点 $x$ における $M$ の接空間 Tangent space of $M$ at $x$ ということで、 $T_x M$ と書きます。各点 $x$ において接空間と呼ばれるベクトル空間が定まります。これは、イメージは 2 次元曲面の各点において接平面があるのと同じように思っていただいて、それを一般化したような概念ということです。もう少し厳密にはこのように定義されるんですけれども、多様体 $M$ がユークリッド空間の部分多様体であって、つまり外側のユークリッド空間があるような場合でしたら、普通にこの曲線の $t=0$ での微分というのはこういう普通の微分と同一視して問題ないので、こういうものが接ベクトルだというふうに思っていただいていいと。つまり 2 次元曲面の場合と同じような感じになっています。
　じゃあ球面の場合でということで、球面の例をいろいろとつけ加えながら話をしていきたいんですが、球面の場合でしたらイメージしていただいたらわかるように、 $x$ という球面上の点がありましたら、外側の空間 $\mathbb R^n$ での $x$ に直交するようなベクトル全体というのが点 $x$ における球面の接空間ということになります。

　続きまして、リーマン計量というものがあります。これは、先ほどちょっと言ったんですが、各点 $x$ においてその接空間があるんですが、そこに内積を与えるような、かつ滑らかな写像のことです。また球面の場合の例ですが、球面は外側に大きいユークリッド空間 $\mathbb R^n$ がありますので、ここで標準内積をこういうふうに考えることができる。これをそのまま使ってやって、リーマン計量というのを定義することができます。これの意味は、球面上の点 $x$ における接ベクトルを 2 つ $\xi$ と $\eta$ ととってきたときに、それら自身もまた $\mathbb R^n$ の中に入っていると思えますので、ここでの内積の仕方をそのまま使って $\xi^T \eta$ ということで、これを内積としましょうと。そうすると、この接空間の中に内積が入りましたということで、任意の点 $x$ についてこういうふうに内積を与えるものとしてリーマン計量 $g$ が定義できるということになっています。

Ｂ：接空間はリーマン多様体のみに依存するものなんですか。さっきの目的関数の最小化のところで関数値には全く関係なくて、曲面の接している方向だけ向いているということですか。
佐藤：接空間自体は多様体だけに依存しています。
Ｂ：最急降下法も。
佐藤：最急降下法のときは、それは目的関数に依存します。
Ｂ： ${\rm grad}$ と言っているのは、これとはまた別ですか。
佐藤：また別です。この次に出てきます。ありがとうございます。

Ｃ：リーマン計量のところで、 $\zeta$ とか $\eta$ というのは、どういうイメージのものなんですか。上の $a, b$ は $n$ 個の実数が並んでいるなとわかりますけれども、その下の $\zeta$ とか $\eta$ というのはどういうものかちょっと想像つかないので。
佐藤：これも球面の場合という特別な例で言うと、まさに $n$ 個の成分を持っているような数ベクトル、 $\mathbb R^n$ の元と思っていただいて結構です。もっと具体的に言うと、 $\mathbb R^n$ の中で点 $x$ をあらわすベクトルとこういう関係にあるようなものということです。なので、 $\mathbb R^n$ の中での内積をそのまま使うことができると。

佐藤：こういうふうにリーマン計量を $g$ と書いたりもするんですが、もうちょっと簡単に単に $\xi$ と $\eta$ の内積というのをブラケットで書く書き方も後々使います。右下に $x$ とかと入っているのは、どの点における接空間を考えているかということをあらわすためにつけてあります。これは点 $x$ における接空間での接ベクトル $\xi, \eta$ の内積をあらわすという書き方です。

　今、おっしゃっていただいた勾配なんですけれども、勾配というのはこのリーマン計量に依存する概念でして、多様体上の関数 $f$ 、最適化の目的関数をイメージはしているんですけれども、別にそうでなくてもよいもっと一般の話ですが、 $f$ の点 $x$ における勾配というものは、まずその点 $x$ における接ベクトルであって、かつ微分に対してこういう関係式を満たすものとして定義されます。これも具体的に球面の場合でやりますと、球面上のレイリー商関数ということで、先ほど考えたものですが、まず $f$ をユークリッド空間全体に拡張したものを $\bar{f}$ とします。つまり、こういうふうにしておきます。そうすると、この $\bar{f}$ の通常のユークリッド空間での勾配というのは、よく知られているように $2Ax$ ということになります。そうすると、 $\xi$ という接ベクトルがあったときに、これは方向微分と思っていただいたらいいんですが、 $f$ の点 $x$ における $\xi$ 方向の微分というのは、 $2Ax$ と $\xi$ の内積になるので、こういうふうに書けると。ただ、じゃあ、 $(2Ax)^T \times \xi$ ということで $2Ax$ が勾配かというと、ユークリッド空間ではそうなんですが、多様体上ではそうではなくて、というのは、これは接ベクトルではないので、勾配になる資格がなくて、ちょっと書きかえをします。この書きかえというのは、この $-xx^T$ という部分をつけ加えた形になっているんですが、これは $x^T \xi$ というのはさっきの話で、 $\xi$ が $x$ と直交しているので、ここは 0 になりますから、この等号は成り立っています。
　こういうふうに書きかえることの意味というのは、こう書きかえてやると、この式というのは $2 (I_n-xx^T) Ax$ と $\xi$ の内積ということになっていますので、こういうふうに書ける。そうするとここは実は $x$ に直交しています。これは $x^T \times 2 (I_n-xx^T)$ というのを計算すれば、 $x^T x = 1$ であるということに注意すると消えますので、これは接ベクトルにちゃんとなっている。ということで、接ベクトルとして $\xi$ との内積でこの関係式を満たしていますから、結局この部分が球面上での勾配であるということになります。もうちょっとイメージを持ちやすいように言いますと、結局これは何をしているかというと、ユークリッド空間でのこの勾配というのは、球面の情報が全く入っていないので球面からはみ出てしまうんですけれども、それを接空間に射影したような形になっています。この $I_n-xx^T$ というところがまさに接空間への射影作用素になっている。こうすると接ベクトルになるので、めでたく多様体上、球面上の勾配が求まったということです。こういうことを一般の多様体でもやっていくことになります。

Ａ：ちなみに今は、外側の空間としてユークリッド空間を考えられる場合には、標準内積を考えればわかりやすいんですけれども、外側のユークリッド空間がない場合というのは、内積をどういうふうにとるかは難しいんですか。
佐藤：そうですね。外側のユークリッド空間が定義されないような場合ですと、個別にいろいろ考えないといけないと。もうちょっと一般の場合でも、リーマン計量が与えられているような多様体の部分多様体である場合には、その外側のリーマン多様体の内積の取り方をそのまま採用しまして、部分多様体でのリーマン計量とすることはできます。

佐藤：ということで、一般には、どうやって計量を入れるかというのは、そのときどきで考えないといけないことではあります。ただ、実際数値計算できるようなものというのは、やっぱり何かしら行列であらわされていたりというのがほとんどですから、そういうことで、普通のベクトル空間の内積の入れ方をうまく使って計量を入れてやることができるという話になります。

　このセクションの最後で、さっき少し紹介したレトラクションというものなんですけれども、これは具体的にはこういうふうに定義をします。 $TM$ というのは、接バンドルと呼ばれるものでして、各点における接空間を全部合わせたような集合です。そこから多様体への写像 $R$ というものは、この 2 つを満たすときにレトラクションと言います。
　 $R_x$ というのは、 $R$ を点 $x$ における接空間に制限したものというふうに定義しますが、このときにこの $R_x$ に零ベクトルを与えたら $x$ が返ってきて、 $R_x$ を 0 のところで $\xi$ 方向に微分してやったら $\xi$ そのものが返ってくる。これが定義なんですが、意味をもうちょっと書きますと、点 $x$ とそれからその点 $x$ における $\xi$ という接ベクトル、これを任意に取りまして、最適化を見据えましたらこういう曲線を考えることになるんですが、こういう曲線を考えますと、この $t=0$ での値というのは $R_x(0)$ ということで、定義から $x$ 、それからこの曲線の $t=0$ での微分というのはこういうふうに書きあらわされて、これも定義から $\xi$ ということで、結局のところこういうふうに曲線を定義してやれば、この曲線は初期点が $x$ で、初速度ベクトルが $\xi$ である。つまり点 $x$ から $\xi$ 方向に伸びるような曲線をこのレトラクションを用いればこういうふうに定義することができる。逆に言うと、そういう曲線を定義したいのでレトラクションはこういうものを満たすように定義してみるということになります。

　これは球面の場合の例なんですが、球面の場合はこういう簡単な式で $x$ と $\xi$ の関数として、こういう $R$ を定義してやるとこれがレトラクションの一例になっています。イメージとしては、これはちょっと球面のつもりの図なんですが、球面上の点 $x$ で、特に最適化で言えば探索方向 $\xi$ というのを考えていると思って、じゃあ $x+\xi$ という点を次の点にしたらいいかというと、これは明らかに球面からはみ出ていますので、これを多様体上に落とす必要がある。球面の場合は簡単で、この $x+ \xi$ というベクトルを自分自身のノルムで割ってやれば、これのノルムは 1 になりますので単位球面上に乗っているということで、こういうふうに $R$ を定義してやれば球面への写像になっています。これが、この 2 つの関係を満たすということは簡単に証明できます。ということで、これは球面上のレトラクションの一例になっている。
　こういう感じで最適化をやっていく準備ができたということになります。

Ｂ：やっていることはわかるんですけれども、これは二度手間ではないんですか。もともとユークリッド空間内での方向を接平面に一旦落として、動いてまた球面に戻すんですよね。最初から球面に、ユークリッド空間内で動いたやつを接平面を経由せずに一気にリーマン多様体上に落としてはだめなんですか。
佐藤：まず、外側のユークリッド空間がないような場合ですと、こういうふうにやるしかないです。外側のユークリッド空間がある場合だったら、それは別の手法としてあり得る話で、その辺とこういう方法との比較というのは、やっていかないといけないなとは思っているところです。ただ、探索方向を接ベクトルとして取らずにやるといった場合に、その収束性の例えば理論的な解析であるとか、そういうところは難しくなってくると思います。ちょっとそれは、テクニカルな部分かもしれませんが。
Ｂ：探索方向、そうか、結局一緒ではないんですか。違うのかな。
佐藤：それは、一緒になるような多様体もあり得るとは思うんですが、一般には一緒にならないはずです。
Ｂ：距離を、ステップサイズをうまく調整すれば同じになるんじゃないかと思って。結局、射影して進んで落とすのと、その方向で進んで射影したときに一緒になるように距離の関係はあるんじゃないかと思うんですけれども。
佐藤：そうですね。それは。
Ｂ：一般にはむずかしい。
佐藤：一般の場合だと、ちょっと難しい。イメージとしては確かに成り立っていそうなんですけれども、一般の場合成り立っているかどうかというのはちょっと今は。でも、少なくとも球面の場合は、今おっしゃったことは確かに成り立っているはずです。
Ｂ：わかりました。
佐藤：その場合はステップ幅の調節で全く同じアルゴリズムになると思います。ありがとうございます。

　続いて共役勾配法です。共役勾配法といいましても、通常の $Ax=b$ という線形方程式を解くような共役勾配法とはちょっと違っていまして、それを一般の関数に拡張したような方法になっています。アルゴリズムとしてはこう書けて、先ほど説明した通りですが、この探索方向をどういうふうに決めるかというところがポイントです。

　これは勾配の逆方向に 1 つ前の探索方向を加えるということなんですけれども、ユークリッド空間ではこれでいいんですが、多様体の場合でしたらこの $+$ が実行できない。なぜかというと、これらが違う接空間に入っているから。こっちは $k+1$ 番目の点の接ベクトルで、こっちは $k$ 番目の点の接ベクトルなので、このままでは足せないということで、それを解決するために vector transport と呼ばれる写像があります。

　これは、何かといいますと、定義はこうなんですが、簡単に言いましたら、接ベクトルを違う点における接空間に移動させるような写像であるということです。

　これは図で描きましたらこういうふうになりますが、点 $x$ において $\eta$ という青い接ベクトルがあったとします。そうしますと、レトラクションがあれば、この $x$ と $\eta$ から別の点 $R_x(\eta)$ というのが定義されます。このときに、点 $x$ においてまた別の接ベクトル $\xi$ というのを考えまして、この $\xi$ をこの $R_x(\eta)$ という点での接ベクトルに持っていきたいということを考えます。 $x$ における接空間を赤い色で書いていまして、 $R_x(\eta)$ における接空間をグリーンで書いているんですけれども、この赤い接ベクトルをこのグリーンの接空間に移したい。例えば、この点 $x$ から、根元だけ移してやって $\xi$ をそのままこっちに引っ張ってきたら、これはこのグリーンの接空間からはみ出てしまっているので、これではうまくいかないということで、これをこのグリーンの接空間に何らかの方法で落としてやります。例えば、外側の空間があるこの図のような状況でしたら、接空間に射影します。赤いベクトルをグリーンの空間に射影するというのでもいいですし、外側の空間がなければそういうことはできないので、また別のやり方を考えなければいけないのですが、いずれにしてもそれを実現するような写像 $\mathcal{T}$ というのを vector transport というふうに呼んでいます。
　一般の多様体でも定義できる vector transport というのがあって、それはレトラクション $R$ に対してその微分を考えてやる、こういうものがちょうどこういう図の状況をうまく満たしてくれる vector transport になっているということが証明できます。

　この vector transport というのを使いますと、多様体上の共役勾配法、ユークリッド空間とほとんど一緒なんですが、こっちは $x_{k+1}$ での接ベクトル、 $\eta_k$ 自体は $x_k$ での接ベクトルなんですけれども、この vector transport を使うことによって、次の点 $x_{k+1}$ での接ベクトルに移してやることができるので、そうすると同じ接空間に入ったからそのベクトル空間の中で足し算ができるということで、実際に共役勾配法をこういうふうに書くことができるという話になっています。
　じゃあ、あと、ステップ幅をどう計算するか、それから $\beta$ 、これは何倍するかということですが、これはどう計算するかと、このあたりが共役勾配法のすごく重要な話題になってきます。

　ステップ幅の話なんですけれども、ステップ幅については、こういう $c_1, c_2$ というスカラーを決めておいて、ユークリッド空間で言えば点 $x_k$ が得られているとして、探索方向 $\eta_k$ が降下方向だとします。つまり、今考えている点での勾配との内積が負になっているというときに、こういう 3 つの不等式を考えます。(2) をアルミホ条件と言いまして、(2) と (3) を合わせてウルフ条件、(2) と (4) を合わせて強ウルフ条件と呼んだりするんですが、こういうアルミホ条件とかウルフ条件とか強ウルフ条件というのが満たされるようなステップ幅を使うと、例えば最急降下法だったらアルミホ条件を満たせば大域的収束性を持つとか、例えばウルフ条件を満たすステップ幅と、とある $\beta$ を使った共役勾配法は大域的収束性を持つとか、そういったことが理論的に証明できるということで、いろんな条件が考えられています。

　これを多様体に拡張するんですが、その拡張のところはちょっと飛ばしまして、流れだけで言うと、これらの不等式を $f$ に関して、 $\alpha$ の関数として $\phi$ というのをこのように定めたらこういうふうに書き直すことができて、これは結局、点 $x_k$ から $\eta_k$ の方向に伸びる直線の上で目的関数を見ましょうという関数になっていまして。

　そうすると多様体では同じように点 $x_k$ から $\eta_k$ の方向に伸びる曲線の上で目的関数を見るということで、こういう $\alpha$ の関数を考えれば全く同じようにこういう式を書き下すことができます。これを $\phi$ を使わずにまた $f$ とか $R$ を使って書き直せばこの不等式がこういうふうになります。そうすると、このユークリッド空間バージョンのアルミホ条件なんかが多様体バージョンのものに書き直せる。(8) がアルミホ条件でして、(8) と (9) を合わせてウルフ条件、(8) と (10) を合わせて強ウルフ条件なんていうふうに呼ばれています。
　こういった条件を満たすようにステップ幅を選べばいいわけです。特に、ここに ${\rm DR}$ というのがあらわれているんですけれども、ここは実は先ほど紹介しました vector transport を使って書けるということで、アルミホ条件は vector transport に依存しないんですが、ほかの条件というのは実は vector transport に依存しているような式になっています。この辺は少しテクニカルな話かと思いますが。

　ユークリッド空間の場合、共役勾配法で $\beta_k$ というのはいろいろ計算方法があるということだったんですけれども、どうやって計算するかといいましたら、こういうふうにいろいろとあります。
　ただ、いずれにも共通することとして、目的関数を 2 次関数にして、すなわち線形共役勾配法、通常の数値線形代数の分野で知られている共役勾配法の場合に、こういう値を考えていきましたら、これらは全部いずれも同じものになって、線形共役勾配法に帰着されます。
　いろいろあるんですけれども、特に今回は Fletcher-Reeves の $\beta$ とそれから Dai-Yuan の $\beta$ と呼ばれるものを多様体に拡張していくということをお話したいと思います。

　 $g$ を ${\rm grad}$ ということで勾配とおいて、 $y$ というのはこの勾配の差というふうに置いてやります。そのときに Fletcher-Reeves というのは、今ご紹介したこういう式なんですけれども、多様体上にこれを拡張しようとしましたら、こういうのは接ベクトルなのでノルムの 2 乗というのは普通にその接空間におけるリーマン計量を使って自分自身との内積を取ってやったらいいし、分子のほうも同様ということで、これはすごく自然に多様体上に拡張してやることができます。
　ところが、Dai-Yuan の方法というのは、こういう $\beta$ でして、これはちょっといろいろ問題があります。分子はやっぱり同じように自分自身の内積ということで多様体上の勾配を使って書けばいいんですが、分母のほうは、じゃあ $\eta$ と $y$ の内積かということでこういうふうに書けるのかなと思うんですけれども、じゃあ $y$ はどうしたらいいのか、 $y$ はユークリッド空間では勾配の差だったんですが、多様体上ではやっぱりさっきと同じようにこれは $k+1$ 番目の点での接ベクトル、こっちは $k$ 番目の点での接ベクトルということで、そのままでは引き算できないので、例えば vector transport を使うのかとか、何が自然な拡張の仕方なのかというのは、ちょっと明らかではないところが出てきて、そこは拡張の難しさになっています。

　まず簡単な Fletcher-Reeves からなんですけれども、収束性はほとんどユークリッド空間の場合と同じように証明できるということなんですが、ただ、その $\mathbb R^n$ の場合の証明をなぞっていきますと、多様体ですと vector transport が出てくるんですが、これがこういう不等式を満たしますよということを仮定しないと理論が破綻する箇所が出てきます。この不等式の意味というのは、動かした後の接ベクトルのノルムが動かす前のもとの接ベクトルのノルム以下になっている。つまり、vector transport が接ベクトルのノルムを大きくしてはいけないと、こういう条件を仮定しないとうまくいかないというところがあります。
　じゃあ、どうやって改良しようかということで、案としては、vector transport がベクトルのノルムを大きくしてしまうときは、それは困るので、ノルムを小さくするような正の数を乗じる、つまりスケーリングをしてやったらいいんじゃないかということで、われわれが提案したのが scaled vector transport と呼ばれるものです。これはこういうふうに定義されていまして、vector transport で接ベクトルを動かしてやるんですが、その自分自身のノルムで割ってやって動かす前の接ベクトル $\xi$ のノルムを掛けてやるということで、そうすると結果として得られるこのベクトルのノルムというのはこことここがキャンセルされるので、結局動かす前の $\xi$ のノルムに一致するということで、こういうスケーリングをすれば動かす前と動かした後で接ベクトルのノルムが一致していて、大きくはならないという簡単な考え方です。

　じゃあ、多様体上の Fletcher-Reeves 法というのを、こういうふうに定義できるのではないかというのがこちらです。ステップ幅は、これはユークリッド空間の場合も強ウルフ条件じゃないと収束性はいえないんですけれども、同じように多様体の場合も強ウルフ条件を仮定します。ここで先ほど vector transport を使うと言っていたんですが、その少し違うバージョンということで $\mathcal{T}^{(k)}$ というものを使っています。これの定義はこちらでして、すなわち、接ベクトルをトランスポートしたいんですけれども、 $\mathcal{T}^R$ というのが普通のトランスポートだと思っていただいて、 $\mathcal{T}^R$ というのが $\eta_k$ のノルムを大きくしてしまわないときは問題ないので、それをそのまま使いましょう。そうじゃないとき、つまり vector transport が $\eta$ のノルムを大きくしてしまうようなときは、 $\mathcal{T}^0$ というさっき定義したこちら、スケーリングをするというものを使いまして、長さを縮めてやろうというのがこの $\mathcal{T}^{(k)}$ というものです。ということで、この $\mathcal{T}^{(k)}$ を使うと絶対にここのノルムというのは $\eta_k$ のノルムを超えないということになって、そうするとユークリッド空間の場合の議論にうまく乗りまして大域的収束性が証明できました。

　この辺の仮定は、リプシッツ仮定と呼ばれているもので、標準的な仮定というか、ごく自然な仮定です。大域的収束性と言っていることの意味は、勾配のノルムの列の ${\rm liminf}$ が 0 という意味です。ユークリッド空間の場合でも、Fletcher-Reeves 法の大域的収束性というのはこの形で、ここがユークリッド空間の勾配、 $\nabla f(x_k)$ というふうになっているわけですが、同様の式で示されているということで、全く同様の収束性を多様体上で保証することができたという話です。

Ａ：先ほどの vector transport というのは、ノルムの値が小さくならないといけないという条件があったと思うんですけれども、それについてイメージができていなくて、ノルムの大きさが大きくなっても次の係数の計算、 $\alpha$ 、 $\beta$ の計算でサイズは調整されるような感覚があるんですけれども、そういうものではないんですか。
佐藤： $\beta$ の計算で調整し得るというのはそのとおりです。ただ、 $\alpha$ のほうは。
Ａ： $\beta$ のほうで。
佐藤： $\beta$ のほうで調整できるというのはあります。
Ａ：トランスポートして、ノルムが大きくなっても $\beta$ の計算でつじつまが合わせられそうな気がするんですけれども。
佐藤：そのとおりです。もちろんそれでよくて、結局これでやったときに、ここをスケーリングしますよというかわりに、そのスケーリングの際に使う定数を $\beta$ に掛けてやって、それを改めて $\beta$ と呼べば、これは $\beta$ の方で調節していると見ることもできます。なので、全く同じことなんですけれども、議論しやすいのはあくまで $\beta$ の形はユークリッド空間の場合と対応させて見たいので、そういう意味で $\beta$ のほうに押しつけないでスケーリングをこの $\mathcal{T}$ のほうでやっているという話です。だから書き方としては、アルゴリズムをどうするかというときには、全くこういうスケーリングのところはやらないということにして、 $\beta$ を違う形で書いておくというのはもちろん同じことなんですけれども。
Ａ：それでも、Fletcher-Reeves は。
佐藤：はい、そうですね、どっちが見やすいかというぐらいの話です。

Ｂ：トランスポートするときに、じゃあ小さければ何でもいいんですか。
佐藤：理論的にはオーケーです。ただし、あんまり小さくするとだめかもしれないですね。そこはもとの接ベクトルの情報を落としてしまうぐらい短くしてしまうとうまくいかないかもしれないですね。

　ここ、繰り返しなんですけれども、従来の手法というのでは、ここの不等式が成り立っていないと困るということで、これをもうあらかじめ仮定してしまおうということで、普通の vector transport を用いるというのがあります。ただ、それですと、さっき言いましたようにうまく行かいない場合がある。実際、この不等式が自然かというとそうではなくて、破れることというのは幾らでもあります。なので、そういうときにはやっぱりスケーリングをちゃんとしてやろうというのがわれわれのやり方です。実際、それはこういうスケーリングしていない方法の改良になっているのかということで、その比較なんですけれども。この不等式ですね。この仮定が成り立たないような例をまずは人為的につくってみます。

　対角行列に対してレイリー商最小化をするという問題です。人為的にということの意味は、計量を標準内積ではないもので定義するというところなんですが、ここに $\xi$ と $\eta$ の内積というのを $G$ という正定値対称行列を挟んで定義することにします。この $G$ は点 $x$ によっていまして、ほぼ単位行列なんですが、(1,1) 成分だけ $x$ の第 1 成分の 2 乗を 10,000 倍したものということで定義しています。これの意味は、この問題の最適解というのは、最小固有値 1 に属する固有ベクトルですので、第 1 成分だけがプラスマイナス 1 でほかの成分が全部 0 というのが最適解です。なので、最適解に近づいてきましたら、この $x$ の第 1 成分の 2 乗というのはどんどん 1 に近づいてきますので、この (1,1) 成分というのが非常に大きくなってきます。
　そうすると、内積をこういうふうに定義しますから、接ベクトルのノルムというのが大きくはかられやすくなるということで、そういう状況を無理やりつくってこの不等式が破れるという場合をつくってみました。

　勾配とかレトラクションとかは $G$ というのが入っているので変な形にはなるんですけれども、こういうふうに計算できまして vector transport もこういうふうに計算できる。こういう必要なものを用意しておいて、最適解では目的関数値は $A$ の最小固有値なので 1 でして、 $f(x_k)$ というのが 1 に収束していけば成功です。

　横軸を反復回数、縦軸を目的関数値としたグラフがこちらなんですけれども、10 万反復しても目的関数値は最小値の 1 という値から非常に離れたところにいます。

　このがたがたがちょっと気になるところなんですが、縦軸をちょっと変えてみまして、今度は $x$ の第 1 成分というのを縦軸にとってみました。そうしますと、これはまたすごくがたがたしているんですが、最適解では $x$ の第 1 成分は 1 ということで、これが 1 に収束すれば成功なんですが、 1 に近づいていっては弾き返される。1 に近づいていっては弾き返される。

　これがうまくいかないとすれば絶対にこれが破れているはずなので、じゃあ実際この不等式の破れぐあいというのを見てみましょうということで、この左辺を右辺で割ったような量、比、を考えます。そうすると、この比が 1 以下になっている場合というのはうまくいっているはずなんですけれども、実際その左辺 / 右辺という比を縦軸にしてまたグラフを書きますと、これがやっぱり 1 を超えてしまっているところがたびたびあります。

　じゃあということで、これは10 万反復までいっていますけれども、2 万反復目まででちょっと拡大して、この前の図とこちらの図を合わせて書いたものがこれです。そうすると、その比が 1 を超えてはいけないということなんですけれども、確かに比が 1 を超えているのと同じタイミングで $x$ の第 1 成分がだんだん 1 に近づいていっているところから一気に弾き返されるというようなことが起きているということで、やっぱりその不等式の破れている部分というのが収束を妨げているということが見てとれます。

　そうすると、じゃあ提案手法のようにスケーリングをしてやったらどうかなというと、ちゃんと $x$ の第 1 成分は 1 に収束していっている様子が見えまして。

　実際、最適解と $x_k$ との距離をプロットしましたらこういう感じで、超 1 次収束しているようだということが見てとれる。100 何十反復ぐらいで終わっている。こういう感じになっています。

　ということで、やっぱりスケーリングは有効だなということはわかりました。ただ、今のは人為的な例でしたので、もうちょっと自然な例を今度は考えます。ほとんど同じような問題で、標準計量ということで内積も自然なものを使います。

　1 点だけ、レトラクションは少し違うものにしました。これも自然なレトラクションで、よく使われるものです。ただ、このレトラクションを使うと vector transport はこういうふうになりまして、そうすると必ずさっきから言っている不等式というのが破れてしまいます。常に vector transport は接ベクトルのノルムを大きくしてしまいます。この式から $\xi$ にさらに直交するベクトル $x$ を横に 1 個つけているのでわかるんですけれども、動かした後のほうがノルムも大きくなってしまっているということで。

　既存手法と提案手法を比較してみましたら実際に提案手法のほうは 200 反復ぐらいで収束しているところが、既存手法だったら 300 反復ぐらいかかっているということで、やっぱりスケーリングはこういう自然な例でも有効だということがわかると、こういう話です。

　これが Fletcher-Reeves の場合でして、Dai-Yuan というのも同じようにありますけれども、ユークリッド空間の場合でしたらこのようなアルゴリズムです。

　なぜ Dai-Yuan の方法が Fletcher-Reeves 法と別にまた考えられたかというと、さっきから強ウルフ条件というのを言っていたんですが、そうではなくてもうちょっと緩いウルフ条件というもので実は大域的収束性が保証されるという話があります。ユークリッド空間の場合は大域的収束性が証明されています。

　これを多様体上に拡張したいということで、また同じように、ただちょっと難しいところがあったりするんですけれども、ちょっとそれは省略しまして。

　いろいろと試行錯誤を経ながら頑張ってこの $\beta$ というのを多様体上に拡張していくと、最終的にはこういう感じになります。

　かなりややこしい式なんですけれども、さらに $y$ をこういう式で定義すると多様体上への自然な拡張になっているということがわかります。
　少しだけ補足すると、ユークリッド空間の場合の $y_k$ というのは、この $g_{k+1} - g_k$ ということだったんですが、多様体上ではこれらが異なる接空間に入っているから引き算できないということで、じゃあ、この $k$ 番目のほうを vector transport してやったらいいのかというふうにさっき言ったんですけれども、実際それではなくて、 $g_{k+1}$ から、 $g_k$ をvector transport してやってさらに補正のためのスカラーを掛けたものを引かないとうまくいかないということがわかります。

　いろいろ試行錯誤を経てこういうものを得まして、先ほどと同じように大域的収束性が証明できました。

　これも数値例を最後に見ますと、同じ球面上のレイリー商の最適化の例で、DY と書いてあるのが Dai-Yuan です。FRと書いてあるのが先ほどまで説明していた Fletcher-Reeves の方法。wWolfe と書いているのは普通のウルフ条件、つまり弱ウルフ条件のつもりなんですが、sWolfe というのが strong Wolfe ということで強ウルフ条件を満たすようにステップ幅を決めているというようなものになっています。
　そうすると、DY というのは水色と赤色ということで、ステップ幅のほうを合わせてこの水色と黄色、DY と FR を比べたら DY のほうがいいということがわかりますし、この赤色と紫色を比べると、これはちょっとどっちがいいかわかりにくいんですけれども。

　もうちょっと次元を上げていったらやっぱりこの赤色の DY のほうがどうもよさそうだということがわかります。

　さらにもうちょっと詳しく見ていきますと、反復回数でいってもやっぱり DY は FR に比べて少ない反復回数で収束する。次元はこっちが100 次元でこっちが 500 次元の問題です。関数の評価回数とかで見ますと DY のやっぱり弱ウルフでやるというのがよかったり、勾配の評価回数もそうです。気になるのは計算時間ですけれども、計算時間で言っても DY をウルフ条件で実装するというのが一番速いということがわかる。そんな感じで DY を提案するというのは、やっぱり FR よりも優れたものを提案するということになっていて、意味があることになっています。しかも、この弱ウルフ条件というのは、強ウルフ条件を満たすようなステップ幅よりも簡単に見つけられるので、そういうところでこの反復回数は多くなってしまっているけれども、関数の評価回数とか勾配の評価回数は小さくなっている。この上の 2 行で比べた場合ですね。反復回数は上のほうが多いんだけれども、評価回数で見ると上のほうが少なくて、結果的に計算時間も短いというようなことになっています。
　こういった形で今のは Dai-Yuan の方法でした。

Ｃ：さっきのグラフだと最適解の距離みたいな感じなんですけれども、今度は勾配のノルムを見ていて違うものを見ている気がするんですけれども、何か理由があるんですか。
佐藤：それは合わせておけばよかったです。理由はないです。
Ｃ：勾配のノルムが十分小さいと十分最適解に近いとか保証みたいなのはあるんですか。
佐藤：それは、個別の評価になってくると思いますが、少なくとももちろん最小点では勾配は 0 というのは理論的に言えているので、ある程度滑らかな関数ですから、その辺の評価はできるはずではあります。

Ａ：さっきの Fletcher-Reeves のほうなんですけれども、不等式が成り立っていない部分がありましたよね。でも、実験結果を見ると収束しているように見えたんですが、それは必要十分ではないということですか。
佐藤：必要十分ではないです。例の不等式を満たすということは収束のための十分条件です。必要条件ではないです。

　今、Fletcher-Reeves と Dai-Yuan を紹介したんですけれども、こことここです。ただ、ユークリッド空間ではこういう基本的な $\beta$ というのが提案されていまして、これは分母が一緒のものとか分子が一緒のものを同じ色であらわしているんですけれども、結局、分子が 2 通りありまして、分母の選び方というのが 3 通りあって、 $2\times 3$ で6 通り提案されています。ほかにも探索方向をこういう勾配の逆方向に 1 つ前の探索方向を加えるだけじゃなくて、さらに適当なベクトルを使ってもう 1 つ加えてやろうという、こういう 3 項共役勾配法というのも提案されています。
　ということで、今は FR と DY の話をしたんですけれども、ほかの $\beta$ も多様体上に拡張できるはずですし、こういう 3 項共役勾配法というのも多様体上に拡張できるはずで、こういうのはどうなるのかなというのは個人的に今後見ていきたいなと思っている話です。

　ということで、まず多様体上の最適化の概観を見てきまして、特にじゃあ実際に最適化はどういう手法でやるのかということで共役勾配法を詳しく説明しました。
最後に、実際、こういう応用例があるということを紹介しようと思っているんですけれども。

　まずは特異値分解への応用というのがあります。数値線形代数への応用の一例ということで、 $m\times n$ の縦長の長方行列を考えて、こういうシュティーフェル多様体 2 つの積多様体上の最適化問題を考えましたら、その解というのは実は特異ベクトルとすごく関係しているということがありまして、そうするとこの最適化問題を解くと特異値分解ができるということで、これは最近、相原先生と一緒に研究させていただいている話で、応用数理学会等で何回か発表させていただいています。
　特異値分解のアルゴリズムだというと、いろいろと特異値分解には優れたアルゴリズムがありますので、例えば速度はこっちのほうが速いなどとはなかなか言えないですけれども、ほかの例もあるということで、目的関数を変えたり多様体を変えても同じ話で、ここで研究した話というのは、ほかのところにもどんどん使えますから、そういうことで今日ははほかの例も紹介します。

　統計のところで正準正準相関分析というのがありますので、そういうところへの応用の話です。平均 0 の 2 組のデータ行列があったとしまして、分散共分散行列とかそういったものをこういうふうに定義しております。このとき、この $X$ と $Y$ の列ベクトルを適当な数ベクトル $u, v$ を用いて線形結合させてやって新しい列ベクトル $f$ と $g$ というのをつくります。つまり、変量を線形結合したという感じです。この $f$ と $g$ の間の相関係数というのは定義はこうなので、実際計算するとこんな感じになる。この相関係数を最大にするような線形結合の仕方、つまり最大にするように $u$ と $v$ を決めようというのが正準相関分析と呼ばれる統計の手法です。
　そうすると、これを最大化するということなんですが、これは無制約の問題ではあるんですけれども、この $u$ と $v$ というのは同次性を持っていますので、分母の平方根の中身が 1 になるような条件をつけてやります。そうすると、この分子だけでこういう簡単な形になりまして、これは最初に紹介したレイリー商の例と似ていて、この $C_x$ と $C_y$ というので球面がちょっと歪められてはいるんですけれども、一般化球面と呼ばれる多様体 2 つの直積の上での問題というふうに考えることができます。

　さらに、この $u$ と $v$ というベクトルを横に伸ばしていって行列にしてやります。行列にしたら今の問題はこういうふうに拡張できるんですが、 $G$ という正定値対称行列があったときに、こういう列直交行列っぽい感じなんですけれども、こういうふうに一般化シュティーフェル多様体というのを定義しておきましたら、この一般化シュティーフェル多様体 2 つの積多様体の上での問題というふうに書き直せるということで、例えば正準相関分析は 2 つの一般化シュティーフェル多様体の積多様体上の最適化問題になっている。こうすると、先ほどの特異値分解の問題と非常によく似ているということになっています。

　という話もありますし、あと制御の話もありまして、制御理論においては、こういう状態方程式と呼ばれるものを考えるんですが、 $x$ は状態、 $u$ が制御入力で $y$ が出力。こういうシステムを考えるときに、この状態の次元 $n$ というのが大きいといろいろ困ることが多いということで、これを小さくしたい、次元を小さくしたモデルというのが考えられます。この $A, B, C$ というのは、そのシステムの特性を決める行列なのですが、これをうまく小さい次元の行列を選んでやることで、この元のシステムと低次元化されたシステムが似たような振る舞いを示すように $A, B, C$ を決めたいという問題です。
　定式化の方法としては、 $A, B, C$ はこういうふうに $U$ という列直交行列でこういう変換を受けているんだと仮定するというのがあります。そうしますと、列直交行列 $U$ で $A_m, B_m, C_m$ をうまく決めてやって、この 2 つのシステムが近いようにできればいい。

　そうすると、これはやっぱりシュティーフェル多様体上の問題になっていて、目的関数はもとのシステムと低次元化したモデルとの誤差の 2 乗になっている。これは、制御の言葉で言うと伝達関数の差の $H^2$ ノルムというものなんですが、ちょっといろいろと行列が複雑に絡み合ってはいるんですけれども、結局 $U$ の関数として定義できるので、例えば先ほどの共役勾配法を使うなんていうことができます。

　また、テンソル補完問題というのもあります。これは、与えられた 3 階のテンソルがあって、このテンソルというのは特定の添字のところだけ成分がわかっているという状況です。そのわかっている成分のところにうまく合うように低ランクの異なるテンソル $X$ というのを見つけようという問題です。つまり、ランクを固定しておいて $X^*$ のわかっている成分のところとの差の 2 乗和というのがなるべく小さくなるように決めようという問題です。

　これは、テンソルがこういうタッカー分解というのを持つという話がありまして、結局この $G$ とか $U_1, U_2, U_3$ という 3 階のテンソルとシュティーフェル多様体上の行列 3 つ、この 4 つで、1 つのテンソルと 3 つの行列で、書けるということが知られています。そうすると、これは 3 つのシュティーフェル多様体と 3 階のテンソル、こういうサイズのテンソル全体の集合との 4 つの直積を考えればこの積多様体上の最適化問題になります。
　さらに、ちょっとここでこの $U_1, U_2, U_3$ に右側から直交行列を掛けてやって、この $G$ というテンソルにもこういう同じ直交行列を掛けてやると実は $X$ が変わらないということがすぐわかりますので、そうするとその構造で同値類を考えるということで、こういう商多様体を考えることができます。この商多様体上の問題と見ることもできます。

　こういう例もありますし、最後ですが、逆固有値問題への応用ということで、二重確率行列と呼ばれる各行の和と各列の和がいずれも 1 となるような非負の正方行列に関して、DSIEP (Doubly Stochastic Inverse Eigenvalue Problem) という問題があります。これは、与えられた複素数の集合があったときに、 $n\times n$ の二重確率行列、つまりこういう行列で、その固有値がちょうどこの与えられた複素数になる二重確率行列 $C$ を求めるという問題です。これは、いろんなところに応用があるそうです。

　この問題も、oblique manifold と呼ばれる多様体ですとか、狭義上三角行列全体の集合ですとか、直交群とかを使いますと、結局のところ oblique manifold と直交群と狭義上三角行列全体の集合という、この 3 つの多様体の直積の積多様体上の最適化問題というふうに書けます。

　ということで、こういう例もある。これは私の知る限り一番新しい応用例です。これはさっき紹介しました共役勾配法を使ってくれているということで、引用していくれていたので見つけたんですけれども、この問題を解くのに先ほど紹介したような共役勾配法が例えば使われていたりするという話です。

　ということで、いろいろとあるわけなんですが、最後にざっと振り返ります。

　今日のお話は、最適化はリーマン多様体上でどういうふうになっているかということをお話しまして、最後に応用例をいろいろ紹介しました。メインパートとしては、共役勾配法と呼ばれる方法を特に詳しく紹介をしました。
　今後は、先ほどの繰り返しですが、共役勾配法というのはユークリッド空間で現在でも盛んに研究されていまして、いろいろ新しい結果が出てきています。そういったものをリーマン多様体の上に拡張していきたいなということですとか、最後に紹介しましたように、いろんな分野の問題がリーマン多様体上の最適化問題になっているということでその解法をいろいろと多様体上の観点から提案していければ、いろいろと役に立てるのかなというようなことを考えております。
　ということで、以上で発表を終えさせていただきたいと思います。どうもありがとうございました。

質疑

司会：何か会場の方から質問があればお願いします。

Ｂ：一番最初のほうの多様体の例のところで教えてもらっていいですか。シュティーフェル多様体は、 $\mathbb R^n$ に入るんですか。
佐藤： $n\times p$ の行列全体の空間に入るということです。これもユークリッド空間というふうに呼んでいるというわけです。
Ｂ：今回出された例は、全部これで言うと上のやつですよね。
佐藤：そうですね。
Ｂ：外が存在しないときというのが、いまいちぴんと来なくて。
佐藤：実は最後の例だけ、商多様体を考えていまして。これは、外側の空間があるようなこういう多様体。これですと、 $n_1\times r_1$ の行列全体という集合、それから $n_2\times r_2$ の行列全体、 $n_3\times r_3$ の行列全体、それからこういうテンソル全体という普通のユークリッド空間の中に入っているんですけれども、これをこういう多様体で割るということで商多様体を考えていまして、そうすると外側の空間が定義されないと。もうちょっと同じような、似たような例がありまして……。
　例えばこういう例があります。これは、さっきの球面上のレイリー商最小化というのを、それは最小固有値だけだったんですが、小さいほうから $p$ 個の固有値まで求めるということで、ちょっと拡張したような問題です（ ${\rm St}(p,n)$ 上の $X$ についての目的関数 ${\rm tr}(X^TAXN)$ の最小化問題。ただし $N$ は対角成分がすべて正の対角行列）。このときに、例えば $Q$ という $p$ 次の任意の直交行列を用意しまして、 $X$ の右側から掛けてやりましたら、これは ${\rm tr}(Q^T X^T AXQ)$ ということで、結局 $Q$ の部分がキャンセルされるので目的関数値が変わらないということがあります。そういうことなので、実際のところこれはシュティーフェル多様体上全体で探すのではなくて、例えば $X_1$ と $X_2$ の間に、ちょうど直交行列で移り合えるような関係のとき同値であると、同値関係 $\sim$ を定義することにしまして、この同値関係で割ってやれば、つまりこういうふうに移り合えるものを同値類として同一視することで、もうちょっと小さい次元の多様体を考えることができます。これで割るということなんですが、これは ${\rm St}(p,n) / \sim$ と書きますけれども、こういうものになる。そうすると、これで結局 $n\times p$ の列直交行列全体を $p$ 次の直交行列で移り合えるものは同一視してみましたという多様体ですけれども、シュティーフェル多様体の元というのは、 $n \times p$ の直交行列ですから、 $\mathbb R^n$ の中の $p$ 本の直交フレームというふうに思えるので、それで直交行列で、平たく言ったら回転とかで、移り合えるものは同一視しているということですので、結局はフレームが張る部分空間だけ見ているということになります。なので、これは実はグラスマン多様体と一致しています。そうすると、もとのシュティーフェル多様体だけで考える場合に比べて、その分だけ次元が小さくなるので、探索空間が狭まってくる。そうすると、最適化しやすくなるんだけれど、これは外側の空間はないという例になっています。同じような話が実はここ（スライド 62）でもやられているんですけれども。
Ｂ：何で小さくなったのに外がないんでしょうか。それは $\mathbb R^{n\times p}$ には入らないんですか。
佐藤： $\mathbb R^{n\times p}$ には入らないです。代表元として $n\times p$ の行列をとってくることはできます。ただし、多様体としてはあくまでこれの上の点というのは、そういう同値類が一つ一つの点になっていますから、外側の空間というのはないです。ただし、実際の計算上は同値類の代表元を 1 個とってきて、つまり $n \times p$ の列直交行列を 1 個とってきて、代用して、まさに代表させて、計算すればいいので、計算上はうまくできるんですけれども、理論的には外側の空間はないということになっています。
Ｂ：グラスマン多様体上で最適化するときに、さっき言っていた接平面に一旦落とさなきゃいけなくなるんですか、そのときは。それの代表があるんだから、結局、探索方向というのは、 $n\times p$ のユークリッド空間内で一旦探しますよね。
佐藤：はい。
Ｂ：その後、グラスマン多様体の接平面に一旦落としてと経由する必要がどこに出てくるのかというのが、いまいちぴんと。
佐藤：最急降下法の場合でしたら、もしかしたら二度手間になっているかもしれないです。ただ、共役勾配法までくると 1 回接空間に落とさずにという考え方でやろうと思うと、多分、かなり話がややこしくなってきまして、この辺でもやっばり接空間の上での足し算とかという話になってきますし。
Ｂ：全部ユークリッド空間でやればいいんじゃないかと。
佐藤：それは一つあり得るのかとは思いますけれども。
Ｂ：結局、1 反復終わった後にその多様体上に落とすという作業をやるのであれば、それまでは全部ユークリッド空間でやっちゃってもいいように思えちゃうんですけれども、そうやるよりは探索方向の決定は接平面で 1 回やったほうがうまくいくということなんですかね。
佐藤：そうですね。ちょっと、接空間に落とさずにやるというのはなかなか、おっしゃっていることはわかるんですけれども、ちょっと難しいのかなというふうに思っています。
Ｂ：わかりました。
Ａ：それは、現実的には多分ありだと思うんですけれども、収束性証明とかはかなり難しくなるんじゃないかな。
佐藤：その辺も全部ユークリッド空間のほうで話をすれば同じようなことを言えるのかもしれないんですけれども、かなりややこしくなってくるとは思います。
Ａ：ユークリッド空間上でいろいろ計算した後に多様体上に戻したときにどこに落ちるのか。
佐藤：そうですね、その辺の話が。
Ｂ：結局、接平面上でつくったやつを多様体上に落とすときに、同じことをやる、起こるんじゃないか。
Ａ：それはある程度、その多様体上のちゃんと距離を定義すれば、いいところに落ちるというのは、ちゃんと解析されているんです。
Ｂ：じゃあ、最初はもともとはユークリッド空間内で持っている関数をある意味で無制約の状況で降下方法を決めて接平面に落とす。そこの落とし方も結局わからないと言ってるのと同じ気がして。2 段階で落とせば何でわかって、1 回で落としたら何でわからなくなるのかというのが。
Ａ：接平面に落とすときには射影なんですよね。平面上に射影してあげて、それを滑らかな曲面に対して自然に落ちてくるところなんですけれども、よくわからないところからいきなり落とすと、それはどこに落ちているのかというのはわからない。
Ｂ：一気に落ちているようで、1 回、接平面を経由して 2 段階ぽんぽんと落ちたというようなことしかできないということなのかもしれない。
佐藤：あとは、多様体から全くはみ出ているような方向でしたら、その方向に目的関数がどういうふうに減少するかというのを見ても、多様体上で 2 段階経由せずに一気に多様体に落としたときにどういうふうに関数値が変化するかというのはちょっと見にくいのかなと。それもやっぱり 1 段階で落とした場合のはみ出たベクトルと多様体上の点との関係をちゃんと導いておけば議論はできるんでしょうけれども、でもそうすると一般の場合の話というのは多分難しくなると思います。
　個別の場合は、例えばこういう多様体だったら結局一気に落とせばこういうふうになるとかという話は多分できると思うんですけれども、全く一般の場合をやろうと思うとやっぱり接ベクトルとして考えてという話になってくるのではないかなと思います。
Ｂ：接ベクトルに一旦行って、 $\alpha$ とかの方向を決めて落とすところが確かにある。その前に最急降下方向、傾きを決めるところは一旦接平面ですらないところでまず決めるんですね。それが接平面に落ちるときは一般の場合でも、きちんと理論があってというなんですか。
佐藤：勾配は球面という外側のユークリッド空間がある場合の例ということで、射影したような感じだというふうに言ったんですけれども、そもそも一般のリーマン多様体上の勾配というのは、まさにこの式を満たす接ベクトルというふうにしか定義できないということで。そういう意味では、そもそも一般の場合は、はみ出ていてもいいよと言われても、そのベクトルを求められないというか。まず自然な勾配を求めようとしたら、もうその時点で接ベクトルになるという感じです。
Ｂ：意味がわかりました。

Ａ：関係してなんですけれども、方向が決まった後にユークリッド空間と、いわゆる正確な直線探索みたいなことで、関数値を一番下げるように選べると思うんですけれども、それに対応するような多様体上の正確な探索という、そういうものというのは対応するものはあるんですか。
佐藤：それは全くユークリッド空間の場合と同じです。結局、直線探索は何をやっているかというと、さっきちょっと見てきたんですが、今いる点から探索方向に伸びるような直線を考えて目的関数値を見ましょうと、ユークリッド空間の場合ですね。そうすると、 $\eta$ というのが降下方向になっていれば、これ（ $\phi(\alpha) = f(x+\alpha \eta)$ ）がまず最初は右下がりで始まります。これはその直線の上で関数値を見ていっているということです。正確な直線探索をやるというのは、これを次の $\alpha$ にしましょうということなんですが、多様体ではどうなるかというと、多様体でも結局、この直線上で関数値を見ていきましょうというかわりに、点 $x$ から探索方向 $\eta$ の方向に伸びる、レトラクションが定義する曲線を考えてやって、この曲線の上で目的関数の値を見ていきましょうということで、同じように単なる 1 変数の実数値関数 $\phi$ というのを定義できますので、それでこのグラフを描くと全くやっぱり同じようになりますから、結局ここを次の $\alpha$ にしましょうというのが正確な曲線探索とでも呼ぶべきものになっているということで、こっちで対応するものになります。
Ａ：それは、実装は結構大変ですか。
佐藤：それは、ユークリッド空間の場合でも通常正確な直線探索というのはあんまりされないとは思います。いろいろもちろん正確に探索する方法はあるとは思うんですけれども。
Ａ：よくわかっていないんですが、その概念としてまずはユークリッド空間に正確な直線探索があって、それは難しいからいろんな手法が考えられるという。
佐藤：そうですね。
Ａ：そういう意味では、正確な直線探索みたいなのがあった上でそれを多分難しいので…。
佐藤：そうです。ちょっと近似的に近くのやつを持ってきましょうという感じですね。

司会：ほかございますか。

Ｃ：多様体の定義みたいなところで、同相写像というのがあったんですけれども、同相写像というのはどういうものですか。
佐藤：同相写像といいますのは、全単射な写像でかつ自分自身もその逆写像も連続である写像です。すなわち、連続的にユークリッド空間と 1 対 1 に対応がつくということですね。
Ｃ：リーマン計量上で勾配を求めるというのが、ちょっと直感的にはよくわかっていなくて、こういう曲面に沿うようなものを見つけているということになるのか、それともまた違うんですか。
佐藤：沿うようなものではなくて……。
Ｃ：飛び出るもの。
佐藤：そういう意味では、接するものとしてということですね。
Ｃ：沿うものを見つけるというのは難しいんですか。
佐藤：それはベクトルではなくということですかね。
Ｃ：ベクトルではないというか、局所的に多様体を平面化してみて直線探索する、そういうアイデアは難しいんですか。
佐藤：それをやると、結局多様体で曲げてやると結局こういう多様体上の勾配を接ベクトルとして求めてそれに接するような曲線の上で探すのと同じことになります。すなわち、この図で例えばこれが勾配だとして、この勾配という接ベクトルに接するような曲線の上で次の点を探しているんですけれども、これは、局所的にこれはユークリッド空間と同一視できるからということで、同一視したユークリッド空間、この図でしたら平面とこの曲面が同一視できるということですけれども、平面の上でこの話を書き直してやると図的にはこういうことをやっているのと同じになります。
Ｃ：そうすると、リーマン多様体上で解を探索していくというのは、制約条件を常に満たしながら解を探索をしているということですか。
佐藤：そうですね、はい。そのとおりです。
Ｃ：そうすると、例えば、固有値問題だと球上で答えを見つけようとするんですけれども、球の反対側から真の解を見つけようとしている場合もあるということですよね。うまく初期解を選ばないと。
佐藤：そうですね。ただ、実は、今のレイリー商の場合ですと $x$ が最適解なら $-x$ も最適解なので、実は反対側から探しているという条件だったら、反対側の解にいくというようなことになります。ただ、もちろんもうちょっと一般的な関数でしたらそういうことは起きます。
Ｃ：そうすると、何か球の中を突っ切っていくようなのに比べたら遅くなってしまう。
佐藤：それは、あり得るとは思います。そうですね、全然別のアルゴリズムということになってくると思うので、それは状況によってどっちがいいかというのはいろいろあり得ると思います。
Ｃ：わかりました。
佐藤：ありがとうございます。

クロージング

司会：すごくたくさん応用例があって、すごく面白そうな、これからも発展していきそうな面白い分野ですね。
佐藤：ありがとうございます。
司会：なかなか最新の、年号が最近のものがすごく多くて、そんなに活発やられているところというのは、いろいろあるとは言え、あまり多くはないと思うので、ぜひまたほかのことも時間のある人はいろいろ聞いてみるといいかなと思います。
　ちょうど時間になりましたので、これで終わりにしたいと思います。どうもありがとうございました。

プロフィール

2013 年 11 月京都大学大学院情報学研究科博士後期課程期間短縮修了。博士（情報学）。日本学術振興会特別研究員（ＰＤ）を経て、現在、東京理科大学工学部情報工学科助教。幾何学的な連続最適化の理論およびその応用の研究に従事。日本応用数理学会、日本オペレーションズ・リサーチ学会、IEEE、SIAM、各会員。

ホームページ：https://sites.google.com/site/hiroyukisatojpn/