学術雑誌の統計データ

日頃、よく参照する学術雑誌は研究テーマの関係で Mathematical Programming であるが、では Mathematical Programming に掲載されている論文が参考文献としてあげている文献について、それらの文献が載っている学術雑誌はどれか。

統計データを検索してみると、
1. Mathematical Programming
2. SIAM Journal on Optimization
3. Mathematics of Operations Research
であった。（ただし、2009年の Math Prog に掲載されている論文のみが対象）

ということで、これらの雑誌の最新版を手元に置いておけるスペースを作成した。
最近は細切れの時間が多いし、あと集中力に欠ける時間帯もある。
これらを手元に置いておけば、こういった時間帯にいつでも参照できて便利である。

統計データには、もちろん、Mathematical Programming をよく参照している学術雑誌に付いてもデータがある。TOP3 は
1. Mathematical Programming
2. SIAM Journal on Optimization
3. European Journal of Operations Research
であった。

TOP3 以降も調べてみると順位が citing, cited で大きく違い、興味深い。

今日の作業内容：統計データチェック 1h + 数値実験確認 1h
今日のランチ： 信華園 レバ野菜炒め \700
明日の予測作業時間：3h

ポートフォリオとSDP

昨日、Math Prog で読んでいた論文の定式化については、以下の論文がベースとなっていた。

A New Cone Programming Approach for Robust Portfolio Selection
Zhaosong Lu

結局のところ、楕円の形の制約を Linear Matrix Inequality に変形しているので、これまで構成してきた楕円の論文とは直接は関係がないようである。
ただ、この論文では、

* 楕円の制約を Linear Matrix Inequaitly に変形するのに S-procedure を用いており、これは何か最適化問題を SDP として定式化できるかどうか検討するのに役立つ可能性がある。
* ポートフォリオ最適化に SDP が利用されている論文として引用することもできる。このなかの参考文献（たとえば、Goldfarb など）もポートフォリオ最適化に数理最適化手法が利用されているようである。

といったことが利点と考えられる。

今日の作業内容：論文校正 2h + 論文読み 3h
今日のランチ：角笛 牛すじ煮込み
明日の予測作業時間：2h

Ubuntu natty チェック

数値実験に時間がかかるので、それと並行して Ubuntu 11.04 の alpha 版をチェックしてみた。

とりあえず、alpha 版でいきなりインストールするのは危険過ぎるので、まずは vmplayer にインストールすることにした。
デスクトップ版をダウンロードしてきて、インストールしてみたが、vmplayer だとうまくインストールがいかないようである。
いくつかのファイルが壊れている、といういメッセージが出て、インストーラーが終了してしまう。

ただ、Live DVD としては実行できるので、これを利用してみた。
Live DVD として起動しておいて、Synaptic で日本のサーバーに変更してから、SDPA がインストールできるかどうか確認してみた。
大量にいろいろなパッケージがインストールされるが(gccやsclapackなど)、SDPAは無事にSynaptic経由（つまりapt-getで）インストールできる。

ついでに、Libreoffice もインストールしてみた。LiveDVD でもインストールできる。
ところで、Libreoffice でも Openoffice のときのように Impress でのキーバインドの変更があまりできない（これが理由でOpenofficeは使っていない）。
これについては、Libreoffice のバグリポートとして登録するのもありと思うので、登録方法を確認してみようと思う。


他に、Math Prog A 126(1) が届いたので、どのような論文があるかを確認。
最初の
Primal-dual first-order methods with O(1/epsilon) iteration-complexity for cone programing
by G. Lan, Z. Lu, R.D.C. Monteiro
は Nesterov の１次法と関連した内容である。
最初は、primal と dual を厳密に分けて話をしていたが、どうやら実際のアルゴリズムでは primal, dual の違いを利用していないようだ。
このあたりは改善の余地ありか？


あと、最後の論文は楕円の計算に関係しているようなので、定式化を確認するために元論文をダウンロードしてきた。
ただ、いまひとつ定式化が理解できないので、もう少し時間をかけて、関係があるのかどうかぐらいは把握したい。

