過去の研究会の記録

第1回 研究会

日　時：2009年3月21日（土）14時 〜
会　場： 中央大学 後楽園キャンパス 6号館4階 6402号室

講演1
講演者：小島政和氏　（東京工業大学）
講演題目：半正定値行列補完における双対性とその SDP への応用
講演概要：
一般に，半正定値条件が課せられた対称行列変数と行列不等式（非線形でもよい）を含む最適化問題を考える．
この問題がコーダルグラフで特徴づけられる疎性構造を有するとき, この問題をより規模の小さな問題に
変換することが出来る．この講演ではこの変換の理論を支える半正定値行列補完とその双対性，4種類の
変換方法， および，線形のSDPへそれらを適用したときのソフトウェアとその計算実験について述べる．
この研究は以下に基づいている．
B-452: S. Kim, M. Kojima, M. Mevissen and M. Yamashita, "Exploiting Sarsity in Linear and
Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion", January 2009．
B-453: K. Fujisawa, S. Kim, M. Kojima, Y. Okamoto and M. Yamashita, "User's Manual for SparseCoLO:
Conversion Methods for SPARSE COnic-form Linear Optimization Problems", February 2009.

講演2
講演者：村松正和氏　（電気通信大学）
講演題目：A Facial Reduction Approach in Conic Programming
講演概要：
錐線形計画 (Conic Programming, CP) はLP, SDP, SOCP を含む広いクラスの凸計画であり、
近年、内点法を中心とした解法が広まりつつある。しかし、LP を除く一般の CP では、
特に「内点許容解」が存在しないとき、数値的困難さが現れ、内点法がうまく動かないことがある。
この講演では、このような数値的困難さを取り除くために、Facial Reduction Algorithm (FRA) を
使う方法を提案する．FRAは、有限回の反復の後、主問題を「内点許容解」が存在する等価な CP に
変形する．また、FRA は Sturm らが提案したdual regularization approach と深い関係があるので
これを説明する．最後に、いくつかの具体例に関して、どのように FRA が働くかを見る．
本研究は電気通信大学の脇隼人氏との共同研究である．


第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での開発およびコミュニティマネジメントを通して、
どうしたら参加できるか、我々は何を求めているか、どうしたら存続、維持できるかなどについて話をする。


第3回 研究会

日　時：2009年10月24日（土）14:00〜
会　場： 中央大学 後楽園キャンパス 6号館4階 6418号室(前回と部屋が異なります)

講演1
講演者：宇野毅明氏　（国立情報学研究所情報学プリンシプル研究系）
講演題目：文字列データの高速類似性解析と可視化技術
講演概要：
近年の検索技術の発達により、ゲノムのような巨大な文字列データベースにおいても、ある程度の曖昧性を許容する
検索が短時間で可能となっている。しかし、文章データの中から類似する物を見つける、ゲノムとゲノムを比較して、
部分的に類似する領域を見つける、といったような巨大な問題の場合、多くの検索が必要となるために莫大な計算時間が
必要となる。本講演では、巨大な文字列データから類似する部分文字列の組を高速で発見する、複数分類法という新しい
手法と、類似する領域を可視化する方法をの紹介する。また、ランダムプロジェクションの利用により、ベクトルデータ
の類似性の検出に使えることも示す。


講演2
講演者：保木邦仁氏　（東北大学大学院理学研究科）
講演題目：最適制御法の思考型ゲームへの応用：名人を超える将棋プログラム作成への取り組み
講演概要：
将棋や囲碁のようなゲームは人工知能研究の基本的なモデルで、人知を超えるコンピュータの作成は計算科学における
大きな目標の一つです。特に、チェスを指すプログラムは1960年代のコンピュータ技術黎明期から真剣に研究されてい
ます。本研究では優劣の判断がより難しい将棋の思考アルゴリズムを最適制御法の枠組みに沿って設計する手法を開発
しました。これは、チェスやその変種のゲームとしては"実用に耐え、役に立つ"初めての機械学習の手法です。


第4回 研究会

日　時：2009年11月21日（土）16:00〜
会　場： 中央大学 後楽園キャンパス 6号館4階 6418号室

