最適性条件の論文

最適性条件の表現方法について考えていたが、埒が明かないので文献調査をしてみた。
いくつかの論文の孫引きをしているうちに、Math Prog に最適性条件を扱っている論文を発見したので、これを読み込んでみることにする。
あと、Yuan の赤い本にも有益そうな内容があることに気がついたので、こちらについてもあとで参照することにする。

今日の作業内容：文献調査 3h + 論文読み 2h
今日のランチ：コピラ　サグチキンカレー
明日の予測作業時間：6h

内点法と Lagranguan Augment

この前から読んでいる論文について、似たような手法がどのようなものがあるか調べてみると、やはり非線形最適化の分野では内点法と Lagranguan Augment が頻繁に出てくる。

内点法は、計算手順が比較的単純なアルゴリズムなので、収束の速さなども研究が進んでおり、そのあたりが参考になる。
ただ、この前から読んでいる内容については、内点法になってしまうと既存研究ですでにあるので、そのあたりをどう取り込んでいくかが考えどころだ。

今日の作業内容：論文下調べ 5h
今日のランチ：つかさ　カンパチまかない丼
明日の予測作業時間：5h

Matlab でのメモリ使用量の確認

Matlab の場合、細かいメモリ使用量を表示する whos というコマンドがある。
ただ、これだと一つ一つの変数を表示するので、全部の変数の合計を知りたいときには、以下のようにする。

      whosResult = whos;
      whos
      whosMemory = 0;
      for wsindex = 1:length(whosResult)
          whosMemory = whosMemory + whosResult(wsindex).bytes;
      end
      fprintf('whosMemory = %f megabytes\n',whosMemory/1024/1024);   
   
これで表示されるのは、その関数で whos が実行されるまでのところの変数だけである。
関数のなかでさらに関数を呼んでいる場合などには、外側の関数でも同じスクリプトを埋め込む必要があるので少し面倒ではあるが、これでメモリ使用状況を確認できる。

今日の作業内容：メモリ使用量 4h
今日のランチ：角笛　チキンステーキ
明日の予測作業時間：6h

Linear and Nonlinear Optimization

この前から考えている SDP 拡張についてだが、やはり一筋縄ではいかないらしい。
最適化問題の最適性条件を作るところから、いきなり頓挫してしまった。

そこで、視点を変えて、基本的なツールにどのようなものがあるかをざっと眺めることにする。
非線形最適化の場合、いろいろと本があるが、最近の本としては

Linear and Nonlinear Optimization
http://math.gmu.edu/~igriva/book/toc.html

が、それぞれの項目が比較的コンパクトにまとまっていて便利である。
基本的な証明なども載っており、実際に拡張しようとしたときに証明としてどのようなステップが必要になりそうか、ということも見通しが立ちやすい。


今日の作業内容：SDP研究 4h
今日のランチ：味庵 豚肉とジャガイモの煮込み
明日の予測作業時間： 5h

SDPARA の論文を再投稿

追加の数値実験などにかなり時間がかかったが、無事に SDPARA の論文を再投稿することができた。
最近は、referee report などもまとめてサイトにアップロードするようになっていて、それらがひとつの PDF に統合されてレフリーがダウンロードできるようになっている。
すべての雑誌が対応しているわけではないが、こういったのはかなり便利である。

これで一仕事終わったことになるので、SDP に拡張しようと思って前に読んでいた論文の続きをそろそろ始められそうだ。

今日の作業内容：SDPARA 再投稿 1h + 論文査読 1h + 論文読み 2h
今日のランチ：つかさ　ミックスフライ
明日の予測作業時間：5h

書類作成の確認

１０月ごろに研究に関しての書類を作成する時期が来るので、前回のときにどのような書類を作成したかを改めて見直しておいた。
それなりに書く時間を取るべき書類なので、今のうちからどのような内容で書くかをある程度絞り込んだ方がいいのかもしれない。

