工学修士, 東京大学, 1991年03月

博士(学術), 総合研究大学院大学, 1994年03月

多項式最適化

線形最適化

非線形最適化

２次錐計画

半正定値計画

錐計画

オペレーションズ・リサーチ

情報通信, 数理情報学

2020年04月 - 現在
電気通信大学, 全学教育・学生支援機構 大学教育センター, 大学教育センター長

2020年04月 - 現在
電気通信大学, 副学長（教育担当）

2008年04月
電気通信大学情報・ネットワーク工学専攻, 教授

1994年03月
総合研究大学院大学, 数物科学研究科, 統計科学専攻

1991年03月
東京大学, 工学系研究科, 情報工学専攻

1989年03月
東京大学, 工学部, 計数工学科

1981年04月01日 - 1984年03月31日
私立武蔵高校

2018年04月 - 2020年03月
論文誌編集委員長, 日本OR学会, 学協会

2009年04月 - 2011年
国際理事, 日本OR学会, 学協会

2008年03月
日本OR学会フェロー, 学協会

1999年 - 2000年
IAOR委員, 日本OR学会, 学協会

1993年 - 1999年
研究普及委員, 日本OR学会, 学協会

受賞日 2017年09月
日本学術振興会, 書面審査において有意義な審査意見を付した専門委員を表彰するもの
有意義な審査意見を付した専門委員
その他の賞, 日本国

受賞日 2017年09月
日本オペレーションズ・リサーチ学会
弱実行不能半正定値計画問題の幾何学的解析
日本オペレーションズ・リサーチ学会論文賞, ブルノ・F・ロウレンソ;村松正和;土谷隆
学会誌・学術雑誌による顕彰

受賞日 2003年03月
日本OR学会文献賞

A Limiting Analysis on Regularization of Singular SDP and its Implication to Infeasible Interior-point Algorithms
Takashi Tsuchiya; Bruno F. Lourenco; Masakazu Muramatsu; Takayuki Okuno
Mathematical Programming, Springer Science and Business Media LLC, 200巻, 1号, 掲載ページ 531-568, 出版日 2022年11月, 査読付, 国際誌, Abstract

We consider primal-dual pairs of semidefinite programs and assume that they are singular, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which would make them strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as the perturbation for regularization is driven to zero. Specifically, we fix two positive definite matrices, $$I_p$$ and $$I_d$$, say, (typically the identity matrices), and regularize the primal and dual problems by shifting their associated affine space by $$\eta I_p$$ and $$\varepsilon I_d$$, respectively, to recover interior feasibility of both problems, where $$\varepsilon $$ and $$\eta $$ are positive numbers. Then we analyze the behavior of the optimal value of the regularized problem when the perturbation is reduced to zero keeping the ratio between $$\eta $$ and $$\varepsilon $$ constant. A key feature of our analysis is that no further assumptions such as compactness or constraint qualifications are ever made. It will be shown that the optimal value of the perturbed problem converges to a value between the primal and dual optimal values of the original problems. Furthermore, the limiting optimal value changes “monotonically” from the primal optimal value to the dual optimal value as a function of $$\theta $$, if we parametrize $$(\varepsilon , \eta )$$ as $$(\varepsilon , \eta )=t(\cos \theta , \sin \theta )$$ and let $$t\rightarrow 0$$. Finally, the analysis leads us to the relatively surprising consequence that some representative infeasible interior-point algorithms for SDP generate sequences converging to a number between the primal and dual optimal values, even in the presence of a nonzero duality gap. Though this result is more of theoretical interest at this point, it might be of some value in the development of infeasible interior-point algorithms that can handle singular problems.
研究論文（学術雑誌）, 英語