今日の作業内容：Ubuntu natty 2h + Math Prog 2h
今日のランチ：味庵　酢豚
明日の予測作業時間：5h

目的関数の直交性

LP の場合、
min c^T x: st Ax = b, x >=0
max b^T y: st A^T y + s = c, s >= 0
が標準系だが、ここで NN94 の表記をした場合に dual は
min b2^T s: s = A^T y + c, s >= 0
となる。
このとき、c と b2 は直交している、と仮定しても一般性は失わない。
（目的関数が定数だけずれる）

これを使うと何かできるかと思うのだが、いろいろと試してみると、
内点法の計算だと b2 が 計算過程で b に戻った状態で使われるようだ。

もう少し検討するのも面白いかもしれない。

今日の作業内容： 直交性の検討 4h
今日のランチ：四川弁当　豚セロリ炒め
明日の予測作業時間：3h

論文雑誌の省略形

今日は、改訂をしてもらっていた楕円の論文について、一通り目を通して校正をした。
この中で参考文献のスタイルを整えていたが、論文雑誌の名称を省略形で書く必要があるので省略形を調べる。
たとえば、SIAM Journal on Optimization は SIAM J. Optim. となる。
ここで、Optimization を Opt. や Opti. ではなく Optim. にしなければならないが、その基準は、

http://www.issn.org/2-22661-LTWA-online.php

を検索することで解かる。

今日の作業内容：論文校正 5h
今日のランチ：シッダルータ チキンカレー
明日の予測作業時間：4h

証明に失敗

楕円のところで考えていたときに、

ベクトル a,b, 正定値行列 M,N が a^T M a <= 1, b^T N b <= 1 を満たすならば、
(a^T N a) (b^T M b) <= 1 が成り立つ

かと思って、いろいろと式を検討してみた。
しかし、うまく証明できず、あとで検討しなおしたら反例があることが解かった。

あとは、SDPA の論文の校正に必要な表を作ったりなどした。

今日の作業内容：証明失敗 2h + 表作り 3h
今日のランチ： らく うな重
明日の予測作業時間：6h

査読論文読み終わり

SDPAの論文の校正を早めるために、査読論文のほうをできるだけ早く片付けることにしたが、これがやはり時間がかかった。
論文の内容が極めて難しい、というわけではないのだが、証明の一部が間違っていたりして、どうしたら証明を完成できるかを考えるのに時間がかかった。
ただ、証明の仕方を勉強する、という意味では、手ごろな教材でもあった。

とにかく読み終わったので、これをレポートにまとめておくことにしよう。

今日の作業内容：アブストラクト作成 1h + 論文査読 5h
今日のランチ：鶏こまち ハンバーグ丼
明日の予測作業時間：3h

最小長楕円は最小面積楕円か？

たとえば、(x,y) 平面で原点を中心として(x0,y0) を通る楕円を考える。
このとき、一周の長さが最小の楕円と面積が最小の楕円は一致するのか？

これが意外と難しい。
たとえば、x^2/a^2 + y^2/b^2 = 1 という楕円は面積は πab となるが、一周の長さを初等関数で表すことができない。

さらに一般に、n 次元空間で考えたときに、体積は楕円を決定する正定値行列の行列式を介して計算できるが、表面積については意外と解からない。

時間があれば、また調べてみることにしよう。

今日の作業内容：数値実験データ準備 2h + 論文査読 1.5h
今日のランチ：　らく　焼魚定食
明日の予測作業時間： 5h

論文校正の方向性をまとめる

数値実験は、まだ終わらないので、その間に論文の校正のポイントをリストアップ。
やはり、きちんと比較ができるように、改良ポイントがストレートにわかる問題をいくつか解くようにしたほうがよさそうである。

あとは、意外と細かい事務処理がたまりつつあるので、そちらを処理しておいた。

今日の作業内容：方向性まとめ(3h)
今日のランチ：食堂　ハンバーグランチ
明日の予測作業時間：3h

