エルデシュナンバーの平均値はどうなるんだろうか？

ふと思うと、エルデシュナンバーの平均値は、年を追うごとに変化しているはずで、平均値はどのような変動をするのか予測できたら、それはそれで面白そうでもある。

各研究者でいえば、エルデシュナンバーは単調減少する。
逆に現状では２より小さくなることはできないし、今から１００年経過したら３より小さくするのは困難になるはずで、２００年も経たないうちに４より小さくはできないはずだろうから、下限は単調増加でもある。
この２つのバランスがどっち側に傾くのか、そのあたりが面白そうでもある。

現時点での SDPARA のコンパイル方法

温故知新、ということで現時点での Debian 上のSDPARA のコンパイル方法をまとめておく。

(1) ほとんどは Install.txt にある情報でコンパイルできる
(2) MUMPS は、4.8 だとエラーが起きてコンパイルを通せなかったので、4.10.0 に変更。使用するバージョンに合わせて mumps/Makefile の build/lib/libdmumps.a も書き換える。
(3) openmpi のファイルが変更になっているので、以下のような修正を Makefile に行う。


SCALAPACK_LIBS  = /usr/lib/libscalapack-openmpi.a /usr/lib/libblacsCinit-openmpi
.a /usr/lib/libblacs-openmpi.a /usr/lib/libblacsCinit-openmpi.a
FORTRAN_LIBS = -lgfortran -lmpif77

特に、FORTRAN_LIBS の -lmpif77 を入れないと MUMPS の一部のファイルで「関数が見つからない」というエラーが起こる。

これで一通りコンパイルも通過して、実行可能となる。

Harmony Search Algorithm

メタヒューリスティクスのひとつに Harmony Search Algorithm というものがある。

A self-adaptive global best harmony search algorithm for continuous optimization problems
http://www.sciencedirect.com/science/article/pii/S0096300310001128

音楽における即興作曲などでどのように曲が変わるか、というところからアナロジーを得て作られているアルゴリズムのようだ。
遺伝的アルゴリズムと似たような雰囲気もあるが、遺伝的アルゴリズムよりも速く計算ができる、とのこと。

整数計画問題による定式化

JIMA の Vol. 66, No.1 に載っている論文のうち、

１．サプライチェーン途絶に対する最適リスク緩和方策
２．災害救助活動のためのロジスティクス・モデルに関する研究
３．人間ドックにおける最適スケジュール作成について

の３つにおいて整数計画問題による定式化が行われていて面白い。

特に、１，２は大震災などに対してどのようにことで数理最適化が役にたつのか、という意味でも勉強になるし、３のようなことも社会に使われる最適化、という意味合いがある。

ぷよぷよと確率最適化

以前に「ぷよぷよ」が NP 完全であることが示されている。
ふと思うに、確率最適化の理論を使ってぷよぷよを解いたら、対戦相手としてはどれくらい強くなれるのであろうか？
将棋や囲碁よりも計算時間の制限がきついので、それなりに難しいかも。
むしろ車の自動運転とかの考えを使ったほうが計算時間的には有利？

非対称錐での内点法

非対称錐についての内点法についての論文が

A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
http://link.springer.com/article/10.1007%2Fs10107-014-0773-1

に出てきていることに気がついた。

ポイントとしては、

1. 主問題側だけのバリア関数を使っている
2. homogeneous な定式化を用いている
3. 計算量は通常の内点法と同じオーダーになる
4. Runge-Kutta の方法を用いて、探索方向を修正している

といったあたり。

パッと思いつく、改良できそうな方向としては、

1. DNN に特化して計算方法を改良する
2. homogeneous ではなくて、infeasible interior-point method にできるかどうか
3. 並列計算で大きな問題を解く

のあたり。

東日本大震災とオペレーションズ・リサーチ

最近の OR/MS Today にインタビュー記事が掲載されていて、東日本大震災のあとにオペレーションズ・リサーチの研究者（本人がいうには数学者）が来ていて、避難計画の策定などにも関係している、ということが分かる。

http://viewer.zmags.com/publication/e9a496eb#/e9a496eb/38

このインタビューでは、東日本大震災だけでなくエボラ出血熱との関わりも述べられている。（OR/MS Today はアメリカのINFORMSなので、エボラ出血熱についての記述のほうが記事では多い。）

オペレーションズ・リサーチを通してどのような貢献ができるのか、という点でとても参考になる。まったく同じ貢献でなくても、このような貢献をするためにはどのように自分は進むべきか、ということを考える起点にもなりそうである。また、折を見て、読み返してみようと思う。

Renegar の first-order method

Nesterov の first-order method を、Renegar が SDP 用にしたものが arXiv で読むことができる。

Efficient First-Order Methods for Linear Programming and Semidefinite Programming
James Renegar
http://arxiv.org/pdf/1409.5832v2.pdf

SDP の定式化を変形することによって、Nesterov の手法を使えるようにする、というのがミソで、この変形を行うと制約式が線形制約だけになる。（問題のむずかしさが目的関数に集約される感じか。）


なかなか面白い手法ではあるが、その一方で
Practical first order methods for large scale semidefinite programming
Stephen Tu, Jingyan Wang
http://www.cs.berkeley.edu/~stephentu/writeups/first-order-sdp.pdf
を見るとソフトウェアへの実装は難しいようである。
どのあたりに難しさがあるのか、ということを確認すると、新しい研究に結びつくかもしれない。