最適化問題に対する超高速&安定計算

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

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

2009年06月30日 22時25分11秒 | Weblog
第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緩和問題 その2

2009年06月29日 00時41分24秒 | Weblog
非負かつ半正定値(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

2009年06月28日 00時29分20秒 | Weblog
我々の最短路研究に関する FAQ 集を公開した。2ページ目のデモ画面とは最短路 Online Solver のことになる。

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


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

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

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

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

2009年06月27日 01時12分00秒 | Weblog
応用に役立つ50の最適化問題ということで以下の50個を揃えてみた(少し強引に50個に合わせたところもあるが)。最適化問題や最適化手法で構成されている。

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

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

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

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

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

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

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

9章:最適化問題に対する情報技術の適用
量子化学分野における半正定値計画問題の応用 蛋白質立体構造解析
コメント
この記事をはてなブックマークに追加

研究室内仮想クラウド

2009年06月26日 00時23分02秒 | Weblog
現在の研究予算から 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緩和問題

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

災害対策システムと AR

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

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

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

2009年06月23日 01時24分07秒 | Weblog
昨年のことになるが、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日

2009年06月22日 17時58分51秒 | Weblog
第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

2009年06月21日 04時06分29秒 | Weblog
Vine Linux で現在 Ver.5 の α2 が公開になっている。仮想マシンでしか使用していないので速度などの点は良くわからないが、Vine Linux の大きな特徴である日本語 LaTeX の使い勝手の良さは引き継がれているようだ。今回の Ver. 5 での大きな変更の1つは 64bit(x64) 版の登場である。ただし gcc のバージョンが 4.1.2 と古めなのが残念なところだ(RHEL Ver.5 と同じ)。
コメント
この記事をはてなブックマークに追加

SDPA 7.3.0 の実験結果

2009年06月20日 03時27分55秒 | Weblog
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 によるクラスタインストール

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

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

Fedora 10 から Fedora 11

2009年06月18日 20時26分00秒 | Weblog
研究室の OS が Fedora 10 のマシンを全て 11 にアップグレードした。以下の二つの方法を試した。

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

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

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

SDPA on AMD Istanbul

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

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

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

○問題2: rabmo.dat-s
マシン1: 30.27s
マシン2: 22.68s
マシン3: 17.62s

○問題3: theta6.dat-s
マシン1: 15.11s
マシン2: 11.80s
マシン3: 10.34s
コメント
この記事をはてなブックマークに追加

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

2009年06月16日 02時56分43秒 | Weblog
そろそろ SDPA オンラインソルバーの次期システムを考え始めている。まずソルバーの特徴だが、以下のようになっている。

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

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