投稿
先週の浜松で行われた RAMP で、無事にセッションオーガナイザーのお仕事が終わりました。
セッションオーガナイザーのお仕事は、その名前が示す通り、セッションをオーガナイズすることですが、そのお仕事を通じて、いろんな方のお世話になりました。
まずは、実行委員長とプログラム委員長のおかげで、セッションをオーガナイズすることに集中できました。
また、講演者の方には、準備段階から原稿の締め切りなど、ほぼきちんと守っていただいて、とても助かりました。おかげさまで、シンポジウムまでに原稿を20回ぐらい読み込むことができました。もちろん、シンポジウムでの発表も、「バリバリの非線形最適化」にふさわしい、どれも面白いものばかりで、勉強になることばかりでした。
帰りの新幹線では、サンテグジュペリの言葉を思い出したりしました。
自分がオーガナイザーをできるのは今回１回切りだと思いますが（いろんな方がオーガナイズすると発表の幅もできると思うので）、もう１回機会があったら是非再度やってみたい、と強く思える貴重な機会でした。
2015年10月23日金曜日
2015年9月29日火曜日
簡単そうに見えて、実は難しい、最適化問題
最小自乗問題
$$ \min \frac{1}{2} || Ax - b ||^2 \quad \mbox{s.t.} \quad x \in R^n $$
は、A の行が一次独立なら簡単に解ける問題。
次に、
$$ \min \frac{1}{2} || x - x^0 ||^2 \quad \mbox{s.t.} \quad x \in R^n,\ x \ge 0$$
である。
ところが、この２つが組み合わさると
$$ \min \frac{1}{2} || Ax - b ||^2 \quad \mbox{s.t.} \quad x \in R^n,\ x \ge 0$$
$$ \min \frac{1}{2} || Ax - b ||^2 \quad \mbox{s.t.} \quad x \in R^n $$
は、A の行が一次独立なら簡単に解ける問題。
次に、
$$ \min \frac{1}{2} || x - x^0 ||^2 \quad \mbox{s.t.} \quad x \in R^n,\ x \ge 0$$
と各変数が非負に制限されるときも簡単に解けて、解としては
$$ x^* = \max\{x,0\} $$である。
ところが、この２つが組み合わさると
$$ \min \frac{1}{2} || Ax - b ||^2 \quad \mbox{s.t.} \quad x \in R^n,\ x \ge 0$$
とたんに、簡単には解けなくなる。
のように内点法ベースなら解けるのであるが、もっと簡単に解けそうにも見えて、そういった解法が見当たらない。
この「簡単そうなのに、より適した解法が案外見当たらない」というところが、面白い。
2015年9月28日月曜日
LPの今までとは違う解法
最近の論文をチェックしていたところ、LP のシンプレックス法や内点法とは異なる解法についての論文があった。
ぱらぱらっとめくったところでは、最適解が得られることなどは証明されている様子だが、どれだけの反復回数で収束するのか、のあたりはまだ検討されていない様子。ただ、「反復回数」の扱いも内点法と同じような基準でいいのかどうかもよく分からないので、単純な比較はできないかも知れない。
流れとしては、シンプレックス法よりも内点法に近い流れなので、中心パスなどとどう関係しているのか、などを考えてみると面白いかと思う。
ぱらぱらっとめくったところでは、最適解が得られることなどは証明されている様子だが、どれだけの反復回数で収束するのか、のあたりはまだ検討されていない様子。ただ、「反復回数」の扱いも内点法と同じような基準でいいのかどうかもよく分からないので、単純な比較はできないかも知れない。
流れとしては、シンプレックス法よりも内点法に近い流れなので、中心パスなどとどう関係しているのか、などを考えてみると面白いかと思う。
2015年9月24日木曜日
unit simplex への射影
unit simplex、つまり
$$ \sum_{i=1}^n x_i= 1, x \ge 0 $$
への射影の方法が以下の論文に掲載されている。
A projected gradient method for optimization over density matrices
D.S. Gonçalves, M.A. Gomes-Ruggiero & C. Lavor
http://www.tandfonline.com/doi/abs/10.1080/10556788.2015.1082105?journalCode=goms20
Dykstra などの交互射影法とは異なり、有限回の計算で解が計算される点が面白い。
ところで、この方法を変形して、
$$ \sum_{i=1}^n x_i= 1 $$
にまずは射影してから計算すると効率が上がったりするのだろうか？
そのあたりを考えてみるのも面白そうではある。
$$ \sum_{i=1}^n x_i= 1, x \ge 0 $$
への射影の方法が以下の論文に掲載されている。
A projected gradient method for optimization over density matrices
D.S. Gonçalves, M.A. Gomes-Ruggiero & C. Lavor
http://www.tandfonline.com/doi/abs/10.1080/10556788.2015.1082105?journalCode=goms20
Dykstra などの交互射影法とは異なり、有限回の計算で解が計算される点が面白い。
ところで、この方法を変形して、
$$ \sum_{i=1}^n x_i= 1 $$
にまずは射影してから計算すると効率が上がったりするのだろうか？
そのあたりを考えてみるのも面白そうではある。
2015年9月14日月曜日
著者が亡くなっても掲載される論文
Mathematical Programming Computation の Volume 7, Number 3 の Preface にいろいろと事情が掲載されている。
非常に意義深いことだな、と思う。
非常に意義深いことだな、と思う。
2015年9月1日火曜日
Matlab ソースを PDF に一括変換する
Matlab のソースを Matlab がインストールされていないパソコンで閲覧したいときには一度 PDF に変換したりすると便利だが、 Matlab の機能の publish だと HTML に変換して PDF に変換するのを一つ一つ行う必要があって、これがなかなかに面倒。
ということで、以下のようなシェルスクリプトで一括変換する。
for i in `find . | grep m$`
do
LANG=C a2ps -1 --pro=color $i -o - | ps2pdf - $i.pdf
done
ここで、 LANG=C を入れているのは、a2ps で日本語が文字化けするので日付などが日本語だと文字化けしてしまうため。
また、--pro=color とすると、出力がカラーになるので、見やすくなる。
ということで、以下のようなシェルスクリプトで一括変換する。
for i in `find . | grep m$`
do
LANG=C a2ps -1 --pro=color $i -o - | ps2pdf - $i.pdf
done
ここで、 LANG=C を入れているのは、a2ps で日本語が文字化けするので日付などが日本語だと文字化けしてしまうため。
また、--pro=color とすると、出力がカラーになるので、見やすくなる。
2015年8月26日水曜日
対角優位行列とゲルシュゴリンの定理
「対角優位行列は半正定値行列である」
という命題が成り立つ方法を考えていたが、ゲルシュゴリンの定理を使ったら、あっというまに示せることがわかった。
やっぱり、いろんな定理を知っている、ということも大事なものである。
という命題が成り立つ方法を考えていたが、ゲルシュゴリンの定理を使ったら、あっというまに示せることがわかった。
やっぱり、いろんな定理を知っている、ということも大事なものである。
登録:
投稿 (Atom)