京都大学時計台百周年記念ホール
English
RAMPシンポジウムについて
プログラムと予稿（10月19日更新）
参加費（10月2日更新）
アクセス（9月27日更新）
お問い合わせ
リンク
For Speakers
セッション４: 錐最適化における理論と応用 (Theory and Applications of Conic Optimization)
半正定値計画問題（SDP）は「2000年の線形計画問題（LP）」とも呼ばれ，LPにおける非負制約を，対称行列の 半正定値制約に置き換えた問題である．制御理論，組合せ理論などに多くの応用例がある．非負制約と半正定値 制約は全く異質な制約に見受けられるが，ともに閉凸錐を与えるという共通点をもつ．1990年代に内点法の解法 としての有効性が示されて以来，SDPはLPを包括する新しい最適化問題として定着しつつある．近年はさらに閉 凸錐上の最適化問題（錐計画問題）に対象が拡張され，活発な研究が行われている．本セッションでは同分野で 活躍されている4名の研究者をお迎えし，理論と応用に関する最新の成果をお話し頂く．
講演
- Etienne de Klerk (Tilburg University)
The complexity of optimization over a simplex, hypercube or sphere
概要 | プロフィール -
林 俊介 （京都大学）
二次錐制約をもつ半無限計画問題に対する切除平面アプローチ
A cutting plane approach for semi-infinite programming problems with second-order cone constraints
概要 | プロフィール - Yu Xia (統計数理研究所)
The Maxdet problem - Algorithm and applications in machine learning
概要 | プロフィール - 山下 真 （神奈川大学）
量子化学における超大規模半正定値計画問題と並列計算による高速求解
SemiDefinite Programming arising from Quantum Chemistry and Parallel Solver
概要 | プロフィール
概要
タイトル： The complexity of optimization over a simplex
概要：
We consider the problem of minimizing a continuous function over a simplex. This relatively simple optimization problem has several applications. If the function is quadratic, the applications already include portfolio optimization, population dynamics, genetics, finding maximum stable sets in graphs, and lower bounding the crossing number of certain classes of graphs. For more general functions, the applications include training neural networks and minimizing the expected shortfall of a portfolio.
We will first review complexity results for minimizing polynomials over the standard simplex. In addition, we show that there exists a polynomial time approximation scheme (PTAS) for minimizing some classes of functions (including Lipschitz continuous functions) over the standard simplex.
タイトル：二次錐制約をもつ半無限計画問題に対する切除平面アプローチ
概要：
半無限計画問題とは，有限次元の決定変数と無限個の制約式で特徴付けられる最適化問題であり，幅広い分野に 応用が可能なことから，これまで盛んに研究がなされてきた．しかし，既存の研究の殆どは等式制約および不等 式制約のみで表されるような問題を対象としており，二次錐制約を含むような半無限計画問題に対する研究はこ れまで殆どなされていなかった．そこで，本研究では，Lai and Wuの提案した切除平面アプローチを二次錐制約 を含む半無限計画問題に拡張した手法を提案する．また，アルゴリズムにおける部分問題とその双対問題の解が 満たすべき二次錐相補性条件に対して，Jordan代数に基づいた解析を行うことにより，提案手法の収束性を示す． さらに，アルゴリズムの性能を調べるために行ったいくつかの数値実験の結果も合わせて報告する．
タイトル：The Maxdet problem - Algorithm and applications in machine learning
概要：
We give some applications of the Maxdet problem in machine learning. The Maxdet problem is an extension of the semidefinite program and the weighted analytic center problem. It concerns the maximization of a sum of linear function and some weighted logarithmic determinants over the intersection of an affine space and the cone of positive semidefinite matrices. This problem can be approximated by interior-point methods with polynomial complexity. This is a joint work with Takashi Tsuchiya.
タイトル：量子化学における超大規模半正定値計画問題と並列計算による高速求解
概要：
原子および分子の電子構造を計算することは、量子化学の基本的な対象として位置している．分子の基底状 態における電子構造を知るには、電子間の相関を表す行列が求まれば十分である．この行列は物理的制約である N-representability条件を満たさなければならないが、半正定値緩和を施すと半正定値計画問題に帰着できる． これを解くことで，分子の電子状態、エネルギーを変分的に求められる。この事実は 1960 年代には既に知られ ていたが，1990年代後半の主双対内点法の研究により数値的に計算することが可能となった．さらに，2000年以 降には, より精密な化学条件を取り込んだ半正定値計画問題へと発展している．
しかしながら，帰着された半正定値計画問題の規模は非常に大きく，1台の計算機では計算不可能な規模になる 傾向にある．そこで、半正定値計画問題に対するソフトウェアであるSDPA を並列化し，PC クラスタ上の計算パ ワーを用いてこのような超大規模半正定値計画問題に取り組む研究を行っている．
本発表では，前半を電子構造が半正定値計画問題に帰着される過程のダイジェストとし，後半を SDPA の並 列化，および PC クラスタ上の数値結果の紹介とする．