でも、今日までで細かい作業はだいたい終わったので、明日から本格的に戻れそうだ。


今日の作業内容：論文査読 4h + 書類確認 2h
今日のランチ：味庵 イカとセロリの炒め物
明日の予測作業時間：6h

英語の校正で気がついたこと

論文を英語の校正に出したので、その修正で気がついたことを列挙しておく。

1. 「３．１倍高速化」などのときには 3.1-times speedup のように times の前にハイフンが入る
2. Schur complement equation を SCE と略すときには Schur Complement Equation (SCE) のように対応するところを大文字にするのではなく Schur complement equation のように小文字のままにする
3. 24GB memory space ではなく、24-GB memory space
4. 数値実験の結果報告は基本的に過去形。ただし、ソフトウェア自体の性能など、今後もそのままであることが期待できることについて(SDPARAのほうが PCSDPよりも速い、など)は現在形

今日の作業内容：英語の構成の確認 7h
今日のランチ：しばた さけいくら丼とお蕎麦のセット
明日の予測作業時間：5h

主双対内点法のねじれ

主双対内点法の最大の問題点は計算時間が大きいことである。
良い精度が得られるので、ある程度計算時間が大きいのは納得であるが、応用などを考えたときに既存手法と比較して同等程度の精度を得るのに相当時間がかかることかある。
おそらく現在の主双対内点法には、まだ改善の余地があるのだと思われる。

ところで、主双対内点法でひとつ気になっていることがある。
それは、主問題と双対問題を完全には対称に扱えていないことである。
アルゴリズムを解析する際に規約で消えるべきところにシグマが残っている箇所があり、直感的にはねじれが残っている。
これが本当にねじれなのか、またこれを利用して高速化できるかどうかは、少し時間を取って検討してみたいところだ。

今日の作業内容：論文校正 5h
今日のランチ：らく 焼き魚定食
明日の予測作業時間：6h

PENNON のアルゴリズムを下調べ

この前から読んでいる論文を SDP に拡張すると、PENNON が解ける範囲になることに気がついたので、PENNON がそのような拡張になっていないかをざっと確認しておいた。
PENNON は名前の通り Penalty 関数を利用しているので、同じ内容ではなく大丈夫そうであった。
数値実験の比較対象にはするべきかと思うが、それについては SDP に拡張できるということが理論的に解ってからで十分そうだ。

まずは、SDP に拡張できるかどうか、そこから検討してみよう。

今日の作業内容：論文読み 3h + PENNON 下調べ 2h
今日のランチ：角笛 とんかつ
明日の予測作業時間：2h

今日はあまり捗らず

今日は細々とした内容が多くてあまり捗らず。
細切れの時間を利用して、学会のホテルなどを検索しておいた。

学会のときに利用するホテルの条件としては、
[1] 学会会場に近い方がいい（歩いても３ブロック程度がよい）
[2] 空港へのアクセスがわかりやすいところ
[3] ドラッグストア or スーパーが近いところ
[4] 大通りにできるだけ面している、など夜も治安が安定していそうなところ
などを考えることにしている。
これらのあとで金銭面なども検討している。
最近は Google map などで [4] などが比較的検討できるので便利である。

今日の作業内容：ホテル検索 1h
今日のランチ：つかさ　カンパチまかない丼
明日の予測作業時間: 4h

FLOPS で測定してみた

この前の Matlab の高速化だが、やはりまだボトルネックになっているらしく、さらなる高速化が必要とのことであった。
そこで、現在の実装がどれだけ CPU を活用できているかについて検討してみた。

すると、3x800万の行列の列ごとに要素を掛ける計算の場合、１００回繰り返しで 16.16 秒かかった。
これから計算すると
1/16.16 * 3 * 800万 * 100 flops = 138Mflops
出ていることになる。