査読論文チェック

論文の校正は数値実験にかかっているので、それと平行して査読依頼が来ている論文をチェックしている。
査読なので内容は書かないが、証明にぽろぽろと誤りがあって、それをひとつひとつチェックするのがかなり大変である。たとえば、必要な前提条件が足りないまま証明を行っている部分が散見される。返信のときにそれらをリストアップすることになりそうだ。


今日の作業内容：論文査読
今日のランチ：角笛　チキンインドカレー
明日の予測作業時間：4h

双対定理と数値的安定性

SDP の内点法では、一般的に Slater の条件を仮定していて、これによって双対定理が成り立っている。
しかし、duality gap が０になることは、もっと弱い条件でも証明できる。

この証明の方法を利用すると数値的に安定するのではないか？と思ったが、うまくいかないようである。
たとえば、graph partition problem は主問題側に実行可能解が存在しない典型的な例である。
これに証明の方法に沿って、最適解の集合を compact にする redundant な制約をいれてみたが、SDPA, SeDuMi で解いても数値精度はそれほど向上しない。

やはり、数値的安定性は難しい問題である。

今日の作業内容：数値的安定性チェック
今日のランチ：四川弁当　豚の角煮
明日の予測作業時間：4h

gpp と sedumi

sedumi はSDPAと比較して数値的に安定している、といわれているが、最近実験してみると gpp の場合にはそうでもないことが解かってきた。
gpp の場合、primal 側に実行可能内点は存在しないが、強双対性定理が成り立つため主問題と双対問題の最適値は必ず一致する。(Slater の条件以外にも強双対定理が成り立つ条件があり、gpp では行列のサイズが偶数のときにそれが成り立つ。[偶数のときは簡単に示せるが、奇数だと簡単にはわからない])
おそらく、homogeneous が影響しているのだろうと思われるが、これについては調べる必要があるのかもしれない。

qap の場合についても似たような現象があるのか調べることにしたいが、gpp の数値実験は、あと２週間程度かかってしまうかもしれない。

今日の作業内容：数値実験確認など
今日のランチ：鶏こまち　鶏せいろ蒸し
明日の予測作業時間：5h

Wolkowicz の論文からの数値実験、やりなおし

Wolkowicz の論文にしたがって問題を生成していた数値実験だが、必要な問題を生成していない、ということが解かったので、もう一度生成しなおした。

ただ、前回の１週間ぐらいかけての数値実験により、ある程度絞りこみを行ってあるので、実質的には 1/100 程度の問題数となっている。
予備的な部分もある程度確認したので、いま行っている gpp, qap の数値実験が終了したら、こちらの実験に移ることにする。

今日の作業内容：数値実験生成しなおし
今日のランチ：つかさ　ブリの唐揚げ
明日の予測作業時間：4h

メールの設定変更の続き

今日は、昨日にひきつづいてメールの設定変更を行っている。
おそらく、いま 40% 程度まで来たので、あと２，３日と言ったところか。
とりあえず落ち着くまでは、重要なメールを見落としていないか注意が必要そうだ。

数値実験については、時間はやはりかかっているが進んでいる。
量子化学の問題は時間がかかりすぎるようなので、もう少し絞りこみが必要かと考えている。

今日の作業内容：メール変更，数値実験確認
今日のランチ：シッダルータ　シーフードカレー
明日の予測作業時間：4h

メール環境の設定変更

迷惑メールなどが増えた関係があったので、今日は大掛かりな作業をしてメール環境を移行している。
おそらく３日ぐらいはメールが安定しないかもしれないが、必要最低限の設定はすでに終わったところだ。
まだ作業が続くので、今日は短めの記事にしておく。

今日の作業内容：メール環境
今日のランチ：らく　焼き魚定食
明日の予測作業時間：4h

QD, DD は Intel Compiler ではコンパイルできない

昨日の machine epsilon を調べる過程で解かったが、
QuadDouble, DoubleDouble のライブラリは Intel Compiler (icpc) ではコンパイルできない。

