2017年9月20日水曜日

ソウルに行ってきた

先週のほとんどの時間を使って、ソウル滞在をしてきた。

日本から見ると、北朝鮮のミサイル問題などでソウルに行くのは危ない、と思うかもしれないが、実際にソウルに行ってみるとそれほど大騒ぎをしていなかった。日本のテレビのようにミサイルの発射画面を繰り返して写したりするわけでもないし、避難訓練とかの案内もまったくなかった。
むしろ、着実に生活水準を上げてきているソウルと、デフレ問題などで生活水準がジリ貧で下がってきている東京の差を、きちんと注視するべきだとは思う。なんだかんだ言っても、自分が頑張る場所は東京なわけだし。



ソウルでは、たまたまスケジュールが重なったドイツからの研究者の Max clique に関するSDP緩和の話を聞くことができて面白かった。自分が普段やってないことを聞くというのは、新しい視点ができていいものだと思う。

自分のほうは、SDP 緩和を SOCP で解く方法などを考えてみたりして、普段の環境とは違うと集中力なども違うので、いい転換になったかと思う。


2017年9月8日金曜日

DSDP という良くできたソフトウェア

数理最適化のコアとなる問題は LP であるが、LP に対する数値解法は SDP などに簡単に拡張できるので、LP に対する新しい論文が出てくると「SDP とかsymmetric optimization に使いました」っていう論文は良く出てくる。
面白いと思うのは、symmetric optimization に拡張したからといって、たいていの場合は内点法の時のように新しい知見が得られるわけではない、というところ。

これと同じように full NT direction についての論文も SDP に拡張されたりなど、いろいろと類似の論文がある。
これについては、
A New Full Nesterov–Todd Step Primal–Dual Path-Following Interior-Point Algorithm for Symmetric Optimization
という、簡単に拡張できるところは基本的にカバーしている内容があったりして、参考になる。(つまり、full NT direction でSDPの論文をさらに書くのは新規性の点で難しいってこと。)


ところで、SDP の探索方向には、NT, AHO, HKM といろいろとあるわけだけど、個人的には DSDP が使っている探索方向がベストな探索方向ではないかと思っている。
数理最適化問題の物理的構造を計算に取り込む、という点で非常にうまくできている。実装する時間が見つかれば SDPA/SDPARA に採用したいぐらいだ。これは10年後か20年後の研究に必ず役に立つと思う。





2017年9月4日月曜日

逆行列求めるって、難しいよね、っていう話。

例えば、sqrt(5)*I [ただし、Iは単位行列] の逆行列は、当然ながら (1/sqrt(5))*I である。
ところが、行列のサイズが n = 1000 ぐらいになると、数値計算ではうまく行かないことがある。余因子行列を用いる方法だと行列式が必要であるが、sqrt(5)*I の行列式が Inf になってしまうのである。Matlab なら


>> n = 1000; A = speye(n)*sqrt(5); det(A)
ans =
   Inf

となってしまう。

これが単純に逆行列ならば (1/sqrt(5))*I で処理すればいいので特に問題ないが、主双対内点法で解きたいような問題にこういった構造があったりすると、数値的不安定になったりして、話が非常にヤヤコシイ。


2017年8月30日水曜日

Julia のパッケージが壊れた

Julia でプログラムを組んでいるときに、あるソルバーの数値精度が悪い状況に遭遇。しかも古いバージョンではちゃんと解けていたので、これはJuliaのところで、そのソルバーのパッケージだけ古いのにすればうまくいくのでは?と思った。

その方法は、例えば、
Pkg.pin("JuMP", v"0.9.2")
などとする。(今回問題となっているソルバーは JuMP ではないけど、例として JuMP を使っている。)
ちなみに、バージョン情報は、
$ cd ~/.julia/v0.6/JuMP
$ git tag --format '%(refname) %(taggerdate)'
などとすれば分かる。

こういったことをいくつかのパッケージで行って遊んでいたら、なんとソルバーの関数を呼べなくなってしまった。
Pkg.free("JuMP")
で元のバージョンに戻してもダメになってしまった。

