[RESEARCH] Makoto Yamashita Home Page

[研究/RESEARCH] Makoto Yamashita Homepage

Mail Adress: Makoto.Yamashita at is dot titech dot ac dot jp
Last Update: 2012/02/03

ページの内容 / Contents
研究概要 / Research Overview
リサーチレポート / Research Report
論文 / Paper
学会発表 / Presentation
ソフトウェア / Software
学位論文 / Degree Paper
所属学会 / Society
受賞 / Prize
プレス / Press
略歴 / CV

研究概要 / Research Overview
キーワード / Keywords
数理計画 / Mathematical Programming
半正定値計画問題 / SemiDefinite Programming
量子化学 / Quantum Chemistry
並列計算 / Parallel Computing
内容 / Abstract
半正定値計画問題は、数理計画分野の核ともいえる線形計画問題を半正定値行列へと拡張した最適化問題である。行列の固有値を制約条件として含むことで、制御理論や組合せ最適化、金融工学など幅広く応用されている。また、Hilbert 空間が数学的基礎として構築されている量子論・量子化学とも親和性も高く、これらへの研究も活発である。
その一方で、これらの応用から発生する半正定値計画問題の規模は大規模化する傾向にあり、一台のコンピュータでは解くことが困難である。
そこで、超大規模な半正定値計画問題に対して、並列計算で高速に解く研究を中心に行なっている。
また、量子論に限らず、物理における様々な最適化問題にも数理計画手法が活用できないかを検討中である。
SemiDefinite Programming (SDP) is an optimizaton problem which extends Linear Programming, the core of Mathematical Programming field, to the space of symmetric matrices. Since SDP can cover eigenvalue constraints, SDP is applied to various field, including control theory, combinatorial optimization, financial engineering. Furthermore, SDP is better suited for quantum theory and quantum chemistry, since they are mathematically based on Hilbelt space.
However, SDP arising from these applications is becoming larger and larger, hence, one computer is not enough to solve the size of current SDPs.
Now, we are trying to solve extremely large-scale SDPs by parallel computing.
In addition, we are also investigating a way to apply mathematical programming methods to many optimization problem arising from physics, not just from quantum theory.

リサーチレポート / Research Report
“Correlative Sparsity Structures and Semidefinite Relaxations for Concave Cost Transportation Problems with Change of Variables,”
[PDF]
Mizutani Tomohiko, Makoto Yamashita
October, 2011
“A high-performance software package for semidefinite programs: SDPA 7,”
[PDF]
Makoto Yamashita, Katsuki Fujisawa, Kazuhide Nakata, Maho Nakata, Mituhiro Fukuda, Kazuhiro Kobayashi, and Kazushige Goto
Research Report B-460, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan,
January, 2010.

