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
を見るとソフトウェアへの実装は難しいようである。
どのあたりに難しさがあるのか、ということを確認すると、新しい研究に結びつくかもしれない。

Julia で sparse Cholesky 分解

Julia の場合、以下のような感じで sparse Cholesky factorization ができる。

julia> A = sprand(100,100,0.1);
julia> B = A*A' + 100*speye(100);
# ここまでで B に sparse で positive definite な行列を生成

julia> C = cholfact(B);
# これで CHOLMOD.Factor が生成される

julia> L = sparse(C);
# これで普通の sparse 行列として L を取り出せる。
# ただし、AMD による行と列の順番変更がある。
# この情報は C.Perm に入っているが、CHOLMOD の情報のままのためインデックスが 0 スタートであり、Julia の１スタートのために C.Perm + 1 など１を足す必要あり。

julia> vecnorm(L*L' - B[C.Perm+1, C.Perm+1])
1.428931331049563e-13

# これで数値誤差が評価できて、数値誤差を除けば正しく計算できていることが分かる。