ちょっと謎だが、良く分からないので、
$ rm -rf ~/.julia/v0.6/
として全パッケージを削除して Pkg.add() でインストールしなおしてみた。



2017年8月10日木曜日

学術的「問い」とは

ある書類で、「学術的「問い」」について記述する項目が新設されていた。
今までにないタイプの質問ではあるけど、非常にいい項目ではないかと思う。

いい機会なので、「学術」について改めて調べてみると
https://kotobank.jp/word/%E5%AD%A6%E8%A1%93-460349
によると
#####
①学問。専門性の高いものをいうことが多い。 「 -論文」
②学問と芸術。また、学問と技術。学芸。
#####
とのこと。

あと、こういったものは「リサーチクエスチョン」とも呼ばれていて、それ自体に関する研究もたくさんある。

2017年8月3日木曜日

デスティニー

最近、研究をしていると
「あぁ、この研究をしているのって、デスティニーだよね」
と思うことがしばしばある。

もちろん、destiny であって、よく似た単語の density ではない。

不思議なもので、何年もかかって自分のところに研究内容が来ていたりして、
「あぁ、これがご縁ってやつか」
とか
「あぁ、これを研究するために今まで勉強してたのか」
とか思ったりする。

なんとも不思議なものだ。

2017年8月1日火曜日

Julia が便利すぎる

今回計算しようと思ったのは、
「1辺が長さ1の正方形の中に n 個の点をランダムに置いた場合に、それらの巡回セールスマン問題の距離の平均はいくつ?」
ということ。

巡回セールスマン問題は NP-完全な問題なので厳密解を計算しようとしたら大変なので、モンテカルロシミュレーションを採用してヒューリスティクスを使って求めた場合の平均でいいことにした。ただ、巡回セールスマン問題のヒューリスティクスを実装したものが C や Python だと思ったほか見つからない(正確にいうと、かなりソースコードに自分で手を入れないといけない)。

ということで、Julia で探してみたら、巡回セールスマン問題のヒューリスティクスを実装してあるパッケージが既にあった。しかも、20行ぐらいを自分で書けば当面の目標は達成できる。

結局自分で書いたソースは以下のような感じで、Julia のパッケージを見つけてから10分ぐらいでコーディング完了。

##### ここから ####
using Distances
using TravelingSalesmanHeuristics

n_max = 20
for n = 1:n_max
    T = 10000
    sum0 = 0
    time1 = @elapsed begin
        for i=1:T
            pts = rand(2,n)
            distmat = pairwise(Euclidean(), pts)
            path, pathcost = solve_tsp(distmat)
            sum0 = sum0 + pathcost
        end
    end
    println("n = $n, average = $(sum0/T), time = $time1")
end
##### ここまで #####

で、実行結果は以下のような出力。
n = 1, average = 0.0, time = 0.135839147
n = 2, average = 1.0450777563744278, time = 0.182987882
n = 3, average = 1.5717746211246175, time = 0.240622039
n = 4, average = 1.8913379727886972, time = 0.309000624
n = 5, average = 2.125071816087441, time = 0.376932182
n = 6, average = 2.3193293493322282, time = 0.455320865
n = 7, average = 2.4779204158273442, time = 0.546624336
n = 8, average = 2.6150744388172296, time = 0.690397053
n = 9, average = 2.7494941691386257, time = 1.037431405
n = 10, average = 2.878494437536675, time = 1.229969995
n = 11, average = 2.984631760238664, time = 1.092407702
n = 12, average = 3.0957685529387713, time = 1.467921928
n = 13, average = 3.2022714958643905, time = 1.920219731
n = 14, average = 3.2997237925066214, time = 2.21402169
n = 15, average = 3.3949127954683385, time = 2.097072679
n = 16, average = 3.491072331414203, time = 2.212287591
n = 17, average = 3.5848683927044824, time = 2.481302509
n = 18, average = 3.6700061119169214, time = 2.758670548
n = 19, average = 3.757282880734828, time = 3.06751467
n = 20, average = 3.8405201350048874, time = 3.414271655

思っていた以上に Julia が便利。