講演者：Hans D. Mittelmann氏　（School of Math & Stats, Arizona State University, AZ, USA）
講演題目：State-of-the-Art in the Solution of Control-Related Nonlinear Optimization Problems
講演概要：
We start by giving an overview of some of our activities related to the computational solution of a range
of optimization problems, including a leading web-based guide to software and its performance and a major
installation of free web-based solvers. Then we sketch two classes of problems from our recent research,
PDE constrained optimization as it arises in the control of PDEs and system identification problems.
The first class gives rise to very large and sparse nonlinear optimization problems that still challenge
state-of-the art algorithms including commercial products. The second class of problems are system identification
problems including those suitable for data-centric estimation and control. At first we will address the solution
of the crest-factor optimization problems utilized in our earlier work, then we will introduce a novel
optimization formulation which has facilitated the application of the MoD (Model-on-Demand) type of control
for process systems. For all problems considered formulations in the modeling language AMPL are utilized and
we sketch some exemplarily.


第5回 研究会

日　時：2010年2月27日（土）14:00〜
会　場： 中央大学 後楽園キャンパス 6号館4階 6410号室

講演1
講演者：渡部大輔氏　（東京海洋大学海洋工学部流通情報工学科）
講演題目：一般化Weberモデルによる航空貨物ハブ施設配置の最適化
講演概要：
本研究では、航空貨物輸送における輸送費用の変化が単一のハブ空港配置に与える影響について、
輸送距離と輸送量をべき関数として一般化したウェーバー問題を用いて考察する。まず、一次元・
二次元の規則的な点配置における輸送費用関数の変化による最適配置の分析を行う。さらに、
東アジアにおける航空貨物の輸送を対象に分析を行い、各国の航空運賃から推定したパラメータ
により、同じ需要分布でも異なる最適配置の結果が得られた。

講演2
講演者：小林和博氏　（海上技術安全研究所物流研究センター）
講演題目：船舶スケジューリングと船の最短路問題
講演概要：
船舶スケジューリングは、複数の荷物を運搬するための最も効率のよい船舶の運航スケジュールを
求める問題である。数理的構造はVehicle Routing Problem (VRP)と同じであるが、船舶および港湾の
運用上の特徴により、有効な解法が陸上のVRPとは異なる. 本発表では集合被覆問題と列生成による
ヒューリスティックな解法を紹介する。船の最短路問題では、出発港から目的港までの航路の選定を、
制約付き2目的最短路問題に定式化する。この問題に対して、ロバスト性をもつ解を与える計算方法について報告する。

第6回 研究会

日　時：2010年3月27日（土）14:00〜
会　場： 中央大学 後楽園キャンパス 6号館4階 6410号室

講演1
講演者：佐藤仁氏　（東京工業大学学術国際情報センター）
講演題目：大規模データ処理と最適化
講演概要：
近年、科学技術計算において大量のデータに対する解析処理が広く行われている。多くの場合、
このような処理は、スーパーコンピュータやクラウドのような大規模並列計算環境で行われるが、
効率的に計算資源を利用するためには、最適化技術が不可欠である。この講演では、大規模並列
計算環境でのデータ処理における最適化技術の応用事例として、複製配置を0-1整数計画問題として
モデル化したファイル複製配置最適化システム、及び、仮想マシンの移動を最短経路問題として
モデル化した大規模データアクセスの高速化技術、について紹介する。

講演2
講演者：竹房あつ子氏　（産業技術総合研究所情報技術研究部門）
講演題目：性能を保証する分散実行環境のためのコアロケーション手法
講演概要：
グリッドとネットワーク資源管理技術により，複数の組織にある計算機やストレージなどの資源と
広帯域ネットワークを必要に応じて組み合わせ，性能が保証された仮想的な利用環境を構築することが
可能になった．この際，利用者の要求する計算機性能や通信帯域を保証しつつ，利用価格や資源の
有効利用など，利用者や資源管理者の方針を考慮して，適切に資源を割り当てる（コアロケーション）
必要がある．さらに，利用者の資源要求に対して即座に処理するためには，コアロケーションに要する
時間も課題となる．
　本研究では，資源が事前予約で複数の組織から提供されることを前提とし，利用者や資源管理者の方針が
反映可能なコアロケーション手法を提案する．提案手法では，分散する計算機群とその間のネットワーク
のコアロケーションを最適化問題にモデル化し，複数の予約プランを作成して適切な資源群を確保する．
評価では，コアロケーションの求解時間を制約条件とソルバの違いにより比較し，実用化に向けて議論する．


