2010年9月30日木曜日

論文読みの続き

今日読んだ論文は

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

2010年9月28日火曜日

SDPA の原稿の修正

SDPA の原稿について、レフリーから修正点がきたので、スケジュールを変更して、今日は修正に時間をあてた。
あまりクリティカルな修正ではなかったので、数学的にはOKそうだ。

SDP relaxation の論文読みは、明日に回す予定。

今日の作業内容:SDPA の原稿修正 6h
今日のBGM: マクロスF OST [1-2], FF12 OST [1,2,4]
今日のランチ:角笛 ポークソテーのきのこソース和え
明日の予測作業時間:6h

2010年9月27日月曜日

SDP relaxation の論文チェック

今日は、以下の5本の 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

2010年9月24日金曜日

convex hull は難しい

今日も一昨日に続いてディスカッション。
やはり convex hull についてでこける。

簡単には証明できないようだ。
convex hull の場合、その中の要素を表す基底が固定しにくいので、それが問題を難しくしている。

今日の作業内容:ディスカッション 3h + 証明トライ 3h
今日のBGM: FF5 Dear Friends
今日のランチ:味庵 卵と明太子の炒め
明日の予測作業時間:5h

2010年9月22日水曜日

ディスカッションな一日

今日は、昨日の続きのような感じでディスカッションがメインだった。
英語でのディスカッションは疲れるので、数学を間違えやすくなるけど(いつも間違えるけど、それがひどくなる)、かなり勉強になった。

今日のディスカッションでよく解からなかったのは、2つの集合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
今日のランチ:日高屋 野菜炒め定食

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 で実行できるようになる。

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

2010年9月17日金曜日

解析力学、つづき

今日までのところで、とりあえず本の本文は読み終わり。
Noether の恒等式に相当するような概念が数理最適化にはないので、これは面白いと思う。
ただ、最後のあたりはそれなりに難しかったので、また週末に目を通すつもりだ。

あと、ワークショップの細かい準備を進めた。

今日の作業内容:解析力学 3h + ワークショップ準備 2h
今日のBGM: FF12 OST [1-2]
今日のランチ:四川 豚の角煮弁当
明日の予測作業時間: 6h

2010年9月16日木曜日

解析力学と主双対内点法

最近書いているとおり、解析力学の本を読んでいる。
解析力学と主双対内点法にある程度の関連があるのはすぐに解かるが、細かいところまでは関連づけられていないところが面白い。
正凖方程式では2つの式で符号があわないが、これも関係がありそうに見える。
いずれにしても、Hamiltonian がよく解からないのでなんともいえないが。
ところで、SDPで量子化学の問題を定式化すると Hamiltonian は係数行列になってしまうので、正凖方程式の Hamiltonian とは別にも見える。これは不思議だ。なんらかの整合性があるのかもしれないが。

あと、今日は CPLEX のインストールを行った。インストール自体は簡単であるが、IBM のサイトから 300MB 程度をダウンロードするのに6時間から7時間ぐらいかかった。「IBM からダウンロード」だからあまり時間はかからないかと踏んでいたが、どうやらアメリカからダウンロードしているようで、かなり時間がかかった。(国内なら Ubuntu の iso でも1時間程度である。)
いずれにしても、問題なく起動できたので良かった。

あと、今日は午前中に集中力が今一つだったので、明日は逆に午前中に解析力学の勉強をしてみようと思う。


今日の作業内容: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

2010年9月14日火曜日

論文投稿

今日は、ようやく SDPARA の論文を投稿した。
最初に書き始めたのが去年の 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

2010年9月10日金曜日

学会最終日

3日間の学会もあっという間に最終日である。
今回の学会は制御系でいつもの最適化系とは異なるところが多いので、今日は最適化系では聞くのが難しいと思われる航空関係のセッションを聞いてみた。

どうやら、いろんな条件の中でいかに安定した飛行を達成するか、というのが重要な目的なようである。
たとえば、風がある状態で飛行船を安定して飛行させる、などの話があった。
数式の細かいところまではさすがに解からなかったが、とても勉強になった。

今日の作業内容:学会参加

2010年9月9日木曜日

学会バンケット

今日は学会のバンケットだった。
インターコンチネンタルでのバンケットで、立食かと思っていたが着席でコース料理だった。
前菜からスープ、魚料理、肉料理、デザート、紅茶と一通りあり、お腹いっぱいであった。
あと、サービスも行き届いており、素晴らしかった。

