離散凸解析、面白い

最近の計算していた内容に離散凸解析が使えるかも、ということで、教えてもらいながら勉強してみている。
同じ凸でありながら、連続の凸関数と離散凸関数では、それなりに様子が違っていて新鮮である。

たとえば、離散凸関数は、うまく拡張すると連続凸関数にできることは知っていたが、逆に連続凸関数だからと言って定義域を整数点だけにしても離散凸関数になっているとは限らないようだ。
（もう、てっきりそうなっているものだと思っていたが。）

まずは数値計算をしてみて、今の計算したい内容に使えるかどうかを見てみて、使えそうだったら、今の計算している関数が離散凸関数ってことだと判断することにしてみている。

今日の作業内容：ワークショップ準備１ｈ＋離散凸２ｈ
明日の予測作業時間：2h

SOCP緩和とSDP緩和の間が必要そう

今日の数値実験だと、
SDP 緩和だと誤差が1%ぐらいだが、計算時間は10分。
SOCP 緩和だと誤差が4%ぐらいだが、計算時間は5秒。
となっていて、やはり SDP 緩和の誤差の小ささが際立つが、もう少し計算時間を短縮したいところ。

この間のあたりで、うまく使えそうなものがあるのかどうか、どうなのだろうか？

今日の作業内容：数値実験をこまごまと 2h
明日の予測作業時間：2h

Matlab での計算時間比較

いま、n 次元行列として A があって、V を 1 から n の添え字の部分集合としたとき、V の要素を行と列にもつ行列を A から作るには

A(V,V)

とすればよい。

ところで、この対角成分を取り出すとした時に、
v = diag(A(V,V))
とするよりも
diagA = diag(A); v = diagA(V);
とした方が圧倒的に高速である。
(このあたり、自動的に Matlab が変換してくれるかと思っていたが、どうやらそうでもないらしい）



今日の作業では、こういった高速化をいくつか入れることで、昨日1時間かかっていた部分を3秒程度まで短縮することができている。

今日の作業内容：プログラムの高速化 3h
明日の予測作業時間：2h

今日から従来モードに戻ります

今日は、数値実験のやり直しを進めておいた。
既存手法と、いま実装してみているヒューリスティクスを比較しやすいように、既存手法の結果を表としてまとめる作業を行っている。
いくつかのソースに分かれているので、複数ステップ必要となっているのが分かりにくいが、コツコツと進める感じになっている。

今日の作業内容：数値実験やり直し 2h
明日の予測作業時間：3h

樹木園計算、面白い

前から計算している樹木園計算が、なかなかに面白い状況となってきている。
どういう状況かというと、

１．既存手法を論文のアルゴリズム通りに自分で実装すると、計算が途中で破綻する。
２．しかしながら、既存手法を実装したソフトウェアがあって、それだと計算もできて、それなりの解が出る。（このソフトウェアは、ソースを公開していない。）
３．その一方で、自分で実装したものでも、データによっては計算が途中で破綻しないときもあり、その場合には既存ソフトウェアよりも３０％程度高速に似たような解が作れる。


これから推測するに、「論文には載っていないヒューリスティクスを使っている」と考えられる。

ただ、このヒューリスティクスがなんなのか不明。
不明ではあるけど、うまく実行できている。
このヒューリスティクス、他のところにも使えるのではないか、と考えると、どんなふうに行っているのか、より一層気になるところである。

なかなかに面白い。

SparsePOP を Windows でコンパイルした時のエラー回避

SparsePOP を Windows 上の Matlab でコンパイルしようとすると、エラーが出てコンパイルができないことがある。

この時には、SparsePOP にある global.h で __func__ を __FUNCTION__ に置換するとコンパイルが通るようになる。

整数制約付き線形計画問題は、線形計画問題に定式化できる

いわゆる Mixed Integer Programming Problem、より正確には整数制約付きの線形計画問題は、線形計画問題に定式化できる。
したがって、指数オーダーで増加するの計算時間と計算メモリに耐えられれば、理論上はシンプレックス法で解くことができる。

定式化するには、
(1) copositive programming により定式化する
(2) copositive programming を sum of squares により定式化する
(3) sum of squares を非常に巨大な LP により定式化する
とすればよい。