第7回 研究会

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

講演1
講演者：金森敬文氏　（名古屋大学 大学院情報科学研究科 計算機数理科学専攻）
講演題目：密度比の推定と計算 ―smoothed analysis からのアプローチ
講演概要：
２つの確率密度の比 (密度比) の推定は，機械学習における重要な課題のひと
つである．例えば，共変量シフト下での回帰分析，外れ値検出，ダイバージェ
ンス推定，条件付き確率密度の推定など，さまざまな統計的推論の問題が密度
比推定の枠組で定式化される．本発表では，密度比推定に対してカーネル関数
と最小２乗法を用いた学習アルゴリズムを提案し，その統計的ないし数値的性
質について考察する．計算効率や数値安定性などの性質は，計算対象となる関
数から定義される条件数と関係が深い．統計的推論においては，データがラン
ダムなので条件数もランダムな確率変数となる．ランダムネスのある状況下で，
学習アルゴリズムの計算効率を議論するために，計算量の分野で提案されてい
る "smoothed analysis" の考え方を利用する．この視点から，提案法は他の
方法と比べて，広いクラスの確率分布に対して条件数が小さな値に分布するこ
とを示す．これにより，提案法が大規模データに対して高い計算効率を持つこ
とが，理論的に裏付けられる．また，学習アルゴリズムを設計するための枠組
として，smoothed analysis の考え方を積極的に利用することの有用性につい
て，今後の可能性を探る．

講演2
講演者：安井雄一郎氏　（中央大学 理工学研究科 博士後期課程）
講演題目：大規模最短路問題に対するダイクストラ法の高速化
講演概要：
最短路問題はネットワーク上の経路探索などの多くの応用を持ち, また他の最適化
問題の子問題として用いられることも多く,適用範囲の広い組合せ最適化問題である.
そのため最短路問題を高速に解くことの重要性は非常に大きくなってきている.
最短路問題に対する解法にはダイクストラ法などの安定的かつ効率的な高速アルゴ
リズムが存在するが, 実問題は非常に大規模(約2,400万点, 約5,800万枝)になるため
高速化が不可欠である. そこで本研究では, バイナリ・ヒープを適用したダイクス
トラ法に対し,メモリ階層構造を考慮した汎用的かつ効率的な高速化を適用することで,
実行性能, グラフ特性に対する安定性, メモリ要求量, 並列実行など, 総合的に最も
優れたソルバーを開発することに成功した. 計算機上の律速箇所を解析するための
実験方法を合わせて示し, 本実装の有用性を裏付けていく.


第8回 研究会

日　時：2010年10月2日（土）14:00〜
会　場： 中央大学 後楽園キャンパス 6号館4階 6410号室

講演1
講演者：Karen Aardal氏（Delft Institute of Applied Mathematics, Faculteit EWI, Technische Universiteit Delft (Netherlands)）
講演題目：Integer programming, lattices, reduced bases
講演概要：
I will discuss how to use the structure of lattices to reformulate and solve
integer programming problems. I will take a closer look at integer knapsack
problems and illustrate how it is possible to use the structure of lattices
to prove properties of certain classes of knapsack problems, and how these
properties can be used in designing practically efficient algorithms.

講演2
講演者：Timo Berthold氏　（Zuse Institute Berlin (ZIB), Berlin (Germany)）
講演題目：Solving MIQCPs with SCIP
講演概要：
Mixed-integer programming (MIP) and constraint programming (CP) proved to be powerful tools to model and solve
large-scale optimization problems. Constraint integer programming (CIP) is a novel generalization of MIP that
supports the notion of arbitrary constraints as in CP. We introduce the algorithmic ideas of CIP and present
SCIP, a framework for constraint integer programming.
We show how to extend SCIP towards a solver for mixed integer quadratically constrained programs (MIQCPs).
The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies
already implemented in SCIP. We give an overview of the relaxation, reformulation, separation, and propagation
techniques that are used to handle quadratic constraints efficiently. Computational experiments indicating
the potential of the approach are provided.
In the second part of the talk, we present Undercover, a primal heuristic for mixed-integer nonlinear
programming (MINLP). The heuristic constructs a MIP subproblem (sub-MIP) of a given MINLP by fixing a subset
of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed
in order to linearize each constraint. Subsequently, these variables are fixed to approximate values, e.g.
obtained from a linear outer approximation. The resulting sub-MIP is solved by a MIP solver. We present
computational results on a general test set of MIQCPs selected from the MINLPLib.


