第2回研究会のお知らせ 更新 6月26日

第2回研究会のお知らせです。場所は前回と同じになります。

日　時 ： 2009年7月25日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6号館4階 6402号室

講演者
1: 山田雄二氏 (筑波大学）

平滑化スプライン最適化による最適ヘッジ問題

最適ヘッジ問題とは，投資家がある資産を売買することによって生じる損失を，別の資産から構成されるポートフォリオによって補てんする際の，最適な資産保有単位を求める問題であり，最も簡単なケースでは，線形回帰問題(もしくは通常の最小二乗問題)に帰着して解くことができる．ところが，より一般的にデリバティブ契約などを用いれば，非線形の支払い構造をもつポートフォリオを定義することができるのであるが，この際，どのような最適化問題を解けばいいかが問題となる．本研究では，平滑化スプライン最適化として知られる一般化加法モデルを適用することにより，最適ヘッジを達成する非線形ポートフォリオの構築を試みる．また，事例として，風力発電取引に適用する際のヘッジ効果や流動性の低い資産を株式などの流動性の高い資産でヘッジする問題について紹介する．


2: 中田真秀氏（理化学研究所）

第一部 : 量子化学からでてくる半正定値計画と多倍長計算

量子化学は半正定値計画をもって定式化でき、従来の方法より変数の数を劇的に減らすことが可能となる。このことは古くから知られていたが、半正定値計画ソルバーの発達をもって初めて、物理的に意味のある、正確な結果を知ることができた(J.Chem.Phys. 114,8282(2001))。
この研究には二つの方向があり、一つは、N-representability条件をどう近似するかというとと、もう一つは巨大な半正定値計画を数値的に正確に解くこと、である。さらに、半正定値計画の精度の必要性より多倍長精度版の半正定値計画法および多倍長精度版のBLAS/LAPACKも開発、もしくは開発中である。

第二部 : オープンソースコミュニティでのソフトウェア開発とコミュニティマネジメントについて
OpenOffice.org/FreeBSD.orgへの参加を通して

現在のあらゆるコンピュータ環境に、もはやフリーソフトウェア(オープンソースソフトウェア)は必須である。フリーソフトウェア(オープンソースソフトウェア)は大抵無料で入手できるため、開発者などに開発費が支払われることはほとんどない。OpenOffice.orgおよびFreeBSD.orgでの開発およびコミュニティマネジメントを通して、どうしたら参加できるか、我々は何を求めているか、どうしたら存続、維持できるかなどについて話をする。

DNN上でのSDP緩和問題 その２

非負かつ半正定値(DNN : doubly non‐negative)制約を両方使用すると SDP 緩和の最適目的関数値が元の問題の最適目的関数値に非常に近い値になる件の続きになる。

1: 現在以下の二つの問題を試しているが、元問題は非凸QP(二次計画問題)になる。これから DNN 制約付き SDP 緩和問題を作る。非負制約によって元問題の凸包に近くなるのではないか？（特に根拠はなし）


2: 非負制約によって制約条件の数が増大する。これから Schur complement 行列の Cholesky 分解がボトルネックになる。
以下は SDPARA 7.2.1.rev8 + GotoBLAS 1.34 + MUMPS 4.8.4 を SDPA クラスタ上で実行したときの結果になる。A と B 両方とも非凸QP に DNN 制約付き SDP 緩和問題を作っている。

A: QAP(二次割当問題)

had20 : 総計算時間 10464.2s
Cholesky bMat = 8472.634236s, 80.973215%

B: Portfolio Selection(ポートフォリオ選択問題)

200101 : 総計算時間 1240.5s
Cholesky bMat = 823.754049s, 66.415721%

最短路 FAQ

我々の最短路研究に関する FAQ 集を公開した。２ページ目のデモ画面とは最短路 Online Solver のことになる。

http://sdpa.indsys.chuo-u.ac.jp/~fujisawa/ss-faq.pdf

大規模最短路問題に対する高速&高性能計算システム

技術の概要
大規模なネットワーク上で二点間の最短路を求める最短路問題は非常に幅広い応用が存在する。例えば実社会における様々な大規模な交通データ（特に道路）に対する経路検索、特にカーナビゲーションシステムや GoogleMaps 上での経路検索などが有名である。最短路問題に対してはダイクストラ法というアルゴリズムが用いられるが、データ構造やメモリ階層構造を考慮した実装上の工夫により世界最高速レベルの速度、安定性、低メモリ消費などの特性を備えたソフトウェアの作成に成功した。またクラウドコンピューティングの技術を用いてユーザからの負荷に応じて自動的に計算サーバを増減する最短路計算システムの開発にも成功した。

従来技術に対する新規性・優位性
1: 世界最高レベルの性能を持った最短路計算エンジン
2: 拡張性の高いアルゴリズムとデータ構造により様々な条件を追加することが可能
3: クラウドコンピューティングの技術による計算サーバの自働増減

応用に役立つ５０の最適化問題

応用に役立つ５０の最適化問題ということで以下の５０個を揃えてみた(少し強引に５０個に合わせたところもあるが)。最適化問題や最適化手法で構成されている。

2章：線形計画問題
線形計画問題 包絡分析法 多目的(線形)計画問題 確率分布の推定 区分線形関数の最小化

3章：整数計画問題
整数計画問題 混合整数計画問題 ナップサック問題(→8章) 2次割当問題 施設配置問題(→6章) 巡回セールスマン問題 集合被覆問題(→6章) ロットサイズ決定問題 制約充足問題

4章：非線形計画問題
微分不可能な目的関数をもつ制約なし最適化問題 相補性問題 変分不等式問題 均衡制約付き数理計画問題 (金融工学)平均・分散モデル (金融工学)平均・絶対偏差モデル (金融工学)条件付きCVaR最小化問題 2次錐計画問題

5章：半正定値計画問題
半正定値計画問題 0-1整数計画問題 グラフ分割問題 システムと制御分野への半正定値計画問題の応用 ロバスト最適化問題 ロバスト線形計画問題 ロバスト最短路問題 最小２乗法 ロバストチェビシェフ近似問題 多項式最適化問題 サポートベクターマシン 最小包囲楕円問題 双線形行列不等式

6章：集合被覆問題
集合被覆問題(→3章) 集合分割問題 配送計画問題 施設配置問題(→3章)

7章：勤務スケジューリング問題
乗務員スケジューリング問題 乗務パターン作成問題 乗務員勤務スケジュール作成問題 看護師スケジューリング問題

8章：切出し・詰込み問題
ナップサック問題(→3章) ビンパッキング問題 １次元資材切出し問題 長方形詰込み問題 (長方形)ストリップパッキング問題 (長方形)面積最小化問題 (長方形)パレット積込み問題 多角形詰込み問題

9章：最適化問題に対する情報技術の適用
量子化学分野における半正定値計画問題の応用 蛋白質立体構造解析

研究室内仮想クラウド

現在の研究予算から Amazon EC2 などのクラウド予算を捻出するのは難しそうなのと、外部の研究用の計算機を借りるのは様々な管理ポリシーを気にする必要があるので、研究室内に仮想クラウド環境(プライベート＆パブリッククラウド）を作成することにした。つまり仮想クラウド環境の仮想環境になる。それとまだ目的が二つほどあって、以下のようになる。

1: 負荷に応じて自動スケールアップ＆ダウンを行う最短路検索システムの研究室内で完結させる
2: SDPA Online Solver の新システム構築

パブリッククラウドマシンの方は Lucie を使って PXE boot から動的インストールを繰り返すということを行うことになる。

◯研究室内プライベートクラウド
SDPA クラスタ(16台), POWER クラスタ(4台)
単独ノード
1: Intel Xeon 5550 2.66GHz (72GB)
2: AMD Opteron 2384 2.7GHz (32GB)
など

◯研究室内パブリッククラウド
単独ノード
1: Intel Core i7 965 3.2GHz (12GB)
2: Intel Core 2 quad 9550 3.0GHz (8GB)
3: AMD Phenom2 X4 955 3.2GHz (8GB)
4: AMD Opteron 270 2.0GHz (4GB)
5: Intel Atom 230 1.6GHz (1GB)
など

DNN上でのSDP緩和問題

非負かつ半正定値(DNN : doubly non‐negative)制約を持つ SDP 緩和問題の最適解を求めると最適解との gap が非常に小さいことが数値実験によってわかってきた。ただし非負制約を全ての変数に対して入れていくとスラック変数の数が膨大になって非常に大きな SDP になってしまう。非負かつ半正定値の錐に対して self‐concordant barrier functionを作成できることがわかっているのだが、高速にニュートン方程式の解を見付けて安定した主双対内点法の作れるかどうかは未知数である。
とにかく現行の内点法アルゴリズムでも SDPARA などを用いてクラスタ計算機で解いていけば結構大きな SDP でも解くことができる。添付の図は問題の説明を省略してあるのでわかりにくいのだが、Cutting-plane algorithm による最適解の上限 \bar{f} と DNN 制約を持つ SDP 緩和問題による \lambda の値の差が小さく、この SDP 緩和問題の性能が良いことがわかる。

災害対策システムと AR

災害対策システムを調べていたら AR(拡張現実)の利用などが書いてあった。AR 系の話は嫌いではないが、人間の調べたり考えたり疑ったりする能力を低下させていくように思える。災害時に狭い地域から多数の人が同時に携帯接続を行えば通信不能になりそうだ。双方向通信ではなくワンセグみたいに受信するだけならば回線がパンクすることもないので、災害時の経路誘導などは一方向通信で行うべきなのだろうか？

この話と関連する今後の研究のことになるが、キーワードは”大規模計算 + 大規模データ + 最適化”となっている。平凡な三つのキーワードに見えるが、全て揃えるのはなかなか難しいようで、真面目に三つ揃ったものを見たことはほとんど無い（一度も無いかもしれないが）。

SDPA と SDPARA に関する二つの疑問

昨年のことになるが、SDPA のユーザーから以下のような質問（疑問）を受けた。理論系だけの知識しか無いとこのような疑問を持つのも当然かもしれないが、今後も様々な開発計画がある。

○疑問 1 : SDPA はソフトウェアとしては完成の域に入っているので、もうやることが無いのでは？

以下のようにマルチスレッド化などによってかなり高速化している。まだまだ出来ることは多いだろう。

問題 : NH3+.2A2".STO6G.pqgt1t2p.dat-s
マシン : Intel Xeon 5550 (2.66GHz) x 2 : メモリ 72GB : Fedora 11 for x86_64

SDPA 7.2.1 (2008年) : 3946.19s
SDPA 7.3.1 (2009年) : 502.8s

もう一つの疑問は SDPA と SDPARA に関するもので以下の通り。

○疑問 2 : ある程度大きな問題では SDPA と SDPARA にはどの程度差があるのか？

これは比較が難しいのだが、あまり大きくない問題では SDPA の方が速い場合が多い。以下の問題では 16 台用いて(SDPARA)、1 台(SDPA)の場合よりも 5 倍程度しか高速ではないが、やはり大きな問題では SDPARA の方に軍配が上がる。

問題 : NH3+.2A2".STO6G.pqgt1t2p.dat-s
○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
HDD : 6TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.3 for x86_64

SDPARA 7.2.1.rev8 (2009年) : 102.1s
SDPA 7.3.1 (2009年) : 502.8s

第2回研究会のお知らせ 更新 6月19日

第2回研究会のお知らせです。場所は前回と同じになります。詳細が決まりましたらまた連絡致します。

日　時 ： 2009年7月25日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6号館4階 6402号室

講演者
1: 山田雄二氏（筑波大学）TBA


2: 中田真秀氏（理化学研究所）

第一部 : 量子化学からでてくる半正定値計画と多倍長計算

量子化学は半正定値計画をもって定式化でき、従来の方法より変数の数を劇的に減らすことが可能となる。このことは古くから知られていたが、半正定値計画ソルバーの発達をもって初めて、物理的に意味のある、正確な結果を知ることができた(J.Chem.Phys. 114,8282(2001))。
この研究には二つの方向があり、一つは、N-representability条件をどう近似するかというとと、もう一つは巨大な半正定値計画を数値的に正確に解くこと、である。精度の必要性より多倍長精度版の半正定値計画法および多倍長精度版のBLAS/LAPACKを開発、もしくは開発中である。

第二部 : オープンソースコミュニティでのソフトウェア開発とコミュニティマネジメントについて
OpenOffice.org/FreeBSD.orgへの参加を通して

もはやフリーソフトウェア(オープンソースソフトウェア)は現在必須になってきた。自由なソフトは配布も大抵無料のため、開発者などに支払われることはない。OpenOffice.orgおよびFreeBSD.org での開発およびコミュニティマネジメントを通して、どうしたら参加できるか、我々は何を求めているか、どうしたら存続するかなどについて話をする。

Vine Linux 5 α2

Vine Linux で現在 Ver.5 の α2 が公開になっている。仮想マシンでしか使用していないので速度などの点は良くわからないが、Vine Linux の大きな特徴である日本語 LaTeX の使い勝手の良さは引き継がれているようだ。今回の Ver. 5 での大きな変更の1つは 64bit(x64) 版の登場である。ただし gcc のバージョンが 4.1.2 と古めなのが残念なところだ(RHEL Ver.5 と同じ)。

SDPA 7.3.0 の実験結果

SDPA 7.3.0 と他のソフトウェア(CSDP, SDPT3, SeDuMi)の比較実験結果を以下に置いた。

http://sdpa.indsys.chuo-u.ac.jp/~fujisawa/ronbun-sdpa7-results.pdf

SDPA の結果を簡単に考察すると、以下のようになる。

1: Schur complement 行列が疎になる場合には、Sparse Cholesky 分解が有効に働く
2: 反対にSchur complement 行列が密かつ大規模になるときには、F1, F2, F3式のマルチスレッド計算が有効に働く
3: 数値精度は他と同程度

Lucie によるクラスタインストール

現在、大規模計算 + 大規模データ + 最適化の研究のために Lucie による動的かつ自動のクラスタインストールを利用している。以前中高生向けのサイエンスセミナーということで半日コースで出来ることを考えていたのだが、”３時間で出来る並列計算機”というのを提案していた。大学生向けの授業でも良いのだが、Lucie を使うと以下のようにシンプルかつ高度に行うことができる。

1: 空 PC (HDD が空あるいは中身を全て消しても良い PC)を複数台用意する。さすがに自作から行うのは時間的につらい。ただしハードウェアの簡単な説明を行う。
2: Lucie によるクラスタインストール。添付の画像のように動的にインストール状況を確認することができる。
3: 実際にいろいろなアプリケーションを動かして並列計算を体験する。

Fedora 10 から Fedora 11

研究室の OS が Fedora 10 のマシンを全て 11 にアップグレードした。以下の二つの方法を試した。

1: コマンドラインから preupgrade とする
2: Fedora 11 のインストールメディア(DVD)を用いる

1 の preupgrade は失敗することもあると言われているのだが、今回は６台のマシンをアップグレードを行って失敗したマシンは１台も無かった。2 とは異なり最新のファイルがインストールされる。よって 2 の方法では終了後に yum -y update を行う必要がある。

ところで、Fedora 11 では glibc のスタティックライブラリがデフォルトではインストールされないので、
yum install glibc-static
と行う必要があった。

SDPA on AMD Istanbul

SDPA 7.3.1.RC2 を AMD Opteron (Istanbul) 2.6GHz (2-way or 4-way) で実行する機会があった。思っていたよりも Istanbul での性能は良いのだが、コストパフォーマンスでは 2-way > 4-way になる。4-way は 2-way の通常２倍以上の値段がするのだが、それに見合うような性能差は当然ながら無いようだ。

マシン１ : AMD Opteron (Shanghai) 2384 2.7GHz x 2 (8コア)
マシン２ : AMD Opteron (Istanbul) 2.6GHz x 2 (12コア)
マシン３ : AMD Opteron (Istanbul) 2.6GHz x 4 (24コア)

○問題１: LiH.1Sigma+.STO6G.pqgt1t2p.dat-s
マシン１: 29.25s
マシン２: 21.48s
マシン３: 16.73s

○問題２: rabmo.dat-s
マシン１: 30.27s
マシン２: 22.68s
マシン３: 17.62s

○問題３: theta6.dat-s
マシン１: 15.11s
マシン２: 11.80s
マシン３: 10.34s

仮想クラウド環境と SDPA オンラインソルバー

そろそろ SDPA オンラインソルバーの次期システムを考え始めている。まずソルバーの特徴だが、以下のようになっている。

1: SDPA は 1 台(マルチコア)で実行
2: SDPARA は 複数台(しかもマルチコア)で実行

SDPA は１台で計算が出来るので、SDPA の計算サーバは 1 台だけ常時稼働させておく。一方、一般的には SDPARA の方が実行時間が長く、多くの計算サーバを必要とする(MPI 並列なので)。いつ計算要求が来るのかわからないのに常時多数の計算サーバを稼働させるのは電源等の無駄遣いなので、普段は止めておく。SDPARA の計算要求が来た場合に動的に計算サーバの確保や構築などを行う。
簡単にまとめると SDPA はプライベートクラウドで、SDPARA はパブリッククラウドで実行する。ただしパブリッククラウドは Amazon 等ではなく、当面は研究室内のサーバで構築する。そしてこのパブリッククラウド用のサーバは普段は止めておく。