論文 / Paper
“Parallel solver for semidefinite programming problem having sparse Schur complement matrix,”
[PDF]
Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhide Nakata, Maho Nakata,
To appear in ACM Transactions on Mathematical Software
Research Report B-463, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan,
September, 2010.
“Enclosing Ellipsoids and Elliptic Cylinders of Semialgebraic Sets and Their Application to Error Bounds in Polynomial Optimization,”
[PDF]
Masakazu Kojima and Makoto Yamashita
To appear in Mathematical Programming
Research Report B-459, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan,
November, 2009.
“SFSDP: a Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems ,”
[PDF]
Sunyoung Kim, Masakazu Kojima, Hayato Waki and Makoto Yamashita
Research Report B-457, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan,
July, 2009.
To appear in Mathematical Programming.
“High Performance Solvers for Semidefinite Programs,”
[PDF]
Makoto Yamashita, Katsuki Fujisawa, Kazuhiro Kobayashi, Mituhiro Fukuda, Kazuhide Nakata and Maho Nakata,
Proceedings of the Korean Society for Industrial and Appplied Mathematcis,
Vol. 6, No. 2, pp. 55--58 (2011), 査読無
“Latest developments in the SDPA Family for solving large-scale SDPs,”
Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhiro Kobayashi, Kazuhide Nakta, Maho Nakata
in "Handbook on Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications" edited by Miguel F. Anjos and Jean B. Lasserre, Springer, NY, USA, Chapter 24, pp. 687--714 (2011), 査読有
“Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion,”
[PDF]
Sunyoung Kim, Masakazu Kojima, Martin Mevissen and Makoto Yamashita
Mathematical Programming B,
Vol. 129, No. 1, pp. 33--68 (2011), 査読有
“Constructing Polyhedral Homotopies on Grid-of-Clusters,”
Tomohiko Mizutani and Makoto Yamashita
Pacific Journal on Optimization,
Vol. 7, No. 2, pp 369--386 (2011), 査読有
“Efficient Parallel Software for Large-Scale Semidefinite Programs,”
Makoto Yamashita, Katsuki Fujisawa
Proceedings of 2010 IEEE International Symposium on Computer-Aided Control System Design,
0178, (2010), 査読有.
“Users Manual for SparseCoLO: Conversion Methods for SPARSE COnic-form Linear Optimization Problems,”
[PDF]
Katsuki Fujisawa, Sunyoung Kim, Masakazu Kojima, Yoshio Okamoto and Makoto Yamashita
Research Report B-453, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan,
Februrary, 2009.
“Variational calculation of second-order reduced density matrices by strong N-representability conditions and an accurate semidefinite programming solver,”
Maho Nakata, Bastiaan Braams, Katsuki Fujisawa, Mituhiro Fukuda, Jerome Percus, Makoto Yamashita and Zhengji Zhao,
Journal of Chemical Physics,
Vol. 128, pp. 164113 (2008), 査読有.
「最適化ソフトウェア SDPA」
[PDF]
中田和秀、藤澤克樹、福田光浩、山下真、中田真秀、小林和博、
応用数理, Vol. 18, No. 1, pp. 2-14 (2008), 査読有.
“Parallel Solver for SemiDefinite Programming，”
[PDF]
Makoto Yamashita，Katsuki Fujisawa and Kazuhide Nakata,
International Journal of Logistics and SCM systems，Vol. 2，No. 1，pp. 22-29 (2007), 査読有．
“SDPA Project: Solving Large-Scale Semidefinite Programs,”
[PDF]
Katsuki Fujisawa，Kazuhide Nakata，Makoto Yamashita and Mituhiro Fukuda,
Journal of the Operations Research Society of Japan，Vol. 50，No. 4，pp. 278-298 (2007), 査読有．
“Large-scale semidefinite programs in electronic structure calculation，”
[PDF]
Mituhiro Fukuda，Bastiaan Braams，Maho Nakata，Michael Overton，Jerome Percus，Makoto Yamashita and Zhengji Zhao,
Mathematical Programming B，Vol. 109，No. 2，pp. 553-580 (2007), 査読有．
“SemiDefinite Programming : Formulations and Primal-Dual Interior-Point Methods，”
Mituhiro Fukuda, Maho Nakata and Makoto Yamashita,
in Reduced-Density-Matrix Mechanics with Applications to Many-Electron Atoms and Moecules
edited by D. A. Mazziotti, John Wiley & Sons, Inc. pp. 103-118 (2007), 査読無.
「量子化学における超大規模半正定値計画問題と並列計算による高速求解」
[PDF]
山下真、
第18回RAMPシンポジウム論文集, pp. 191-207 (2006), 査読無（招待講演）.
“Solving Large Scale Optimization Problems via Grid and Cluster Computing，”
[PDF]
Katsuki Fujisawa，Masakazu Kojima，Akiko Takeda and Makoto Yamashita,
Journal of the Operation Research Society of Japan，Vol. 47，No. 4，pp. 265-274 (2006), 査読有．
“Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs,”
[PDF]
Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima and Kazuhide Nakata,
in Parallel Combinatorial Optimization edited by El-Talbi, Wiley-Interscience, pp. 211-238 (2006), 査読有.
“Simple Hamiltonians which exhibit drastic failures by variational determination，”
Maho Nakata，Bastiaan Braams，Mituhiro Fukuda， Jerome Percus，Makoto Yamashita and Zhengji Zhao,
Journal of Chemical Physics，Vol. 125，pp. 244109 (2006), 査読有.
“A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs，”
[PDF]
Kazuhide Nakata，Makoto Yamashita，Katsuki Fujisawa and Masakazu Kojima,
Parallel Computing，Vol. 32，No. 1，pp. 24-43 (2006), 査読有．
“High Performance Grid and Cluster Computing for Some Optimization Problems”,
[PDF]
Katsuki Fujisawa，Masakazu Kojima，Akiko Takeda and Makoto Yamashita,
Proceedings of SAINT 2004 Work Shops，(2004), 査読有．
“SDPARA: SemiDefinite Programming Algorithm PARAllel Version，”
[PDF]
Makoto Yamashita，Katsuki Fujisawa and Masakazu Kojima,
Parallel Computing，Vol. 29，No. 8，pp. 1053-1067 (2003), 査読有．
“Second Order Cone Programming Relaxation of a Positive Semidefinite Constraint，”
[PS.GZ]
Sunyoung Kim，Masakazu Kojima and Makoto Yamashita,
Optimization Methods and Software，Vol. 18，No. 5，pp. 535-541 (2003), 査読有．
“Implementaion and Evaluation of SDPA 6.0，”
[PDF]
Makoto Yamashita，Katsuki Fujisawa and Masakazu Kojima,
Optimization Methods and Software, Vol. 18，No. 4，pp. 491-505 (2003), 査読有．