第9回 研究会

日　時：2010年11月20日（土）14:00〜
会　場： 中央大学 後楽園キャンパス 6号館4階 6410号室

講演1
講演者：高野 祐一氏（筑波大学, 日本学術振興会PD）
講演題目：コンスタント・リバランス・ポートフォリオ選択問題に対する多項式最適化アプローチ
講演概要：
ポートフォリオ選択問題とは、手持ちの資金を各金融資産に投資して運用する際の投
資比率を決定する問題である。本発表では、コンスタント・リバランス戦略を採用し
た多期間ポートフォリオ選択問題を扱う。コンスタント・リバランスとは、計画期間
の複数時点で一定比率にリバランス（投資比率の修正）を行う投資戦略であり、実務
で採用されることも多く、理論的にも好ましい性質を持つ。しかし、この戦略を採用
した多期間ポートフォリオ選択問題は非凸計画問題となるため、その大域的最適解を
得ることは難しい。一方で、平均‐分散基準を利用することで問題は多項式計画問題
として定式化され、本発表では Lasserre (2001) によって提案された「多項式計画
問題に対する半正定値計画緩和」を利用して求解を試みる。さらに、次数の高い多項
式計画問題を解くことを目的に、Lasserre (2001) の半正定値計画緩和を利用した切
除平面法を提案し、数値実験によってその性能を検証する。

講演2
講演者：Mozart Menezes氏　（Zaragoza Logistics Center, Zaragoza (Spain)）
講演題目：Correlation and Disruption Induced Effects on Location Problems
講演概要：
In this work we study a class of locations models where facilities may fail.
The problems are defined in a network and some important properties of the
objective functions are analyzed. Asymptotic results were obtained suggest
behavioral consistency of location patterns as function of the probability
of failure. In order to go beyond those asymptotic results and, in order to
accept the fact that failures may be correlated, we shift methodology and also
present results developed in a continuous location setting: a simple (yet classic)
2-facility problem on a unit segment, with customer demand distributed uniformly
over the segment. We analyze problems with Median and Center objectives under complete
and incomplete customer information regarding the state of facilities. Managerial
insights are discussed.


第10回 研究会

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

講演1
講演者：Thorsten Koch氏（Zuse Institute Berlin (ZIB), Berlin）
講演題目：How to survive Real-World Projects as a Mathematician
(Lessons and experiences from 10 years of industry projects)
講演概要：
This talks aims at sharing the experience from 10 years of
successfully employing integer programming in industry projects with the
audience. After numerous research-industry collaboration projects we
found that there are several reoccurring topics during these projects.
The problems encountered seem to be universally the same, as there are
very common misunderstandings between the partners. We will try to draw
some general conclusions and using the projects of the author as
examples to show some common pitfalls. We will talk about acquiring
projects, getting them running and how to explain the results to
practitioners. Listening to this talk requires no particular knowledge
of mathematics.

講演2
講演者：品野勇治氏（Zuse Institute Berlin(ZIB), Berlin）
講演題目：Parallel MIP solvers developed at ZIB: current state of the art
講演概要：
混合整数計画(MIP: Mixed Integer Programming)ソルバの近年の性能向上は著しく，
様々な現実問題が混合整数計画問題に定式化され解かれるケースも増えつつある．
商用の混合整数計画ソルバの多くは，既にマルチ・スレッド化され並列化されて
いる．本講演では，ZIB(Zuse Institute Berlin)で開発されている並列混合整数
計画ソルバ群について紹介する．並列混合整数計画ソルバは，既存の混合整数計画
ソルバを並列化する共通のソフトウェア・フレームワーク上に構築されている．
そのフレームワークの概要と，北ドイツ最大のスーパーコンピュータHLRN IIによる
最新の数値実験結果（１ジョブの実行に最大7,168コアを利用）について報告する．


