2018年7月4日水曜日

エルデシュ数の最小化はどうすればできるのか?

あんまり意味のある話題ではないけど、「エルデシュ数のような数を最小化するには、どのように共著者を増やしていくべきか?」というのが頭の中に浮かんで、なんだかよくわからない状態になっている。

「どういう論文を書くべきか?」という話なのではなくて、「グラフ最適化問題として定式化したときにどうすると最適解が得られるとかあるんだろうか?」という話。より正確には、共著者を n 人までとしたときに、エルデシュ数の最大値 k を最小化するにはどうすればいいのか?という話。

単純に考えると「その時点でエルデシュ数が最大の人と共著すればよい」というような greedy なアルゴリズムがパッと浮かぶけど、果たしてそれで最適な解が得られるのか?のか、それとも、ちゃんと反例が浮かぶのかどうか、も気になる。
また別に単純に考えても、NP-hard な気がする。

例えば、ビジネスの世界だと人と人をつなげる人というのは重要だろうから、こういう計算ができるのは、それなりに意味があるようにも思う。
たぶん、「●●問題」とか名前のついている最適化問題に定式化できるんだろうなぁ、と推測はしている。


2018年6月28日木曜日

論文読み:A semidefinite programming method for integer convex quadratic minimization

今回読んだのは、
A semidefinite programming method for integer convex quadratic minimization
https://link.springer.com/article/10.1007/s11590-017-1132-y

「整数点上で2次関数を最小にする」という問題を扱っていて、名前の通り SDP 緩和を使っている。
線形制約などの他の制約が入っていないのが特徴で、この場合には連続緩和とLagrangian Dual でどれだけ目的関数値に違いが出るか、という評価式を与えている。(ただし、両方とも元問題の下界を与えるので、元問題の最適値がどこか、ということは分からない。)
あとは、乱択アルゴリズムを数値実験で評価している。


2018年6月22日金曜日

Ipopt を Linux 上の Matlab で使えるようにコンパイルする

Matlab 用の Ipopt の Linux でのインストール方法をまとめておいたら、どこかで役に立つかもしれないので書いておくことにする。

ただ、前回も書いたように Ipopt を使うときには、SeDuMi とか fmincon は使えないので、普段は Ipopt を使わないようにしておいて、必要な時だけ Matlab を起動したら Ipopt に関する部分だけを実行するようにしたほうがよい。

まずは、コンパイル。ホームの下に展開したものとして書いておく。 Matlab のバージョンは適宜修正のこと
tar xzf Ipopt-3.12.10.tgz
cd ~/Ipopt-3.12.10/ThirdParty/Mumps
./get.Mumps
mkdir ~/Ipopt-3.12.10/share
cp ~/Ipopt-3.12.10/Ipopt/contrib/MatlabInterface/MatlabInterface.site ~/Ipopt-3.12.10/share/
cd ~/Ipopt-3.12.10/share/
mv MatlabInterface.site config.site
~/Ipopt-3.12.10/configure --prefix=~/Ipopt-3.12.10/install --with-matlab-home=/usr/local/MATLAB/R2015a
make && make install
cd ~/Ipopt-3.12.10/share/Ipopt/contrib/MatlabInterface/src
make
cp .libs/*.o .
make

ここでは、下から2個目の make は失敗で終わるので、cp .libs/*.o . をしてから、再度 make を実行している。

このあと、Matlab の実行時に
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libstdc++.so.6:/usr/lib/x86_64-linux-gnu/li
bgfortran.so.3:/lib/x86_64-linux-gnu/libgcc_s.so.1:/usr/lib/x86_64-linux-gnu/lib
quadmath.so.0.0.0:~/Ipopt-3.12.10/install/lib/libipopt.so.1  /usr/local/MATLAB/R2015a/bin/matlab -nodisplay
のように ~/Ipopt-3.12.10/install/lib/libipopt.so.1 をロードする。
(この libipopt.so.1 が SeDuMi や fmincon と相性が悪い様子。)
ちなみに、libstdc++, libgfortran, libgcc_s, libquadmath もロードしているが、このあたりはそれぞれのコンピュータごとにパスが変わっているかもしれない。

あとは、Matlab の中でパスを設定する。
addpath(strcat(getenv('HOME'),'Ipopt-3.12.10/share/Ipopt/contrib/MatlabInterface/src'));

これで Ipopt を Matlab から実行できるはず。


2018年6月12日火曜日

IPOPT の Matlab は SeDuMi と一緒にできない

IPOPT の Matlab 版を Linux にインストールして試しているが、どうやら IPOPT の so ファイルと SeDuMi との相性が良くないようで、SeDuMi の実行が変な結果になる。例えば、K.s が整数でなくなったりする。

で、どうするか、というと、IPOPT の引数にいれるものを一通り save でファイルに保存しておいて、Matlab からもう一つMatlabを呼び出して、その中で load と IPOPT の実行をする、という具合にするとうまく行く。

Matlab は mex -setup も実用上できなくなっているし、SeDuMi も SeDuMi でコンパイルを通らないし、やっぱりメンテナンスというのは本当に大変なんだなぁ、と思ったりする。

2018年6月6日水曜日

Matlab で関数ハンドラの微分

Matlab では、関数ハンドラそのものは diff で微分できないけど、シンボリック演算を挟むと微分できる。

具体的には、
https://jp.mathworks.com/matlabcentral/answers/356136-derivative-in-function-handle
にあるように以下のように微分を行う。

syms x
f = @(x) x + log(x)
f1 = matlabFunction(diff(f(x)));
f2 = matlabFunction(diff(f1(x)));

関数ハンドラも微分できるというのは、思っていた以上に便利。

2018年6月5日火曜日

CPLEX と MATLAB で crash する

Matlab から CPLEX を呼び出すとクラッシュすることが多い。
どうやら CPLEX は少しのバージョンの Matlab でしか動作確認してないことが原因らしい。

CPLEX も Matlab も一度実行できる環境ができたら、ハードウェアが壊れるまで保存しておいた方がいいのかな、とも思ったりする。
というか、CPLEX 側で「この Matlab は動作対象外ですよ」とかバージョンチェックしてくれたら、もっと簡単にわかるわけだけど、CPLEX の Matlab ライブラリは Matlab のバージョンチェックをする機能がないのかもしれない。

2018年6月4日月曜日

論文読み:A data-independent distance to infeasibility for linear conic systems

今回は、
http://www.optimization-online.org/DB_FILE/2018/05/6632.pdf
をチェックしてみた。
簡単にいうと、実行不可能なSDPが与えられているときに、実行不可能であるということをどうやって数値化するか、ということだった。

この数値化については、いろいろと既存研究もあって、何種類かの数値化方法がまとめられていて、それらの類似点や比較なども載っていて、そのあたりが勉強になる。

そういえば、こういうのを数値計算でやろうとすると、どうしても machine epsilon の壁が厚く立ちはだかるけど、数値化の種類によっては数値誤差の影響をあまり受けずに計算出来たりもするんだろうか?