2011年9月30日金曜日

内点法25周年とRobust最適化のサーベイの論文

European Journal of Operational Reseach に accept された論文で、「内点法25周年」というものがある。
ざっと目を通してみたが、25年の歴史を振り返っているのが前半で、後半には QP に適用した場合の多項式時間での収束などの証明が載っている。
また、最後のあたりは matrix free の計算についても触れており、数値実験が行われている。
matrix free のあたりはSDPAでも参考になるかもしれない。

あと、SIAM Review のほうには Robust 最適化のサーベイが掲載されている。
Theory and Applications of Robust Optimization
Robust 最適化はSIAMから本が出ていて、これで基本的な内容はカバーできるが、このサーベイは解りやすい例とこれからの応用を中心にまとめてあって、1本の論文で全体を見通せるような構成になっている。

今日の作業内容:PDF proof チェック 4h
今日のランチ:ちゅらさん タコライス
明日の予測作業時間:2h

2011年9月29日木曜日

内点法の証明手順

今日は内点法の論文をチェックしたが、内点法の証明はいくつかの基本的なステップがある。

(1) KKT 条件の左辺の微分でできる行列が、 KKT 条件の成り立つ点でも逆行列を持つこと(基本的には陰関数定理による)
(2) 中心パスの点がセンタリングパラメータ mu について連続微分可能なこと
(3) mu^k を小さくしながら、KKT 条件の成り立つ点に収束すること

内点法については Wright の本が要点をまとめてあり、非常に参考になる。


ちなみに、今日読んだ論文は記号表記が利用できそうであった。

今日の作業内容:内点法の論文チェック 3h
今日のランチ:信華園 かたやきそば
明日の予測作業時間: 4h

2011年9月28日水曜日

もう一度、基本の論文を再確認

今日はあまり時間が取れなかったので、基本の論文を再復習しておいた。
もう一段、難しい論文についても読み直す必要があるが、こちらは明日になりそうだ。
あと、lubuntu11.10 についても、もう一度 vmware でインストールして、どのようになっているか、TeXなどについても確認しておきたい。


今日の作業内容:再復習 1h
今日のランチ:つかさ 生サーモン照り焼き
明日の予測作業時間:5h

2011年9月27日火曜日

書類の校正

先週書いた書類については、表現が専門的すぎる印象があったので、大幅に校正することにした。すでに一度書いた文章なので大きく変更するのは難しいが、やはりいい書類にするためには必要なことだと考えている。
まだもう少し日数がかかりそうだ。

今日の作業内容:書類校正 3h
今日のランチ:シッダルータ キーマカレー
明日の予測作業時間:2h

2011年9月26日月曜日

Windows 版 SDPA と OpenBLAS

Windows 版の SDPA は OpenBLAS を利用しているが、どうやら 64bit Windows だと OpenBLAS の違いから数値誤差が変化するようだ。
もともと、内点法の場合は、錐の境界に近づくと数値誤差の影響が大きくなることが知られているが、OpenBLAS の違いで数値誤差に変化が出るようである。
なお、基本的に OpenBLAS についてはコンパイル時に git で最新版をダウンロードしてリンクするようにしている。
(詳細は、Windows版の SDPA をダウンロードして、その中にあるコンパイル用のシェルスクリプトをみると分かる)


あと、Windows 版の SDPA のコンパイルのために、Windows 版のコンパイルのためだけに準備してある Debian を久しぶりに起動したが、Debian の sid は lxde で構成しているとアップデートマネージャによるアップデートだけで更新が済み、半年後とのメジャーリリースがある Ubuntu と比べるときわめて楽である。

そういえば、この前、 lxde のメニューからの起動の時に lxterminal の引数を変更できない、と書いたが、これは root 権限を使えば変更できることが分かった。
/usr/share/applications/lxterminal.desktop
に設定ファイルがあり、このなかの Exec が実際のコマンド行である。たとえば、
Exec= lxterminal --geometry=80x15
と変更すれば良い。
ただし、このファイルの設定に失敗すると、lxterminal をメニューから起動できなくなるので、注意が必要である。
(自分も失敗したが、このときはssh でログインしてファイルを修正した。)

今日の作業内容:Windows 版コンパイル 2h + 書類作成 1h
今日のランチ:味庵 チンジャオロースー
明日の予測作業時間:4h

2011年9月22日木曜日

今週は書類作成だった

今週は、書類の作成が中心で時間が終わってしまった。
ただ、この時期の書類は、今後の展開などにも重要なので、やはり時間をかけて書類を作成している。
提出まであと2週間ほどあるので、それまでに何回か見直して修正することになる。

今日の作業内容:書類作成 4h
今日のランチ:らく 鶏の照り焼き
明日の予測作業時間:5h

2011年9月21日水曜日

Lubuntu 11.10 を試してみた