あと、今日は Hannson の KYP-LMI の話を聞いた。KYP-LMI は構造があるので、SDP にしたときに correlative sparsity が出てくるかもしれない。
これは気になるところだ。

明日は早くももう学会最終日だ。

今日の作業内容:学会参加

2010年9月8日水曜日

学会発表

今日は、国際学会で発表。
制御系の学会であったが、セッションに来た人の人数は最適化の学会のときよりも多かったかもしれない。
あと、一番最初のプレナリー直後のパラレルセッションの最初の枠の最初の部屋の最初の発表、つまり一般の発表では一番最初、というのは、珍しかったかもしれない。

とりあえず、無事に発表が終わり、国際学会も最初のセッションで半分以上終わった印象である。

今日の作業内容:学会発表
今日のランチ: Buco di Muro インカの目覚めとチンゲン菜のパスタ

2010年9月7日火曜日

Matlab の fmincon で十分であった

conjugate の続きであるが、Matlab の fmincon で十分に計算できることが解かった。
しかも、元の論文よりも高速に高精度に解けている。
やはり、データマイニングでは、主双対内点法のような超一次収束のアルゴリズムは必要ないのではないかという印象がある。
もともとサンプルデータはあくまでサンプルであって、サンプルに必要以上の高い精度で近づけること自体にあまり意味がないためである。
精度は低くても大きい問題を解くことが重要そうである。

あと、解析力学の勉強で気になったところを抜粋。
どうやら Lagrannge の未定乗数法には、ディラックが作った拡張のようなものがあるらしい。これは free 変数の扱いに関係するかもしれない。
あと、ネーターの第一定理は、数理最適化とどういった関係があるのか、あるいはまったくないのか気になるところである。

今日の作業内容:conjugate 2h + 解析力学 2h
今日のBGM: FF10 OST [1-4]
今日のランチ: らく うな重
明日の予測作業時間: 6h

2010年9月6日月曜日

conjugate ダメだった

以前から気になっていた conjugate であるが、もう一度計算式を立てなおして式変形をしていたところ、そのときに計算していた SOCP とまったく同じ形になることが解かった。
2週間ぐらいの時間が飛んでしまったが、非常に勉強になった。

ただ、問題の簡単さから Matlab の Optimization Toolbox でも解けるような気がしてきている。
これは、明日の午前中の作業にしよう。
まずは、Optimization Toolbox の使いかたを学習して、それをプログラムに組めばいけるはずである。

あとは、SDPA のバグ取りをしていた。Callable-library は予想外の使われかたをすることもあるため(初期化を2度呼んでみたりなど)、メモリーリークを防ぐ構造を何重にも仕組む必要が有り、この一部分が予想外の使いかたでメモリーリークをしていた。
これについては、バグが取れたので、次のリリースのときに反映させようと思う。

今日の作業内容:SDPA 2h + conjugate 3h
今日のBGM: マクロスF OST [1-2], FF6 OST [1-3]
今日のランチ:つかさ ぶり照り焼き
明日の予測作業時間: 6h

2010年9月3日金曜日

大掃除とconjugateと

午前中に部屋の大掃除を行った。
計算した紙や書類なども含めて、だんだんと溜るので、半年に一度程度、ある程度ばっさりと処理することにしている。
多少なりは綺麗になった気がする。

あと、午後に conjugate の計算をしばらくぶりに行った。
ただ、よくよく考えたら、今計算すべきは conjugate ではなく subgradient だった。
これに気がつくまでに1時間ぐらいロスした。

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

2010年9月1日水曜日

発表練習

来週の学会用の発表練習をしてみた。20分のところ、つっかえつっかえで30分ぐらいかかっている。話す内容をすっきりとさせれば、きちんと20分に収まるかと考えている。

あと、解析力学の本は、復習を兼ねてもう一度最初から読むことにした。

他に、SDPA の開発版のほうのバグをチェック。どうやらメモリ範囲外にアクセスしようとしているのだが、GotoBLAS のほうに原因があるのか、それとも SDPA のほうに原因があるのか、いまひとつ切り分けられていない。GotoBLAS の関数だけを呼ぶようなプログラムを作って確認するのが楽かもしれない。

今日の作業内容:発表練習 2h + 解析力学 2h
今日のBGM: ARIA OST [1-3]
今日のランチ: 信華園 肉野菜炒め
明日の予測作業時間:6h