2020年11月26日木曜日

TeXLive の10%しか使ってない

TeXLive を 2020 に上手く更新できなかったので再インストールすることした。

scheme を full にして完全インストールすると5GB以上のディスクを消費するが、試しに scheme を basic にしてインストールしてみた。

もちろん、いろいろと足りないパッケージがあって、例えば algorithm.sty が入ってなかったので、

$ tlmgr search --global --file algorithm.sty

として algorithms パッケージを特定して、これをインストールしてみた。

$ tlmgr install algorithms

他にも足りないものがあれば逐次インストールして、あと platex も入ってなかったのでplatexもインストールしてみた。

結果的には500MBぐらいの容量だけで自分が使っているTeXソースをコンパイルできた。

どうやら、自分のところではTeXLiveの機能の10%だけで十分なようだ。

 


2020年11月18日水曜日

ssha (sshでなくて)

Termuxを使っているときに気がついたけど、ssh だけでなく ssha  というコマンドもあり、これが結構便利。

ssha  の場合は、https://wiki.termux.com/wiki/Remote_Accessにも 書かれている通り、

ssh-agent を自動的に処理してくれることになっており、例えば

 $ ssha server01

としてsshのパスフレーズを入力してserver01 にログインした後に、もう一度 Termux の別のセッションから

 $ ssha  server01

とすると、今度はパスフレーズの入力を省略してログインできる。


片方のセッションでエディタを使っていて、もう片方でコマンドラインで実行する、と言ったときに便利。(似たようなことは screen コマンドで複数のウィンドウを使ってもできるけど。)

 


2020年9月25日金曜日

Matlab の mex のための gcc 6.3.0 のコンパイル方法

 Matlab R2020a のmexでコンパイルするには、gcc のバージョンが6.3.0とかなり古いものが必要となるが、gcc 6.3.0 はそのままではgcc 10.1.0 ではコンパイルできなかったので(途中でエラーが出る)、コンパイル方法をメモしておく。

$ wget http://ftp.mirrorservice.org/sites/sourceware.org/pub/gcc/releases/gcc-6.3.0/gcc-6.3.0.tar.gz

$ tar xzf gcc-6.3.0.tar.gz

$ mv gcc-6.3.0 gcc-6.3.0-source

$ cd gcc-6.3.0-source

$ ./contrib/download_prerequisites

$ cd ..

$ mkdir -p build

$ cd build

$ ../gcc-6.3.0-source/configure --prefix=[インストールパス]/gcc-6.3.0 --disable-multilib --disable-libsanitizer

$ make


make が途中で止まったら、

emacs +61 x86_64-pc-linux-gnu/libgcc/md-unwind-support.hn

struct ucontext *uc_ = context->cfa;

ucontext_t *uc_ = context->cfa;

とする。


これで再度 make をする。

$ make

また停止したら、 `find . | grep java-signal.h`

./include/java-signal.h:31:10: note: forward declaration of ‘struct _Jv_catch_fpe(int, siginfo_t*, void*)::ucontext’

   struct ucontext *_uc = (struct ucontext *)_p;    \

の部分を

   ucontext_t *_uc = (ucontext_t *)_p;    \

にする。   


これで再度 make をする。

$ make

あとは make install する

$ make install 


インストールした後の環境変数の設定方法としては、

export PATH=[インストールパス]/gcc-6.3.0/bin:$PATH

export LD_LIBRARY_PATH=[インストールパス]/gcc-6.3.0/lib64/:$LD_LIBRARY_PATH

とする。

2020年3月11日水曜日

Dropbox paperのダークモード

Dropbox paper が LaTeX 表記を使えるので、他の人に送りたい簡単なメモなどにつかっったりしている。
いつごろかダークモードにできるようになって、自分のPCではダークモードになっているのだが、困ったことに切り替えボタンが見つからない。。。
ダークモードと普通のモードの切り替えができずにどうしたものか。。。

2020年2月19日水曜日

Julia の using にかかる時間を先に precompile する

Julia でプログラムを実行していると、using のときに precompile が行われるのだけど、これが結構な頻度であって、しかも時間がかかる。しかも、「ちょうど計算を始めたタイミング」で起きるので、あんまり感じが良くない。

こういったのは、パッケージモードに入って precompile しておけばよいようだ。

julia > ]
(v1.3) pkg > precompile

これでインストールされているパッケージがすべてprecompileされた状態になる。



2020年2月3日月曜日

論文読み:Centering ADMM for the Semidefinite Relaxation of the QAP

今回チェックした論文は
Centering ADMM for the Semidefinite Relaxation of the QAP
http://www.optimization-online.org/DB_FILE/2020/01/7569.pdf
というもの。

タイトルにある通り、ADMMでQAPに対するSDP緩和を解くという話だけど、
単純なADMMではなく、内点法のバリア関数のように log det を導入して、
中心パスの近くに寄せようというもの。

アルゴリズムのアイデアについては面白いなぁ、と思う。
first-order method と second-order method の両方の性質を兼ね備えていると面白い。

数値実験については、計算時間が掲載されていないので、パフォーマンスは良く分からない。
あと、最後の Table 3 は、 mu < 1.0e-3 という比較的緩めの停止条件なので、
Centering LB と Standard LB の差はそれほど大きくない(有効桁数よりも小さいところ)。

個人的には、SDPに対して ADMM を使うのは、やはり固有値分解のボトルネックが気になるところ。
内点法だとCholesky分解で計算できるので入力行列の疎性をそのまま変数行列に引き継げるので、
そのあたりで工夫の面白さもあるけど、固有値分解を入れてしまうと、この疎性が壊れてしまうことが多い。

