SeDuMi の eigK.m がバグってるっぽい？

ここ半年ぐらい、SeDuMi の eigK を実行しているときに良くわからないエラーで止まっていたが、どうもバグっぽい様子。

具体的には、
https://github.com/sqlp/sedumi/blob/master/eigK.m
の７７行目がバグのようで、

	74: li = 0;
	75: xi = nf;
	76: lab = zeros(N,1);
	77: li(li+1:li+nl) = x(xi+1:xi+nl);
	78: xi = xi + nl;

となっていて、74行目でスカラーと定義されている li に77行目で配列代入している。

おそらく、li(li+1:li+nl) ではなくて、lab(li+1:lib+nl) なのではないかと思っていて、自分のところではエラーが消えてなくなったけど、もう少し確認してみたほうがいいのかもしれない。

論文読み：Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

Optimization Online に載っていた以下の論文を読んでみた。

Decision Diagram Decomposition for Quadratically Constrained Binary Optimization
http://www.optimization-online.org/DB_HTML/2018/10/6837.html

扱っている問題は、目的関数が線形で、制約は2次式、あと各変数は0-1変数という問題。
これを MILP に変形して解いている。
この変形に Diagram を使って、うまいことやっている。

基本的には変数の数が増えているので、計算時間が短縮できるかどうかは入力問題しだいだけど、Diagram を使っているところが、なかなかに面白い工夫だと思う。

京都で制御と最適化のワークショップに参加してきた

京都で行われた制御と最適化のワークショップに参加してきた。

SDPについては主要な応用の一つに制御理論があるので、制御分野と数理最適化分野は比較的近い分野にあるわけだけど、一つのワークショップになっているのは、あんまりないかもしれない、と思う。

今回は制御分野の先生からの発表やコメントなどもいろいろと聞くことができて、いつもとは違う視点だったりで参考になるところが多々あった。こういう風に「近い分野だけど、いつもは一緒にやっていない」というところがワークショップを行うのは、いい刺激になるな、と思った。


あと、ワークショップが終わった後に話をしていたところで話題の一つになっていたのが「数理最適化の分野は、一般化しすぎる」ということだった。
分かりやすく錐最適化の言葉で例を作るなら「LPでできたことをSDPとか対称錐とかに一般化する」ということで、つまり「むしろ計算対象を特化することで、より効率的なアルゴリズムを作れるはずだ」ということだった。

数理最適化分野で一般化が良く行われる理由は、個人的には「どういう応用があるかわかっているから」ということだと思っている。つまり、「この問題を解くことに需要はあるのだろうか？」ということを余り真剣に考える必要がない。逆に計算対象を特化すると「この狭い範囲しか計算対象にしないアルゴリズムに、本当に需要はあるんだろうか」ということをキチンと議論しないとならない。

一般化と特化は、どちらかが正解で残りが間違い、という二者択一のものではなくて、両方とも正解であると個人的には思う。どっちに行ってもオモチロイ研究を作り出せることができる。

こういったことを考える視点をもらえた、というだけでも、今回のワークショップは行ってきてよかったなぁ、と思う。
またいつか参加してみたいものだ。

xkeymacs のＯＫボタン

Windows の標準ショートカットキーは使いにくいので（特にカーソル移動をショートカットでできないのが痛い）、xkeymacs を使っている。
ただ、xkeymacs は設定画面が昔のままなので、高い解像度だと「ＯＫ」ボタンがウィンドウからはみ出してしまい、そのままだと押せない。