第11回 研究会

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

講演1
講演者：北原知就氏（東京工業大学）
講演題目：単体法によって生成される実行可能基底解の個数の上界について
講演概要：
単体法は線形計画問題に対する最初の解法で，実用上は非常に効率的であることが知られている。
しかし，一般的な線形計画問題に対する単体法の反復回数の評価はほとんど知られていない．
その大きな障害となっているのが，Klee-Mintyによって発表された単体法が指数回の反復回数を
必要とし得るという事実である．北原-水野(2010年)はマルコフ決定問題に対するYeの解析(2010年)を
応用し，単体法が生成する実行可能基底解の上界を示した。得られた上界は問題の制約式の個数、
変数の個数，およびすべての実行可能基底解の正の要素の最大値と最小値の比，の多項式で表される．
そして問題が非退化のとき，この上界は反復回数の上界となる。本講演では、上界を得るための解析に
ついて詳しく説明する。また，新たに開発した簡易版Klee-Minty問題を使い，良い上界が得られていることを示す．

講演2
講演者：後藤和茂氏（米 Microsoft Corporation）
講演題目：最適化における性能測定
講演概要：
本講演では構成を大きく２つに分ける。前半では講演者の経験をもとにアメリカの文化及び労働環境について
具体例を交えて紹介する。後半では講演者の専門である最適化に関して、特に最適化の評価をするための
性能測定（いわゆるベンチマーク）についての解説を行う。プログラムの作成においては単に正しい結果が
必要なだけではなく多くの場合同時に性能を必要とする場合が多いが、その性能を評価する手法に関しては
あまり知られていない。そこで本講演では性能を正確に測定する手法を紹介するとともに、対象となるシステム
から得られる特性から性能を予測することにより得られた性能の妥当性を検証する手法を紹介する。


第12回 研究会

日　時：2011年12月17日（土）14:00〜
会　場： 中央大学 後楽園キャンパス 6号館 4階 6410号室

講演1
講演者：高野祐一氏（東京工業大学）
講演題目：A Nonlinear Control Policy Using Kernel Method for Dynamic Asset Allocation
(動的資産配分のためのカーネル法を利用した非線形制御ポリシー)
講演概要：
本発表では, 非線形制御ポリシーを用いて多期間にわたる動的な資産配分を決定する最適化問題を
定式化し, 問題求解のための計算手法を提案する.
ここで, 制御ポリシーとは投資対象資産の過去の収益の関数である.
カーネル法を利用することで, 非線形関数の中から最適な制御ポリシーを選択する問題は
凸2次最適化問題として定式化される.
さらに, L1-ノルムを用いた正則化を利用することで問題を線形最適化問題に帰着する.
計算実験では, 投資対象資産の収益率のシナリオを1期間自己回帰モデルによって生成し,
先行研究の手法と比較して我々の提案する投資戦略は良好な運用成績を得られることを示す.

講演2
講演者：田中 勇真氏（名古屋大学）
講演題目：Lagrangian-based column generation for the node capacitated in-tree packing problem
(頂点容量付き有向全域木パッキング問題に対するラグランジュ緩和に基づく列生成法)
講演概要：
In this paper, we deal with the node capacitated in-tree packing problem. The input consists of
a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails.
The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing
number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers
under the constraint that the total consumption of the packed in-trees at each node does not exceed the
capacity of the node. This problem is known to be NP-hard.
Previously, we proposed a two-phase heuristic algorithm for this problem. The algorithm generates
promising candidate in-trees to be packed in the first phase and computes the packing number of each in-tree
in the second phase. In this paper, we improve the first phase algorithm by using Lagrangian relaxation
instead of LP (linear programming) relaxation.
We conducted computational experiments on graphs used in related papers and on randomly generated
instances. The results indicate that our new algorithm generates in-trees faster than our previous algorithm
and obtains better solutions than existing algorithms without generating many in-trees.


トップページへ戻る

SCOPE（「計算と最適化の新展開」研究部会）
主査 ： 藤澤克樹 （中央大学）
幹事 ： 後藤順哉 （中央大学）


Copyright, SCOPE All rights reserved, 2009.