Lubuntu 11.10 の daily build を vmware でインストールしてみた。
iso のダウンロードは、
http://cdimage.ubuntu.com/lubuntu/daily/current/
からできる。
インストールは、インストール言語をC(英語とか日本語とかあるリストの一番上)でインストールして、そのあとで日本語表示などを入れると比較的簡単にできる。

標準インストールでディスク消費量は 2.1GB 程度。Ubuntu の3分の2程度から半分程度である。
ここに sdpa, libsdpa-dev, sdpam をインストールすると、ディスクが 500MB 程度消費される。
500MB は大きいが、これには理由がある。標準で gcc, octave などがインストールされていないので、この3つをインストールするときに同時にインストールされるためである。
SDPA や SDPA-M などは普通に利用できる。

あと、Lubuntu 11.10 は Ubuntu 11.10 に比較すると、かなり高速に動く。メモリ消費量も少ない。
特に、chromium で重たいページをチェックすると差が表れやすいように感じる。

まだベータ版なので修正も入るかと思うが、ほとんど問題なく使える。

ところで、アプリケーションランチャ に lxterminal を追加したとき、引数をつけたい ("lxterminal --geometry=80x15"のようにしたい)のだが、その方法がよくわからなかった。
このあたりは、また方法を探そうと思う。

今日の作業内容:Lubuntu チェック 2h + 書類作成 3h
今日のランチ:食堂 ライスS, 油揚げとわかめの味噌汁, 唐揚げ&ハンバーグ, 秋のバランス惣菜
明日の予測作業時間:4h

2011年9月20日火曜日

Lubuntu 11.10を下調べしてみる

来月になると Ubuntu が 11.10 になるが、その時点で Lubuntu が Ubuntu Family のひとつとなるようである。
Youtube などでは、Lubuntu 11.10 のベータ版を実行している様子などが既に取り上げられているが、Ubuntu と比較するとソフトウェアなどが抑えられ、無駄の少ない構成になっているように思われる。
すこし時間を取って、ベータ版がどの程度になっているかを vmware などで確認しようと考えている。

今日の作業内容:書類作成 4h
今日のランチ:角笛 ハンバーグきのこソース
明日の予測作業時間:4h

2011年9月15日木曜日

一難去って、また一難

この前から考えている問題は、最適性条件を導出するところまではできた。(形ができてしまえば、それが正しいということを示すのは簡単だった。)
ただ、この最適性条件はいまの形式だと微分できない(ニュートン法などに持ち込めない)ため、方程式の形を変形する必要がある。
このあたりがまた難しいところだ。

今日の作業内容:最適性条件 2h + 論文読み 2h
今日のランチ:つかさ カンパチまかない丼
明日の予測作業時間:4h

2011年9月14日水曜日

ここまでのまとめ作り

最近の内容をそろそろどこまで進んだかを把握するためにも、TeX でまとめることにした。
ただ、今日は思っていたほど時間が取れなかったので、明日以降も続けることになる。

あと、最近読んでいた論文は証明に間違いがあったので、間違いについてのメールを著者に送っておいたが、まだ反応は特になし。なんらかの方法で簡単に修正できる間違いなのか、それともクリティカルな間違いなのか、が気になる。

今日の作業内容:TeX でのまとめ 1h
今日のランチ:らく 焼き魚定食
明日の予測作業時間:3h

2011年9月13日火曜日

SDPA のダウンロードは半数が Windows

SDPA のメインのホームページが sourceforge に移ってからだいぶたつので、sourceforge にある SDPA のダウンロードに関する統計情報を確認してみた。
(これは、アカウントとは関係なく確認できる範囲の情報なので、特にパスワードなどは必要なく調べることができる。)

2011-02-11 に sourceforge に登録してから 2011-09-13 の時点までで 1093 のダウンロードがあり、特に 2011-06 からは毎月 200 以上のダウンロードになっている。
なお、登録したのは 2011-02-11 であるが、準備などの期間も含まれているので、公開になっているのは2011-04 からである。

OS については、Windows がトップの 55%, 次が Linux である。
これはダウンロードしたOS なので、「Windows で Linux 向けのソースコードをダウンロードして、あとで Linux にコピー」などした場合には、Windows にカウントされると思われる。
ただ、その効果を含めないとしてもWindows のダウンロードの割合が大きいので、Windows 用のファイルを整備するというのは重要であると考えられる。

国別のベスト5は、1.アメリカ、2.日本、3.フランス、4.スペイン、5.中国となっている。
アメリカは最近になってダウンロード数が増えているようでもある。

なお、Debian, Ubuntu に関しては apt-get でもインストールできるので、そちらでも別途ダウンロード数があり、今回のはそれを含めていない。

今日の作業内容:最適性条件の検討 5h
今日のランチ:味庵 鶏肉の甘味噌炒め
明日の予測作業時間:4h

2011年9月12日月曜日

今日は式変形だけで終わった