いろいろと調べてみたら、なんとウィンドウの中に「ＯＫ」ボタンが残っていた。(https://www52.atwiki.jp/wbdev/pages/20.html)
この「ＯＫ」ボタンを発見した人、すごすぎる。いったい、どういう技術を使ったんだろうか、気になる。

ちなみに、「ＯＫ」ボタンを押す変わりに Enter キーを押しても設定できる。

OPTAでもらった質問を考えてみた

ずっと前に OPTA で発表させてもらったときに
「定式化としては線形の目的関数と凸２次制約を含む MI-SOCP だけど、ポートフォリオの計算のように凸２次を目的関数にして線形制約を入れる MI-QP にすれば、もっと短時間の計算でできるのでは？」
というコメントを頂いた。

せっかくいただいたコメントを無駄にするのももったいない、ということで、試行錯誤を繰り返してみること４か月。結論をまず書くと
「短時間にならない。。。」
ということだった。

MI-SOCP で解いた時も、分枝限定法の上界と下界のギャップが小さくできるまでに必要なノードの数が非常に増えてしまったが、MI-QP で行ってもノード数がやはり増えてしまった。特にギャップが2%を下回ると、そこからの改善がどうにも得られなくてノード数の増加を招いている。

今回数値計算している問題は、凸２次のところに現れる係数行列が特殊な構造を持っているので、そのあたりが解くのを難しくしているのかもしれない。
また、いろいろと試行錯誤してみることにする。

Julia は関数に入れると高速化できる

最近になってシミュレーテッド・アニーリングのプログラムを作って C と Julia で比較したところ、C は 1.2 秒ぐらいなのに Julia だと 30 秒ぐらいかかっていて、「Julia、遅いなぁ～」と思っていた。

ところが、
https://qiita.com/ceptree/items/b5cfca180e85e61c42a8
によると、「関数に入れないと Julia では速くならない」ということなので、さっそくプログラムの最初に

function test()

と入れて、最後に
end # end of test()
test()

として
@time include("test.jl")
としてみたら、ほぼ C 言語と同じ 1.2 秒台まで短くなった。

何回も繰り返して実行してみると、C言語のほうが速かったり Julia のほうが速かったり、という感じで、言語の差というよりも他プロセスの動作状況のほうが影響が大きい感じだった。

Julia 1.0 が出てた

Julia 1.0 が８月上旬にリリースされていた。
早速インストールしてみたけど、まだまだ使える状態ではないので、Julia 0.6 か 0.7 のほうが良さそう。

Major version up ということで、言語仕様が変わっていて、周りのパッケージがまだ追い付いていない状況であって、さっきやってみた感じでは CPLEX のパッケージなどは使えない。
(いままで is_linux() とかだった関数が Sys.islinux() などに変更になっていたりする。）

あと、Pkg もデフォルトでは import されていないので、
import Pkg
と明示する必要があるようだ。

他にも、いろいろとバグがあるようで、例えば、変数のスコープがおかしくなっているようで、
a = 0; for i=1:3; a += i; end
が実行できない。(0.6 では、もちろん実行できる。）

そのうちに、細かいバグが修正されていくのかもしれない。

ISMP2018の甘い思い出

ISMP2018に参加した人にとっての甘い思い出といえば、これ。

そう、ココナッツ味のお菓子。

パッケージとしてはこんな感じで、トラムＡライン沿いにあるショッピングセンターの中のスーパーで売っていた。

 お土産に買ってきたら日本でもそれなりに好評。もっと買ってきても良かった。

アインシュタインの言葉

http://www.mathcs.emory.edu/~vicki/preprint/PsdSosSurvey.pdfのファイルに引用されている言葉に

"In theory, theory and practice are the same. In practice, they are　different. - A. Einstein"

というのがあって、「数理最適化もその通りだなぁ」、と思ったりする。

良くあるのは、論文でアルゴリズムでは収束することが証明されているのに、実際にプログラムを作ってみると全然収束しないパターン。
アルゴリズムが証明されることとアルゴリズムが動作することは、結構大きな差があって、非負多項式と Sum of Squares の差なんて小さいもの、と思ったりもする。


アインシュタインの言葉の中には別の本に載っていたものを数理最適化の言葉で考えると「最適化問題は双対問題で考えたほうがいいよ」みたいなもの（実際には、相当別の言葉で書いてあるけど）があって、すごい洞察力だなぁ、と思う。

Julia で単項式列挙

多項式の単項式を列挙するのは結構面倒で手間暇がかかるけど、Julia だと

@polyvar x[1:4]
for i in multiexponents(4,3); println(prod(x.^i)); end

という感じでx_1,x_2,x_3,x_4 の３次の多項式を列挙できる。
(もちろん、Combinatorics などの Package はあらかじめインストールする必要があるけど。）

実行すると

julia> for i in multiexponents(4,3); println(prod(x.^i)); end

x1^3

x1^2x2

x1^2x3

x1^2x4

x1x2^2

x1x2x3

x1x2x4

x1x3^2

x1x3x4

x1x4^2

x2^3

x2^2x3

x2^2x4

x2x3^2

x2x3x4

x2x4^2

x3^3

x3^2x4

x3x4^2

x4^3

となる。

日本、遅れすぎなのでは？

ＮＨＫのニュースサイトに
「電気自動車や電動バイク 充電時間短縮へ“電池交換式”に注目」
https://www3.nhk.or.jp/news/html/20180730/k10011555551000.html?utm_int=news_contents_news-main_006
という記事があるが、これに出てきている Gogoro は台湾で実物を見たときに確かに良くできていると思った。
あと、街中でもそれなりに見かけたし（見分け方を教えてもらったので、簡単に Gogoro の電動バイクなのか見分けられるようになった）、Gogoro のショップの前を通るときに電池交換をしている人も多かった（電池交換自体は、コンビニでコーヒーを買うよりも短時間でできる）。

IT関係などを中心に台湾は日本よりも５年ぐらい先に行ってるのかも、と思う。
似たようなところでは、バイクシェアリングのサービスも台湾は便利になっていて、東京も台湾式を取り入れたほうがユーザーにとってはメリットがあるのでは？と思うぐらい。

国際学会で訪れたことのあるバンクーバーやボルドーと比べても、台湾のIT関係の進み具合は強い印象があって、日本も参考になるところが多いな、と個人的には思っている。

ISMP2018に参加してきた

もう３週間ぐらいたっているけど、ISMP2018に参加してきたので、その感想などを思いつくままに書いてみる。

１．初日の semi plenary は人があふれてた。

初日は一番参加者が多いということで、最初の plenary で 1000 人以上来ていたように感じたけど、semi plenary が２パラレルでも２教室で500席もない状態で、思いっきり溢れる参加者。

まぁ、local committee が人数予測を間違った、というところだと思うけど、この程度のことは参加している側からすれば大目に見るべき範囲かな、と思ったりしている。

むしろ、今回の ISMP ではどの plenary とかを聞きに行きたいかを事前にデータとして取るという試みがあったわけであって、データマイニングだったり機械学習だったり数理最適化だったりの研究者がサポートできた問題。

２．セッション内容、面白かった。

plenary とかは Math Prog に載っているので聞きに行かなくても情報は簡単に手に入るけど、小さいセッションの話はインターネットだけではたどり着けない情報や新しい論文の話もあったりするので、とても面白かった。

あと、ISMP は機械学習関係のアルゴリズムも発表されていたけど、世の中のディープラーニングとかで実用化が急速に進んでいるところを考えると、なんか時代の移り変わりというものを考えさせるような気もする。

個人的には、SDP の数値関係とかの話が面白かった。
あとは、交通関係の最適化で derivative free を使っていたのは、まったく別分野の最適化問題にも応用が利きそうなので、発想が面白かった。
いちおう、聞いてきて面白かった内容などは１５件ぐらいメモ書きにして残してある。

あと、量子情報関係の内容も増えてきて、数理最適化分野における次のブームになるのかも、と思ったりする。

３．会計

学会全体で会計が黒字だったか赤字だったのか気になったりもするけど、今回は学会の様子から、どっちだったかはだいたい検討がつく。

４．悲喜こもごも

受賞関係で人づてに色んな情報が耳に入ってきたりする。人づてなので正確かどうか分からないけど、有名な先生とかもそれなりに苦労してるんだろうなぁ、と勝手に想像したりする。

５．フランスも日本とあんまり変わらない人がいる

ISMP2018の最終日にワールドカップの試合でフランスが勝ったということで、街中にはクラクションを鳴らして走る車があったりで、こういうので騒いだりするのは日本とあんまり変わらないなぁ、と個人的に思う。

６．トラム、楽しい
５日間フリーパスでトラムに乗っていると駅名とか覚えるし、ダイヤがどう組まれているかも覚えるし、なかなかに楽しい。
そんでもって、「もう地図がなくても、だいたいの場所は行けるぞ！」ってなった頃に離れないといけないのが、なかなかに寂しい。

７．カヌレ、うまい

さすがカヌレ発祥の地。日本でもコンビニとかで買えるようになってほしい。

と、書いてみて５－７は ISMP というよりもボルドーのことだった。
そういえば、次回の ISMP は北京って案内が出ていた。

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

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

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

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

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

論文読み：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 になるのは簡単とは思えないし。

論文読み：Theoretical challenges towards cutting-plane selection

切除平面法についての理論面の情報を集めた論文が出ていた。

https://link.springer.com/content/pdf/10.1007%2Fs10107-018-1302-4.pdf

サーベイのような位置づけの論文で、どういった cut があるのか、それらがどういう性質を持っているのか、などがまとめられている。
確率論的な立場で cut の性質を証明している Theorem 1 は、こういった視点があるのか、と思ったりする。

あと、この論文の Final Remarks は秀逸。
the answers may not be unique.
の他にも含蓄の多い言葉が並んでいる。
Final Remarks 全体を引用したくなるけど、そうすると引用としては長くなりすぎるので止めておくが、CPLEX, GuRoBi などを使っている人は、一読の価値があるんじゃないかと思う。

sharelatex の synctex がズレるのを回避できる

sharelatex は便利だけど、synctex で PDF から tex に移動したときに数十行ぐらい常にズレるのが気になっていた。つまり、PDF で範囲指定をしてから、画面中央の左矢印で tex に移動すると、範囲指定していたところからは数十行ズレた位置に移動してしまう。

ずっと気になっていたのだが、今日何気に PDF をダブルクリックしてみたら、tex が該当箇所にほぼ正確に移動できることが分かった。
こんなに簡単な方法で回避できるとは思ってもみなかった。

発表した内容よりもいい定式化に気がついた

土曜日に発表したときに定式化をあげたけど、今朝の通勤時間にもっといい式変形があることに気がついた。非ゼロの数を1/3程度にできる。

で、３０分ぐらいでプログラムを作って実行してみたけど、思っていたほど効果が出ない。
計算時間だと 5 % 程度しか削減できない。
内点法の動きは、ちょっと謎だ。

まぁ、今回のはうまく行かなかったけど、first-order method に使えるかもしれないんで、もう少し考えてみることにする。

研究集会で発表してきた

土曜日にあった研究集会で発表をさせてもらった。
今回の発表では、ここまでの研究内容の棚卸もいろいろとできたし、もらったコメントも勉強になるコメントが多く、とてもいい機会になった。

今回の内容については、似たような構造の数理最適化問題がたくさんあるので、まだまだ何本も論文にできるような内容を含んでいるかと思うし、もっと時間を使ってやっていけたら、とも思う。今回の発表でもらったコメントなどで「Todoリスト」も強化できたし。

また、数理最適化があまり使われてこなかった分野の話でもあるけど、数理最適化手法が強い効果を発揮したりもするので、数理最適化手法を作れる人には面白いかな、と思ったりもする。個人的には、離散最適化の人が入ってきたりしたらアルゴリズムを作るという意味では無敵なんだろうな、と予想していたりもするけど、その一方で参入障壁も大きいかもしれない。

あと、違った分野の人とやり取りをしていると、「数理最適化だけだと井の蛙かも？」ということに気づいたりする。専門用語の違いから話が全く通じなかったりすることもあったりするけど（自分の英語力のなさも見落とせない要素だけど）、分野の違いを超えて研究をするのにどういったことが大事なのか、ということを教わったりもする。こういった経験は、別に進めている放射線治療に関する最適化などの勉強にも役立っている。


あと、今回の発表で細かいところでは、最後の質問が終わったところでピッタリ予定の時間になったのが、「あぁ、こういう偶然ってあるもんなんだなぁ」と思ったりもした。発表スピードは自分でコントロールできるにしても、質問の数とかは自分ではコントロールできるものではないし。

そんな色々があるにしても、もうちょっと研究を頑張って、いろんなところに役立てられるようになれれば、と思う今日この頃。

sharelatex の日本語入力がうまくいかない

ローカルなところにインストールした sharelatex だが、今までほとんど英語しか入力してなかったので気にならなかったが、日本語を入力しようとすると変な四角が出てきて、これがどうしたものか、というところ。

具体的には、
https://qiita.com/RAWSEQ/items/7f9fc0fd4b3d572856ed
にあるような Ace エディタで日本語入力するときのトラブルと同じ症状なのだけど、これを sharelatex で回避するにはどうしたらいいかが今一つよくわからない。

うーん、ローカルで CSS 制御すれば回避できそうだけど、それを調べるのも今のところは面倒だし、どうしたものか。

まぁ、その点を除けば sharelatex はとても良くできていて、やっぱり便利。

CPLEX の前処理をパズル感覚で楽しむ

最近、CPLEX で LP を解いているが、CPLEX の前処理が思っていた以上に優秀である。
例えば、A*x = b という等式制約を A*x <= b と (-A)*x <= (-b) と２つの不等式制約に分解すると一般的には内点がなくなるので、内点法では解きにくいはずである。しかも、A と (-A) が両方入ると行の線形独立も失われれる。
単純に内点法を組むとうまく行かない、という典型例なのだが、CPLEX だと前処理がきちんと働いて、それなりに数値的に安定して解ける。

ということで、CPLEX の前処理ではうまく処理できないような LP の例を簡単に作れないだろうか？ということを試してみているのだが、これがパズル感覚でなかなかに面白い。
単純に A と (-A) を入れるだけでなくて、もう少し細工をしたりすると CPLEX が CPX_STAT_NUM_BEST を返すようになる。

もっと単純な例で CPX_STAT_NUM_BEST を出せないだろうか？と、ついついいじり倒してしまう。

ただ、「こういう例で CPX_STAT_NUM_BESTを出せるよ」という例題をインターネットに公開してしまうと、CPLEX の開発者がうっかり見つけてしまって、それを回避してしまう前処理を入れてしまうかもしれないから、イタチごっごかもしれないけど。

台湾、進んでるなぁ

INFORMS の雑誌に台湾の AI とかブロックチェーンとかの話が載っていたのでパラパラと読んでみたけど、第一印象としては「台湾、進んでるなぁ」ということだった。

結構実用化に近いことをやってたりもしているようなので、重要な特許とかは先に抑えたりとかもしているかもしれない。（ブロックチェーンについては、特許を押さえるようにしている企業が日本の中にもある、というのを読んだ記憶がある。）
そうなると、こういった分野で基礎研究の論文とか書くにしても、特許と重なってないか、とかを慎重に調べる必要があるんだろうなぁ、と思ったりする。論文のデータベースで検索とかする時に特許の情報が一緒に掲載されたりということは見たことがないから、両方調べたりするのは大変そう。

AIとかブロックチェーンとかだと、台湾はこれから大きく発展していくのかもしれない、と思うような話だった。

Linux の screen が勝手に終了してしまうのを回避する

いつのころからか、Linux の screen コマンドや nohup コマンドがログアウトと同時に勝手に終了（あるいは切断）してしまっていて、困っていたのだが、今日になって調べてみたら systemd の変更に由来していることが分かった。

基本的な原因は
http://gihyo.jp/admin/clip/01/linux_dt/201605/30
にあるけれど、解決策としては、
http://blog.daionet.gr.jp/gami/server/systemd%E3%81%A8gnu-screen.html
にあるように
/etc/systemd/logind.conf 
に KillUserProcesses=No を書いて再起動すると screen や nohup が使えるようになる。

上記２つめの URL の記事だと No を書いただけだと反映されない、と書いてあったが、自分のところの設定では再起動してみたら反映されていた。この記事が書かれた後に、また設定の仕方に変更があったのかもしれない。

研究集会に参加してきた

今日は政策研究大学院大学での研究集会に参加してみて、あまり長い時間はいられなかったけど、どれも面白い話だった。

まずは、ＳＤＰで主問題と双対問題の両方に内点がないような問題で、その場合には「ほぼ確実に」双対ギャップがある、という話だった。
面白いのは、元の主問題を摂動した SDP の目的関数値は双対問題の値に近くなる、ということだと思う。つまり、摂動SDPの最適値と双対問題の間にあるギャップが分かれば、双対問題の値を求められるわけで、内点法では解けないような問題が解けるようになるかもしれない。

あと、クラスタリングの方法は、ある基準を満たせば凸計画問題で最適なクラスタリングができる、という理論的側面の話があった。
この基準について、どれくらいタイトなのか、というところが分かると、さらに面白いなぁ、と思う。つまり、その基準に使っている値よりも少しでも大きいと最適でないクラスタリングが作れるかどうか、ということ。

もう一つは機械学習系の DC アルゴリズムの話で、こちらの数値実験は精度が 10^{-5} ぐらいの緩いところでは matlab の fmincon よりも速い、という話だった。ただ、matlab の fmincon は汎用ソルバーなので、Lipshitz 条件を満たさない関数でも扱えるはずだから、fmincon よりも速い、というのは妥当なところかと思う。
個人的には、||x||_0 <= k の制約を ||x||_0 = k にも置き換えられたら、もっといろんな問題も解けるなぁ、と思ったり、あとは停留点だけでなくて Robinson 条件とかも満たしているかどうか調べると面白そう、と思ったりした。


やっぱり、たまに他のところで話を聞いてくると、いろいろと思いついたりでいいなぁ。

「最適解に収束しない最適化アルゴリズム」ってないだろうか。。。

いまひとつ矛盾しているように思えるかもしれないけど
「最適解に収束しない最適化アルゴリズム」
がどこかにあったりしないか、探してみて早１か月。
これが当然のことながら見つからない。

内点法にしても first-order method にしても、「最適解に収束します」っていう証明はありふれているけど、「最適解の近くにたどり着けます」っていう証明はあんまりなかったりする。要するに、最適解の１０％ぐらいのところまでたどり着けば十分なことは実際には多いけど、そういった実用と数学的な証明は噛み合ってなくて、そのギャップをなんとか埋められないかな、と思ったりもしているところ。

三菱総研の不思議

この前に三菱総研の常務理事の講演会があって、これを聞いてきたけど、三菱総研でどういったことに注力しているか、など聞くことができてとても面白かった。時間は９０分しかなかったけど、連続講演で細かいところも聞いてみたいところだった。
普段、論文を書いたりしていると、あまり経営などの視点を持っていないけど、こういう話を聞くと大局的なところも分かっていいかと思った。例えば、論文を推敲しているときも「この単語をこっちの単語に入れ替えたほうがいいだろうか？」など考えているときに、大局的なところがあると判断基準になったりするかと思う。

あと、もうひとつ面白いと思ったのは、「次のイノベーションはどこの分野に起こりそうか」ということを、ある程度はロジカルに見出すことができるということだった。その根拠も確かに聞いてみるとその通りで、目から鱗な感じだった。

それで何晩か考えてみて不思議なのは、「次のイノベーションがどこにあるかわかるのに、三菱総研にイノベーションのイメージがついてこないのはなぜ？」というあたり。ベンチャーと連携したり、とかやっているという話もあったけど、社外と連携するよりも社内でやったりする方が小回りとかも利くようなするのに、そういうわけでもない。
こういうときに「何が足りてないんだろうか？」とか考えるのも勉強の一つになりそうだ。

sharelatex は日本語変換もリアルタイムで同期しているのか～

最近試している sharelatex だけど、非常に面白いことに日本語変換もリアルタイムで同期されている。

たとえば、２台のPCでとなりあってやっているときに、片方のPCで「日本語変換」も「日本語へんか」とか途中まで入力すると、それがもう片方の PC に表示される。カーソルの位置がどこにあるかもわかるので、「他の人がこのあたりを編集しているから、自分は別のところを編集していよう」とかが簡単にできるようになっている。

TeXstudio とか TeXshop とかには、もう戻れないかも。

TeX の \c, \l をどうにかする

TeX には \c, \l など一文字からなるコマンドがあって、非常に迷惑だったのだが、これを回避できる方法があることが分かった。

そもそものところからいうと、\a, \b, \c などを a, b, c などのベクトル表記だったりに充てようとすると \c や \l の内容を上書きする必要があって、この場合にヨーロッパのアクセントに使うべき \c, \l を回避できずに参考文献などで困ってしまう。

こういった場合は
\let\strokel\l
として \strokel にオリジナルの \l を控えさせておいて、それから\rewcommand で \l を再定義すれば回避できる。

今回の内容では
https://tex.stackexchange.com/questions/154067/new-command-and-l-with-stroke
が参考になった。


ただ、参考文献の著者名とかにウムラウトとか必要か？と言われると、そもそも論としては疑問も残るもの。もちろん、著者名を正確に表現できた方がいいのは当然にしても、それだったら漢字やハングルの著者名だって、そのまま表現できるべきであるわけで、まぁ、そのあたりは学術雑誌もちゃんとグローバル化されているわけじゃないんだよね、ってことなのかもしれない。

sharelatex がすごい便利

最近、sharelatex をローカル環境にインストールして使い始めてみている。
（オンライン版もあるので、そっちのほうが簡単だとは思うのだけど、そっちは使わずにローカルにインストールしている。）

ローカルの環境で TeXLive をフルに入れると docker のイメージファイルが 8GB くらいになったりもするし、docker をどうやって使ったらいいか勉強するのが手間ではあったけど、TeX のソースファイルを書く上では、TeXWorks, TeXstudio, Emacs, Atom とかよりも軽快で便利。

特に便利なのは、TeX の構文チェックをリアルタイムで行ってくれるところ。
TeX だと \begin で始まったのが \end で終わってないとコンパイルエラーになるけど、どこでエラーになるのかログを見ただけだといまいちわからなくて、このエラーが結構大変。
でも、sharelatex だと \begin を入れると \end が入っていない場合に赤くなるので、簡単に異常な状態が分かる。ついでに $$ も同様に分かりやすい。
これのおかげでコンパイル回数もだいぶ削減できて、SDD に優しい環境のような気がする（最初に 8GB も使ってるけど）。

Knuth 以上の天才なんじゃないだろうか

Knuth といえばアルゴリズムを勉強したことがあるような人なら誰でも知っている超有名研究者なわけだけど、TeX の基礎を創った開発者としても超有名。

その Knuth を超えるんじゃないか、と個人的に思うのが
http://www.kabipan.com/densan/article.html
の内容。
簡単にいうと、TeX の主要な機能である自動番号付けと相互参照を Java Script で作ってしまう、というもの。
しかも、世の中には Mathjax もあるし、Java Script で bibtex も処理できてしまうようだし、TeX で作られている論文の９割以上は TeX をインストールしなくても HTML + Mathjax + Java Script で、論文としての読むに堪えるものは再現できるのではないかと思ってしまう。（というか、オンラインで論文を読んでいるときには、最近ではほとんどの機能がそうやって再現されているみたいだし。）


まぁ、こういうのが気になっているのも、そもそも TeX が衰退してきているなぁ、と感じるところにある。
https://www.slideshare.net/iesli/20141108-senooken-tex
によると TeX, LaTeX などの検索回数は 1/3 程度に減ってきているようで、世界の研究者の数が1/3に減ったりしてはいないだろうから、TeX は新しい研究者には支持されていない、ということを示唆しているのではないかと思ったりする。

TeXLive はインストールすると 2.5 GB 以上の容量があるし、Android などのタブレットやスマホへの移植も進んでいない。
PC でのコンパイルも、PCそのものの性能は向上しているけど、TeX 処理系が遅くなっていて、10年前のほうが高速にコンパイルできたんじゃないか？って思ったりするほど。

それだったら、いっそのこと、HTML + Mathjax + Java Scriptで作ってしまった方がいいのではないかと思う。
これならブラウザが動いていれば CJK の問題もブラウザが吸収してくれるし、開発する部分は100MBもないだろうから（1MB でも主要な機能の９割はいけるのでは？）、少ない人数でも十分に開発できるかもしれない。
エディタとブラウザがあればいいから、Android や Chromebook などでも十分に論文を書けると思う。TeX の挫折理由の一つであるインストールも簡単になるだろうから、挫折する人は減るだろうし。

論文読み：An improved version of Chubanov’s method for solving a homogeneous feasibility problem

An improved version of Chubanov’s method for solving a homogeneous feasibility problem
http://www.tandfonline.com/doi/full/10.1080/10556788.2017.1368509

をざっと読んでみた。Chubanov の方法を改良して性能を上げるっていうものだった。

この論文を読んでいて気が付いたけど、Chubanov の方法は norm の取り方が結構重要なので、双対 norm を入れると dual の方法が作れるのかー。
数値結果については Gurobi よりも良いということになっているけど、問題が小さいので何とも言い難いところかと。数値実験はオマケのような立ち位置なのかもしれない。

３次元以上のSDP の錐は、SOCP では表現できない

２次元の半正定値行列の成す錐が SOCP で書けることは良く知られている事実だけど、３次元以上の場合に SOCP では書けない、ということが証明されていた。
詳しくは、
On representing the positive semidefinite cone using the second-order cone
https://link.springer.com/article/10.1007%2Fs10107-018-1233-0
に載っていた。

そういえば、SOCP を LP で任意精度で近似するのは LPP を使えばできるけど、SDP を SOCPで任意精度で近似するっていうのは出来るんだろうか？
それが今後の展開なんだろうか？

論文読み：A Network Flow Model for Irrigation Water Management

灌漑施設についてネットワーク最適化問題として定式化して解く、という論文があったので目を通してみた。

A Network Flow Model for Irrigation Water Management
https://journals.lib.unb.ca/index.php/AOR/article/view/20397

解く手法は、min cost flow を使っている。
論文のモデルは結構面白いかと思うが、この論文をベースに何かするとしたらベンチマーク問題のようなものがないとちょっと難しいかと思う。
やはり、データが整理されている、というのは重要な点なのかもしれない。

論文読み：Augmented Lagrangian functions for cone constrained optimization: the existence of global saddle points and exact penalty property

今回は、Journal of Global Optimization に掲載されていた
Augmented Lagrangian functions for cone constrained optimization: the existence of global saddle points and exact penalty property
をチェックしてみた。

基本的には、タイトルが示す通り、錐最適化問題についての augmented Lagrangian についての理論的性質を調べている、というものだった。
数値解法については特に触れてなくて、解の性質などを中心に解析している感じだった。


この論文とはちょっと離れるが、最近はinexact な Newton 法、内点法、augmented Lagrangian については調べるようにしていて、こういったものを使うと SDP に対する内点法を今までよりも高速に計算できるアルゴリズムを作れるかも、と思ったりしている。
（どうやってアルゴリズムを作ればいいか、という全体の枠組みは分かりつつあるので、それぞれのステップをきちんと作る方法を調べている、というところ。）