比較として、octave で行列積を使ってみた。基本的に octave の行列積は ATLAS の dgemm (BLAS level3)が用いられているので、それなりに CPU を効率的に使うことができているはずである。
(GotoBLAS などを用いると、さらにベターだが、今回は簡略化）
結果として 5000x5000 の行列積で 143.35 秒かっかった。これから計算すると
1/143.35 * 5000 * 5000 * 5000 flops = 812Mflops
であった。500x500 だと 0.3807 秒で 300Mflops である。

level3 に対して 6分の1程度の性能まで来ているので、これ以上のスピードアップを図るのであればキャッシュなどの利用も検討対象となる。ただ、Matlab の mex に組み込む必要があり、Linux 専用に組み込むわけにもいかず、そのあたりも考える必要がありそうだ。


あと、ついでに気がついたが、Ubuntu の apt-get でインストールされる octave について、リンクされている ATLAS はマルチスレッドに対応していないようだ。複数コアのCPUで実験してみたが dgemm 利用時でも 101 % を超えることがなかった。


今日の作業内容：Matlab 高速化 2h + 論文読み 4h
今日のランチ：味庵 翡翠麺の冷やし中華
明日の予測作業時間：3h

どうにか論文読み終わり

１５時間ぐらいかかったけど、どうにか論文を読み終わった。
SIAM Optimization に載っている論文だが、数か所誤りのように見えるところもあって、かなり時間がかかった。
ただ、まだ１度、目を通しただけなので何度か目を通してきちんと理解する必要がありそうだ。

今日の作業内容：論文読み 4h
今日のランチ：四川 豚肉のニンニクの芽炒め
明日の予測作業時間：2h

論文読みの続き

この前から読んでいる論文は、証明が難しくて時間がかかっている。
１ページ理解して進むのに１時間ぐらいかかる。

ただ、これをSDPに拡張するような研究は今までされていないので、この論文の証明を理解すれば SDP 拡張へのステップとなると考えられる。
いまは我慢のときなのかもしれない。

今日の作業内容：論文読み 6h
今日のランチ：つかさ しめさば
明日の予測作業時間：6h

校正されている論文

この前から読んでいる論文は、雑誌掲載の分が PDF で入手できなかったので、インターネットで著者のページからダウンロードしてきたものを読んでいたが、どうやら投稿段階のもので数式に誤植などが目立ち読むのが大変になってきていた。

そこで、雑誌からハードコピーをして読み直している。２度目ということもあるが、表記が統一されているので読みやすくなっている。やはり、論文投稿の後にある校正の段階が重要だということが伺うことができる例である。

今日の作業内容：論文読み 4h + 論文チェック 2h
今日のランチ：シッダルータ チキンカレー
明日の予測作業時間：3h

BLASとかで高速化が難しい線形計算

SNL の計算でいまボトルネックとなっている部分が BLAS などでは高速化できないようなので手こずっている。

計算は数学的には簡単で、3 x n 行列 X に対して n 次元ベクトル a があって、このときに 3 x n 行列 Y を求めるものである。ただし、Y(i,j)  = X(i,j) * a(j) である。

Matlab の場合は、
Y = X*spdiags(a,0,length(a),length(a));
でできるにはできるが、これがかなり遅い。

計算式がY(i,j) = X(i,j) *a(j)であるため、各 j について BLAS の daxpy を使うこともできるのだが、iのループが3しかなく、BLAS を呼ぶオーバーヘッドが大きくなり BLAS も効率的に使うことができない。

現状は
 for j=1:n
  val = a(j);
  Y(1,j) = X(1,j) * val;
  Y(2,j) = X(2,j) * val;
  Y(3,j) = X(3,j) * val;
end
でループ展開をして回していて、上記の BLAS, Matlab よりも高速になっているが、それでもボトルネックのままなので、高速化をしたいところである。

なお、n=200万ぐらい必要で、この計算が 3000 回程度必要となっている。

今日の作業内容：Matlab 高速化 3h + 論文読み 3h
今日のランチ：らく 鶏照り焼き冷麦
明日の予測作業時間：2h