論文読み：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

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

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

ここでは、下から２個目の 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 から実行できるはず。

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

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

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

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

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)));

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

CPLEX と MATLAB で crash する

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

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

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

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

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

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

論文読み：An ADMM-Based Interior-Point Method for Large-Scale Linear Programming

今回は、
http://www.optimization-online.org/DB_HTML/2018/05/6643.html
にあった論文を読んでみた。

結論：ADMM を使うと、粗い精度の計算においても内点法は遅くなる。

個人的には粗い精度でしかもSparse Inverse Covariance Estimationのようなタイプなら通常の内点法よりも速くなるのでは？と思っていたが、予想以上に遅かった。

たしかに他の問題でも錐最適化に ADMM を使うと内点法よりも遅かった。
やはり錐最適化問題の場合、homogeneous の性質が非常に強力なので、これを使えない ADMM は分が悪いのかもしれない。

あるいは、SDPT-3 や Mosek など、高速化されたソフトウェアと比較しているのが良くないのかもしれない。それらと比較できるほどに mature になるのは簡単とは思えないし。