正確に書くとコンパイルも通るし実行もできるが、桁数が足りていないことがある。
DoubleDouble で確認したところでは、icpc だと double と同じ machine epsilon になってしまう。

SDPA-QD, DD をコンパイルするときには icpc ではなく gcc でコンパイルする必要がある。

今日の作業内容：machine epsilon チェック、論文読み
明日の予測作業時間：5h

machine epsilon の謎

数値実験に関して machine epsilon を確認する必要があったので調べているが、ひとつ解からないことがある。
gcc で #define されている machine epsilon が IEEE の定義の２倍になっていることである。
gcc の場合には、

http://sugarpot.sakura.ne.jp/yuno/?gcc%2Fmacro

に書かれているとおり

$ gcc -xc -E -dM /dev/null | grep EPSILON

で 2.2204460492503131e-16 であるが、IEEE の定義はこの半分である。
なかなかに難しい。


あと、数値実験については予備実験と並行して本実験用の問題の選択を行っている。
基本的に本実験の問題数は予備実験の 10分の1から100分の1程度になるので、どういう問題であれば全体の傾向を掴みつつ論文としてまとまりができるか、が重要である。

今日の作業内容：数値実験＋machine epsilon
今日のランチ：四川　鶏小松菜炒め
明日の予測作業時間：5h

SDPA-GMP を Intel Compiler でコンパイル

SDPA-GMP の数値実験用に Intel Compiler でコンパイルしようとしたがエラーが出るので、以下にコンパイル方法をまとめておく。

1. コンパイラなどを設定
export CC=icc
export CFLAGS="-O2 -openmp -DDIMACS_PRINT -std=c++0x"
export CXX=icpc
export CXXFLAGS=$CFLAGS
export FC=ifort
export FCFLAGS="-O2 -i8 -openmp"
export F77=ifort
export FFLAGS="-O2 -i8 -openmp"
2. configure をする
3. make する
ここで spooles の build がエラーで止まるので、そうしたら
   cd spooles/build
   vi timings.h
   で timings.h を編集し、 の行の後に
struct timezone {
     int tz_minuteswest;
     int tz_dsttime;
 };
   を書き込む。
  make -f makefile global
  cp spooles.a libspooles.a
  cd ../.. (SDPA-GMP のディレクトリに戻る)
  make
 
  これでコンパイルすると、最後のリンクでなぜかうまくいかないので、icpc によるリンクのコマンド(-o sdpa_gmp が指定されているのでわかる）まで来たらいつまで経ってもリンクが終わらないので Ctrl-C で強制終了し、最後のコマンドをコピーペーストする。
このあと、最後のコマンドから -static オプションと最後の -lpthread を外して、リンクしなおす。

この手順によって SDPA-GMP を Intel Compiler でコンパイルできる。


なお、昨日から行っている数値実験は 4800 問中 4300 問まできた。明日には hubbard に移れるかと思う。

今日の作業内容：SDPA-GMP コンパイル
今日のランチ：たちばな　ちらし寿司
明日の予測作業時間：5h

数値実験再開

今日から本格的に数値実験を再開。

gpp, qap については冬休み中の計算で予備計算は終了したので、あとで本計算に移行できる予定。
あと、Wolkowicz の論文のデータについては、 いま予備計算の段階。こちらは計算する問題数が多いがひとつひとつが小さいので明日のうちには終わるかと考えている。（ざっと5000問程度ある）

あと、楕円の計算については、主成分分析の計算を導入する必要がありそうなので、そちらについては明日主成分分析を復習するところから始めることにする。

今日の作業内容：数値実験進行
今日のランチ：らく　さけイクラ丼
明日の予測作業時間：3h

メールチェック

今日は仕事始めなのでメールチェックなどの軽い仕事を中心に進めた。

ところで、SDPA の論文校正はスケジュール的にかなりタイトなことに気がついた。
明日の時点でスケジュールをもう一度確認しなおしたほうがよさそうだ。