学会発表 / Presentation
If you want presentation material, please send me e-mail.

KSIAM Annual Meeting 2011
[PPT]
KSIAM Annual Meeting 2011
Seogwipo KAL Hotel, (Seogwipo, South Korea), November 25th, 2011.
INFORMS Annual Meeting 2011
[PPT]
INFORMS Annual Meeting 2011
Charlotte Conference Center, (Charlotte, USA), November 15th, 2011.
SIAM Opt 2011
[PPT]
Siam Conference on Optimization 2011
Darmstadtium Conference Center, (Darmstadt, Germany), May 18th, 2011.
SDP@NCKU
[PDF]
Talk at National Center for Theoretical Sciences (South)
National Cheng Kung University (NCKU), (Tainan, Taiwan), April 16th, 2011.
SNL@NCKU
[PDF]
Talk at National Center for Theoretical Sciences (South)
National Cheng Kung University (NCKU), (Tainan, Taiwan), April 16th, 2011.
SDP@ZIB
[PPT]
Parallel Computing and SDP Workshop
Zuse-Institut Berlin (ZIB), (Berlin, Japan), December 1st, 2010.
MSC 2010
[PPT]
2010 IEEE Multi-Conference on Systems and Control
Pacifico Yokohama, (Yokohama, Japan), September 8th, 2010.
Erice 2010
[PPT]
Nonlinear Optimization, Variational Inequalities and Equilibrium Problems
"E. Majorana" Centre for Scientific Culture (Erice, Italy), July 5th, 2010.
ISMP 2009
[PPT]
The International Symposium on Mathematical Programming 2009
Chicago Marriott Downtown Magnificent Mile (Chicago, USA), August 2009.
Informs Annual Meeting 2008
[PPT]
Informs Annual Meeting
Marriott Wardman Park Hotel (Washington DC, USA), October 2008.
Informs Annual Meeting 2007
Informs Annual Meeting
Washington Convention Center (Seattle, USA), November 2007.
RAMP 2006
[PPT] in Japanese
第20回 RAMP シンポジウム
京都大学 (京都, 日本), October 2006.
ISMP 2006
The International Symposium on Mathematical Programming 2006
The Federal University of Rio de Janeiro (Rio de Janeiro, Brazil), July 2006.
SIAM-PP06
SIAM Conference on Parallel Processing for Scientific Computing 2006
Sir Francis Drake Hotel (San Francisco, USA), Feburary 2006.
Informs Annual Meeting 2005
Informs Annual Meeting
Hilton San Francisco and Renaissance Parc 55 San Francisco (San Fransisco, USA), November 2005.
ICCOPT I
International Conference on Continuous Optimization (ICCOPT)
Rensselaer Polytechnic Institute (New York, USA), August 2004.
CORS/INFORMS
CORS/Informs Joint Meeting
Banff International Centre (Banff, Canada), May 2004.
SAOR @ Tsukuba 2004
筑波大学 (茨城, 日本), June 2004.
SIAM-PP04
SIAM Conference on Parallel Processing for Scientific Computing 04
Hyatt at Fisherman's Wharf (SanFransisco, USA), February 2004.
ISMP 2003
The International Symposium on Mathematical Programming 2003
Technical University of Denmark (Copenhagen, Denmark), August 2003.
SAOR @ Tsukuba 2003
筑波大学 (茨城, 日本), June 2003.
NAS 2003
Numerical Analysis Symposium 2003 小湧園 (神奈川, 日本), May 2003.
OR 2003
Operations Research Society of JAPAN meeting
Keio University (Kanagawa, Japan), March 2003.
SC 2002
Super Computing 2002
I participates as an exhibition side.
Baltimore Convention Center (Baltimore, US), November 2002.
JSOM 2002
The Second Japanese-Sino Optimization Meeting (JSOM 2002),
Riega Royal Hotel (Kyoto, Japapn), September 2002.