この前の最適性条件を違う角度から見たら、もっと使い勝手のいい条件に変形できそうなので変形してみているが、どうやら一筋縄ではいかないようだ。
一般に対称行列X,Yがあったときに、Xの固有ベクトルが Y の固有ベクトルとは限らない。
LP の場合には、対称行列 = 対角行列というような扱いになるのでこの点が表面化しないが、SDP の場合にはストレートに表面化する。
もう少し考えてみることにする。

今日の作業内容:式変形 3h
今日のランチ:シッダルータ チキンカレー \800
明日の予測作業時間:6h

2011年9月9日金曜日

LP へと単純化

昨日読んでいた内容を、 LP に単純化してどういう効果があるのかを調べてみた。
やはり探索方向と関係があるようなので、このあたりは利用できそうだ。

これを逆に固有ベクトルなどを導入して SDP に戻すわけで、その過程がどうなるかが楽しみなところ。

今日の作業内容:LP に単純化 2h
今日のランチ: つかさ しめさば
明日の予測作業時間:4h

2011年9月8日木曜日

最適性条件の論文を発見

この前検討していた SDP への拡張で懸案事項だった最適性条件の論文だが、少し問題が変形される形の状態での条件が掲載されているものを今日になって発見した。
この論文は 2011 Nov の掲載予定のものなので、オンラインで利用可能になってから日が浅いのだろうと思われる。
形が違うので、これをダイレクトに利用するわけにはいかないが、LP に限定するとどうなるか、などもう少し細かいところも検討して利用できるかどうか判断したい。

今日の作業内容:論文読み 2h
今日のランチ:ちゅらさん 豆腐のチャンプル定食
明日の予測作業時間:4h

2011年9月7日水曜日

Farkas の Lemma と KKT 条件

最適化問題で Primal 側の実行可能性を調べるときに、Farkas の Lemma を用いるのが便利であり、それを用いて Primal 側の最適解の情報を Farkas の Lemma で変形してみた。

そこで、周辺の条件も加えて最適解の満たすべき条件を調べて見ると、結局 KKT 条件と同じ条件が出てきてしまった。
もともと Farkas の Lemma は強双対条件が成り立つのを示すのにも使われるので、KKT 条件とも密接な関係があるわけで、結果を見ると当然といえば当然であるが、こうやって過程をチェックするのも勉強になる。

今日の作業内容:Farkas の Lemma で下調べ 2h + 論文読み 2h
今日のランチ:らく 焼き魚定食
明日の予測作業時間:4h

2011年9月6日火曜日

Sun&Yuan の本

昨日、今日と Sun&Yuan の Springer の本で証明などを読んでいるが、途中途中で証明が分かりにくいところが結構ある。
いくつかに条件分岐しないといけないところが、そのうちのひとつしか検討していなかったり、今まで仮定していなかったことが既に仮定されていたかのように登場することもある。

数学関係の書籍には誤植などももちろんあるので、そのあたりを確認しながら読む必要があるのだが、これが逆にかなりの勉強となる。

今日の作業内容:本読み 3h + 書類作成 1h
今日のランチ:みずしま 牛タンと豚バラ炒めの定食
明日の予測作業時間:5h

2011年9月5日月曜日

複数の文献で証明を読む

数理最適化で同じ問題を扱っていても、違う文献だと証明に少しずつ違いがある。
このような場合に2つの文献の証明を比較してみると、理解度が深まる。
たとえば、片方の文献では自明のように扱っているが、もう片方ではなぜそうなるのか理由が書かれている場合もあるし、一方の文献では証明でカバーしきれていないケースが存在する、といったことに気がつくこともある。

今日の作業内容:文献下調べ 3h
今日のランチ:味庵 角煮うどん
明日の予測作業時間:6h

2011年9月2日金曜日

どうやら違う条件だった

昨日、「横断条件」が載っていた論文は、

A. Shapiro, First and second order analysis of nonlinear semidefinite programs,
Math Prog 77 No2 (1997), pp301-

であるが、この論文に載っている内容は自分が探している条件とは少し異なることが分かった。
固有値の関係でずれがあることが分かった。

あと、今日は Yuan の本をチェック。
こちらも参考になりそうなことが書いてあるので、復習を兼ねながら読み進めている。

今日の作業内容:論文読み 2h + 本読み 2h
今日のランチ:角笛 穴子チラシ
明日の予測作業時間:4h




2011年9月1日木曜日

横断条件

SDP を主双対内点法で解くときには、Slater の条件を仮定するのがよく行われるが、「横断条件」というものもあるらしい。

横断条件が満たされるとSlater の条件が自動的に満たされる、ということなので、「横断条件」のほうが狭いとは思う。ただ、「横断条件」の定義が多様体とか微分とかで書かれているので、どのような定義なのかがいまひとつ分かっていない。

「横断条件」の性質を調べてみると、今までとは違ったことがわかるのかもしれない。

今日の作業内容:論文読み 5h
今日のランチ:たんや ざるカレー
明日の予測作業時間:4h