A fixed-point method for approximate projection onto the positive semidefinite cone
https://www.sciencedirect.com/science/article/pii/S0024379517300903
とかにあるような手法で近似計算したほうが良いのだろうか?

2020年1月18日土曜日

論文読み:An inexact first-order method for constrained nonlinear optimization

今回チェックした論文は、
An inexact first-order method for constrained nonlinear optimization
https://www.tandfonline.com/doi/abs/10.1080/10556788.2020.1712601?journalCode=goms20

一般(非凸も含むけど関数は連続微分可能)の制約付き最適化問題について、first-order method で解く、というもの。
アルゴリズムの特徴としては、
1. 制約はペナルティ項として目的関数に組み込んで、それを最小化する。等式制約c(x)=0については絶対値 |c(x)| を用いて、不等式制約 c(x) <= 0 については max{c(x), 0} を用いる。
2. ペナルティ項付き目的関数を1次までのTaylor展開をして(つまり線形近似をして)、それを最小化することで探索方向を決める。さらに探索方向に沿って Armijo のルールを適用してステップ長を決める。
3. ペナルティのウェイトは、双対問題の情報を使って更新する。
4. 子問題を解いたりするときには信頼領域法も併用する。

計算量については、得たい精度が epsilon の場合には O(1/(epsilon^2)) ということで、first-order method ではよく見かえる計算量なわけだけど、面白いと思うのは非線形の制約がついても計算量としては決して悪くない、ということ。
つまり、epsilon だけで計算量を評価する場合には、制約なし最適化問題と制約あり最適化問題は計算量が同じになるということである。


個人的には、今回の論文のアルゴリズムは複雑すぎる印象がある。例えば、Armijo のルールと信頼領域法を併用しているのは、どちらか一方でいいようにも感じる。
その一方で、一般の制約付き最適化問題への first-order method の適用はあまり多くないので、こういったところから他の手法を組み合わせていろいろと発展させられるかもしれない。

2020年1月12日日曜日

論文読み:On the Complexity of an Inexact Restoration Method for Constrained Optimization

今回チェックした論文は、
On the Complexity of an Inexact Restoration Method for Constrained Optimization
https://epubs.siam.org/doi/abs/10.1137/18M1216146?mobileUi=0
というもの。

非線形の制約付き最適化問題
min : f(x) s.t. h(x) = 0, x \in Omega
に対する IR (Inexact Restoration) が O(epsilon_{feasible}^{-1} + epsilon_{optimality}^{-2}) の反復回数で収束する、というもの。
ここで、epsilon_{feasible} は h(x) = 0 に対する許容残差で、epsilon_{optimality}は最適値に関する許容ギャップというところ。
あと、Omega は compact である、という仮定を満たせば理論的には良くて、実用上は l<=x <= u のような上下限制約などがおもなたいしょうになるとのこと。

アルゴリズムは、||h(x)||^2 を減らす Restoration Phase と f(x) を減らす Phase があって、それぞれの Phase では、BFGS、あるいは SQP に近いような近似によって計算が行われている。ただ、2次微分は使っていないので、基本的には first-order method の範囲であり、そう考えると、上の計算量のオーダーも納得というところ。

この論文ではアルゴリズムの数値実験は行っていないのでどれくらいの速度で実際に計算できるかどうか分からないが、アルゴリズムの構成からすると最適解近くでの収束速度が良くなさそうにも思う。(もともと SIAM Journal on Optimization という雑誌に載っている結果は理論面がメインなので、実際の計算速度という意味では他の雑誌に載っているアルゴリズムの方が良いことが多いように個人的には思っている。)

この論文の拡張としては、シンプルなものとしては、制約に半正定値制約を入れて SDP も扱えるようにする、とかがあるかと思う。


2020年1月8日水曜日

Termux の Emacs の起動を速くする

Termux での Emacs を起動すると 7 秒程度かかるので、これを少しだけ速くする。

基本的には言語のロードを外す。
具体的には
cd /data/data/com.termux/files/usr/share/emacs/26.3/lisp
cp loadup.el loadup.el.original
として、
emacs loadup.el


(load "language/chinese")
(load "language/cyrillic")
...

などとなっている各言語で自分が使わないところは行頭にセミコロンをつけてコメントアウトする。
これによって、だいたい5秒ぐらいまで短縮された。


本当は他のパッケージも外したいところだが、なぜか上手くいかず、変なメッセージが出て Emacs がクラッシュしてしまう。

2020年1月1日水曜日

論文読み:A Limiting Analysis on Regularization of Singular SDP and its Implication to Infeasible Interior-point Algorithms

A Limiting Analysis on Regularization of Singular SDP and its Implication to Infeasible Interior-point Algorithms

http://www.optimization-online.org/DB_HTML/2019/12/7528.html

SDPの場合には、主問題と双対問題の両方に内点実行可能解があれば(つまり、Slater の条件が満たされれば)、主問題と双対問題の最適値が一致する、という双対理論は良く知られている。

この論文で扱っているのは、内点実行可能解がない場合(weakly infeasible とかなっている場合)にどうするか、という話で、結論を先に書くと「主問題と双対問題の最適値の間が得られる」ということだった。

個人的に今後の展開として面白そうかな、と考えられるのは、以下の2点といったところ。
1.homogenous self-dual の定式化を行ったときに、「主問題と双対問題の最適値の間のどこにくるか」を、より正確に扱うことが出来るかどうか。(例えば kappa と theta のあたりを解析すると面白いかもしれない。)
2.SDP緩和をすると目的関数値が -\inftyになってしまうような問題(SDP緩和が非常に弱い例)にどういう値が得られるか(元問題との差がどれくらいになるか)。