ソフトウェア / Software
SDPA
(link to SDPA Home page)
SemiDefinite Programming Algorithm.
A computer software to solve SemiDefinite Programming.
It is written in C++ language and based on Mehrotra Type Primal-Dual Interior-Point Methods.
The latest version solves successfully various SDPs with the advantage of ATLAS and LAPACK.
SDPARA
SDPARA ( SDPARA can be found at SDPA Home Page )
SemiDefinite Programming Algorithm paRAllel version.
A parallel implementation of SDPA with MPI and ScaLAPACK.
The parallel processing applied to the evaluation of the Schur complement matrix and its Cholesky factorization enables us to solve the excessively large SDPs.

学位論文 / Degree Paper
Doctor of Science, March 2004
at Tokyo Institute of Technology
Doctor Thesis : Parallel Implemetation of Primal-Dual Interior-Point Methods for SemiDefinite Programming
Advisor : Prof Masakazu Kojima
[PDF]
Master of Science, March 2001
at Tokyo Institute of Technology
Master Thesis : Simulation of evolution in botanical system by Tierra-like method and its analysis (written in Japanese)
Advisor : Prof Masakazu Kojima
修士論文のプログラムへのリンク

所属学会 / Society
SIAM (Society for Industrial and Applied Mathematics) / 米国応用数理学会

MPS (Mathematical Programming Society) / 数理計画学会

INFORMS (Institute for Operations Research and the Management Sciences) / 米国オペレーションズリサーチ学会

日本オペレーションズリサーチ学会 / Japan Operations Research Society

日本経営工学会 / Japan Industrial Management Association

受賞 / Prize
Funai Prize for sience promotion
(with Masakazu Kojima, Susumu Shindoh, Kazuhide Nakata, Shinji Hara, Katsuki Fujisawa, Shinji Mizuno, Akiko Yoshise), 2003
船井情報科学振興賞
小島政和、進藤晋、中田和秀、原辰次、藤沢克樹、水野眞治、吉瀬章子と共同受賞、2003
Tejima Prize for Doctoral Thesis, 2005
手島記念研究賞 [博士論文賞]

プレスリリース / Press Release
富士通のプレスリリースに、量子化学の構造計算をスパコン(T2K,富士通製)上の SDPARA で解いた内容が掲載されました。(2010/05/28)
詳しくは http://pr.fujitsu.com/jp/news/2010/05/28.html をご覧ください
Fujitsu issues a press release: On T2K supercomputer SDPARA solves SDPs arising from quantum chemistry.
For details, see http://www.fujitsu.com/global/news/pr/archives/month/2010/20100528-01.html
or http://www.asahi.com/english/TKY201005280221.html

略歴 / CV
2008.04--present
Assistant Professor
Department of Mathematical and Computing Sciences
Graduate school of information science and engineering
Tokyo Institute of Technology
東京工業大学　大学院情報理工学研究科
数理・計算科学専攻　助教
2004.04--2008.03
Assistant Professor
Department of Information Systems Creation
Faculty of Engineering
Kanagawa University
神奈川大学　工学部　情報システム創成学科　特別助教
2004.03
Doctor of Science at Tokyo Institute of Technology
博士(理学) 東京工業大学
2001.03
Master of Science at Tokyo Institute of Technology
修士(理学) 東京工業大学