Solving SDP completely with an inerior point oracle
Bruno F. Lourenco; Masakazu Muramatsu; Takashi Tsuchiya
Optimization Methods and Software, Taylor & Francis, 36巻, 2-3号, 掲載ページ 425-471, 出版日 2021年, 査読付, We suppose the existence of an oracle which solves any semidefinite programming (SDP) problem satisfying strong feasibility (i.e. Slater's condition) simultaneously at its primal and dual sides. We note that such an oracle might not be able to directly solve general SDPs even after certain regularization schemes are applied. In this work we fill this gap and show how to use such an oracle to ‘completely solve’ an arbitrary SDP. Completely solving entails, for example, distinguishing between weak/strong feasibility/infeasibility and detecting when the optimal value is attained or not. We will employ several tools, including a variant of facial reduction where all auxiliary problems are ensured to satisfy strong feasibility at all sides. Our main technical innovation, however, is an analysis of double facial reduction, which is the process of applying facial reduction twice: first to the original problem and then once more to the dual of the regularized problem obtained during the first run. Although our discussion is focused on semidefinite programming, the majority of the results are proved for general convex cones.
研究論文（学術雑誌）, 英語

Development of Artificial Intelligence to Classify Quality of Transmission Shift Control Using Deep Convolutional Neural Networks
Takefumi Kawakami; Takanori Ide; Eiji Moriyama; Kunihiro Hoki; Masakazu Muramatsu
IEEE Transactions on Vehicular Technology, IEEE, 69巻, 12号, 掲載ページ 16168-16172, 出版日 2020年, 査読付
研究論文（学術雑誌）, 英語

Approach to Problem of Minimizing Network Power Consumption Based on Robust Optimization
B.C. Das; S. Takahashi; E. Oki; M. Muramatsu
International Journal of Communication Systems, online available巻, 出版日 2019年01月, 査読付
研究論文（学術雑誌）, 英語

Comparative Performance of Green Pipe, Green Hose and Green Hose-Rectangle Models in Power Efficient Network
B.C. Das; E. Oki; M. Muramatsu
IEEE Communications Quality and Reliability Workshop, 出版日 2018年05月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Network congestion minimization models based on robust optimization
Bimal Chandra Das; Satoshi Takahashi; Eiji Oki; Masakazu Muramatsu
IEICE Transactions on Communications, Institute of Electronics, Information and Communication, Engineers, IEICE, E101B巻, 3号, 掲載ページ 772-784, 出版日 2018年03月01日, 査読付, This paper introduces robust optimization models for minimization of the network congestion ratio that can handle the fluctuation in traffic demands between nodes. The simplest and widely used model to minimize the congestion ratio, called the pipe model, is based on precisely specified traffic demands. However, in practice, network operators are often unable to estimate exact traffic demands as they can fluctuate due to unpredictable factors. To overcome this weakness, we apply robust optimization to the problem of minimizing the network congestion ratio. First, we review existing models as robust counterparts of certain uncertainty sets. Then we consider robust optimization assuming ellipsoidal uncertainty sets, and derive a tractable optimization problem in the form of second-order cone programming (SOCP). Furthermore, we take uncertainty sets to be the intersection of ellipsoid and polyhedral sets, and considering the mirror subproblems inherent in the models, obtain tractable optimization problems, again in SOCP form. Compared to the previous model that assumes an error interval on each coordinate, our models have the advantage of being able to cope with the total amount of errors by setting a parameter that determines the volume of the ellipsoid. We perform numerical experiments to compare our SOCP models with the existing models which are formulated as linear programming problems. The results demonstrate the relevance of our models in terms of congestion ratio and computation time.
研究論文（学術雑誌）, 英語

Classification of Time Series Measurement Data for Lock-Up Clutch of Automatic Transmission of Vehicles Using Deep Convolutional Neural Networks
Takefumi Kawakami; Takanori Ide; Kiyohisa Tomita; Eiji Moriyama; Hiroshi Tsutsui; Kunihito Hoki; Masakazu Muramatsu
SAE Technical Papers, SAE International, 2018-巻, 0399号, 掲載ページ 1-5, 出版日 2018年, 査読付, A newly developed classifying method for time series measurement data of automatic transmission of vehicles is presented. The proposed method uses deep convolutional neural networks to learn what is comfortable acceleration. In addition, our proposal method employs supervised learning based on experienced engineer's criterion. As a demonstrative problem, we consider the classification of time series measurement data for lock-up clutch control of an 8 speed automatic transmission.
研究論文（国際会議プロシーディングス）, 英語

Facial reduction and partial polyhedrality
Bruno F. Lourenco; Masakazu Muramatsu; Takashi Tsuchiya
SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 28巻, 3号, 掲載ページ 2304-2326, 出版日 2018年, 査読付
研究論文（学術雑誌）, 英語

An extension of Chubanov’s algorithm to symmetric cones
Bruno F. Lourenço; Tomonari Kitahara; Masakazu Muramatsu; Takashi Tsuchiya
Mathematical Programming, Springer Verlag, 173巻, 1-2号, 掲載ページ 1-33, 出版日 2017年11月13日, 査読付, In this work we present an extension of Chubanov’s algorithm to the case of homogeneous feasibility problems over a symmetric cone (Formula presented.). As in Chubanov’s method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and (Formula presented.). Following an earlier work by Kitahara and Tsuchiya on second order cone feasibility problems, progress is measured through the volumes of those intersections: when they become sufficiently small, we know it is time to stop. We never have to explicitly compute the volumes, it is only necessary to keep track of the reductions between iterations. We show this is enough to obtain concrete upper bounds to the minimum eigenvalues of a scaled version of the original feasibility problem. Another distinguishing feature of our approach is the usage of a spectral norm that takes into account the way that (Formula presented.) is decomposed as simple cones. In several key cases, including semidefinite programming and second order cone programming, these norms make it possible to obtain better complexity bounds for the basic procedure when compared to a recent approach by Peña and Soheili. Finally, in the appendix, we present a translation of the algorithm to the homogeneous feasibility problem in semidefinite programming.
研究論文（学術雑誌）, 英語

Application of SOCP in Power Efficient Networks
B.C. Das; E. Oki; M. Muramatsu
SIAM Conference on Optimization (OP17), 出版日 2017年05月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Improved Simulation Adjusting
K. Hoki; N. Araki; S. Takahashi; M. Muramatsu
ICGA journal, International Computer Games Association, 39巻, 掲載ページ 195-204, 出版日 2017年, 査読付
研究論文（学術雑誌）, 英語

Pure Nash equilibria of competitive diffusion process on toroidal grid graphs
Yuki Sukenari; Kunihito Hoki; Satoshi Takahashi; Masakazu Muramatsu
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 215巻, 掲載ページ 31-40, 出版日 2016年12月, 査読付, We consider a competitive diffusion process for two players on two-dimensional toroidal grid graphs. Pure Nash equilibria for the game are completely characterized; i.e., for arbitrary-sized toroidal grid graphs, we list all the initial positions that are pure Nash equilibria. (C) 2016 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語

畳み込みニューラルネットワークを用いた囲碁における一局の棋譜からの棋力推定
荒木伸夫; 保木邦仁; 村松正和
情報処理学会論文誌, 情報処理学会, 57巻, 11号, 掲載ページ 2365-2373, 出版日 2016年11月15日, 査読付, 囲碁のプロ棋士は,一局の棋譜を見ればプレイヤの棋力がわかると言われている.本稿では,畳み 込みニューラルネットワーク(Convolutional Neural Network; CNN)を使用し,一局の囲碁の棋譜より, プレイヤの棋力を推定する手法を提案する.プレイヤのレート値を推定する実験と,プレイヤを上級/中 級/初級にクラス分けする実験を行なった.提案手法を実装して囲碁クエスト [14] の 13 路盤棋譜データを 用いて学習させて実験したところ,レート値を推定する手法としては従来手法 [1] より平均自乗誤差が小さ くなることがわかった.また,クラス分類する実験においては,一度 CNN を用いてレート値を推定して からその値に応じてクラス分けを行なう手法と,最初からクラス分類を CNN に学習させる手法の 2 種類 を提案し,それぞれ長所と短所があることを確かめた.
研究論文（学術雑誌）, 日本語

Mixed-Integer SOCP Model for Robust and Power Efficient Networks
B.C. Das; I.A. Ouédraogo; E. Oki; M. Muramatsu
The Fifth International Conference on Continuous Optimization, National Graduate Institute for Policy Studies (GRIPS), 出版日 2016年08月, 査読付
研究論文（国際会議プロシーディングス）, 英語

A Simple SOCP Formulation of Minimization of Network Congestion Ratio
B.C. Das; E. Oki; M. Muramatsu
State-of-the-art and future development of the optimization techniques, RIMS, Kyoto University, 出版日 2016年08月, 査読付
研究論文（国際会議プロシーディングス）, 英語

A Structural Geometrical Analysis of Weakly Infeasible SDPs
Bruno F. Lourenco; Masakazu Muramatsu; Takashi Tsuchiya
Journal of Operations Research Society of Japan, 日本オペレーションズ・リサーチ学会, 59巻, 3号, 掲載ページ 241-257, 出版日 2016年07月, 査読付, In this article, we develop a detailed analysis of semidefinite feasibility problems (SDFPs) to understand how weak infeasibility arises in semidefinite programming. This is done by decomposing a SDFP into smaller problems, in a way that preserves most feasibility properties of the original problem. The decomposition utilizes a set of vectors (computed in the primal space) which arises when we apply the facial reduction algorithm to the dual feasible region. In particular, we show that for a weakly infeasible problem over n × n matrices, at most n − 1 directions are required to approach the positive semidefinite cone. We also present a discussion on feasibility certificates for SDFPs and related complexity results.
研究論文（学術雑誌）, 英語

ディープラーニングを用いたコンピュータ囲碁～Alpha Goの技術と展望～
伊藤毅志; 村松正和
情報処理, 情報処理学会, 57巻, 4号, 掲載ページ 335-337, 出版日 2016年03月15日, 招待, This article reports the deep learning based technology of computer Go recently developed by Google. Alpha Go, the computer Go program based on this technology, is the first one that beat a human professional Go player with no handicap, and is going to play matches against one of the top professional players on March. We survey the technology, and give some comments on the matches.
研究論文（学術雑誌）, 日本語

Perturbed sums-of-squares theorem for polynomial optimization and its applications
Masakazu Muramatsu; Hayato Waki; Levent Tuncel
OPTIMIZATION METHODS & SOFTWARE, TAYLOR & FRANCIS LTD, 31巻, 1号, 掲載ページ 134-156, 出版日 2016年, 査読付, We consider a property of positive polynomials on a compact set with a small perturbation. When applied to a polynomial optimization problem (POP), the property implies that the optimal value of the corresponding SemiDefinite Programming (SDP) relaxation with sufficiently large relaxation order is bounded from below by (f* - epsilon) and from above by f* + epsilon (n + 1), where f* is the optimal value of the POP. We propose new SDP relaxations for POP based on modifications of existing sums-of-squares representation theorems. An advantage of our SDP relaxations is that in many cases they are of considerably smaller dimension than those originally proposed by Lasserre. We present some applications and the results of our computational experiments.
研究論文（学術雑誌）, 英語

Weak infeasibility in second order cone programming
Bruno F. Lourenço; Masakazu Muramatsu; Takashi Tsuchiya
Optimization letters, Springer, 掲載ページ 1-13, 出版日 2015年12月24日, 査読付, The objective of this work is to study weak infeasibility in second order cone programming. For this purpose, we consider a sequence of feasibility problems which mostly preserve the feasibility status of the original problem. This is used to show that for a given weakly infeasible problem at most m directions are needed to get arbitrarily close to the cone, where m is the number of Lorentz cones. We also tackle a closely related question and show that given a bounded optimization problem satisfying Slater’s condition, we may transform it into another problem that has the same optimal value but it is ensured to attain it. From solutions to the new problem, we discuss how to obtain solution to the original problem which are arbitrarily close to optimality. Finally, we discuss how to obtain finite certificate of weak infeasibility by combining our own techniques with facial reduction. The analysis is similar in spirit to previous work by the authors on SDPs, but a different approach is required to obtain tighter bounds on the number of directions needed to approach the cone.
研究論文（学術雑誌）, 英語

Monte-Carlo Simulation Adjusting
Nobuo Araki; Masakazu Muramatsu; Kunihito Hoki; Satoshi Takahashi
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI, 掲載ページ 3094-3095, 出版日 2014年06月21日, 査読付, In this paper, we propose a new learning method sim- ulation adjusting that adjusts simulation policy to im- prove the move decisions of the Monte Carlo method. We demonstrated simulation adjusting for 4 × 4 board Go problems. We observed that the rate of correct an- swers moderately increased.
研究論文（国際会議プロシーディングス）, 英語

Facial Reduction Algorithms for Conic Optimization Problems
Hayato Waki; Masakazu Muramatsu
Journal of Optimization Theory and Applications, 158巻, 1号, 掲載ページ 188-215, 出版日 2013年07月, 査読付, In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal-dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal-dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems
our facial reduction algorithm in fact enhances the numerical stability in those problems. © 2012 Springer Science+Business Media New York.
研究論文（学術雑誌）, 英語

Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
Hayato Waki; Maho Nakata; Masakazu Muramatsu
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, SPRINGER, 53巻, 3号, 掲載ページ 823-844, 出版日 2012年12月, 査読付, We observe that in a simple one-dimensional polynomial optimization problem (POP), the 'optimal' values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial evidences for the strange behaviors of the SDP solvers are given. This result gives a warning to users of the SDP relaxation method for POPs to be careful in believing the results of the SDP solvers. We also demonstrate how SDPA-GMP, a multiple precision SDP solver developed by one of the authors, can deal with this situation correctly.
研究論文（学術雑誌）, 英語

Efficiency of three forward-pruning techniques in shogi: Futility pruning, null-move pruning, and Late Move Reduction (LMR)
Kunihito Hoki; Masakazu Muramatsu
Entertainment Computing, Elsevier B.V., 3巻, 3号, 掲載ページ 51-57, 出版日 2012年, 査読付, The efficiency of three forward-pruning techniques, i.e., futility pruning, null-move pruning, and LMR, is analyzed in shogi, a Japanese chess variant. It is shown that the techniques with the α-β pruning reduce the effective branching factor of shogi endgames to 2.8 without sacrificing much accuracy of the search results. Because the average number of the raw branching factor in shogi is around 80, the pruning techniques reduce the search space more effectively than in chess. © 2011 International Federation for Information Processing.
研究論文（学術雑誌）, 英語

次の一手問題を用いた囲碁プレイヤの局面認識についての分析
高橋克吉; 村松正和; 伊藤毅志; 松原仁
情報処理学会論文誌, 情報処理学会, 52巻, 12号, 掲載ページ 3796-3805, 出版日 2011年12月, 査読付, 囲碁は完全情報ゼロ和ゲームとして多くのチェスライクゲームと同様に分類される が,ゲームの性質は大きく違うと考えられる.本研究は,囲碁における人の思考過程 について調べ,将棋との比較を行った.被験者に次の一手問題を提示し,発話プロト コルと視線の記録をもとに思考過程を分析した.上級者は盤面全体を見ており,先読 みよりも石の形によって手を決めていた.囲碁の上級者は主に石の形から情報を得て いると考えられる.将棋の上級者は視線を中央からほとんど動かさず,深い先読みを 行って次の手を決定しており,囲碁と将棋で上級者の思考過程に差異があった.これ は,囲碁と将棋のゲームとしての性質の違いを示していると考えられる.
研究論文（学術雑誌）, 日本語

An extension of the elimination method for a sparse sos polynomial
Hayato Waki; Masakazu Muramatsu
Journal of the Operations Research Society of Japan, Operations Research Society of Japan, 54巻, 4号, 掲載ページ 161-190, 出版日 2011年, 査読付, We propose a method to reduce the sizes of SDP relaxation problems fur a given polynomial optimization problem (POP). This method is an extension of the elimination method for a sparse SOS polynomial in [8] and exploits sparsity of polynomials involved in a given POP. In addition, we show that this method is a partial application of a facial reduction algorithm, which generates a smaller SDP problem with an interior feasible solution. In general, SDP relaxation problems for POPs often become highly degenerate because of a lack of interior feasible solutions. As a result, the resulting SDP relaxation problems obtained by this method may have an interior feasible solution, and one may be able to solve the SDP relaxation problems effectively Numerical results in this paper show that the resulting SDP relaxation problems obtained by this method can be solved fast and accurately. © The Operations Research Society of Japan.
研究論文（国際会議プロシーディングス）, 英語

A facial reduction algorithm for finding sparse SOS representations
Hayato Waki; Masakazu Muramatsu
OPERATIONS RESEARCH LETTERS, ELSEVIER SCIENCE BV, 38巻, 5号, 掲載ページ 361-365, 出版日 2010年09月, 査読付, The facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial [M. Kojima, S. Kim, H. Waki, Sparsity in sums of squares of polynomials, Math. Program. 103 (2005) 45-62] removes monomials which do not appear in any SOS representations. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial. (C) 2010 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語

INVARIANCE UNDER AFFINE TRANSFORMATION IN SEMIDEFINITE PROGRAMMING RELAXATION FOR POLYNOMIAL OPTIMIZATION PROBLEMS
Hayato Waki; Masakazu Muramatsu; Masakazu Kojima
PACIFIC JOURNAL OF OPTIMIZATION, YOKOHAMA PUBL, 5巻, 2号, 掲載ページ 297-312, 出版日 2009年05月, 査読付, Given a polynomial optimization problem (POP), any nonsingular affine transformation on its variable vector induces an equivalent POP. Applying Lasserre's SDP relaxation (SIAM J.Opt. 11:796-817, 2001] to the original and the transformed POPs, we have two SDPs. This paper shows that these two SDPs are isomorphic to each other under a nonsingular linear transformation, which maps the feasible region of one SDP onto that of the other isomorphically and preserves their objective values. This fact means that the SDP relaxation is invariant under any nonsingular affine transformation.
研究論文（学術雑誌）, 英語

Implementation Issues of Second-Order Cone Programming Approaches for Support Vector Machine Learning Problems
Rameswar Debnath; Masakazu Muramatsu; Haruhisa Takahashi
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E92A巻, 4号, 掲載ページ 1209-1222, 出版日 2009年04月, 査読付, The core of the support vector machine (SVM) problem is a quadratic programming problem with a linear constraint and bounded variables. This problem can be transformed into the second order cone programming (SOCP) problems. An interior-point-method (IPM) can be designed for the SOCP problems in terms of storage requirements as well as computational complexity if the kernel matrix has low-rank. If the kernel matrix is not a low-rank matrix, it can be approximated by a low-rank positive semi-definite matrix, which in turn will be fed into the optimizer. In this paper we present two SOCP formulations for each SVM classification and regression problem. There are several search direction methods for implementing SOCPs. Our main goal is to find a better search direction for implementing the SOCP formulations of the SVM problems. Two popular search direction methods: HKM and AHO are tested analytically for the SVM problems, and efficiently implemented. The computational costs of each iteration of the HKM and AHO search direction methods are shown to be the same for the SVM problems. Thus, the training time depends on the number of IPM iterations. Our experimental results show that the HKM method converges faster than the AHO method. We also compare our results with the method proposed in Fine and Scheinberg (2001) that also exploits the low-rank of the kernel matrix, the state-of-the-art SVM optimization softwares SVMTorch and SVMlight. The proposed methods are also compared with Joachims 'Linear SVM' method on linear kernel.
研究論文（学術雑誌）, 英語

SparsePOP - A sparse semidefinite programming relaxation of polynomial optimization problems
Hayato Waki; Sunyoung Kim; Masakazu Kojima; Masakazu Muramatsu; Hiroshi Sugimoto
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, ASSOC COMPUTING MACHINERY, 35巻, 2号, 掲載ページ 883, 出版日 2008年07月, 査読付, SparsePOP is a Matlab implementation of the sparse semidefinite programming (SDP) relaxation method for approximating a global optimal solution of a polynomial optimization problem (POP) proposed by Waki et al. [2006]. The sparse SDP relaxation exploits a sparse structure of polynomials in POPs when applying "a hierarchy of LMI relaxations of increasing dimensions" Lasserre [2006]. The efficiency of SparsePOP to approximate optimal solutions of POPs is thus increased, and larger-scale POPs can be handled.
研究論文（学術雑誌）, 英語

Equality based contraction of semidefinite programming relaxations in polynomial optimization
Cong Vo; Masakazu Muramatsu; Masakazu Kojima
Journal of Operations Research Society of Japan, ELSEVIER SCI LTD, 51巻, 1号, 掲載ページ 111-125, 出版日 2008年03月, 査読付, The SDP (semidefinite programming) relaxation for general POPs (polynomial optimization problems), which was proposed as a method for computing global optimal solutions of POPs by Lasserre, has become an active research subject recently. We propose a new heuristic method exploiting the equality constraints in a given POP, and strengthen the SDP relaxation so as to achieve faster convergence to the global optimum of the POP. We can apply this method to both of the dense SDP relaxation which was originally proposed by Lasserre, and the sparse SDP relaxation which was later proposed by Kim, Kojima, Muramatsu and Waki. Especially, our heuristic method incorporated into the sparse SDP relaxation method has shown a promising performance in numerical experiments on large scale sparse POPs. Roughly speaking, we induce valid equality constraints from the original equality constraints of the POP, and then use them to convert the dense or sparse SDP relaxation into a new stronger SDP relaxation. Our method is enlightened by some strong theoretical results on the convergence of SDP relaxations for POPs with equality constraints provided by Lasserre, Parrilo and Laurent, but we place the main emphasis on the practical aspect to compute more accurate lower bounds of larger sparse POPs.
研究論文（学術雑誌）, 英語

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones
Masakazu Kojima; Masakazu Muramatsu
Mathematical Programming, 110巻, 2号, 掲載ページ 315-336, 出版日 2007年07月, 査読付
研究論文（学術雑誌）, 英語

Towards a pivoting procedure for a class of second-order cone programming problems having multiple cone constraints
Masakazu Muramatsu
Pacific Journal of Optimization, 3巻, 掲載ページ 87-98, 出版日 2007年01月, 査読付
研究論文（学術雑誌）, 英語

囲碁における連数の最大値について
宮代隆平; 矢野洋平; 村松正和
情報処理学会論文誌, 48巻, 掲載ページ 3463-3469, 出版日 2007年, 査読付
研究論文（学術雑誌）, 日本語

A pivoting procedure for a class of second-order cone programming
M Muramatsu
OPTIMIZATION METHODS & SOFTWARE, TAYLOR & FRANCIS LTD, 21巻, 2号, 掲載ページ 295-314, 出版日 2006年04月, 査読付, We propose a pivoting procedure for a class of second-order cone programming (SOCP) problems having one second-order cone, but possibly with additional non-negative variables. We introduce a dictionary, basic variables, nonbasic variables, and other necessary concepts to define a pivot for this class of SOCP problems. In a pivot, two-dimensional SOCP subproblems are solved to decide which variables should be entering or leaving the basis. Under a nondegeneracy assumption, we prove that the objective function value is strictly decreasing by a pivot unless the current basic solution is optimal. We also propose an algorithm using the pivoting procedure which has a global convergence property.
研究論文（学術雑誌）, 英語

２次錐計画のサブクラスに対する単体法的アルゴリズムにおけるピボット選択規則について
栗田圭介; 村松正和
統計数理, 53巻, 掲載ページ 349-360, 出版日 2006年
研究論文（学術雑誌）, 日本語

Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity
H Waki; S Kim; M Kojima; M Muramatsu
SIAM JOURNAL ON OPTIMIZATION, SIAM PUBLICATIONS, 17巻, 1号, 掲載ページ 218-242, 出版日 2006年, 査読付, Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of the supports for sums of squares ( SOS) polynomials that lead to efficient SOS and semidefinite program ( SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.
研究論文（学術雑誌）, 英語

An efficient support vector machine cone programming for learning method with second-order large-scale problems
R Debnath; M Muramatsu; H Takahashi
APPLIED INTELLIGENCE, SPRINGER, 23巻, 3号, 掲載ページ 219-239, 出版日 2005年12月, 査読付, In this paper we propose a new fast learning algorithm for the support vector machine (SVM). The proposed method is based on the technique of second-order cone programming. We reformulate the SVM's quadratic programming problem into the second-order cone programming problem. The proposed method needs to decompose the kernel matrix of SVM's optimization problem, and the decomposed matrix is used in the new optimization problem. Since the kernel matrix is positive semidefinite, the dimension of the decomposed matrix can be reduced by decomposition (factorization) methods. The performance of the proposed method depends on the dimension of the decomposed matrix. Experimental results show that the proposed method is much faster than the quadratic programming solver LOQO if the dimension of the decomposed matrix is small enough compared to that of the kernel matrix. The proposed method is also faster than the method proposed in (S. Fine and K. Scheinberg, 2001) for both low-rank and full-rank kernel matrices. The working set selection is an important issue in the SVM decomposition (chunking) method. We also modify Hsu and Lin's working set selection approach to deal with large working set. The proposed approach leads to faster convergence.
研究論文（学術雑誌）, 英語

A unified class of directly solvable semidefinite programming problems
M Muramatsu
ANNALS OF OPERATIONS RESEARCH, SPRINGER, 133巻, 1-4号, 掲載ページ 85-97, 出版日 2005年01月, 査読付, We propose a class of semidefinite programming (SDP) problems for which an optimal solution can be calculated directly, i.e., without using an iterative method. Several classes of such SDP problems have been proposed. Among them, Vanderbei and Yang (1995), Ohara (1998), and Wolkovicz (1996) are well known. We show that our class contains all of the three classes as special cases.
研究論文（学術雑誌）, 英語

The support vector machine learning using the second order cone programming
R Debnath; M Muramatsu; H Takahashi
2004 IEEE INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORKS, VOLS 1-4, PROCEEDINGS, IEEE, 掲載ページ 2991-2996, 出版日 2004年, 査読付, In this paper we propose a data dependent learning method for the support vector machine. This method is based on the technique of second order cone programming. We reformulate the SVM's quadratic problem into the second order cone problem. The proposed method requires to decompose the kernel matrix of SVM optimization problem. In this paper we apply Cholesky decomposition method. Since the kernel matrix is positive semidefinite, some columns of the decomposed matrix diminish. The performance of the proposed method depends on the reduction of dimensionality of the decomposed matrix. Computational results show that when the columns of decomposed matrix are small enough, the proposed method is much faster than the quadratic programming solver LOQO.
研究論文（国際会議プロシーディングス）, 英語

A new model for large margin classifiers by second order cone programming
R Debnath; M Muramatsu; H Takahashi
IC-AI '04 & MLMTA'04 , VOL 1 AND 2, PROCEEDINGS, C S R E A PRESS, 掲載ページ 877-882, 出版日 2004年, 査読付, In this paper, we propose a new method which can obtain the maximal margin hyperplane in the classification problem We formulate the classification problem into the second order cone programming problem. The proposed method deals with multi-class problems in a natural way unlike the support vector machine. This method does not necessitate all training data for learning, and thus reduces the learning time. Both theoretic and experimental results show the viability of the proposed method.
研究論文（国際会議プロシーディングス）, 英語

Generalization of Kernel PCA and Automatic Parameter Tuning
Takahide Nogayama; Masakazu Muramatsu; Haruhisa Takahashi
Proccedings of The ANZIIS 2003 Conference, 掲載ページ 173-178, 出版日 2003年12月, 査読付
研究論文（国際会議プロシーディングス）, 英語

A new second-order cone programming relaxation for max-cut problems
M Muramatsu; T Suzuki
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, ELSEVIER SCI LTD, 46巻, 2号, 掲載ページ 164-177, 出版日 2003年06月, 査読付, We propose a new relaxation scheme for the MAX-CUT problem using second-order cone programming. We construct relaxation problems to reflect the structure of the original graph. Numerical experiments show that our relaxation gives better bounds than those based on the spectral decomposition proposed by Kim and Kojima [16], and that the efficiency of the branch-and-bound method using our relaxation is comparable to that using semidefinite relaxation in some cases.
研究論文（学術雑誌）, 英語

On a commutative class of search directions for linear programming over symmetric cones
M Muramatsu
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, KLUWER ACADEMIC/PLENUM PUBL, 112巻, 3号, 掲載ページ 595-625, 出版日 2002年03月, 査読付, The commutative class of search directions for semidefinite programming was first proposed by Monteiro and Zhang (Ref. 1). In this paper, we investigate the corresponding class of search directions for linear programming over symmetric cones, which is a class of convex optimization problems including linear programming, second-order cone programming, and semidefinite programming as special cases. Complexity results are established for short-step, semilong-step, and long-step algorithms. Then, we propose a subclass of the commutative class for which we can prove polynomial complexities of the interior-point method using semilong steps and long steps. This subclass still contains the Nesterov-Todd direction and the Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro direction. An explicit formula to calculate any member of the class is also given.
研究論文（学術雑誌）, 英語

直列型生産ラインシステムにおける最適加工容量配分問題と その二次錐計画法による解法
石塚陽; 村松正和; 鷺森崇
日本経営工学会論文誌, 公益社団法人 日本経営工学会, 52巻, 6号, 掲載ページ 363-372, 出版日 2002年, 査読付, 直列型生産システムにおける最適加工容量(サービス率)配分問題を定式化し, 二次錐計画法による解法を提案する.問題は, 総加工容量(サービス率の総和)が与えられたもとで, 定常状態におけるスループットを最大にするような各工程への加工容量配分をもとめることである.スループットの厳密な値を求めることは一般に困難であるので, ここではいわゆる「サンプルパス最適化」に基づくアプローチを採用する.すなわち, ある固定された乱数系列のもとでのシミュレーションから求まるスループットの近似値を最大化することにより近似最適配分を求めるというものである.この近似スループットの最大化問題が多数の線形制約条件と少数の二次錐制約条を有する二次錐計画問題に変換できることを示し, 効率的なアルゴリズムを構築する.数値実験により, 本論文の方法が100工程を超える大規模なシステムに対しても適用可能であることを示す.
研究論文（学術雑誌）, 日本語

The Gauss-Newton direction in semidefinite programming
S Kruk; M Muramatsu; F Rendl; RJ Vanderbei; H Wolkowicz
OPTIMIZATION METHODS & SOFTWARE, GORDON BREACH PUBLISHING, TAYLOR & FRANCIS GROUP, 15巻, 1号, 掲載ページ 1-28, 出版日 2001年, 査読付, Most of the directions used in practical interior-point methods far semidefinite programming try to follow the approach used in linear programming, i.e., they are defined using the optimality conditions which are modified with a symmetrization of the perturbed complementarity conditions to allow for application of Newton's method. It is now understood that all the Monteiro-Zhang family, which include, among others, the popular AHO, NT, HKM, Gu, and Toh directions, can be expressed as a scaling of the problem data and of the iterate followed by the solution of the AHO system of equations, followed by the inverse scaling. All these directions therefore share a defining system of equations.
The focus of this work is to propose a defining system of equations that is essentially different from the AHO system: the over-determined system obtained from the minimization of a nonlinear equation. The resulting solution is called the Gauss-Newton search direction. We state some of the properties of this system that make it attractive for accurate solutions of semidefinite programs. We also offer some preliminary numerical results that highlight the conditioning of the system and the accuracy of the resulting solutions.
研究論文（学術雑誌）, 英語

Commutative class and power class of search directions for symmetric cone linear programming
M.Muramatsu
The first Sino-Japan Optimization Meeting，香港，中国, 0巻, 出版日 2000年10月
研究論文（国際会議プロシーディングス）, 英語

On network simplex method using the primal-dual symmetric pivoting rule
M Muramatsu
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, OPERATIONS RES SOC JAPAN, 43巻, 1号, 掲載ページ 149-161, 出版日 2000年03月, 査読付, We consider a network simplex method using the primal-dual symmetric pivoting rule proposed by Chen, Pardalos, and Saunders. For minimum-cost network-flow problems, we prove global convergence of the algorithm and propose a new scheme in which the algorithm can start from an arbitrary pair of primal and dual feasible spanning trees. For shortest-path problems, we prove the strongly polynomial time complexity of the algorithm.
研究論文（学術雑誌）, 英語

Primal-dual affine-scaling algorithms fail for semidefinite programming
M Muramatsu; RJ Vanderbei
MATHEMATICS OF OPERATIONS RESEARCH, INST OPERATIONS RESEARCH MANAGEMENT SCIENCES, 24巻, 1号, 掲載ページ 149-175, 出版日 1999年02月, 査読付, In this paper, we give an example of a semidefinite programming problem in which primal-dual affine-scaling algorithms using the HRVW/KSH/M, MT, and AHO directions fail. We prove that each of these algorithms can generate a sequence converging to a non-optimal solution and that, for the AHO direction, even its associated continuous trajectory can converge to a non-optimal point. In contrast with these directions, we show that the primal-dual affine-scaling algorithm using the NT direction for the same semidefinite programming problem always generates a sequence converging to the optimal solution. Both primal and dual problems have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and are nondegenerate everywhere.
研究論文（学術雑誌）, 英語

Affine scaling algorithm fails for semidefinite programming
M Muramatsu
MATHEMATICAL PROGRAMMING, ELSEVIER SCIENCE BV, 83巻, 3号, 掲載ページ 393-406, 出版日 1998年11月, 査読付, In this paper, we introduce an affine scaling algorithm for semidefinite programming (SDP), and give an example of a semidefinite program such that the affine scaling algorithm converges to a non-optimal point. Both our program and its dual have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and they are non-degenerate everywhere. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
研究論文（学術雑誌）, 英語

Convergence analysis of the projctive scaling aigorithm based on a long-step homogeneous affine scaling aigorithm(共著)
Masakazu Muramatsu; Takashi Tsuchiya
Mathematical programming, ELSEVIER SCIENCE BV, 72巻, 3号, 掲載ページ 291-305, 出版日 1996年03月, 査読付, In this paper we give a new convergence analysis of a projective scaling algorithm. We consider a long-step affine scaling algorithm applied to a homogeneous linear programming problem obtained from the original linear programming problem. This algorithm takes a fixed lambda less than or equal to 2/3 of the way towards the boundary of the nonnegative orthant at each iteration. The iteration sequence for the original problem is obtained by pulling back the homogeneous iterates onto the original feasible region with a conical projection, which generates the same search direction as the original projective scaling algorithm at each iterate. The recent convergence results for the long-step affine scaling algorithm by the authors are applied to this algorithm to obtain some convergence results on the projective scaling algorithm. Specifically, we will show (i) polynomiality of the algorithm with complexities of O(nL) and O(n(2)L) iterations for lambda < 2/3 and lambda = 2/3, respectively; (ii) global convergence of the algorithm when the optimal face is unbounded; (iii) convergence of the primal iterates to a relative interior point of the optimal face; (iv) convergence of the dual estimates to the analytic center of the dual optimal face; and (v) convergence of the reduction rate of the objective function value to 1 - lambda.
研究論文（学術雑誌）, 英語

An affine scaling method with an infeasible starting point : analysis under nondegeneracy assumption(共著)
M Muramatsu; T Tsuchiya
Annals of Operations Research, BALTZER SCI PUBL BV, 62巻, 掲載ページ 325-355, 出版日 1996年, 査読付, In this paper, we propose an infeasible-interior-point algorithm for linear programming based on the affine scaling algorithm by Dikin. The search direction of the algorithm is composed of two directions, one for satisfying feasibility and the other for aiming at optimality. Both directions are affine scaling directions of certain linear programming problems. Global convergence of the algorithm is proved under a reasonable nondegeneracy assumption. A summary of analogous global convergence results without any nondegeneracy assumption obtained in [17] is also given.
研究論文（学術雑誌）, 英語

Affine scaling algorithm fails for semidefinite programming
MURAMATSU M.
2, 掲載ページ 16, 出版日 1996年
英語

Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems (共著)
Takashi Tsuchiya; Masakazu Muramatsu
SIAM Journal on Optimization, SIAM PUBLICATIONS, 5巻, 3号, 掲載ページ 525-551, 出版日 1995年08月, 査読付, In this paper we present new global convergence results on a long-step affine scaling algorithm obtained by means of the local Karmarkar potential functions. This development was triggered by Dikin's interesting result on the convergence of the dual estimates associated with a long-step affine scaling algorithm for homogeneous LP problems with unique optimal solutions. Without requiring any assumption on degeneracy, we show that moving a fixed proportion lambda up to two-thirds of the way to the boundary at each iteration ensures convergence of the iterates to an interior point of the optimal face as well as the dual estimates to the analytic center of the dual optimal face, where the asymptotic reduction rate of the value of the objective function is 1-lambda. We also give an example showing that this result is tight to obtain convergence of the dual estimates to the analytic center of the dual optimal face.
研究論文（学術雑誌）, 英語

Infeasibility Detection in an Affine Scaling Infeasible Interior Doint Algorithm
Research Memorandum The Institute of Statistical Mathematics, 553号, 出版日 1995年
研究論文（大学，研究機関等紀要）, 英語

A Convergence analysis of a long-step variant of the projective scaling algorithm (共著)
Research Memorandum, (]G0061[)454 The Institute of Statistical Mathematics, 出版日 1993年
研究論文（大学，研究機関等紀要）, 英語

An affine scaling method with an infeasible Starting Point (共著)
MURAMATSU M.
Research Memorandum (]G0061[)490, The Institute of Statistical Mathematics, The Institute of Statistical Mathematics, 出版日 1993年
研究論文（大学，研究機関等紀要）, 英語

1-G-4 さまざまなグラフにおける情報拡散ゲームのナッシュ均衡に関する考察(学生セッション:意思決定)
櫻井 亮佑; 村松 正和; 高橋 里司; 保木 邦仁
公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2015年03月26日, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015巻, 掲載ページ 144-145, 日本語, 110009981417, AN00351206

完全正値性の判定に関する数値実験 (最適化アルゴリズムの進展 : 理論・応用・実装)
田口 良典; 高橋 里司; 村松 正和
京都大学, 出版日 2015年01月, 数理解析研究所講究録, 1931巻, 掲載ページ 37-46, 日本語, 1880-2818, 110009881112, AN00061013

面の話
村松正和
近年,半正定値計画や共正他計画といった新しい最適化問題が出現しているが,その基礎となるのは凸錐や凸集合といった概念である.凸集合には「面」と呼ばれる概念があるが,それは通常の多面体における面とはやや異なった定義であり,その差異に注意すべき点がある.本稿では,凸集合や凸錐における「面」について,基本的な部分から最新の結果までを,筆者の気の趣くままに紹介する., 日本オペレーションズ・リサーチ学会, 出版日 2014年, オペレーションズ・リサーチ, 59巻, 1号, 掲載ページ 5-10, 日本語, 招待, 記事・総説・解説・論説等（その他）, 0030-3674, 110009686612, AN00364999

ジョルダン代数
脇隼人; 村松正和
公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2010年11月, オペレーションズ・リサーチ, 55巻, 11号, 掲載ページ 718-719, 日本語, 記事・総説・解説・論説等（その他）, 0030-3674, 110007880839, AN00364999

コンピュータ囲碁の飛躍の背景
美添一樹; 村松正和
日本評論社, 出版日 2010年10月, 数学セミナー, 49巻, 10号, 掲載ページ 52-27, 日本語, 記事・総説・解説・論説等（その他）, 0386-4960, 40017291503, AN10333470

二次錐計画
脇隼人; 村松正和
出版日 2010年10月, オペレーションズ・リサーチ, 55巻, 10号, 掲載ページ 655-656, 日本語, 記事・総説・解説・論説等（その他）

A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones
Masakazu Kojima; Masakazu Muramatsu
出版日 2009年, Computational Optimization and Applications, 42巻, 1号, 掲載ページ 31-41, 英語, 査読付, 0926-6003, 10025482257

プロ棋士対コンピュータ：FIT2008 における囲碁対局報告
村松正和
出版日 2009年01月, 情報処理, 50巻, 1号, 掲載ページ 70-73, 日本語, 記事・総説・解説・論説等（その他）

連続最適化における未解決問題
村松正和
連続最適化の理論的研究における未解決問題を,特に,線形計画,錐線形計画,多項式計画,2次計画の各テーマに絞って紹介する., 公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2008年01月, オペレーションズ・リサーチ, 53巻, 1号, 掲載ページ 10-14, 日本語, 記事・総説・解説・論説等（その他）, 0030-3674, 110006532513, AN00364999

半正定値計画と内点法
村松正和
出版日 2007年, オペレーションズ・リサーチ, 52巻, 掲載ページ 513-518, 日本語, 記事・総説・解説・論説等（その他）, 10020194073

多項式計画と錐線形計画ーー非線形計画への線形計画からのアプローチ
村松正和
出版日 2006年, システム／制御／情報, 50巻, 掲載ページ 8-13, 日本語, 記事・総説・解説・論説等（その他）

多項式計画と錐線形計画–非線形計画への線形計画からのアプローチ
村松正和
出版日 2006年, システム／制御／情報, 50巻, 掲載ページ 8-13, 日本語, 記事・総説・解説・論説等（その他）

錐線形計画への招待
村松正和
出版日 2003年, システム／制御／情報, 47巻, 5号, 掲載ページ 223-228, 日本語, 査読付, 記事・総説・解説・論説等（その他）

「アイスクリーム・コーンの中には何がある?」
村松正和
出版日 2000年, (Introduction to the second-order cone programming problems)アイ・サイ問答教室，システム/制御/情報, 44巻, 9号, 掲載ページ 541-542, 日本語, 査読付, 記事・総説・解説・論説等（その他）

あたらしい数理最適化
久保幹雄; J.P.ペドロソ、A. レイス; 村松正和
日本語, 共著, 近代科学社, 出版日 2012年

最適化法
田村明久; 村松正和
日本語, 共著, 共立出版株式会社, 出版日 2002年04月

新編OR事典(共著)
村松正和
日本語, 日本オペレーションズ・リサーチ学会, 出版日 2000年

経営科学OR用語大辞典(共著)朝倉書店
日本語, 出版日 1999年

居酒屋チェーン店における従業員の勤務表作成問題
中村克; 村松正和
口頭発表（一般）, 日本OR学会2023年度春季研究発表会
発表日 2023年03月07日

A Variant of Knapsack Problem Efficient for Benders Decomposition
Kosuke Aratani; Masakazu Muramatsu
口頭発表（一般）, 13th International Congress on Advanced Applied Informatics Winter, 査読付
発表日 2022年12月

居酒屋スタッフのスケジューリング問題
中村克; 村松正和
口頭発表（一般）, 日本OR学会2022年度春季研究発表会
発表日 2022年03月18日

木の最小シュタイナー支配集合
古舘周平; 村松正和
口頭発表（一般）, 日本OR学会2022年春季研究発表会
発表日 2022年03月17日

小型電動固定翼の交通網の設計
和田和馬; 村松正和
口頭発表（一般）, 日本語, 日本OR学会 2022年春季研究発表会
発表日 2022年03月17日

非線形計画って何だろう？
村松正和
口頭発表（招待・特別）, 日本語, モデリングを通して見えた世界, 招待, 国内会議
発表日 2022年03月12日

Solving SDP completely with an interior point oracle
Masakazu Muramatsu
口頭発表（招待・特別）, 英語, International Conference on Nonlinear Analysis and Convex Analysis (NACA) and International Conference on Optimization: Techniques and Applications (ICOTA), 招待, NACA and ICOTA Organizing Committee, Hakodate, Japan, 国際会議
発表日 2019年08月31日

A 2-approximation algorithm for minimum knapsack problem with single continuous variable
Yuki Kimura; Masakazu Muramatsu
口頭発表（一般）, 英語, International Conference on Nonlinear Analysis and Convex Analysis and International Conference on Optimization Techniques and Applications, NACA-ICOTA Organizing Committee, Hakodate, Japan, 国際会議
発表日 2019年08月30日

Solving SDP by projection and rescaling algorithms
Natsuki Okamura; Bruno F. Lourenco; Masakazu Muramatsu
口頭発表（一般）, 英語, International Conference on Continuous Optimization 2019, Mathematical Optimization Society, Berlin, 国際会議
発表日 2019年08月07日

Extensions of Chubanov’s Projection and Rescaling Algorithms
Masakazu Muramatsu
口頭発表（一般）, 英語, Numerical Verification (NIVEA) 2019, 国際会議
発表日 2019年02月27日

Extensions of Projection and Rescaling Algorithms
Masakazu Muramatsu
口頭発表（招待・特別）, 英語, International Workshop on Control and Optimization, 招待, 豊田理化学研究所・特定課題研究 「制御工学研究者と応用数学研究者の連携による革新的な制御理論構築」, 京都大学, 国際会議
発表日 2018年08月07日

Extensions of Projection and Rescaling Algorithms
Masakazu Muramatsu
口頭発表（招待・特別）, 英語, International Symposium on Control and Optimization, 招待, 豊田理化学研究所・特定課題研究 「制御工学研究者と応用数学研究者の連携による革新的な制御理論構築」, 京都大学, 国際会議
発表日 2018年08月07日

An extension of Chubanov’s algorithm to symmetric cone programming
Masakazu Muramatsu
口頭発表（招待・特別）, 英語, ISMP 2018, 招待, Mathematical Optimization Society, Bordeaux, France., 国際会議
発表日 2018年07月03日

Comparative Performance of Green Pipe, Green Hose, and Green Hose-Rectangle Models in Power Efficient Network
Masakazu Muramatsu
口頭発表（一般）, 英語, IEEE-CQR 2018, 国際会議
発表日 2018年05月15日

錐線形計画と Facial Reduction への招待
村松正和
口頭発表（招待・特別）, 日本語, 第60回自動制御連合講演会, 自動制御連合講演会, 国内会議
発表日 2017年11月10日

錐線形計画と Facial Reduction への招待
村松正和
口頭発表（招待・特別）, 日本語, 第60回自動制御連合講演会, 自動制御連合講演会, 電気通信大学, 国内会議
発表日 2017年11月10日

Chubanov による同次線形計画問題の内点許容解を求めるアルゴリズムとその拡張に関する最近の展開
村松正和
口頭発表（招待・特別）, 日本語, RAMPシンポジウム2017, 招待, 日本オペレーションズ・リサーチ学会数理計画研究部会, 筑波大学, http://infoshako.sk.tsukuba.ac.jp/~ramp/index.html, 国内会議
発表日 2017年10月13日

Chubanov による同次線形計画問題の内点許容解を求めるアルゴリズムとその拡張に関する最近の展開
村松正和
口頭発表（招待・特別）, 日本語, RAMPシンポジウム2017, 招待, 日本オペレーションズ・リサーチ学会数理計画研究部会, 筑波大学, http://infoshako.sk.tsukuba.ac.jp/~ramp/index.html, 国内会議
発表日 2017年10月13日

同次対称錐計画問題の内点実行可能解を求める新しいアルゴリズム
村松正和
口頭発表（一般）, 日本語, 数理最適化の発展：モデル化とアルゴリズム, 数理解析研究所, 数理解析研究所, https://sites.google.com/site/narushimalab/krims2017, 国内会議
発表日 2017年08月25日

Partial Polyhedrality and Facial Reduction
Masakazu Muramatsu; Bruno Lourenco; Takashi Tsuchiya
口頭発表（一般）, 英語, SIAM Conference on Optimization 17, 招待, Society for Industrial and Applied Mathematics, Vancouver, Canada., https://www.siam.org/meetings/op17/, 国際会議
発表日 2017年05月24日

Network Congestion Minimization Models Based on Robust Optimization
Bimal Chandra Das
口頭発表（一般）, 英語, 研究集会「最適化：モデリングとアルゴリズム」, 統計数理研究所, 東京都立川市, 国内会議
発表日 2017年03月23日

An extension of Chubanov's algorithm to symmetric cone feasibility problems
Bruno F. Lourenco
口頭発表（一般）, 日本語, 研究集会「最適化：モデリングとアルゴリズム」, 統計数理研究所, 東京都立川市, 国内会議
発表日 2017年03月23日

対称錐に対する Chubanov のアルゴリズムの拡張
Bruno F. Lourenco
口頭発表（一般）, 日本語, 日本オペレーションズ・リサーチ学会2017年春季研究発表会, 日本オペレーションズ・リサーチ学会, 沖縄県那覇市, 国内会議
発表日 2017年03月17日

三角形総面積最大化問題に関する研究
市橋志朗
口頭発表（一般）, 日本語, 日本オペレーションズ・リサーチ学会2017年春季研究発表会, 日本オペレーションズ・リサーチ学会, 沖縄県那覇市, 国内会議
発表日 2017年03月16日

A new algorithm for finding an interior feasible point of a homogeneous linear symmetric cone system
Masakazu Muramatsu; Bruno F. Lourenco; Tomonari Kitahara; Takashi Tsuchiya
口頭発表（招待・特別）, 英語, 2nd ISM-ZIB-IMI MODAL Workshop on Mathematical Optimization and Data Analysis, 招待, The Institute of Statistical Mathematics, Zuse Institute of Berlin, Institute of Math for Industry., Berlin, Germany, http://www.zib.de/node/3105, 国際会議
発表日 2017年

A new algorithm for finding an interior feasible point of a homogeneous linear symmetric cone system
Masakazu Muramatsu; Bruno F. Lourenco; Tomonari Kitahara; Takashi Tsuchiya
口頭発表（招待・特別）, 英語, 2nd ISM-ZIB-IMI MODAL Workshop on Mathematical Optimization and Data Analysis, 招待, The Institute of Statistical Mathematics, Zuse Institute of Berlin, Institute of Math for Industry., Berlin, Germany, 国際会議
発表日 2017年

内点オラクルによる錐線形計画問題の完全な求解
Bruno F. Lourenco
口頭発表（一般）, 日本語, 日本オペレーションズ・リサーチ学会秋季研究発表会, 日本オペレーションズ・リサーチ学会, 国内会議
発表日 2016年09月16日

Weak Infeasibility, Facial Reduction, and Geometry in Conic Programming
Masakazu Muramatsu
口頭発表（一般）, 英語, International Conference on Continous Optimization 2016, Mathematical Optimization Society, Tokyo, Japan, http://www.iccopt2016.tokyo, 国際会議
発表日 2016年08月09日

Solving SDP completely with an Interior-Point Oracle
Takashi Tsuchiya
口頭発表（一般）, 英語, International Conference on Continous Optimization 2016, Mathematical Optimization Society, Tokyo, Japan, http://www.iccopt2016.tokyo, 国際会議
発表日 2016年08月09日

A Mixed-Integer SOCP Model for Robust and Power Efficient Networks
Bimal Chandra Das
ポスター発表, 英語, International Conference on Continous Optimization 2016, Mathematical Optimization Society, Tokyo, Japan, 国際会議
発表日 2016年08月09日

FRA-Poly, Partial Polyhedrality and Facial Reduction
Bruno F. Lourenco
口頭発表（一般）, 英語, International Conference on Continuous Optimization 2016, Mathematical Optimization Society, Tokyo, Japan, http://www.iccopt2016.tokyo, 国際会議
発表日 2016年08月08日

さまざまなグラフにおける情報拡散ゲームの ナッシュ均衡に関する考察
櫻井亮佑; 村松正和; 高橋里司; 保木邦仁
口頭発表（一般）, 日本語, 日本OR学会春季研究発表会, 日本OR学会, 国内会議
発表日 2015年03月26日

Weak Status of Conic Programming
Masakazu Muramatsu
口頭発表（招待・特別）, 英語, First Pacific Optimization Conference, 招待, Jiangnan University, Wuxi, China, http://poc2014.jiangnan.edu.cn/index.htm, In this talk, we look at the weak status of conic programming problems from the following viewpoints: (i) How the weak status causes numerical difficulty in solving problems, (ii) How to recover the strong status of conic programming, (iii) How to exploit the weak status in a positive way to solve specific problems, and (iv) A geometric structure of the weak status of SDP., 国際会議
発表日 2014年10月31日

Monte-Carlo Simulation Adjusting
Nobuo Araki; Masakazu Muramatsu; Kunihito Hoki; Satoshi Takahashi
ポスター発表, 英語, AAAI 2014, THE ASSOCIATION FOR THE ADVANCEMENT OF ARTIFICIAL INTELLIGENCE (AAAI), Quebec city, Canada, 国際会議
発表日 2014年07月

面の話 PartII
村松正和
公開講演，セミナー，チュートリアル，講習，講義等, 日本語, 最適化の理論と応用 -- 未来を担う若手研究者の集い 2014, 招待, 日本OR学会「最適化の理論と応用」研究部会, 筑波大学, http://www.misojiro.t.u-tokyo.ac.jp/~y-koba/SOTA/mirai14.html, 国内会議
発表日 2014年06月01日

A Geometrical Analysis of Weak Infeasibility in Semidefinite Programming and Related Issues
Bruno Lourenco; Masakazu Muramatsu; Takashi Tsuchiya
口頭発表（一般）, 英語, SIAM Conference on Optimization, SIAM, San Diego, USA, 国際会議
発表日 2014年05月22日

モンテカルロ木探索における予測読みに関する研究
モンテカルロ木探索における予測読みに関する研究; 荒井 光; 村松正和
口頭発表（一般）, 日本語, エンターテイメントと認知科学シンポジウム, 電気通信大学 エンターテイメントと認知科学研究ステーション, 電気通信大学, http://entcog.c.ooco.jp/entcog/contents/symposium/date/20150319.html, 国内会議
発表日 2014年03月20日

低ランク整数完全正値行列 の判定について
川瀬 弘樹; 村松 正和; 高橋 里司
口頭発表（一般）, 日本語, 日本オペレーションズ・リサーチ学会春季研究発表会, 日本オペレーションズ・リサーチ学会, 大阪大学, 国内会議
発表日 2014年03月07日

2次元トーラスグラフ上での情報拡 散ゲームにおけるナッシュ均衡
祐成友樹; 村松正和
口頭発表（一般）, 日本語, 日本オペレーションズ・リサーチ学会秋季研究発表会, 日本オペレーションズ・リサーチ学会, 徳島大学, 国内会議
発表日 2013年09月12日

Adaptive SDP relaxation for Polynomial Optimization
Masakazu Muramatsu
口頭発表（一般）, 英語, ICCOPT 2013, Mathematical Optimization Society, 国際会議
発表日 2013年07月31日

多項式計画に対する半正定値緩和
村松正和
口頭発表（招待・特別）, 日本語, 組合せ最適化セミナー, 招待, 国内会議
発表日 2012年07月

情報拡散ゲームにおけるナッシュ均衡 についての一考察
伊藤彰宏; 村松正和
口頭発表（一般）, 日本語, 日本OR学会,日本OR学会2011年度春季研究発表会
発表日 2012年03月

東京23区踏破問題の解法
祐成友樹; 村松正和
口頭発表（一般）, 日本語, 日本OR学会,日本OR学会2011年度春季研究発表会
発表日 2012年03月

多項式計画に対する半正定値緩和の不思議な性質
村松正和
口頭発表（招待・特別）, 日本語, ワークショップ「最適化理論の産業・諸科学への応用」, 九州大学マスフォアインダストリ研究所
発表日 2011年10月

多項式計画に対する半正定値緩和の不思議な性質
村松正和
口頭発表（招待・特別）, 日本語, ワークショップ「最適化理論の産業・諸科学への応用」, 九州大学マスフォアインダストリ研究所, 福岡県, 国際会議
発表日 2011年10月

Strange Behaviors of Interior-point Methods for Solving Semidefinite Programming Problems in Polynomial Optimization and their Reason
村松正和
シンポジウム・ワークショップパネル（公募）, 日本語, 最適化手法の深化と広がり, 京都大学数理解析研究所, 京都
発表日 2011年07月

半正定値計画問題に対する単体法の実装報告
加藤誉運; 田村明久; 山崎康史; 村松正和; 脇隼人
口頭発表（一般）, 日本語, 日本OR学会,２００９年度秋季研究発表会
発表日 2009年09月

Facial Reduction Algorithm and Conic Expansion Algorithm
Masakazu Muramatsu; Hayato Waki
口頭発表（一般）, 英語, ISMP2009
発表日 2009年08月

A Facial Reduction Algorithm for Semidefinite Programming Problems in Polynomial Optimization
Hayato Waki; Masakazu Muramatsu
口頭発表（一般）, 英語, ISMP2009
発表日 2009年08月

計算と最適化の新展開に向けて
久野誉人; 村松正和; 藤澤克樹
口頭発表（一般）, 日本語, 日本オペレーションズリサーチ学会,春期研究発表会
発表日 2009年03月

錐線形計画における錐の面的縮小と正則拡大およびその応用
村松正和; 脇隼人
口頭発表（一般）, 日本語, 日本オペレーションズリサーチ学会,春期研究発表会
発表日 2009年03月

A Facial Reduction Approach in Conic Programming
村松正和; 脇隼人
口頭発表（一般）, 日本語, SCOPE,日本オペレーションズリサーチ学会研究部会
発表日 2009年03月

Strange behaviors of interior-point mehtods for solving semidefinite programming problems in polynomial optimization
Hayato Waki; Masakazu Muramatsu
口頭発表（一般）, 英語, HPOPT2008
発表日 2008年06月

Semidefinite programming relaxation for polynomial optimization problems
Masakazu Muramatsu
口頭発表（招待・特別）, 英語, International Conference on Modeling, Computation and Optimization, Indian Statistical Institute, Delhi, India, 国際会議
発表日 2008年01月

Semidefinite programming relaxation for polynomial optimization problems
Masakazu Muramatsu
口頭発表（招待・特別）, 英語, International Conference on Modeling, Computation and Optimization, Indian Statistical Institute, Delhi, India, 国際会議
発表日 2008年01月

コンピュータ囲碁における局所的なヨミを用いた群分割について
山崎大輔; 橋本千裕; 村松正和
口頭発表（一般）, 日本語, エンターテイメントと認知科学研究ステーション,第一回エンターテイメントと認知科学シンポジウム
発表日 2007年03月

Aspects of SDP Relaxation for Polynomial Optimization
Masakazu Muramatsu
口頭発表（招待・特別）, 英語, Global Optimization -- Integrating Convexity, Optimization, Logic Programming, and Computational Algebraic Geometry, Erwin Schlodinger Institute for Mathematical Physics, Wien, Austria, 国際会議
発表日 2006年12月

A Sparse SDP Relaxation for Polynomial Optimization Problems over Symmetric Cones
村松正和; 小島政和
口頭発表（一般）, 英語, ISMP2006,ISMP2006
発表日 2006年08月

A Sparse SDP Relaxation for Polynomial Optimization Problems over Symmetric Cones
村松正和; 小島政和
口頭発表（一般）, 英語, INFORMS2006 Hong Kong
発表日 2006年06月

Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity
Masakazu Muramatsu; Masakazu Kojima; Sunyoung Kim; Hayato Waki
口頭発表（一般）, 英語, IFORS Hawaii
発表日 2005年07月

On a Simplex Method for a Class of Second-Order Cone Programming
Masakazu Muramatsu; Keisuke Kurita
口頭発表（一般）, 英語, SIAM Conference on Optimization
発表日 2005年05月

SparsePOP: A Sparse SDP relaxation of Polynomial Optimization Problems
Hayato Waki; Sunyoung Kim; Masakazu Kojima; Masakazu Muramatsu
口頭発表（一般）, 英語, Positive Polynomials
発表日 2005年03月

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones
Masakazu Kojima; Masakazu Muramatsu
シンポジウム・ワークショップパネル（公募）, 英語, HPOPT2004, HPOPT2004, Amsterdam
発表日 2004年06月

２次錐計画とその応用
村松正和
口頭発表（招待・特別）, 日本語, 第１５回RAMPシンポジウム, RAMP
発表日 2003年

対称錐上の線形計画に対する内点法における探索方向の可換族について
村松正和
口頭発表（招待・特別）, 日本語, 日本OR学会秋季研究発表会, 日本オペレーションズ・リサーチ学会
発表日 2003年

On Commutative Class of Search Directions for Symmetric Cone Programming
M.Muramatsu
口頭発表（一般）, 英語, International Symposium on Mathematical Programming, 国際会議
発表日 2000年08月

大学院総合コミュニケーション科学
The University of Electro-Communications

大学院総合コミュニケーション科学
電気通信大学

総合コミュニケーション科学
The University of Electro-Communications

総合コミュニケーション科学
電気通信大学

連続最適化基礎論
電気通信大学

連続最適化基礎論
電気通信大学

数理計画法
電気通信大学

数理計画法
電気通信大学

大学院技術英語
電気通信大学

Graduate Technical English
The University of Electro-Communications

大学院技術英語
電気通信大学

2022年04月 - 現在
電子情報通信学会

2007年 - 現在
情報処理学会

2000年04月 - 現在
日本応用数理学会

1999年 - 現在
SIAM(Society for Industrial and Applied Mathematics)

1994年04月 - 現在
日本OR学会

1994年 - 現在
Mathematical Optimization Society

無限次元統計モデルに基づくベイズ予測理論の構築とデータ解析手法の開発
駒木 文保; 諸星 穂積; 村松 正和; 田中 冬彦; 奥戸 道子
日本学術振興会, 科学研究費助成事業, 東京大学, 基盤研究(A), 22H00510
研究期間 2022年04月01日 - 2027年03月31日

悪条件錐線形計画問題の理論とアルゴリズム
村松正和
錐線形計画は様々なサブクラスあるいは応用が提案されており、近年研究の発展が目覚まし い。その中で、錐線形計画の実用化において大きな障害となっているのが「悪条件な問題」 の存在である。悪条件の極限として退化がある。悪条件あるいは退化した錐線形計画問題 は実用において頻繁に出現するにもかかわらず、従来のアルゴリズムでは解くことができ ない。 本研究は、錐線形計画問題における悪条件性に関してその理解を深め、またそのような問 題に対応する新しいアルゴリズムを開発することにより、錐線形計画の裾野を広げ、実用 に足る段階へもっていくことを目的とする。
研究期間 2020年04月01日 - 2024年03月31日

面削減法を用いた錐線形計画の双対理論と誤差解析
村松正和
研究代表者
研究期間 2017年04月01日 - 2020年03月31日

現実世界の競争に近い複雑なゲームに対するヒューリスティック手法の適用
保木 邦仁; 西野 順二; 伊藤 毅志; 村松 正和
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 行動の選択肢が多く、状況や状態遷移を部分的にしか観測できない、現実世界における競争により近いゲームにおいて、既存ヒューリスティック手法の大規模化を達成することにより、競争に勝つ人工知能技術の開発を目指した。そして、囲碁、麻雀、大貧民、チェス、デジタルカーリングなどを題材にして人工知能の研究を行い、この目的を実現する新規アルゴリズムを開発し、論文としてこれらの成果を発表した。, 16K00503
研究期間 2016年04月01日 - 2020年03月31日

錐線形計画における退化とモデリング
村松正和
研究代表者
研究期間 2014年04月01日 - 2017年03月31日

潜在情報事前分布に基づくベイズ統計理論の構築と応用
駒木文保
研究期間 2014年04月01日

凸最適化の情報幾何:展開と応用
土谷 隆; 小原 敦美; 村松 正和; 福田 光浩
日本学術振興会, 科学研究費助成事業, 基盤研究(B), 半正定値計画問題および対称錐計画問題に対し,主双対内点法の反復回数が中心曲線上の情報幾何的積分で近似的に表現できることを理論的に示し,近似が非常によくあてはまることを,実用規模の問題に対する数値実験を通じて確認した.また,世界最大規模の34300次元の大規模ガウシアングラフィカルモデルの求解に成功した.大規模ガウシアングラフィカルモデル推定のための主双対内点法も開発した.悪条件の半正定値計画問題に対する正則化や面縮小法等の研究を実施した., 20340024
研究期間 2008年 - 2010年

非線形半正定値計画問題に対する数値的に安定した主双対内点法の開発
吉瀬 章子; 藤澤 克樹; 山本 芳嗣; 久野 誉人; 繁野 麻衣子; 村松 正和
日本学術振興会, 科学研究費助成事業, 筑波大学, 基盤研究(C), 本研究の目的は,非線形半正定値計画問題に対する主双対内点法を開発することである.半正定値計画問題は線形計画問題のような多面体ではない閉凸錐上の最適化問題であることから,漸近的な最適値は存在しても,最適解は存在しない(最適値に収束する点列が発散する)という現象が頻繁に発生する.このため線形半正定値計画問題に対する主双対内点法において,最適性の判定は常に数値的な困難をともなう.最適解の精度は,応用先である組合せ最適化問題やロバスト最適化問題に多大な影響をもたらす.このような理由により,線形半正定値計画問題の解法に対して,数値的な安定性を保証するためのさまざまな工夫が提案されてきた.非線形半正定値計画問題に対する主双対内点法を開発する上で,こうした数値的安定性に対する配慮はさらに必要不可欠である.本研究では特殊な同次モデルを用いることで,数値的な不安定さを軽減させることを試みた.この結果,凸非線形半正定値計画問題に対して, 1. 許容解の存在あるいは狭義許容解の存在を仮定しなくとも,有界で自明な初期点をもつパスが存在し, 2. 任意のパスの集積点は同次モデルの解であり, 3. 元の問題が解をもつのであれば,その集積点から有界な解が算出でき, 4. 元の問題が強非許容である場合は, Lipschitz連続の仮定のもとで,その集積点から非許容性を保証でき,さらに特に問題が線形である場合は, 5. 多項式時間の反復で十分な精度の解が得られることが保証できる,同次モデルと同次アルゴリズムの提案を行った., 18560052
研究期間 2006年 - 2007年

グラフィカルモデルの二次平均場近似と確率的情報処理への応用
高橋 治久; 村松 正和; 堀田 一弘
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 本研究では,神経間の相関をモデル化できる神経回路を構築し,それをパターン認識問題に応用することを目的として行った.最初に,従来のアナログ神経回路網を相関を考慮したモデルに拡張した.無向グラフィカルモデルとしてのマルコフランダムフィールド(MRF)のナイーブな平均場近似を考えれば,それはアナログニューラルネットワークとなるが,相関の情報は落とされ,直接的表現は不可能である.そこでMRFや条件付きマルコフ場(CRF)を共分散の情報を保存しながら,確定的モデルで近似する新しい平均場近似モデルを提案した.このモデルでは,位相変数を導入し,位相方程式により位相差のコサインが相関係数を表すことができる.位相方程式は,発振ニューラルネットワークの位相方程式と係数を除いて同様な形であり,位相同期と確率的相関の類似性を表している.このことは,発振ニューロンといういわば生理学的には不自然な情報処理形態を考えなくとも,通常のニューラルネットワークで,同様の情報処理が可能であることを示しているが,相関を表現できるのでそれ以上の能力がある.このモデルに対し,平均場近似としての精度を検証し,従来法より遙かに高精度であることを確認した.次にイレギュラーな局所最小値が出来ないことを実験的に確認した.最後に,パターン認識問題への応用を行い,共分散による出力を用いた場合,平均値を使うよりも格段に識別精度が上がることを確認した.これにより,もう一つの結論として,脳内表現では相関は分散以上に重要であることが分かった., 17500088
研究期間 2005年 - 2007年

離散・連続アプローチを融合した高度最適化システムの開発
今井 浩; 村松 正和; 土谷 隆; 今井 桂子; 室田 一雄; 浅野 孝夫
日本学術振興会, 科学研究費助成事業, 東京大学, 基盤研究(B), コンピュータによる最適化技法は,その適用範囲が広いことから,新手法の開発・発見は,非常に大きなインパクトを色々な分野に対して与える.本研究では,これまでに各分担者が独自に開発した線形計画法に対する内点法・計算幾何算法・マトロイド理論・論理関数理論を用いたシステム解析技法について,融合した共同研究を本研究を通して遂行することにより,新たな理論的成果を上げるとともに,そのソフトウェアシステムを開発することを目的とした. 本研究により,連続的な側面では線形計画の枠組を拡張した半正定値計画問題での内点法の拡張を行ない,離散的最適化の枠組からは離散凸理論の確立を果たした.これにより,線形計画問題と凸多面体を通して理解されていた連続構造と離散構造の橋渡しが,マトロイドや劣モジュラシステムなどをさらに拡張した枠組で可能になり,両方のアルゴリズム成果の融合が可能になった.この連続・離散の橋渡しを土台に,確率的手法を通した離散・連続アプローチの融合が実現した.具体的には,半正定値計画を論理式最大充足化問題に適用し,半正定値計画のレベルで連続値解を得た後,ランダム丸めすることにより離散解でよい近似解を構成し,詳細な解析を通して従来法を上回る近似性能の保証を可能にした.離散・連続の両面をもった幾何的最適化問題として辺長和最小3角形分割問題に取り組み,分枝切除法という連続性を活用した離散最適化のアプローチの有効性を実証した.離散システムの最も基本としての集合族を表現するモデルとして,論理関数処理法として注目されている2分決定グラフの理論を拡張し,集合族処理に適したアルゴリズムを開発するとともに,実際にシステムを開発して,その成果を広く公開している., 07555615
研究期間 1995年 - 1996年