Organization
School of Engineering Professor
Title
Professor
External link
NAKATA KAZUHIDE
News & Topics
-
2019/07/02
Languages： Japanese
ソネット・メディア・ネットワークス株式会社（以下、SMN）の研究開発組織「a.i lab.」（アイラボ）は、東京工業大学工学院 経営工学系の中田和秀准教授の研究室との共同研究により、ユーザーへの介入効果を最適化するUplift Modeling手法を開発しました。
Degree
-
Doctor of Science ( Tokyo Institute of Technology )
Research Interests
-
numerical analysis
-
経営工学
-
optimization
-
machine learning
-
operations research
-
computer science
Education
-
Tokyo Institute of Technology Information Science and Engineering Mathematical and Computing Sciences
1996 - 1998
Country： Japan
-
Tokyo Institute of Technology School of Science Dept. of Information Science
1992 - 1996
Country： Japan
-
Tokyo Institute of Technology
2002
Research History
-
Institute of Science Tokyo Department of Industrial Engineering and Economics, School of Engineering, Professor
2024.10
-
Tokyo Institute of Technology School of Engineering, Department of Industrial Engineering and Economics Professer
2021 - 2024.9
-
Tokyo Institute of Technology School of Engineering, Department of Industrial Engineering and Economics Associate Professor
2016 - 2021
-
Tokyo Institute of Technology Graduate School of Decision Science and Technology Associate Professor
2008 - 2016
-
Tokyo Institute of Technology Graduate School of Decision Science and Technology Assistant Professor
2002 - 2008
-
The University of Tokyo Department of Applied Physics Assistant Professor
1999 - 2002
Professional Memberships
-
The Japanese Society for Artificial Intelligence
-
日本ファイナンス学会
-
The Operations Research Society of Japan
-
Mathematical Programming Society
-
The Japan Society for Industrial and Applied Mathmatics
Papers
-
Decision Diagram Optimization for Allocating Patients to Medical Diagnosis
Aru Suzuki, Ken Kobayashi, Kazuhide Nakata, Yuta Kurume, Naoyuki Sawasaki, Yuki Sasamoto
Lecture Notes in Operations Research 406 - 411 2025.8
-
Estimating Sales Transitions between Competing Products via Optimal Transport Reviewed
Shoki Yamao, Ryota Ueda, Shoichiro Koguchi, Michi Nakase, Aru Suzuki, Kohdai Toyoda, Ken Kobayashi, Kazuhide Nakata
PLOS ONE 20 ( 6 ) e0325173 2025.6
-
Interior-Point Vanishing Problem in Semidefinite Relaxations for Neural Network Verification.
Ryota Ueda, Takami Sato, Ken Kobayashi, Kazuhide Nakata
CoRR abs/2506.10269 2025.6
-
Online joint optimization of sponsored search ad bid amounts and product prices on e-commerce Reviewed
Shoichiro Koguchi, Kazuhide Nakata, Ken Kobayashi, Kosuke Kawakami, Takenori Nakajima, Kevin Kratzer
Proccedings of 14th International Conference on Operations Research and Enterprise Systems 2025.2
-
Zero-shot Demand Forecasting for Products with Limited Sales Periods. Reviewed
Shota Nagai, Ryota Inaba, Rei Oishi, Shuhei Aikawa, Yusuke Mibuchi, Hinata Moriyama, Ken Kobayashi, Kazuhide Nakata
IEEE Big Data 5154 - 5160 2024.12
-
Balancing Immediate Revenue and Future Off-Policy Evaluation in Coupon Allocation Reviewed
Naoki Nishimura, Ken Kobayashi, Kazuhide Nakata
Proceedings of The 21th Pacific Rim International Conference on Artificial Intelligence 2024.11
-
Distribution-aligned Sequential Counterfactual Explanation with Local Outlier Factor Reviewed
Shoki Yamao, Ken Kobayashi, Kentaro Kanamori, Takuya Takagi, Yuichi Ike, Kazuhide Nakata
Proceedings of The 21th Pacific Rim International Conference on Artificial Intelligence 2024.11
-
Trend Analysis with Interpretability and Cold-Start Problems for Recommender Systems Reviewed
Tomofumi Hara, Yuki Sumiya, Kazuhide Nakata
The Review of Socionetwork Strategies 18 2024.8
-
GENERALIZATIONS OF DOUBLY NONNEGATIVE CONES AND THEIR COMPARISON Reviewed
Mitsuhiro Nishijima, Kazuhide Nakata
Journal of the Operations Research Society of Japan 67 ( 3 ) 84 - 109 2024.7
-
Keyword-Level Bayesian Online Bid Optimization for Sponsored Search Advertising Reviewed
Kaito Majima, Kosuke Kawakami, Kota Ishizuka, Kazuhide Nakata
Operations Research Forum 5 ( 2 ) 2024.5
-
Towards Assessing and Benchmarking Risk-Return Tradeoff of Off-Policy Evaluation Reviewed
Haruka Kiyohara, Ren Kishimoto, Kosuke Kawakami, Ken Kobayashi, Kazuhide Nakata, Yuta Saito
2024.5
-
Zero-Inflated Poisson Tensor Factorization for Sparse Purchase Data in E-Commerce Markets Reviewed
Keisuke Mizutani, Ayaka Ueta, Ryota Ueda, Ray Oishi, Tomofumi Hara, Yuki Hoshino, Ken Kobayashi, Kazuhide Nakata
The 11th International Conference on Industrial Engineering and Applications 2024.1
-
SCOPE-RL: A Python Library for Offline Reinforcement Learning and Off-Policy Evaluation
Haruka Kiyohara, Ren Kishimoto, Kosuke Kawakami, Ken Kobayashi, Kazuhide Nakata, Yuta Saito
2023.12
-
Temporal Positive Collective Matrix Factorization for Interpretable Trend Analysis in Recommender Systems Reviewed
Tomofumi Hara, Yuki Sumiya, Kazuhide Nakata
Proceedings of 2023 IEEE International Conference on Data Mining 2023.12
-
Online Flipped Conference Based Data Science Education Program and Its Educational Effectiveness in Multi-University Collaboration Reviewed
Masayuki Goto, Manabu Kobayashi, Takeshi Moriguchi, Yoichi Seki, Hideo Suzuki, Takashi Namatame, Kazuhide Nakata, Aya Ishigaki, Masao Ueda, Kimitoshi Sato, Kenta Mikawa, Haruka Yamashita, Tomoaki Tabata, Tianxiang Yang, Ayako Yamagiwa, Yutaka Tajiri
Proceedings of the 2023 Asian Conference of Management Science and Applications 2023.12
-
Decision Tree Clustering for Time Series Data: An Approach for Enhanced Interpretability and Efficiency2 Reviewed
Masaki Higashi, Minje Sung, Daiki Yamane, Kenta Inamuro, S. Nagai, Ken Kobayashi, Kazuhide Nakata
2023.11
-
Cardinality-constrained distributionally robust portfolio optimization Reviewed
Ken Kobayashi, Yuichi Takano, Kazuhide Nakata
European Journal of Operational Research 309 ( 3 ) 1173 - 1182 2023.9
-
Approximation hierarchies for copositive cone over symmetric cone and their comparison Reviewed
Mitsuhiro Nishijima, Kazuhide Nakata
Journal of Global Optimization 88 ( 4 ) 831 - 870 2023.8
-
An IPW-based Unbiased Ranking Metric in Two-sided Mark Reviewed
Keisho Oh, Naoki Nishimura, Minje Sung, Ken Kobayashi, Kazuhide Nakata
KDD 203 workshop "Causal Inference and Machine Learning in Practice: Use cases for Product, Brand, Policy, and beyond" abs/2307.10204 2023.8
-
Inverse-optimization-based uncertainty set for robust linear optimization Reviewed
Ayaka Ueta, Mirai Tanaka, Ken Kobayashi, Kazuhide Nakata
International Conference on Operations Research 2023.8
-
Patent Classification for Business Strategy with BERT Reviewed
Masaki Higashi, Yoshimasa Utsumi, Kazuhide Nakata
Proceedings of 6th International Conference on Intelligent Computing & Optimization 2023.4
-
IPC prediction of patent documents using neural network with attention for hierarchical structure Reviewed
Yuki Hoshino, Yoshimasa Utsumi, Yoshiro Matsuda, Yoshitoshi Tanaka, Kazuhide Nakata
PLOS ONE 18 ( 3 ) e0282361 - e0282361 2023.3
-
育児Q&Aサイトにおける質問の時系列を考慮した複数の子供の月齢予測 Reviewed
東将己, 山根大輝, 原朋史, 梅津大雅, 馬嶋海斗, 松井諒生, 中田和秀
オペレーションズ・リサーチ 68 ( 2 ) 75 - 84 2023.2
-
The realized local volatility surface Reviewed
Yuming Ma, Shintaro Sengoku, Kazuhide Nakata
Journal of Investment Strategies 12 1 - 21 2023
-
Predicting response probability by embedding questions in online question recommendation Reviewed
Yuki Hoshino, Makoto Tasaki, Keisuke Mizutani, Motoya Azami, Kota Ishizuka, Kazuhide Nakata
Proceedings of The 21st IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology(WI-IAT'22) 2022.11
-
Noise–Robust Sampling for Collaborative Metric Learning Reviewed
Ryo Matsui, Suguru Yaginuma, Taketo Naito, Kazuhide Nakata
The Review of Socionetwork Strategies 2022.10
-
A deep bi-directional long-short term memory neural network-based methodology to enhance short-term electricity load forecasting for residential applications Reviewed
Sara Atef, Kazuhide Nakata, Amr B. Eltawil
Computers & Industrial Engineering 170 108364 - 108364 2022.8
-
Michiya Kuramata, Ryota Katsuki, Kazuhide Nakata
PLOS ONE 17 ( 4 ) e0266846 - e0266846 2022.4
-
Hierarchical Bayesian recommendation model for inter-company collaboration using cross-industry questionnaire Reviewed
Yuki Hoshino, Ryo Matsui, Kota Ishizuka, Koya Ishikawa, Taiga Umetsu, Kazuhide Nakata
Proceedings of 2022 IEEE 9th International Conference on Industrial Engineering and Applications 2022
-
井上 光太郎, 中田 和秀
企業金融 74(2) 16 - 26 2022
-
Confident Collaborative Metric Learning Reviewed
Ryo Matsui, Taketo Naito, Suguru Yaginuma, Kazuhide Nakata
Proceedings of the IEEE International Workshop on Data Mining for Service 2021.12
-
Constrained Generalized Additive 2 Model With Consideration of High-Order Interactions Reviewed
Akihisa Watanabe, Michiya Kuramata, Kaito Majima, Haruka Kiyohara, Kensho Kondo, Kazuhide Nakata
Proceedings of the International Conference on Electrical Computer and Energy Technologies 2021.12
-
Bilevel cutting-plane algorithm for cardinality-constrained mean-CVaR portfolio optimization Reviewed
Ken Kobayashi, Yuichi Takano, Kazuhide Nakata
Journal of Global Optimization 2021.7
-
Seasonal Inventory Management Model for Raw Materials in Steel Industry Reviewed
Kosuke Kawakami, Hirokazu Kobayashi, Kazuhide Nakata
INFORMS Journal on Applied Analytics 2021.7
-
A block coordinate descent method for sensor network localization Reviewed
Mitsuhiro Nishijima, Kazuhide Nakata
Optimization Letters 2021.6
-
Generating Search Text Ads from Keywords and Landing Pages via BERT2BERT Reviewed
Kota Ishizuka, Kai Kurogi, Kosuke Kawakami, Daishi Iwai, Kazuhide Nakata
Preceedings of The 35th Annual Conference of the Japanese Society for Artificial Intelligence 2021.6
-
Michiya Kuramata, Ryota Katsuki, Kazuhide Nakata
2021 IEEE 8th International Conference on Industrial Engineering and Applications (ICIEA) 556 ( 565 ) 2021.4
-
Text Mining for Factor Modeling of Japanese Stock Performance Reviewed
K. Ishizuka, K. Nakata
2021 IEEE 8th International Conference on Industrial Engineering and Applications (ICIEA) 538 - 542 2021.4
-
タクシーの流し営業における強化学習を用いた顧客獲得ナビ Reviewed
岩田真奈, 桑原惇, 石塚湖太, 倉又迪哉, 清原明加, 中田和秀
オペレーションズ・リサーチ 66 ( 2 ) 75 - 83 2021
-
Online Trading Models in the Forex Market Considering Transaction Costs
Koya Ishikawa, Kazuhide Nakata
arXiv preprint ( 2106.03035 ) 2021
-
A hybrid Variable Neighbourhood Search and Dynamic Programming approach for the Nurse Rostering Problem Reviewed
Mohammed Abdelgalil, Amr Eltawil, Zakaria Yahia, Kazuhide Nakata
Journal of Industrial and Management Optimization 17 ( 4 ) 2051 - 2072 2021
-
反実仮想機械学習を用いたタクシーの乗車数予測と配置最適化 Reviewed
松井諒生, 住谷有規, 笹尾知広, 中田和秀
オペレーションズ・リサーチ 66 ( 2 ) 66 - 74 2021
-
Cost-Effective and Stable Policy Optimization Algorithm for Uplift Modeling with Multiple Treatments Reviewed
Yuta Saito, Hayato Sakata, Kazuhide Nakata
Proceedings of the 2020 SIAM International Conference on Data Mining 406 - 414 2020.5
-
Unbiased Recommender Learning from Missing-Not-At-Random Implicit Feedback Reviewed
Yuta Saito, Suguru Yaginuma, Yuta Nishino, Hayato Sakata, Kazuhide Nakata
Proceedings of The 13th ACM International WSDM Conference (WSDM2020) 501 - 509 2020.2
-
自然言語処理的アプローチによるテレビ視聴データの解析 Reviewed
土橋諒太, 陳晨, 三浦真和, 中田和秀
オペレーションズ・リサーチ 65 ( 2 ) 85 - 92 2020.2
-
Technical Progress Analysis Using a Dynamic Topic Model for Technical Terms to Revise Patent Classification Codes
Mana Iwata, Yoshiro Matsuda, Yoshimasa Utsumi, Yoshitoshi Tanaka, Kazuhide Nakata
arXiv preprint ( 2012.10120 ) 2020
-
A hybrid evolutionary-simplex search method to solve nonlinear constrained optimization problems, Soft Computing, Reviewed
Alyaa Abdelhalima, Kazuhide Nakata, Mahmoud El-Alem, Amr Eltawil
Soft Computing 23 12001 - 12015 2019.11
-
Doubly Robust Prediction and Evaluation Methods Improve Uplift Modeling for Observational Data Reviewed
Yuta Saito, Hayato Sakata, Kazuhide Nakata
Proceedings of SIAM International Conference on Data Mining 70 431 - 446 2019.5
-
Ryuta Tamura, Ken Kobayashi, Yuichi Takano, Ryuhei Miyashiro, Kazuhide Nakata, Tomomi Matsui
Journal of Global Optimization 70 ( 2 ) 431 - 446 2019.3
-
部分再帰型ニューラルネットワークを用いたヘアサロンチェーンにおける顧客の離脱予測 Reviewed
福永峻, 田村悠, 根市和旗, 市瀬将也, 小槙瑠理子, 花村鴻太郎, 戸田開人, 片山翔太, 中田和秀
オペレーションズ・リサーチ 64 ( 2 ) 87 - 95 2019.2
-
Ensemble LDAを用いた既存および新規顧客へのスタイリスト推薦 Reviewed
高正妍, 田澤浩二, チョウイ, 大原靖之, 山野上勇人, 桑原惇, 片山翔太, 中田和秀
オペレーションズ・リサーチ 64 95 - 101 2019.2
-
Mahmoud Heshmat, Kazuhide Nakata, Amr Eltawil
Computers & Industrial Engineering 124 347 - 358 2018.7
-
Guided Particle Swarm Optimization Method to Solve General Nonlinear Optimization Problems Reviewed
Alyaa Abdelhalima, Kazuhide Nakata, Mahmoud El-Alem, Amr Eltawil
Engineering Optimization 50 ( 4 ) 568 - 583 2018.7
-
多重共線性を考慮した回帰式の変数選択問題の定式化 Invited
田村隆太, 小林健, 高野祐一, 宮代隆平, 中田和秀, 松井知己
オペレーションズ・リサーチ 63 ( 3 ) 128 - 133 2018.3
-
ファッションECサイトにおけるアンケートを用いたブランド推薦システム Reviewed
田村悠, 吉住宗朔, 福永峻, 三宅聡一郎, 片山翔太, 中田和秀
オペレーションズ・リサーチ 63 ( 2 ) 91 - 98 2018.2
-
Best subset selection for eliminating multicollinearity Reviewed
Ryuta Tamura, Ken Kobayashi, Yuichi Takano, Ryuhei Miyashiro, Kazuhide Nakata, Tomomi Matsui
Journal of the Operations Research Society of Japan 60 ( 3 ) 321 - 336 2017.7
-
待ち行列シミュレータを用いた区役所における職員配置最適化 Reviewed
田澤浩二, 吉住宗朔, 平野豪一, 片山翔太, 中田和秀
オペレーションズ・リサーチ 62 75 - 82 2017.2
-
Apparel Item Recommendation using Graph Regularized Nonnegative Tensor Factorization
Koji Tazawa, Kazuki Neichi, Yasuyuki Ohara, Kazuki Chikuma, Shota Katayama, Kazuhide Nakata
Department of Industrial Engineering and Economics Working Paper, Tokyo Institute of Technology 2017 ( 5 ) 2017
-
Modified Formulation for the Appointment Scheduling Problem of Outpatient Chemotherapy Departments Reviewed
M. Heshmat, K. Nakata, A. Eltawil
2017 4TH INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND APPLICATIONS (ICIEA) 192 - 196 2017
-
半正定値計画緩和に基づく擬似スティッチを用いたTPLのためのレイアウト分割手法 Reviewed
半田昌平, 高橋篤司, 中田和秀, 松井知己
第29回 回路とシステムワークショップ 論文集 pp. 214 - 219 2016.5
-
山根智之, 菅原光太郎, 西村直樹, 小林健, 吉田佑輔, 高野祐一, 中田和秀
オペレーションズ・リサーチ：経営の科学 61 ( 2 ) 65 - 70 2016.2
-
廣瀬貴也, 鈴木翔太, 佐藤悠介, 鈴木寛人, 中田和秀
京都大学数理解析研究所講究録 1981 98 - 116 2016
-
Fast implementation for semidefinite programs with positive matrix completion Reviewed
Makoto Yamashita, Kazuhide Nakata
OPTIMIZATION METHODS & SOFTWARE 30 ( 5 ) 1030 - 1049 2015.10
-
Quay crane allocation problem with the internal truck capacity constraint in container terminal
Ahmed Karam, Amr Eltawil, Nermine Harraz, Tomohiko Mizutani, Kazuhide Nakata
RIMS Kokyuroku 1931 94 - 106 2015
-
Successive Projection Method for Well-Conditioned Matrix Approximation Problems Reviewed
Mirai Tanaka, Kazuhide Nakata
IEEE SIGNAL PROCESSING LETTERS 21 ( 4 ) 418 - 422 2014.4
-
Positive definite matrix approximation with condition number constraint Reviewed
Mirai Tanaka, Kazuhide Nakata
OPTIMIZATION LETTERS 8 ( 3 ) 939 - 947 2014.3
-
ファジィクラスタワイズ回帰を用いた共同購入型クーポンサイトの閲覧傾向分析 Reviewed
高野祐一, 田中未来, 鮏川矩義, 竹山光将, 神里栄, 千代竜佑, 小林健, 田中研太郎, 中田和秀
日本オペレーションズ・リサーチ 59 81 - 87 2013
-
Numerical reduction method for doubly nonnegative optimization problems Reviewed
Mirai TANAKA, Kazuhide Nakata, hayato waki
Journal of Math-for-Industry 5 41 - 50 2013
-
Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhide Nakata, Maho Nakata
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 39 ( 1 ) 6 2012.11
-
Mirai Tanaka, Kazuhide Nakata, Hayato Waki
PACIFIC JOURNAL OF OPTIMIZATION 8 ( 4 ) 699 - 724 2012.10
-
Latest developments in the SDPA family for solving large-scale SDPs Reviewed
Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhiro Kobayashi, Kazuhide Nakata, Maho Nakata
International Series in Operations Research and Management Science 166 687 - 713 2012
-
Quadratic and Convex Minimax Classification problems Reviewed
Tomonari Kitahara, Shinji Mizuno, Kazuhide Nakata
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN 51 ( 2 ) 191 - 201 2008.6
-
Optimization Software SDPA Reviewed
Nakata Kazuhide, Fujisawa Katsuki, Fukuda Mituhiro, Yamashita Makoto, Nakata Maho, Kobayashi Kazuhiro
Bulletin of the Japan Society for Industrial and Applied Mathematics 18 ( 1 ) 2 - 14 2008
-
SDPA project: solving large-scale semidefinite programs Reviewed
Katsuki Fujisawa, Kazuhide Nakata, Makoto Yamashita, Mituhiro Fukuda
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN 50 ( 4 ) 278 - 298 2007.12
-
An extension of a minimax approach to multiple classification Reviewed
Tomonari Kitahara, Shinji Mizuno, Kazuhide Nakata
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN 50 ( 2 ) 123 - 136 2007.6
-
A conversion of an SDP having free variables into the standard form SDP Reviewed
Kazuhiro Kobayashi, Kazuhide Nakata, Masakazu Kojima
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 36 ( 2-3 ) 289 - 307 2007.4
-
Parallel Solver for SemiDefinite Programming Reviewed
Makoto Yamashita, Katsuki Fujisawa, Kazuhide Nakata
International Journal of Logistics and SCM systems 2 ( 1 ) 22 - 29 2007
-
Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs Reviewed
Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuhide Nakata
Parallel Combinatorial Optimization 211 - 238 2006.4
-
Preprocessing sparse semidefinite programs via matrix completion Reviewed
K Fujisawa, M Fukuda, K Nakata
OPTIMIZATION METHODS & SOFTWARE 21 ( 1 ) 17 - 39 2006.2
-
A parallel primal-dual interior-point method for semidefinite programs using positive definite matrix completion Reviewed
K Nakata, M Yamashita, K Fujisawa, M Kojima
PARALLEL COMPUTING 32 ( 1 ) 24 - 43 2006.1
-
ROBUST TRACKING ERROR OPTIMIZATION PROBLEMS BY SECOND-ORDER CONE PROGRAMMING Reviewed
Inaba Hiroki, Mizuno Shinji, Nakata Kazuhide
Transactions of the Operations Research Society of Japan 48 12 - 25 2005
-
Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results Reviewed
K Nakata, K Fujisawa, M Fukuda, M Kojima, K Murota
MATHEMATICAL PROGRAMMING 95 ( 2 ) 303 - 327 2003.2
-
Incomplete orthogonalization preconditioners for solving large and dense linear systems which arise from Semidefinite Programming Reviewed
SL Zhang, K Nakata, M Kojima
APPLIED NUMERICAL MATHEMATICS 41 ( 1 ) 235 - 245 2002.4
-
大規模な半正定値計画問題に対する数値解法 Reviewed
中田和秀
2002.4
-
Generalized conjugate residual method for solving large and dense linear systems in semidefinite programming Reviewed
Shao-Liang Zhang, Kazuhide Nakata
Proceedings of Fifth China-Japan Seminar on Numerical Mathematics 234 - 241 2002
-
Maho Nakata, Hiroshi Nakatsuji, Masahiro Ehara, Mituhiro Fukuda, Kazuhide Nakata, Katsuki Fujisawa
The Journal of Chemical Physics 114 ( 19 ) 8282 - 8292 2001
-
Numerical Evaluation of the SDPA (SemiDefinite Programming Algorithm) Reviewed
Katsuki Fujisawa Mituhiro Fukuda, Masakazu Kojima, Kazuhide Nakata
High Performance Optimization Techniques 267 - 301 2000
-
Solving Sparse Semidefinite Programs by Matrix Completion (part II)
Kazuhide Nakata, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota
1174 130 - 137 2000
-
Matrix Completion and Semidefinite Programming
Kazuhide Nakata, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota
135 223 - 237 2000
-
Solving Sparse Semidefinite Programs by Matrix Completion (part I)
Mituhiro Fukuda, Kazuhide Nakata, Katsuki Fujisawa, Masakazu Kojima, Kazuo Murota
1174 122 - 129 2000
-
Exploiting sparsity in semidefinite programming via matrix completion I: General framework Reviewed
Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota, Kazuhide Nakata
SIAM Journal on Optimization 11 ( 3 ) 647 - 674 2000
-
Using the Conjugate Gradient Method in Interior-points Methods for Semidefinite Programs Reviewed
46 ( 2 ) 297 - 316 1998.12
-
Semidefinite Programming with the Conjugate Gradient Method
中田 和秀, 藤沢 克樹, 小島 政和
統計数理研究所共同研究レポート 1113 224 - 247 1998
-
Exploiting sparsity in primal-dual interior-point methods for semidefinite programming Reviewed
K Fujisawa, M Kojima, K Nakata
MATHEMATICAL PROGRAMMING 79 ( 1-3 ) 235 - 253 1997.10
Books
-
Intelligent Computing and Optimization: Proceedings of the 6th International Conference on Intelligent Computing and Optimization 2023 (ICO2023), Volume 4 (Lecture Notes in Networks and Systems, 854
Masaki Higashi, Yoshimasa Utsumi, Kazuhide Nakata（ Role： Contributorpp. 84-94）
Springer 2023.12 （ ISBN:9783031501500 ）
-
Advances in Artificial Intelligence, Selected Papers from the Annual Conference of Japanese Society of Artificial Intelligence
Kota Ishizuka, Kai Kurogi, Kosuke Kawakami, Daishi Iwai, Kazuhide Nakata（ Role： Joint authorpp. 27-33）
Springer 2022.4 （ ISBN:9783030964504 ）
-
基礎数学IV 最適化理論
中田 和秀他（ Role： Joint author2.2節）
東京化学同人 2019.10 （ ISBN:9784807914968 ）
-
Handbook on Semidefinite Cone and Polynomial Optimization
Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhiro Kobayashi, Kazuhide Nakata, Maho Nakata, M.F. Anjos, J.B. Lasserre（ Role： Joint authorChapter 24）
Springer 2011 （ ISBN:9781461407683 ）
-
Parallel Combinatorial Optimization
Makoto Yamashita, Mituhiro Fukuda, Katsuki Fujisawa, Masakazu Kojima, Kazuhide Nakata, l-G. Talbi（ Role： Joint authorChapter 9）
John Wiley ＆ Sons, Inc 2006 （ ISBN:9780471721017 ）
-
High Performance Optimization
NAKATA Kazuhide（ Role： Joint authorChapter 11）
Springer 2000 （ ISBN:9780792360131 ）
MISC
-
タクシープローブデータの分析による業務改善：最適化と機械学習 Invited
中田和秀
第34回RAMP数理最適化シンポジウム論文集 113 - 128 2022.10
-
企業の情報開示と株式の市場流動性─記述定性情報のケース Invited
田中研人, 木村遥介, 中田和秀, 井上 光太郎
証券アナリストジャーナル 60 ( 10 ) 36 - 48 2022.10
-
量子アニーリングと組合せ最適化 Invited
倉又 迪哉, 中田 和秀
オペレーションズ・リサーチ 67 ( 6 ) 280 - 289 2022.6
-
自然言語処理の発展と有用性 Invited
井上光太郎, 中田和秀
企業会計 74 ( 2 ) 160 - 170 2022.2
-
経営工学によるスマート社会の実現を目指して ー東京工業大学 中田研究室ー Invited
中田和秀
経営システム 30 ( 1 ) 43 - 47 2020
-
主双対内点法 Invited
中田 和秀
オペレーションズ・リサーチ 64 ( 4 ) 218 - 224 2019.4
-
データ解析コンペティションへの挑戦 Invited
中田和秀
オペレーションズ・リサーチ 63 ( 5 ) 274 - 277 2018.5
-
中田和秀
オペレーションズ・リサーチ 61 ( 10 ) 670 - 671 2016.10
-
Parallel Computing for Large-scale Semidefinite Programs
Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhide Nakata, Maho Nakata
Tokyo Institute of Technology Bulletin 2013.2
-
半正定値計画の問題記述＆解決能力 Invited
中田和秀
オペレーションズ・リサーチ 55 ( 7 ) 387 - 392 2010.7
-
第23回企業事例交流会ルポ Invited
中田 和秀, 梅谷俊治
オペレーションズ・リサーチ 54 504 - 505 2009
-
Fujisawa Katsuki, Kojima Masakazu, Nakata Kazuhide, Fukuda Mituhiro, Yamashita Makoto, Nakata Maho
RIMS Kokyuroku ( 1614 ) 136 - 143 2008.10
-
大規模な半正定値計画問題の解法 Invited
中田 和秀
第17回RAMPシンポジウム論文集 52 - 64 2005.10
-
平成17年度春季研究発表会ルポ Invited
山下 真, 中田 和秀, 後藤 順哉, 井床 利生
オペレーションズ・リサーチ 50 ( 7 ) 500 - 504 2005
-
第１５回RAMPシンポジウムルポ Invited
中田 和秀, 下平 英寿, 武田 朗子, 小林 和博
オペレーションズ・リサーチ 49 256 - 257 2004
Awards
-
研究奨励賞
2024.3 日本ソーシャルデータサイエンス学会
山尾奬紀,植田遼太,髙口奨一郎,中瀬達,鈴木愛,豊田耕大,小林健,中田和秀
-
第37回 全国大会優秀賞
2023.11 人工知能学会
馬嶋海斗, 中田和秀
-
研究奨励賞
2017.3 日本ソーシャルデータサイエンス学会
-
事例研究賞
2016.9 日本オペレーションズ・リサーチ学会
-
研究奨励賞
2015.3 日本ソーシャルデータサイエンス学会
-
船井情報科学振興賞
2003.3 船井情報科学振興財団
Research Projects
-
機械学習を用いた最適化問題の自動モデリングと構造を利用したアルゴリズムの開発
Grant number：23K20266 2020.4 - 2025.3
日本学術振興会 科学研究費助成事業 基盤研究(B)
中田 和秀, 田中 未来, 小林 健, 水野 眞治
Grant amount：\14560000 （ Direct Cost: \11200000 、 Indirect Cost：\3360000 ）
機械学習によってモデリングを行った場合、一般に関数が複雑になり扱いが難しい。そのような関数の勾配を近似計算することにより複雑な目的関数を持つ凸最適化問題を解くアルゴリズムを提案し、その理論的解析や計算性能の検証を行った。モデリング誤差の問題を解決するためロバスト最適化や分布ロバスト最適化を利用する時、不確実性集合をどのように定義するか決める必要がある。この問題を解決するため、ロバスト線形計画問題における不確実性集合を定義する際に逆最適化理論を援用する手法を提案した。また、分布ロバスト最適化において、Wasserstein距離やモーメントを用いた場合にそのハイパーパラメータの設定方法を提案した。不確実性が高い状況においては、ベイズ理論を用いてモデル化することが有効である。その状況において、階層ベイズでモデル化を行い、その後確率変動を考慮した最適化を行う枠組みを提案した。非常に多くの最適化問題を含んだ枠組みとして、対称錐上で定義された一般化共正定値錐がある。この問題に対して複数の階層近似法を提案し、理論的並びに数値実験的に比較を行った。
幾つかの事例研究も行った。まず、Eコマースなどに対し、時系列データに対する解釈可能性と効率性を両立した決定木クラスタリング手法、明示的ドメイン情報と潜在的階層構造を考慮した解釈可能性とトレンド分析を両立した時間依存非負値行列因子分解法、少ないデータに対応したゼロ過剰ポアソンテンソル因子分解法を提案した。次に、日中のオプション価格変動実績データから機械学習法によりボラティリティサーフェイスを推定する手法を開発した。最後に、教師なしクラスタリングを用いたタンパク質機能予測法を提案した。
これらの研究成果は２本の査読付きジャーナル論文と６本の査読付き国際会議プロシーディングに掲載された。また、国内外で合計2１件の研究発表を行い、研究成果の周知をはかった。 -
機械学習を用いた最適化問題の自動モデリングと構造を利用したアルゴリズムの開発
Grant number：20H02385 2020.4 - 2025.3
日本学術振興会 科学研究費助成事業 基盤研究(B) 基盤研究(B)
中田 和秀, 田中 未来, 水野 眞治
Grant amount：\14560000 （ Direct Cost: \11200000 、 Indirect Cost：\3360000 ）
最適化モデリングのための機械学習法として、季節変動を考慮した予測と方策の最適化手法の提案、階層ベイズを用いた隠れた関係性の発見とその関係性を利用した最適化のフレームワークの提案、機械学習法による自動モデリングから生じる誤差に対するノイズに頑強な学習法の提案、データの不均衡性と解釈性を考慮したモデリング法の提案を行った。そして、それらを鉄鋼業界の実データ、包括的なアンケートデータなどに適用して、提案手法の有効性の検証を行った。
また、多レベル最適化問題の下位問題を有限反復の勾配法で解く近似を再帰的に行なうことで多レベル最適化問題を1 レベルの最適化問題に近似的に帰着し、この近似や近似後の問題の勾配の計算を連鎖律と自動微分によって計算機上で自動的に行うアルゴリズムを提案した。また、最適化問題の構造や性質（微分、劣勾配、凸性、疎性など）を利用して効率よく最適解の計算が可能となるアルゴリズムとして、位置推定問題に対するブロック座標降下法と基数制約を含んだポートフォリオ選択問題に対して２段階の切除平面法を提案し、その理論的な収束性を導いた。また、特殊なジョブショップスケジューリング問題に対する近似アルゴリズムを提案した。
また、社会で実際に機械学習と最適化が利用されているシチュエーションについて理解するため、dualチャネルにおけるサプライチェンマネジメントに対する価格や在庫管理について研究を行い、現実問題を解決することに成功した。
これらの成果を６本の査読付き論文と２８回の研究発表（内１２回は国際会議）として公表した。 -
Next Optimization Methods for Social Implementation of Machine Learning Systems
Grant number：19H00808 2019.4 - 2022.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A) Grant-in-Aid for Scientific Research (A)
Mizuno Shinji
Grant amount：\30420000 （ Direct Cost: \23400000 、 Indirect Cost：\7020000 ）
In order to promote the social implementation of machine learning systems, we here focused on optimization algorithms that offer their computational foundations. We expanded the problem class that can be solved with high accuracy in reasonable time by enhancing and nicely applying conic optimization techniques. We also developed efficient approximation algorithms especially for discrete optimization problems that have wide applications. On the other hand, we developed modeling methodologies such that the resulting outputs can be easily accepted in practice by users of machine learning systems, as well as efficient algorithms for them. In particular, we found that imposing users’ knowledge as a constraint in the learning stage without compromising its performance is effective in practice.
-
テキスト分析による有価証券報告書の文章情報の情報価値の分析
Grant number：18K18566 2018.6 - 2021.3
日本学術振興会 科学研究費助成事業 挑戦的研究(萌芽) 挑戦的研究(萌芽)
井上 光太郎, 中田 和秀, 池田 直史
Grant amount：\6240000 （ Direct Cost: \4800000 、 Indirect Cost：\1440000 ）
本年度は、最初に有価証券報告書のテキストデータを分析可能なフォーマットにするための変更作業を進め、その上でいくつかの分析を開始した。第1に任意の２つの企業の有価証券報告書の記載内容の類似性が、企業間のM&A実施とその経済効果に与える影響を分析した。第2に有価証券報告書に記載された個別企業の戦略やリスク認識などが、当該企業の株式のリスクプレミアムに与える影響の検証を進めた。第3に有価証券報告書の記載内容の特徴量を計測し、それらがどのような経済的意味を持つかの分析を進めている。
第1の研究については、有価証券報告書に記載された事業内容、研究開発動向の企業間の類似性が将来のM&Aの発生確率に強い正の効果を持つこと、またその類似性がM&Aのプレスリリースに記載されたM&Aの目的等の記述と強い正の相関を持つことを確認した。これらの結果は企業行動の予測に関して、有価証券報告書のテキスト情報が定量情報にない独自の情報価値を持つことを示す。この論文について、２つの学会での報告を経て、現在は国内査読付き学会誌に投稿中である。
第2の研究については、有価証券報告書の「事業等のリスク」の記載内容が、その企業の1期先の株式市場におけるリスクプレミアムを予測するかについての検証を行っている。分析結果として、有価証券報告書に記載されたリスク情報が、翌期の株価に反映される当該企業のリスクに対し説明力を持つこと示した。本研究について、２つの学会での報告を経て、現在、追加の分析を行っている。
第3の研究については、有価証券報告書の記載内容に対し、LDA(Latent Dirichret Allocation)と階層的LDAを用いて特徴量を抽出し、結果として階層的LDAでは産業の特徴を捉えたトピックを抽出できていることが確認できた。現在は、階層的LDAで抽出した特徴量の持つ意味を評価するために，将来の利益率の予測可能性などを分析中である。 -
テキスト分析による企業戦略、リスク等の計測とＭ＆Ａや資本政策等の企業ファイナンス行動の関係分析
2018.4 - 2021.3
公益財団法人 野村財団 金融・証券のフロンティアを拓く研究助成
井上光太郎, 中田和秀, 池田直史
-
An Efficient Numerical Method for Optimal Contribution Problem based on Conic Optimization
Grant number：15K00032 2015.4 - 2019.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
Yamashita Makoto, FUKUDA mituhiro, KOJIMA masakazu, NAKATA kazuhide, KIM sunyoung, MULLIN tim j., SAFARINA sena
Authorship：Coinvestigator(s)
Grant amount：\3510000 （ Direct Cost: \2700000 、 Indirect Cost：\810000 ）
Optimal contribution problems arising from tree breeding or other optimization problems can be formulated as a mixed-integer second-order cone programming problem. We propose fast numerical methods that exploits conic optimization approaches. The proposed linear approximation reduces the computation time to about 1/10 of an existing method for obtaining exact solutions. Another new method, a steep ascent method, cannot theoretically guarantee the optimality, but it successfully outputs a favorable solution in several seconds.
-
Research and Development of Decision Making Platform by New Optimization Model
Grant number：26242027 2014.4 - 2019.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A) Grant-in-Aid for Scientific Research (A)
MIZUNO SHINJI, kojima Masakazu
Grant amount：\39130000 （ Direct Cost: \30100000 、 Indirect Cost：\9030000 ）
In this research, we had the following results for three purposes. For the modeling of decision making problems, we constructed new models for portfolio optimization problems, storage problems in a container terminal, and variable selection problems for eliminating multicollinearity.
For the development of algorithms, we had new results for the simplex method and LP-newton methods for linear programming problems, approximation algorithms for covering integer programming problems, and robust algorithms for symmetric cone programming problems.
For the development of decision making platform, we implemented and evaluated computer programs for solving large scale scheduling problems with practical constraints, minimum maximal flow problems, and multi-period portfolio selection problems. -
Development of a global logistics system that can respond to a rapidly changing society
Grant number：26350417 2014.4 - 2019.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C) Grant-in-Aid for Scientific Research (C)
Nakata Kazuhide
Grant amount：\4680000 （ Direct Cost: \3600000 、 Indirect Cost：\1080000 ）
In order to conduct efficient logistics in a rapidly changing social environment, it is necessary to deal with uncertain factors. For this reason, we have researched methods for predicting the near future to the past data as accurately as posible using machine learning methods. Also, in order to obtain a satisfactory solution in a realistic time, we have developed a practical optimization algorithm that calculates an approximate solution stably. Using these research results, we have worked on case studies and developed efficient modeling and optimization algorithms for various real problems.
We published these results as 15 peer-reviewed articles and 9 non-peer-reviewed articles. We also made presentations at 38 domestic and international conferences, including 6 invited talks. -
連続時間モデルによる多期間動的ポートフォリオ最適化
2011 - 2014
年金積立金管理運用独立行政法人
土谷隆
-
Development of the modeling tool to use the symmetric cone programming efficiently
Grant number：22710136 2010.4 - 2014.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B) Grant-in-Aid for Young Scientists (B)
NAKATA Kazuhide
Grant amount：\3120000 （ Direct Cost: \2400000 、 Indirect Cost：\720000 ）
In order to solve real problems using the symmetric cone programming, we developed modeling and the algorithm to solve the typical real problems efficiently. In addition, we have developed a modeling tool that integrates computer algebra system and financial engineering. QuantOnline that we developed can be computed by easy modeling over the Internet. Furthermore, we have succeeded in the development of algorithms that efficiently solve matrix approximation problems including constraints on condition number.
-
公的年金運用におけるポートフォリオ最適化についての研究
2009 - 2010
年金積立金管理運用独立行政法人
水野眞治
-
Grant number：20241038 2008 - 2012
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A) Grant-in-Aid for Scientific Research (A)
MIZUNO Shinji, KOJIMA Masakazu, HIGA Kunihiko, NINOMIYA Shoiti, OGATA Wakaha, NAKAGAWA Hidetoshi, NAKATA Kazuhide, NAKANO Yumiharu, KITAHARA Tomonari, TAKANO Yuichi
Grant amount：\36010000 （ Direct Cost: \27700000 、 Indirect Cost：\8310000 ）
We have carried out theoretical research into mathematical technology of finance and financial engineering including three main topics ‘ optimization and operations research’,‘stochastic numerical analysis’, and ‘information network security’. We opened software of them to the internet. We also designed and developed a financial numerical calculation system. As a result, it makes possible to easily access our highly specialized mathematical technology.
-
Grant number：19310096 2007 - 2009
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B) Grant-in-Aid for Scientific Research (B)
KOJIMA Masakazu, FUJISAWA Katsuki, TAKEDA Akiko, NAKATA Kazuhide, YAMASHITA Magkoto, FUKUDA Mituhiro, KIM Sunyoung
Grant amount：\19760000 （ Direct Cost: \15200000 、 Indirect Cost：\4560000 ）
We studied primal-dual interior-point methods for solving a semidefinite program which is one of the most important optimization problems having lots of applications in various fields of science and engineering, and developed a software package SDPA based on them. SDPA solves larger scale problems in shorter time than the existing software packages. As applications of SDPA, we provided SparsePOP for polynomial optimization problems and SFSDP for large scale sensor network localization problems.
-
超大規模な錐計画内題を解くロバストアルゴリズムの開発
Grant number：17710126 2005 - 2007
日本学術振興会 科学研究費助成事業 若手研究(B) 若手研究(B)
中田 和秀
Grant amount：\1500000 （ Direct Cost: \1500000 ）
本研究では、超大規模な錐計画問題を実用的な計算資源でロバストに解くアルゴリズムの開発を目的としている。
2次錐制約を半正定値制約や非負制約と統一的に扱う枠組みを考案した。Iまた、ロバストな解法を実現するため、主双対内点法が破錠しないような計算スキームを提案し、プログラミング言語C++で実装した。その結果、錐計画問題を主双対内点法によって安定的に解くソフトウェアの開発に成功した。
超大規模な対称錐計画問題は、入力データの多くはゼロである。このような疎性を主双対内点法でより有効に利用するための前処理法を提案した。さらに、この前処理を高速に行う方法を実装した。これにより、問題の疎性の利用し、主双対内点法を効率よく実行することが可能となった。
最後に、同様の数理計画問題を解く他のソフトウェアとの比較実験を行うことにより、本研究の有効性を実証するができた.
これらの成果を専門分野の研究者に紹介し、学術交流を通じてその意義を明らかにするため、11月に行われたINFORMS (オペレーションズ・リサーチとマネジメントサイエンスのフォーラム)の年会にて研究課題の発表を行った。また、学術論文として論文誌に投稿する準備中である。
本研究により、主双対内点法などの数理計画法について詳しくない研究者でも、簡便に超大規模な錐計画問題を安定して解くことができるようになる。それは、構造最適化・システム制御・組合せ最適化・非凸計画・量子化学・統計・金融工学のような様々な工学分野における研究や開発に対し、非常に大きなサポートとなる。 -
金融リスク管理のための新ITモデルの研究と開発
2004 - 2007
日本学術振興会 基盤研究(A)
水野眞治
Grant type：Competitive
-
多項式計画問題に対する大域的最適解法とその並列計算
Grant number：16016234 2003 - 2005
日本学術振興会 科学研究費助成事業 特定領域研究 特定領域研究
小島 政和, 藤澤 克樹, 武田 朗子, 中田 和秀, 山下 真
Grant amount：\13000000 （ Direct Cost: \13000000 ）
本研究の主目的は凸最適化で蓄積された計算手法をさらに発展させ,クラスタおよびグリッド計算技術を融合し,非凸計画問題の中核をなす多項式計画問題および多変数多項式方程式系を計算効率良く解く並列計算手法・ソフトウェアを開発することにあった.以下の研究成果をあげた.
1.半正定値計画問題に対する主双対内点法ソフトウェアSDPAおよびその並列版の改良:これまで開発した単一CPUソフトウェアSDPA,並列版ソフトウェアSDPARA, SDPARA-Cがより一般的な形式の半正定値計画問題(具体的には,自由変数を含む問題)を扱えるように改良を行った.また,数値的な安定性を高め,精度を高めるための技術として,4倍精度計算を部分的に取り込むことに関して研究を行い,計算実験を通してその有効性を検証した.
2.凸緩和手法の開発・改良:平成16年度の研究により開発した多項式計画問題に対する疎性を活用した半正定値計画緩和計算機への実装を行い,計算実験を通してその有効性を検証した.また,多項式計画問題に等式条件が含まれる場合について,生成される緩和半正定値計画問題の数値的な不安定を解消するための研究を行った.さらに,疎性を活用した半正定値計画緩を対称錐上の多項式最適化問題へ拡張した.
3.多変数多項式方程式系のすべての複素孤立解を計算する多面体的ホモトピー法ソフトウェアPHoMの改良,並列版の開発:PHoMの並列版を開発し,これまで解くことの出来なかった超大規模な多項式方程式系の求解計算に成功した.また,多面体的ホモトピーの構築に必要な多項式方程式系の混合体積の新しい計算手法を提案し,その有効性を計算実験を通して検証した.
4.半正定値計画問題を解くためのソフトウェアであるSDPA, SDPARA-C, SDPARAに関するOnline Solverを構築し,その試験的運用を開始した.並列計算をも提供するOnline Solverは世界的にも例がない. -
半正定値計画問題に対する実用的な主双対内点法の実現とその一般公開
Grant number：14750049 2002 - 2004
日本学術振興会 科学研究費助成事業 若手研究(B) 若手研究(B)
中田 和秀
Grant amount：\2000000 （ Direct Cost: \2000000 ）
研究期間の最終年度となる本年度の研究業績は次の通りである。
1.主双対内点法を効率よく並列計算する手法を提案し、MPIを利用することにより実装を行った。そして、東京工業大学松岡研究室のpcクラスタPresto IIIや東京電機大学藤澤研究室のpcクラスタSDPAで実証実験を行った。その結果、開発したソフトウェアは、既存のソフトウェアに比べ非常に高いスケーラビリティを有し、大規模な半正定値計画問題と解くことが可能であることが確認できた。これらの成果は、Journal of Optimization Methoeds and Software誌に掲載予定の論文と東京工業大学 数理・計算科学専攻のテクニカルレポートで報告している。さらに、現在2本の論文を投稿中である。
2.本研究課題の成果物を多くの人に利用してもらうため、ソフトウェアのソースコードをインターネット上で一般に公開した。ホームページのアドレスはhttp://grid.r.dendai.ac.jp/sdpa/である。これにより、ANSI C準拠のコンパイラがあれば、誰でもすぐに超大規模な半正定値計画問題を解くことが可能となった。また、ソフトウェアのドキュメントは、東京工業大学 数理・計算科学専攻のテクニカルレポートとしてまとめた。
3.現実社会の問題として、ロバスト・トラッキングエラー最小化問題に適用し、上記の手法の有効性を検証した。この成果は日本オペレーションズ・リサーチ学会誌に掲載されることが決まっている。
3年間の研究期間が終了したが、この期間の一連の研究により、当初の目標である、実用的な計算資源で超大規模な半正定値計画問題を解く主双対内点法を実現し、そのソフトウェアをインターネットで一般に公開する、という研究課題は十分に達成することが出来た。 -
逐次凸緩波アルゴリズムの並列実行とその組合せ最適化問題への応用
Grant number：14019038 2002
日本学術振興会 科学研究費助成事業 特定領域研究
小島 政和, 中田 和秀, 藤沢 克樹
Authorship：Coinvestigator(s)
Grant amount：\3800000 （ Direct Cost: \3800000 ）
この研究の目的は凸計画問題に対する計算手法をGrid技術を用いた分散コンピューティング環境で並列化・高速化し,それを緩和として利用し,組合せ最適化問題の解法を開発することにあった.このための研究を行い,以下の成果を得た.
1.逐次凸緩和に用いる半正定値計画問題に対するソフトウエアSDPAを高速化し,計算実験を行った.この高速化により,半正定値計画問題に対する既存の汎用ソフトウエアのなかで最速となった.
2.SDPAにおいて探索方向を計算する部分に関して並列化を行ったソフトウエアSDPARAを開発し,計算実験を行い,その有効性を検証した.特に,量子化学から生ずる大規模な半正定値計画問題を解くことに初めて成功した.より大規模な問題を解くため本グループが提案した半正定値補完技術に基づくデータ疎生の有効利用を並列計算に用いる研究を行い,その並列実装を開始した.
3.より柔軟な逐次凸緩和の枠組みを提案した.これにより,従来の半正定値計画,線形計画に加えて2次錐計画を含む様々な凸計画問題を緩和に利用可能になった.また,線形計画緩和に関して実験的解析を行い,特殊な問題に関しては半正定値計画緩和よりも有効であることを示した.
4.逐次凸緩和を利用した組合せ最適化問題を含む非凸最適化問題に対する並列分枝限定法を提案し,その開発を開始した.すでに中規模な問題に対する計算実験を行い,提案した並列分枝限定法が有効に働くことを検証している.より大規模な問題を高速に解くためには,上記の1,2,3で行った研究をこの枠組に取り込む必要がある. -
Efficient Algorithms for Large Optimization Problems
Grant number：12680433 2000 - 2002
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C) Grant-in-Aid for Scientific Research (C)
MIZUNO Shinji, NAKATA Kazuhide, YAJIMA Yasutoshi
Grant amount：\3400000 （ Direct Cost: \3400000 ）
This research aims to develop efficient algorithms for solving large optimization problems and to investigate their theoretical properties and practical usage. In 2000, we did basic research for the purpose. There are 3 types of variables, free variables, nonnegative variables and bounded variables. in large optimization problems. We investigated efficient algorithms which can handle all these types of variables simultaneously. In 2001, we studied algorithms for solving large problems with a special structure. Especially, we proposed a new algorithm for solving multistage stochastic programming problems. These problems could be very large when the number of stages is not small. We use the special structure of the problems and developed an efficient algorithm for them. In 2002, we investigated a new algorithm for solving large linear and nonlinear programming problems. The algorithm uses a logarithmic transformation to the variables in the problem. This transformation makes the path of centers smooth and the algorithm efficient. From some preliminary computational experiment, we found that the algorithm can solve large problems very quickly.
-
超大規模な半正定値計画の数値計算に関する研究
Grant number：12780326 2000 - 2001
日本学術振興会 科学研究費助成事業 奨励研究(A) 奨励研究(A)
中田 和秀
Grant amount：\1700000 （ Direct Cost: \1700000 ）
半正定値計画問題に対する主双対内点法の変数行列に対し、行列補完理論を導入することにより、この密となる変数行列にある種の疎構造が存在することを証明した。そして、この疎構造を主双対内点法に応用する方法として、conversion版とcompletion版の2通りの方法を提案した。この方法により、変数の個数が多くなる半正定値計画問題を非常に効率よく解くことが可能となった。その結果、変数の数が1千万程度の大規模半正定値計画問題を解くことに成功した。
主双対内点法の各反復で解く係数行列が大規模で密となる線形方程式系に対し、クリロフ部分空間法などに代表される様々な反復解法を適用する枠組みを提案した。また、係数行列の構造を活かすため、対称逐次過剰緩和法などの定常反復法を前処理として用いた。そして、その効率性を理論的・実験的に検証した。この方法により、線形制約の個数が多くなる半正定値計画問題を非常に効率よく解くことが可能となった。その結果、制約の数が20万以上の大規模半正定値計画問題を解くことに成功した。さらに、それらの結果を拡張することにより、係数行列が大規模で密となる一般の線形方程式系に対し、クリロフ部分空間法や前処理としての定常反復法を適用する枠組みを構築した。
以上の成果を日本応用数理学会やSWoPPで発表することにより、専門分野の研究者に紹介した。さらに、半正定値計画問題に対する主双対内点法を量子化学分野に応用することにより、従来のアルゴリズムでは解くことが困難であった最適化問題を解くことに成功し、それらも論文としてまとめた。