投稿
今日読んだ論文は
Nemirovski, Roos, Terlaky : On maximization of qudratic form over intersection of ellipsoids with common center, Math Prog A, 86, 463-473, 1999
で、この論文で扱っている問題は
max x^T A x : s.t. x^T A_i x <= 1
となっている。特に、\sum_i A_i \succ \O という仮定が入っているが、これは実行可能領域のコンパクト性を仮定できるので、いい形の仮定である。（より一般には、A_1,...,A_m の convex hull の中に正定値行列が含まれればよい。）
証明の途中からは難しくて読み飛ばしたが、近似比が constant ではなく m に依存するのが一般的で、constant になるのは特殊な例だけ、というのも勉強になった。
あと、最後の inhomogeneous の変形も重要そうである。
今日の作業内容：論文読み 4h
今日のBGM: Steamboy OST
今日のランチ：いろは 豚汁定食
明日の予測作業時間：5h
2010年9月29日水曜日
Goemans & Williamson
Goemans & Williamson の Max-cut への SDP 緩和についての論文を読む。
Goemans and Williamson: "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming", Journal Of ACM, 42(6), 1995, 1115-1145
「SDP緩和が NP-hard な問題に利用できる」ということを証明した論文であって、やはり SDP 緩和の証明の基本でもある。
特に、Lemma 3.2 の確率に関する系が数学的に重要で、あとはこれのアレンジである。
あと、Lovasz の論文に strongly self-dual という概念があったので、これについても調べてみようと思うが、明日は別の論文を読む予定なので、さらにあとになるかもしれない。
他に、SDPA のソースを Debian だけでなく、Ubuntu でもコンパイルした。
Debian と Ubuntu では gcc のバージョンが違うためか、どちらかで warning にならなくても、もう一方で warning となるケースがある。
（現時点で gcc のバージョンでは Debian-unstable のもののほうが Ubuntu-10.04 のものより新しい）
今日の作業内容：SDPA コンパイル 3h + 論文読み 3h
今日のBGM: EVA OST [1,2]
今日のランチ：信華園 マーボー春雨
明日の予測作業時間：5h
Goemans and Williamson: "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming", Journal Of ACM, 42(6), 1995, 1115-1145
「SDP緩和が NP-hard な問題に利用できる」ということを証明した論文であって、やはり SDP 緩和の証明の基本でもある。
特に、Lemma 3.2 の確率に関する系が数学的に重要で、あとはこれのアレンジである。
あと、Lovasz の論文に strongly self-dual という概念があったので、これについても調べてみようと思うが、明日は別の論文を読む予定なので、さらにあとになるかもしれない。
他に、SDPA のソースを Debian だけでなく、Ubuntu でもコンパイルした。
Debian と Ubuntu では gcc のバージョンが違うためか、どちらかで warning にならなくても、もう一方で warning となるケースがある。
（現時点で gcc のバージョンでは Debian-unstable のもののほうが Ubuntu-10.04 のものより新しい）
今日の作業内容：SDPA コンパイル 3h + 論文読み 3h
今日のBGM: EVA OST [1,2]
今日のランチ：信華園 マーボー春雨
明日の予測作業時間：5h
2010年9月28日火曜日
SDPA の原稿の修正
SDPA の原稿について、レフリーから修正点がきたので、スケジュールを変更して、今日は修正に時間をあてた。
あまりクリティカルな修正ではなかったので、数学的にはＯＫそうだ。
SDP relaxation の論文読みは、明日に回す予定。
今日の作業内容：SDPA の原稿修正 6h
今日のBGM: マクロスF OST [1-2], FF12 OST [1,2,4]
今日のランチ：角笛 ポークソテーのきのこソース和え
明日の予測作業時間：6h
あまりクリティカルな修正ではなかったので、数学的にはＯＫそうだ。
SDP relaxation の論文読みは、明日に回す予定。
今日の作業内容：SDPA の原稿修正 6h
今日のBGM: マクロスF OST [1-2], FF12 OST [1,2,4]
今日のランチ：角笛 ポークソテーのきのこソース和え
明日の予測作業時間：6h
2010年9月27日月曜日
SDP relaxation の論文チェック
今日は、以下の５本の SDP relaxation の論文をチェックした。
[1] Ge and Ye, "On Doubly Positive Semidefinite Programming Relaxations", 2010, Optimization Online
[2] He, Luo, Nie and Zhang, "Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization", 2007, たしか Optimization Online
[3] Luo, Ma, So, Ye and Zhang, "Semidefinie Relaxation of Quadratic Optimization Problems", 2010, IEEE Signal Processing Magazine 20
[4] Nesterov, "Semidefinite relaxation and nonconvex quadratic optimization", 1998, Optimization Methods and Software 9
[5] Ye, "Approximating quadratic programming with bound and quadratic constraitns", 1999, Math Prog 84
[1] については最近のもので、quadratic constraind quadratic proggramming (QCQP) について、SDP 緩和と Doubly-Non-Negative (DNN) 緩和の場合で、どれだけの差があるか、というもの。DNN 緩和だからといって SDP 緩和よりも良くならないことがある、DNN緩和で SDP 緩和よりも改善できる場合でも改善量には限界がある、などが指摘されている。
[2] については、quadratic な制約のみで homogeneous。いろいろな場合を示しているが、それぞれの場合が特殊過ぎる印象。
[3] は信号処理の研究者向けに SDP relaxation をまとめたもの。基本的なところは、Goemans and Williamson をやはりベースにしている。SDP relaxation でどの位の比率で計算できるか、がまとまっている点は、あとで参考にしやすい。
[4] は、nonconvex quadratic optimization でどの程度のことができるかを Goemans and Williamson を拡張する形で展開。
[5] は、[4] をさらに拡張しているが、証明のテクニックは [4] とほぼ同じ流れ。
まとめると、Goemans and Williamson の論文が基本中の基本であって、これを拡張するときに[4]の証明方法が参考になる。
明日は、Goemans and Williamson の論文ともう1本論文をチェックして、どれがつかえそうかピックアップする。
今日の作業内容：SDP relaxation 5h + 解析力学 1h
今日のBGM: Xenosaga III OST [1-2], FF5 OST [1-2]
今日のランチ： シッダルータ ほうれんそうとマッシュルームのカレー
明日の予測作業時間：6h
[1] Ge and Ye, "On Doubly Positive Semidefinite Programming Relaxations", 2010, Optimization Online
[2] He, Luo, Nie and Zhang, "Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization", 2007, たしか Optimization Online
[3] Luo, Ma, So, Ye and Zhang, "Semidefinie Relaxation of Quadratic Optimization Problems", 2010, IEEE Signal Processing Magazine 20
[4] Nesterov, "Semidefinite relaxation and nonconvex quadratic optimization", 1998, Optimization Methods and Software 9
[5] Ye, "Approximating quadratic programming with bound and quadratic constraitns", 1999, Math Prog 84
[1] については最近のもので、quadratic constraind quadratic proggramming (QCQP) について、SDP 緩和と Doubly-Non-Negative (DNN) 緩和の場合で、どれだけの差があるか、というもの。DNN 緩和だからといって SDP 緩和よりも良くならないことがある、DNN緩和で SDP 緩和よりも改善できる場合でも改善量には限界がある、などが指摘されている。
[2] については、quadratic な制約のみで homogeneous。いろいろな場合を示しているが、それぞれの場合が特殊過ぎる印象。
[3] は信号処理の研究者向けに SDP relaxation をまとめたもの。基本的なところは、Goemans and Williamson をやはりベースにしている。SDP relaxation でどの位の比率で計算できるか、がまとまっている点は、あとで参考にしやすい。
[4] は、nonconvex quadratic optimization でどの程度のことができるかを Goemans and Williamson を拡張する形で展開。
[5] は、[4] をさらに拡張しているが、証明のテクニックは [4] とほぼ同じ流れ。
まとめると、Goemans and Williamson の論文が基本中の基本であって、これを拡張するときに[4]の証明方法が参考になる。
明日は、Goemans and Williamson の論文ともう1本論文をチェックして、どれがつかえそうかピックアップする。
今日の作業内容：SDP relaxation 5h + 解析力学 1h
今日のBGM: Xenosaga III OST [1-2], FF5 OST [1-2]
今日のランチ： シッダルータ ほうれんそうとマッシュルームのカレー
明日の予測作業時間：6h
2010年9月24日金曜日
convex hull は難しい
今日も一昨日に続いてディスカッション。
やはり convex hull についてでこける。
簡単には証明できないようだ。
convex hull の場合、その中の要素を表す基底が固定しにくいので、それが問題を難しくしている。
今日の作業内容：ディスカッション 3h + 証明トライ 3h
今日のBGM: FF5 Dear Friends
今日のランチ：味庵 卵と明太子の炒め
明日の予測作業時間：5h
やはり convex hull についてでこける。
簡単には証明できないようだ。
convex hull の場合、その中の要素を表す基底が固定しにくいので、それが問題を難しくしている。
今日の作業内容：ディスカッション 3h + 証明トライ 3h
今日のBGM: FF5 Dear Friends
今日のランチ：味庵 卵と明太子の炒め
明日の予測作業時間：5h
2010年9月22日水曜日
ディスカッションな一日
今日は、昨日の続きのような感じでディスカッションがメインだった。
英語でのディスカッションは疲れるので、数学を間違えやすくなるけど（いつも間違えるけど、それがひどくなる）、かなり勉強になった。
今日のディスカッションでよく解からなかったのは、２つの集合C^* と \hat{C} の違いである。
Q_i (i=1,...,m) が正定値のときに、
C^* = conv{(x,x x^T) : x^T Q_i x <= 1 (i=1,...,m)}
\hat{C} = {(x,X): Q_i \bullet X <=1 (i=1,...,m), X - x x^T \succeq O}
で定義されていて、C^* \subset \hat{C} は簡単に示せる。逆が成り立つのかどうか解からない。
今日の作業内容：ディスカッション 4h
今日のランチ：いろは 豚肉のアスパラガス巻き
明日の予測作業時間：6h
英語でのディスカッションは疲れるので、数学を間違えやすくなるけど（いつも間違えるけど、それがひどくなる）、かなり勉強になった。
今日のディスカッションでよく解からなかったのは、２つの集合C^* と \hat{C} の違いである。
Q_i (i=1,...,m) が正定値のときに、
C^* = conv{(x,x x^T) : x^T Q_i x <= 1 (i=1,...,m)}
\hat{C} = {(x,X): Q_i \bullet X <=1 (i=1,...,m), X - x x^T \succeq O}
で定義されていて、C^* \subset \hat{C} は簡単に示せる。逆が成り立つのかどうか解からない。
今日の作業内容：ディスカッション 4h
今日のランチ：いろは 豚肉のアスパラガス巻き
明日の予測作業時間：6h
2010年9月21日火曜日
ワークショップがあった
今日は、ワークショップがあって、その裏方の仕事がたくさんあった。
ワークショップの話を聞いていて、いくつか面白い話もあった。
ミンコフスキー和や、パズル的なものなどもあったし、グラフ理論の剛性のようなものもあった。
ただ、最近読んでいる本ほどはドキドキしなかった。
今日の作業内容：ワークショップ 8h
今日のランチ：日高屋 野菜炒め定食
ワークショップの話を聞いていて、いくつか面白い話もあった。
ミンコフスキー和や、パズル的なものなどもあったし、グラフ理論の剛性のようなものもあった。
ただ、最近読んでいる本ほどはドキドキしなかった。
今日の作業内容：ワークショップ 8h
今日のランチ：日高屋 野菜炒め定食
2010年9月19日日曜日
Sedumi on octave
今日試してみたところ、sedumi も octave で実行できることがわかった。
patch も作れるが、ここの blog ではファイルを添付できないので、作業内容をまとめておく。
まず、install_sedumi.m では、
[1] flags{1} = '-O'; を flags{1} = ''; に修正する
[2] 以下の2行は先頭に % をつけてコメントアウトする
flags{end+1} = '-DmwIndex=int';
flags{end+1} = '-DmwSize=int';
[3] BLAS,LAPACK を指定する。具体的には
libs = '-lmwblas';
と
libs = '-lmwlapack';
の行を
libs = '/usr/lib/atlas-base/atlas/liblapack.a /usr/lib/atlas-base/atlas/libblas.a';
にする。(libatlas-base-dev をインストールした場合)
[4] mex コマンドを修正する。具体的には
temp = [ 'mex ', flags, ' ', targets64{i}, ' "', libs ,'"'];
が
temp = [ 'mkoctfile --mex', flags, ' ', targets64{i}, ' "', libs ,'"'];
になる。
次に、givens.h の 40行目
#include "matrix.h"
をコメントアウトする（行頭に // をつける）
最後に、論理AND, 論理OR が &,|のひとつずつなのを &&,|| に修正する。
修正が入るファイルは、
SeDuMi_1_21/checkpars.m
SeDuMi_1_21/getsymbada.m
SeDuMi_1_21/install_sedumi.m
SeDuMi_1_21/optstep.m
SeDuMi_1_21/posttransfo.m
SeDuMi_1_21/pretransfo.m
SeDuMi_1_21/sedumi.m
SeDuMi_1_21/stepdif.m
SeDuMi_1_21/widelen.m
SeDuMi_1_21/wregion.m
である。
これらの修正を施すと、sedumi も octave で実行できるようになる。
patch も作れるが、ここの blog ではファイルを添付できないので、作業内容をまとめておく。
まず、install_sedumi.m では、
[1] flags{1} = '-O'; を flags{1} = ''; に修正する
[2] 以下の2行は先頭に % をつけてコメントアウトする
flags{end+1} = '-DmwIndex=int';
flags{end+1} = '-DmwSize=int';
[3] BLAS,LAPACK を指定する。具体的には
libs = '-lmwblas';
と
libs = '-lmwlapack';
の行を
libs = '/usr/lib/atlas-base/atlas/liblapack.a /usr/lib/atlas-base/atlas/libblas.a';
にする。(libatlas-base-dev をインストールした場合)
[4] mex コマンドを修正する。具体的には
temp = [ 'mex ', flags, ' ', targets64{i}, ' "', libs ,'"'];
が
temp = [ 'mkoctfile --mex', flags, ' ', targets64{i}, ' "', libs ,'"'];
になる。
次に、givens.h の 40行目
#include "matrix.h"
をコメントアウトする（行頭に // をつける）
最後に、論理AND, 論理OR が &,|のひとつずつなのを &&,|| に修正する。
修正が入るファイルは、
SeDuMi_1_21/checkpars.m
SeDuMi_1_21/getsymbada.m
SeDuMi_1_21/install_sedumi.m
SeDuMi_1_21/optstep.m
SeDuMi_1_21/posttransfo.m
SeDuMi_1_21/pretransfo.m
SeDuMi_1_21/sedumi.m
SeDuMi_1_21/stepdif.m
SeDuMi_1_21/widelen.m
SeDuMi_1_21/wregion.m
である。
これらの修正を施すと、sedumi も octave で実行できるようになる。
2010年9月18日土曜日
SDPA-M on Octave
ずっと以前に octave で SDPA-M をコンパイルしようとしたところ、あまりにたくさんのエラーが出たために断念していたが、今日もう一度コンパイルしてみたところ、ある程度の修正で実行できることがわかった。
どうやら、octave にかなりの機能追加があったようだ。
実際に SDPA-M をコンパイルするには、octave3.2, octave3.2-headers をインストールしておいて、
mex コマンドを mkoctfile --mex に修正し、-largeArrayDims を外し、CC=${CC} CXX=${CXX} -O -g などのオプションも外す。
これによって、コンパイルが通るようになる。
ただし、mxGetCell のあたりでメモリーリークかなにかで挙動がおかしくなることがあるので、mexsdpa.cpp では
cell_ptr = mxGetCell(F_ptr, cell_index);
の行の後に、
dims = (mwIndex*)mxGetDimensions(F_ptr);
で挙動がおかしくなる dims を上書きする。
あと、param.m の maxNumCompThreads も octave には存在しないので、これも修正する。
この場合は、Matlab との互換性を維持するため、
try
OPTION0.NumThreads = maxNumCompThreads;
catch
OPTION0.NumThreads = 1;
end
のように回避する。
同じ問題を SDPA (コマンドライン) と SDPA-M (Matlab) で解いた場合、オーバーヘッドがある分 SDPA-M のほうが若干遅い。octave にしても、やはり若干遅くなる。
今日の作業内容： SDPA-M on Octave 6h
どうやら、octave にかなりの機能追加があったようだ。
実際に SDPA-M をコンパイルするには、octave3.2, octave3.2-headers をインストールしておいて、
mex コマンドを mkoctfile --mex に修正し、-largeArrayDims を外し、CC=${CC} CXX=${CXX} -O -g などのオプションも外す。
これによって、コンパイルが通るようになる。
ただし、mxGetCell のあたりでメモリーリークかなにかで挙動がおかしくなることがあるので、mexsdpa.cpp では
cell_ptr = mxGetCell(F_ptr, cell_index);
の行の後に、
dims = (mwIndex*)mxGetDimensions(F_ptr);
で挙動がおかしくなる dims を上書きする。
あと、param.m の maxNumCompThreads も octave には存在しないので、これも修正する。
この場合は、Matlab との互換性を維持するため、
try
OPTION0.NumThreads = maxNumCompThreads;
catch
OPTION0.NumThreads = 1;
end
のように回避する。
同じ問題を SDPA (コマンドライン) と SDPA-M (Matlab) で解いた場合、オーバーヘッドがある分 SDPA-M のほうが若干遅い。octave にしても、やはり若干遅くなる。
今日の作業内容： SDPA-M on Octave 6h
2010年9月17日金曜日
2010年9月16日木曜日
解析力学と主双対内点法
最近書いているとおり、解析力学の本を読んでいる。
解析力学と主双対内点法にある程度の関連があるのはすぐに解かるが、細かいところまでは関連づけられていないところが面白い。
正凖方程式では２つの式で符号があわないが、これも関係がありそうに見える。
いずれにしても、Hamiltonian がよく解からないのでなんともいえないが。
ところで、SDPで量子化学の問題を定式化すると Hamiltonian は係数行列になってしまうので、正凖方程式の Hamiltonian とは別にも見える。これは不思議だ。なんらかの整合性があるのかもしれないが。
あと、今日は CPLEX のインストールを行った。インストール自体は簡単であるが、IBM のサイトから 300MB 程度をダウンロードするのに６時間から７時間ぐらいかかった。「IBM からダウンロード」だからあまり時間はかからないかと踏んでいたが、どうやらアメリカからダウンロードしているようで、かなり時間がかかった。（国内なら Ubuntu の iso でも１時間程度である。）
いずれにしても、問題なく起動できたので良かった。
あと、今日は午前中に集中力が今一つだったので、明日は逆に午前中に解析力学の勉強をしてみようと思う。
今日の作業内容：CPLEX インストール 3h + 解析力学 3h
今日のBGM: 電脳コイル OST [1-2], ARIA OST [1-3]
今日のランチ：味庵 五目焼きそば
明日の予測作業時間： 6h
解析力学と主双対内点法にある程度の関連があるのはすぐに解かるが、細かいところまでは関連づけられていないところが面白い。
正凖方程式では２つの式で符号があわないが、これも関係がありそうに見える。
いずれにしても、Hamiltonian がよく解からないのでなんともいえないが。
ところで、SDPで量子化学の問題を定式化すると Hamiltonian は係数行列になってしまうので、正凖方程式の Hamiltonian とは別にも見える。これは不思議だ。なんらかの整合性があるのかもしれないが。
あと、今日は CPLEX のインストールを行った。インストール自体は簡単であるが、IBM のサイトから 300MB 程度をダウンロードするのに６時間から７時間ぐらいかかった。「IBM からダウンロード」だからあまり時間はかからないかと踏んでいたが、どうやらアメリカからダウンロードしているようで、かなり時間がかかった。（国内なら Ubuntu の iso でも１時間程度である。）
いずれにしても、問題なく起動できたので良かった。
あと、今日は午前中に集中力が今一つだったので、明日は逆に午前中に解析力学の勉強をしてみようと思う。
今日の作業内容：CPLEX インストール 3h + 解析力学 3h
今日のBGM: 電脳コイル OST [1-2], ARIA OST [1-3]
今日のランチ：味庵 五目焼きそば
明日の予測作業時間： 6h
2010年9月15日水曜日
Fedora 13 でのMatlab の不具合とconfigure の続き
Fedora 13 で SDPA-M を動かすと、一部変な動きが起こる。
どうやら Fedora 13 では、 MatlabR2010a は完全には動作していないようである。
たとえば、
$ matlab -Dgdb
と gdb を attach して実行しようとすると、これだけで segmentaion fault が起こる。
この fault は最新の R2010b では解決されているのかもしれないが、R2010b がないので確認できていない。
あと今日は、configure スクリプトの調整をしてきた。
configure 関係は、実際にコンパイルまでしないとバグが解からないので、かなり大変である。
今日だけで SDPA を 7 回ぐらいコンパイルしていると思う。
もちろん、download, patch, configure, make, make install, example のテスト までを一括してシェルスクリプトにしているのでだいぶ楽であるが、結果の確認は人手である。
ほかにワークショップの細々とした準備を行なってきた。
今日の作業内容： configure 3h + ワークショップ準備 2h
今日のBGM: FF10 OST [1,2,3]
今日のランチ： らく うな重
明日の予測作業時間: 6h
どうやら Fedora 13 では、 MatlabR2010a は完全には動作していないようである。
たとえば、
$ matlab -Dgdb
と gdb を attach して実行しようとすると、これだけで segmentaion fault が起こる。
この fault は最新の R2010b では解決されているのかもしれないが、R2010b がないので確認できていない。
あと今日は、configure スクリプトの調整をしてきた。
configure 関係は、実際にコンパイルまでしないとバグが解からないので、かなり大変である。
今日だけで SDPA を 7 回ぐらいコンパイルしていると思う。
もちろん、download, patch, configure, make, make install, example のテスト までを一括してシェルスクリプトにしているのでだいぶ楽であるが、結果の確認は人手である。
ほかにワークショップの細々とした準備を行なってきた。
今日の作業内容： configure 3h + ワークショップ準備 2h
今日のBGM: FF10 OST [1,2,3]
今日のランチ： らく うな重
明日の予測作業時間: 6h
2010年9月14日火曜日
論文投稿
今日は、ようやく SDPARA の論文を投稿した。
最初に書き始めたのが去年の 7 月だったので、だいぶかかってしまった。
次の投稿については、もっときちんとしたスケジュールを立てる必要があるかと考えている。
ともあれ、これでひと段落であるため、次を頑張りたいところだ。
あとは、SDPA の configure の調整を行った。
修正していたところで間違いが入っていたことに気がついたので、これを修正した。
他に、解析力学では、Hamilton-Jacobi の方法で母関数を求められるらしいので、これについてはちょっと調べてみたほうがいいかもしれない。
今日の作業内容：論文投稿 2h + configure 3h + 解析力学 1h
今日のBGM: FF8 OST [1,2,4]
今日のランチ：とりこまち 鶏ユッケ丼
明日の予測作業時間：5h
最初に書き始めたのが去年の 7 月だったので、だいぶかかってしまった。
次の投稿については、もっときちんとしたスケジュールを立てる必要があるかと考えている。
ともあれ、これでひと段落であるため、次を頑張りたいところだ。
あとは、SDPA の configure の調整を行った。
修正していたところで間違いが入っていたことに気がついたので、これを修正した。
他に、解析力学では、Hamilton-Jacobi の方法で母関数を求められるらしいので、これについてはちょっと調べてみたほうがいいかもしれない。
今日の作業内容：論文投稿 2h + configure 3h + 解析力学 1h
今日のBGM: FF8 OST [1,2,4]
今日のランチ：とりこまち 鶏ユッケ丼
明日の予測作業時間：5h
2010年9月13日月曜日
Matlab の mex と GLIBCXX
Fedora 13 で Matlab の mex をコンパイルして実行しようとすると、
GLIBCXX_3.4.11 not found
のようなエラーが出ることがある。
これは、Fedora が持っている libstdc++ のバージョンが Matlab の libstdc++ よりも上であることが原因である。(Matlab はインストール時に libstdc++ をインストールしている。)
これを回避するには、コマンドラインからであれば
$ LD_PRELOAD=/lib64/libgcc_s.so.1:/usr/lib64/libstdc++.so.6:/usr/lib64/libgfortran.so.3:$LD_PRELOAD matlab
のようにして matlab を実行する。ここでは 64bit 版なので、32bit 版のときにはすこしファイル名が異なる可能性がある。
なお、GUI でも実行させたいのであれば、
/usr/local/matlab/MatlabR2010a/bin/.matlab7rc.sh
の最初に
export LD_PRELOAD=/lib64/libgcc_s.so.1:/usr/lib64/libstdc++.so.6:/usr/lib64/libgfortran.so.3:$LD_PRELOAD
と書き込む。
今日は、他に SDPARA 7.3.1 のソースコードを準備した。
おそらく明日のうちに SDPARA 7.3.1 を公開できるのではないかと考えている。
あと、論文として
A structured exploiting preprocessor for semidefinite programs derived from the Kalman-Yakubovich-Popov lemma
をチェック。
KYP-Lemma から生成される特殊な形の SDP を高速に解いてる。
特に Schur complment matrix を計算するところでは、入力行列が low-rank であることを利用して高速化している。ここでは、SDPT3 の SCM 計算のルーチンを入れ換えているようだ。
SDPA の場合には、SCM の高速化をしているため、ここのルーチンを入れ換えるのは、相当に難しいと考えられる。
あと、量子化学で少し気がついたのでメモだが、
ある状態の Hamiltonian は電子密度行列の Legendre 変換で結ばれている。
このことはそれなりに重要そうだ。
今日の作業内容：SDPARA ソース準備 1h + KYP-Lemma 2h
今日のBGM: EVA OST [1-3]
今日のランチ：いろは 豚汁定食
明日の予測作業時間: 5h
GLIBCXX_3.4.11 not found
のようなエラーが出ることがある。
これは、Fedora が持っている libstdc++ のバージョンが Matlab の libstdc++ よりも上であることが原因である。(Matlab はインストール時に libstdc++ をインストールしている。)
これを回避するには、コマンドラインからであれば
$ LD_PRELOAD=/lib64/libgcc_s.so.1:/usr/lib64/libstdc++.so.6:/usr/lib64/libgfortran.so.3:$LD_PRELOAD matlab
のようにして matlab を実行する。ここでは 64bit 版なので、32bit 版のときにはすこしファイル名が異なる可能性がある。
なお、GUI でも実行させたいのであれば、
/usr/local/matlab/MatlabR2010a/bin/.matlab7rc.sh
の最初に
export LD_PRELOAD=/lib64/libgcc_s.so.1:/usr/lib64/libstdc++.so.6:/usr/lib64/libgfortran.so.3:$LD_PRELOAD
と書き込む。
今日は、他に SDPARA 7.3.1 のソースコードを準備した。
おそらく明日のうちに SDPARA 7.3.1 を公開できるのではないかと考えている。
あと、論文として
A structured exploiting preprocessor for semidefinite programs derived from the Kalman-Yakubovich-Popov lemma
をチェック。
KYP-Lemma から生成される特殊な形の SDP を高速に解いてる。
特に Schur complment matrix を計算するところでは、入力行列が low-rank であることを利用して高速化している。ここでは、SDPT3 の SCM 計算のルーチンを入れ換えているようだ。
SDPA の場合には、SCM の高速化をしているため、ここのルーチンを入れ換えるのは、相当に難しいと考えられる。
あと、量子化学で少し気がついたのでメモだが、
ある状態の Hamiltonian は電子密度行列の Legendre 変換で結ばれている。
このことはそれなりに重要そうだ。
今日の作業内容：SDPARA ソース準備 1h + KYP-Lemma 2h
今日のBGM: EVA OST [1-3]
今日のランチ：いろは 豚汁定食
明日の予測作業時間: 5h
2010年9月10日金曜日
2010年9月9日木曜日
2010年9月8日水曜日
2010年9月7日火曜日
Matlab の fmincon で十分であった
conjugate の続きであるが、Matlab の fmincon で十分に計算できることが解かった。
しかも、元の論文よりも高速に高精度に解けている。
やはり、データマイニングでは、主双対内点法のような超一次収束のアルゴリズムは必要ないのではないかという印象がある。
もともとサンプルデータはあくまでサンプルであって、サンプルに必要以上の高い精度で近づけること自体にあまり意味がないためである。
精度は低くても大きい問題を解くことが重要そうである。
あと、解析力学の勉強で気になったところを抜粋。
どうやら Lagrannge の未定乗数法には、ディラックが作った拡張のようなものがあるらしい。これは free 変数の扱いに関係するかもしれない。
あと、ネーターの第一定理は、数理最適化とどういった関係があるのか、あるいはまったくないのか気になるところである。
今日の作業内容：conjugate 2h + 解析力学 2h
今日のBGM: FF10 OST [1-4]
今日のランチ： らく うな重
明日の予測作業時間： 6h
しかも、元の論文よりも高速に高精度に解けている。
やはり、データマイニングでは、主双対内点法のような超一次収束のアルゴリズムは必要ないのではないかという印象がある。
もともとサンプルデータはあくまでサンプルであって、サンプルに必要以上の高い精度で近づけること自体にあまり意味がないためである。
精度は低くても大きい問題を解くことが重要そうである。
あと、解析力学の勉強で気になったところを抜粋。
どうやら Lagrannge の未定乗数法には、ディラックが作った拡張のようなものがあるらしい。これは free 変数の扱いに関係するかもしれない。
あと、ネーターの第一定理は、数理最適化とどういった関係があるのか、あるいはまったくないのか気になるところである。
今日の作業内容：conjugate 2h + 解析力学 2h
今日のBGM: FF10 OST [1-4]
今日のランチ： らく うな重
明日の予測作業時間： 6h
2010年9月6日月曜日
conjugate ダメだった
以前から気になっていた conjugate であるが、もう一度計算式を立てなおして式変形をしていたところ、そのときに計算していた SOCP とまったく同じ形になることが解かった。
２週間ぐらいの時間が飛んでしまったが、非常に勉強になった。
ただ、問題の簡単さから Matlab の Optimization Toolbox でも解けるような気がしてきている。
これは、明日の午前中の作業にしよう。
まずは、Optimization Toolbox の使いかたを学習して、それをプログラムに組めばいけるはずである。
あとは、SDPA のバグ取りをしていた。Callable-library は予想外の使われかたをすることもあるため（初期化を２度呼んでみたりなど）、メモリーリークを防ぐ構造を何重にも仕組む必要が有り、この一部分が予想外の使いかたでメモリーリークをしていた。
これについては、バグが取れたので、次のリリースのときに反映させようと思う。
今日の作業内容：SDPA 2h + conjugate 3h
今日のBGM: マクロスF OST [1-2], FF6 OST [1-3]
今日のランチ：つかさ ぶり照り焼き
明日の予測作業時間： 6h
２週間ぐらいの時間が飛んでしまったが、非常に勉強になった。
ただ、問題の簡単さから Matlab の Optimization Toolbox でも解けるような気がしてきている。
これは、明日の午前中の作業にしよう。
まずは、Optimization Toolbox の使いかたを学習して、それをプログラムに組めばいけるはずである。
あとは、SDPA のバグ取りをしていた。Callable-library は予想外の使われかたをすることもあるため（初期化を２度呼んでみたりなど）、メモリーリークを防ぐ構造を何重にも仕組む必要が有り、この一部分が予想外の使いかたでメモリーリークをしていた。
これについては、バグが取れたので、次のリリースのときに反映させようと思う。
今日の作業内容：SDPA 2h + conjugate 3h
今日のBGM: マクロスF OST [1-2], FF6 OST [1-3]
今日のランチ：つかさ ぶり照り焼き
明日の予測作業時間： 6h
2010年9月3日金曜日
大掃除とconjugateと
午前中に部屋の大掃除を行った。
計算した紙や書類なども含めて、だんだんと溜るので、半年に一度程度、ある程度ばっさりと処理することにしている。
多少なりは綺麗になった気がする。
あと、午後に conjugate の計算をしばらくぶりに行った。
ただ、よくよく考えたら、今計算すべきは conjugate ではなく subgradient だった。
これに気がつくまでに１時間ぐらいロスした。
conic programming は基本的に
min c^T x : A*x = b, x \in K
であるが、ここで A,b,c がベクトル u の線形であるとして、関数 f(u) を
f(u) = min c(u)^T x : A(u)*x = b(u), x \in K
を考える。このときに f(u) の subgradient を求めたい。
おそらく厳密には求まらないので（使うときにも精度が必要がない）、最適解の情報を primal,dual の両方から使えば、ある程度できそうな気がしている。
もう少し確認する必要がある。
今日の作業内容：大掃除 3h + conjugate 3h
今日のBGM: EVA OST [1-3]
今日のランチ： さか本 とろろ丼とおそばのセット
明日の予測作業時間：4h
計算した紙や書類なども含めて、だんだんと溜るので、半年に一度程度、ある程度ばっさりと処理することにしている。
多少なりは綺麗になった気がする。
あと、午後に conjugate の計算をしばらくぶりに行った。
ただ、よくよく考えたら、今計算すべきは conjugate ではなく subgradient だった。
これに気がつくまでに１時間ぐらいロスした。
conic programming は基本的に
min c^T x : A*x = b, x \in K
であるが、ここで A,b,c がベクトル u の線形であるとして、関数 f(u) を
f(u) = min c(u)^T x : A(u)*x = b(u), x \in K
を考える。このときに f(u) の subgradient を求めたい。
おそらく厳密には求まらないので（使うときにも精度が必要がない）、最適解の情報を primal,dual の両方から使えば、ある程度できそうな気がしている。
もう少し確認する必要がある。
今日の作業内容：大掃除 3h + conjugate 3h
今日のBGM: EVA OST [1-3]
今日のランチ： さか本 とろろ丼とおそばのセット
明日の予測作業時間：4h
2010年9月2日木曜日
Debian 軽量インストールのまとめ
今日は、Debian のインストールと他の作業を並行して行った。
Debian は Gnome などを入れずに LXDE でインストールできるので、そのまとめをしておく。
（ただし、これは必要なものしか入れないので、何が必要か自分でリストをあらかじめ作っておく必要がある）
1. Debian のサイトから最小インストールの iso をダウンロード (businesscard と名前がついているもの)
2. iso を使って普通にインストール。ただし、パッケージやサーバを選択するときに、「デスクトップ環境」のチェックを外す。（これでGnomeを外せる）
3. ログイン後のターミナルで日本語が表示できないので
export LANG=C
で英語メッセージに切替える
4. /etc/apt/source.list で lenny を sid に変更する。(これは、unstable にあるパッケージを利用するため unstable に変更するので、unstable でも OK なところでのみすること）
5. apt-get update
6. apt-get upgrade
ここで、udev が引っかかって upgrade できないはず。このときは
apt-cache search linux-image
で最新の kernel を見つけて、これをインストールする。例えば、
apt-get install linux-image-2.6.32-5-686
となる（amd64なら最後の 686 が amd64）
ここで再起動。
7. apt-get update
8. apt-get upgrade
9. apt-get install lxde
ここで再起動。
これで、GUI でログインできるようになるが、なぜか今回は gdm が起動せず、CUI ログインの startx は実行できるので、apt-get install xdm で xdm をインストール
あとは、必要に応じて
10. apt-get install update-notifier
11. apt-get install build-essential g++ gfortran
12. apt-get install chromum-browser-l10n
13. apt-get install ttf-vlgothic emacs anthy-el
14. apt-get install gitk
15. apt-get install xpdf
16. apt-get install lv
さらに、日本語を入力するには、
17. apt-get install uim uim-xim uim-anthy
としておいて、メニューから[設定]==[入力メソッド切替器]で uim-toolbar を選択し、ログアウトしてログインしなおす。
これで必要最低限に近い状態にできる。
ただ、Ubuntu を必要最低限にしたときよりも起動やそれぞれの動作に時間がかかるような気がする。
今日の作業としては、他に発表練習。だいたい一通り通して25分以内になった。最初のあたりをつっかえるので、それがなくなれば、20分切れると考えている。
今日の作業内容：Debian 5h + 発表練習 1h
今日のBGM: 解くになし
今日のランチ：角笛 鶏の唐揚げ薬味ソース
明日の予測作業時間：6h
Debian は Gnome などを入れずに LXDE でインストールできるので、そのまとめをしておく。
（ただし、これは必要なものしか入れないので、何が必要か自分でリストをあらかじめ作っておく必要がある）
1. Debian のサイトから最小インストールの iso をダウンロード (businesscard と名前がついているもの)
2. iso を使って普通にインストール。ただし、パッケージやサーバを選択するときに、「デスクトップ環境」のチェックを外す。（これでGnomeを外せる）
3. ログイン後のターミナルで日本語が表示できないので
export LANG=C
で英語メッセージに切替える
4. /etc/apt/source.list で lenny を sid に変更する。(これは、unstable にあるパッケージを利用するため unstable に変更するので、unstable でも OK なところでのみすること）
5. apt-get update
6. apt-get upgrade
ここで、udev が引っかかって upgrade できないはず。このときは
apt-cache search linux-image
で最新の kernel を見つけて、これをインストールする。例えば、
apt-get install linux-image-2.6.32-5-686
となる（amd64なら最後の 686 が amd64）
ここで再起動。
7. apt-get update
8. apt-get upgrade
9. apt-get install lxde
ここで再起動。
これで、GUI でログインできるようになるが、なぜか今回は gdm が起動せず、CUI ログインの startx は実行できるので、apt-get install xdm で xdm をインストール
あとは、必要に応じて
10. apt-get install update-notifier
11. apt-get install build-essential g++ gfortran
12. apt-get install chromum-browser-l10n
13. apt-get install ttf-vlgothic emacs anthy-el
14. apt-get install gitk
15. apt-get install xpdf
16. apt-get install lv
さらに、日本語を入力するには、
17. apt-get install uim uim-xim uim-anthy
としておいて、メニューから[設定]==[入力メソッド切替器]で uim-toolbar を選択し、ログアウトしてログインしなおす。
これで必要最低限に近い状態にできる。
ただ、Ubuntu を必要最低限にしたときよりも起動やそれぞれの動作に時間がかかるような気がする。
今日の作業としては、他に発表練習。だいたい一通り通して25分以内になった。最初のあたりをつっかえるので、それがなくなれば、20分切れると考えている。
今日の作業内容：Debian 5h + 発表練習 1h
今日のBGM: 解くになし
今日のランチ：角笛 鶏の唐揚げ薬味ソース
明日の予測作業時間：6h
2010年9月1日水曜日
発表練習
来週の学会用の発表練習をしてみた。２０分のところ、つっかえつっかえで３０分ぐらいかかっている。話す内容をすっきりとさせれば、きちんと２０分に収まるかと考えている。
あと、解析力学の本は、復習を兼ねてもう一度最初から読むことにした。
他に、SDPA の開発版のほうのバグをチェック。どうやらメモリ範囲外にアクセスしようとしているのだが、GotoBLAS のほうに原因があるのか、それとも SDPA のほうに原因があるのか、いまひとつ切り分けられていない。GotoBLAS の関数だけを呼ぶようなプログラムを作って確認するのが楽かもしれない。
今日の作業内容：発表練習 2h + 解析力学 2h
今日のBGM: ARIA OST [1-3]
今日のランチ： 信華園 肉野菜炒め
明日の予測作業時間：6h
あと、解析力学の本は、復習を兼ねてもう一度最初から読むことにした。
他に、SDPA の開発版のほうのバグをチェック。どうやらメモリ範囲外にアクセスしようとしているのだが、GotoBLAS のほうに原因があるのか、それとも SDPA のほうに原因があるのか、いまひとつ切り分けられていない。GotoBLAS の関数だけを呼ぶようなプログラムを作って確認するのが楽かもしれない。
今日の作業内容：発表練習 2h + 解析力学 2h
今日のBGM: ARIA OST [1-3]
今日のランチ： 信華園 肉野菜炒め
明日の予測作業時間：6h
登録:
投稿 (Atom)