Luenberger & Ye の本の第４版

Luenberger & Ye の Linear and Nonlinear Programming の最新版である第４版には ADMM の Section が追加されていた。

具体的には、14.7 節にあり、２つのブロックのときには収束すること、および３つのブロックのときには必ずしも収束しないこと等がまとめられている。

少し参考にしてみようと思う。

論文レフリーをやってみて思うこと

いくつかの論文をレフリーして思うのは、何回かの改訂を経て、最終的に

「この論文、ついに accept できるなぁ」

というタイミングがあって、なんかちょっとホッコリとした気分になったりもする。

もちろん、それまでに「証明のここが間違っている」とか厳しいことも書かないといけない場面もあったりして、「これがうまく行けばいいのに」と凹んだりもするわけだけど、最終的にそれらがクリアされてくると、「おぉ！」とか思ったりもするし。

そんなこんなで、新しい論文が出来上がっていく過程では、著者とレフリーは直接会うことはないわけだけど（実際に会う機会があっても、「自分がレフリーやってます」とは言えないわけだけど）、いろいろとあるもんだなぁ、としみじみしたりもする。

DIMACS のクリークのデータを Matlab 用に変換する

DIMACS のクリーク用データは、
https://turing.cs.hbg.psu.edu/txn131/clique.html
のサイトから入手できるが、バイナリ形式であるので、これを Matlab で扱いやすいように変換をする。

実際のファイルは、
https://turing.cs.hbg.psu.edu/txn131/file_instances/clique/DIMACS_cliques.tar.gz
にある。

これを展開して、 ascii ファイルに一度変換する。
変換ファイルは、
https://turing.cs.hbg.psu.edu/txn131/file_instances/converter.tar.gz
にあって、make でコンパイルした後に、
$ ./bin2asc DIMACS_cliques/MANN_a9.clq.b
とすると ascii ファイルで MANN_a9.clq が出来上がる。
一括変換なら
$ for i in DIMACS/*.clq.b; do ./bin2asc $i; done
である。

これを Matlab で処理して、一括変換する。
ただし、枝の数が 10 万を超えるものは、大きいので変換はスキップする。
以下のスクリプトを使っている。


TOO_LARGE = 100000;
dirs = dir('*.clq');
for index = 1:length(dirs)
    filename = dirs(index).name;
    fprintf('index = %d, filename = %s... ', index, filename);

    fp = fopen(filename, 'r');
    m = 0;
    n = 0;
    comments = {};
    while 1
        line1 = fgets(fp);
        if length(line1) == 1
            % end of file
            break;
        end
        if line1(1) == 'c'
            comments{length(comments)+1} = line1;
        end
        if line1(1) == 'p'
            strings = strsplit(line1);
            n = str2double(strings(3));
            m = str2double(strings(4));
            fprintf('node = %d, edge = %d\n', n, m);
            if m > TOO_LARGE
                break;
            end
            I = zeros(m, 1);
            J = zeros(m, 1);
            count = 1;
        end
        if line1(1) == 'e'
            strings = strsplit(line1);
            I(count) = str2double(strings(2));
            J(count) = str2double(strings(3));
            % fprintf('e[%d] = %d, %d\n', count, I(count), J(count));
            count = count + 1;
            if rem(count, 5000) == 0
                fprintf('e[%d]... ', count);
            end
        end
    end % end of while
        if m > TOO_LARGE
            fprintf(' : SKIP too large \n');
            continue; % to next file
        end
       
        A = sparse(I,J,ones(m,1),n,n);
        A = A+A';

    savefile = strrep(filename, '.clq', '.mat');
    save(savefile, 'A', 'comments');

    for i = 1:length(comments); fprintf('%s', comments{i}); end

end



出来上がったファイルは、
load MANN_a9
などで読み込むことができて、
for i = 1:length(comments); fprintf('%s', comments{i}); end
でコメントも表示できる。

Matlab でのエディタとコマンド入力の間のキーボードショートカット

Matlab の IDE でエディタとコマンド入力のところを行ったり来たりするのにマウスでクリックするのがめんどくさいと思っていたが、キーボードショートカットを調べてみたら、

Ctrl + Tab

で移動できることが判明。これで、さらに便利になった。

欲しいキーボードショートカットとしては、エディタで編集している時に一つ前の履歴のコマンドを実行するショートカットがあればいいとは思う。
たとえば、function [x,y] = test01(a, b, c) などがあるときに、F5 を押しただけでは a,b,c を入力できないけど、a,b,c を変更せずにソースを修正しながら何回も実行してテストするときなどには、こういった機能があったりすると便利だ。
今の状態だと、「Ctrl + Tab => 上 => Enter => Ctrl + Tab」 とすればできるけど、これがF4 なり、F8 などで、一回でできると便利かとは思う。

20年後の数理最適化はどうなっているか？

今からざっと２０年前は内点法がある程度できあがってきた頃。
年初めということで、現在から２０年たったら数理最適化の研究はどうなっているかを考えてみるのも一興かとも思う。

大まかな予想としては（一部に、「そうできたらいいなぁ」という願望も含む）、

１．純粋数学に近い研究と実用に近い研究へと、大きく２極化する

たとえば、Math Prog などに掲載されるようなものは、パッとすぐには実用化には結びつかないような、むしろ純粋数学に近いようなところが多くなるかと思う。これはこれで基礎理論として純粋に理論を追究していくタイプになって面白そう。

逆に実用に近いところでは、メタヒューリスティクスのように厳密な最適解ではないが、実用的な計算時間で妥当な近似解を出すようなところが増えるのではないかと思う。これはこれで、実社会への応用が着実に行われて面白いと思う。

２．リアルタイム最適化が行えるようになる

たとえば、分枝限定法などは長時間の計算になるので、計算している途中で変数を追加したり削除したりを行いたくなってくる。
途中のノードの計算結果を見たときに変数と制約の追加や削除を自由に行えるようなアルゴリズムを作れたら、非常に面白い。
これができれば、小さいデータでテストをしながらも、順調に進めば大きなデータにアルゴリズムをリスタートすることなく移行することができるようになる。
たとえば、データの変化を追いかけたい金融のポートフォリオの計算などに使えるかと思う。

３．クラウドソーシングで研究機関が個人からも研究を受注できるようになる

数理最適化分野だけに限る必要はないが、クラウドソーシングを利用することによって、企業のような大組織だけでなく個人からも研究を受注できるようになる。
クラウドソーシングを使うと、もっと気軽に「こういった研究が欲しい」という声を聴ける可能性もあり、今までは把握できなかった研究テーマなどが発掘でできるようになるだけでなく、研究成果をよりダイレクトに還元することができるようになる。
数理最適化や確率・統計などの一部を含むオペレーションズ・リサーチは、「問題解決学」という側面ももっているので、非常に面白そう。


まずは思いつくのはこんなところ。
３については技術的には既に可能なので、２０年とかからずとも不思議ではない。

数理最適化に関係するいろんな人が「２０年後に数理最適化はどうなっているか」を予測し始めたら、それも見てみたかったりもする。