Master of Engineering, The University of Tokyo, Mar. 1991

Ph. D., The Graduate University for Advanced Studies, Mar. 1994

Polynomial Optimization

Linear optimization

Nonlinear optimization

Second-order cone programming

Semidefinite programming

Conic linear programming

Operations research

Informatics, Mathematical informatics

Apr. 2020 - Present
The University of Electro-Communications, Organization for Education and Student Support Education Development Center, 大学教育センター長

Apr. 2020 - Present
The University of Electro-Communications, Vice President (Education)

Apr. 2008
Department of Computer and Network Engineering, The University of Electro-communications, Professor

Mar. 1994
The Graduate University for Advanced Studies, Graduate School, Division of Mathematical and Physical Science, 統計科学専攻

Mar. 1991
The University of Tokyo, Graduate School, Division of Engineering, 情報工学専攻

Mar. 1989
The University of Tokyo, Faculty of Engineering, 計数工学科

01 Apr. 1981 - 31 Mar. 1984
私立武蔵高校

Apr. 2018 - Mar. 2020
Editor-in-Chief, Journal of the Operations Research Society of Japan, The Operations Research Society of Japan, Society

Apr. 2009 - 2011
国際理事, 日本OR学会, Society

Mar. 2008
Fellow, Society

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

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

Sep. 2017
日本学術振興会, 書面審査において有意義な審査意見を付した専門委員を表彰するもの
有意義な審査意見を付した専門委員
Others, Japan

Sep. 2017
The Operations Research Society of Japan
弱実行不能半正定値計画問題の幾何学的解析
Best Paper of the Year, Bruno F. Lourenco;Masakazu Muramatsu;Takashi Tsuchiya
Official journal

Mar. 2003
日本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, Nov. 2022, Peer-reviwed, True, 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.
Scientific journal, English

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, Peer-reviwed, 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.
Scientific journal, English

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, Peer-reviwed
Scientific journal, English

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, Jan. 2019, Peer-reviwed
Scientific journal, English

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, May 2018, Peer-reviwed
International conference proceedings, English

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, 01 Mar. 2018, Peer-reviwed, 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.
Scientific journal, English

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, Peer-reviwed, 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.
International conference proceedings, English

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, Peer-reviwed
Scientific journal, English

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, 13 Nov. 2017, Peer-reviwed, 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.
Scientific journal, English

Application of SOCP in Power Efficient Networks
B.C. Das; E. Oki; M. Muramatsu
SIAM Conference on Optimization (OP17), May 2017, Peer-reviwed
International conference proceedings, English

Improved Simulation Adjusting
K. Hoki; N. Araki; S. Takahashi; M. Muramatsu
ICGA journal, International Computer Games Association, 39, 195-204, 2017, Peer-reviwed
Scientific journal, English

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, Dec. 2016, Peer-reviwed, 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.
Scientific journal, English

Estimating Player's Strength by CNN from One Game Record of Go
Nobuo Araki; Kunihito Hoki; Masakazu Muramatsu
情報処理学会論文誌, 情報処理学会, 57, 11, 2365-2373, 15 Nov. 2016, Peer-reviwed, 囲碁のプロ棋士は,一局の棋譜を見ればプレイヤの棋力がわかると言われている.本稿では,畳み 込みニューラルネットワーク(Convolutional Neural Network; CNN)を使用し,一局の囲碁の棋譜より, プレイヤの棋力を推定する手法を提案する.プレイヤのレート値を推定する実験と,プレイヤを上級/中 級/初級にクラス分けする実験を行なった.提案手法を実装して囲碁クエスト [14] の 13 路盤棋譜データを 用いて学習させて実験したところ,レート値を推定する手法としては従来手法 [1] より平均自乗誤差が小さ くなることがわかった.また,クラス分類する実験においては,一度 CNN を用いてレート値を推定して からその値に応じてクラス分けを行なう手法と,最初からクラス分類を CNN に学習させる手法の 2 種類 を提案し,それぞれ長所と短所があることを確かめた.
Scientific journal, Japanese

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), Aug. 2016, Peer-reviwed
International conference proceedings, English

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, Aug. 2016, Peer-reviwed
International conference proceedings, English

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, Jul. 2016, Peer-reviwed, 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.
Scientific journal, English

ディープラーニングを用いたコンピュータ囲碁～Alpha Goの技術と展望～
伊藤毅志; 村松正和
情報処理, 情報処理学会, 57, 4, 335-337, 15 Mar. 2016, Invited, 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.
Scientific journal, Japanese

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, Peer-reviwed, 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.
Scientific journal, English

Weak infeasibility in second order cone programming
Bruno F. Lourenço; Masakazu Muramatsu; Takashi Tsuchiya
Optimization letters, Springer, 1-13, 24 Dec. 2015, Peer-reviwed, 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.
Scientific journal, English

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, 21 Jun. 2014, Peer-reviwed, 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.
International conference proceedings, English

Facial Reduction Algorithms for Conic Optimization Problems
Hayato Waki; Masakazu Muramatsu
Journal of Optimization Theory and Applications, 158, 1, 188-215, Jul. 2013, Peer-reviwed, 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.
Scientific journal, English

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, Dec. 2012, Peer-reviwed, 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.
Scientific journal, English

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, Peer-reviwed, 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.
Scientific journal, English

Analysis on Go players’ recognition when they are thinking next moves
高橋克吉; 村松正和; 伊藤毅志; 松原仁
情報処理学会論文誌, 情報処理学会, 52, 12, 3796-3805, Dec. 2011, Peer-reviwed, 囲碁は完全情報ゼロ和ゲームとして多くのチェスライクゲームと同様に分類される が,ゲームの性質は大きく違うと考えられる.本研究は,囲碁における人の思考過程 について調べ,将棋との比較を行った.被験者に次の一手問題を提示し,発話プロト コルと視線の記録をもとに思考過程を分析した.上級者は盤面全体を見ており,先読 みよりも石の形によって手を決めていた.囲碁の上級者は主に石の形から情報を得て いると考えられる.将棋の上級者は視線を中央からほとんど動かさず,深い先読みを 行って次の手を決定しており,囲碁と将棋で上級者の思考過程に差異があった.これ は,囲碁と将棋のゲームとしての性質の違いを示していると考えられる.
Scientific journal, Japanese

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, Peer-reviwed, 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.
International conference proceedings, English

A facial reduction algorithm for finding sparse SOS representations
Hayato Waki; Masakazu Muramatsu
OPERATIONS RESEARCH LETTERS, ELSEVIER SCIENCE BV, 38, 5, 361-365, Sep. 2010, Peer-reviwed, 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.
Scientific journal, English

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, May 2009, Peer-reviwed, 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.
Scientific journal, English

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, Apr. 2009, Peer-reviwed, 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.
Scientific journal, English

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, Jul. 2008, Peer-reviwed, 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.
Scientific journal, English

Equality based contraction of semidefinite programming relaxations in polynomial optimization
Cong Vo; Masakazu Muramatsu; Masakazu Kojima
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, ELSEVIER SCI LTD, 51, 1, 111-125, Mar. 2008, Peer-reviwed, 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.
Scientific journal, English

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones
Masakazu Kojima; Masakazu Muramatsu
Mathematical Programming, 110, 2, 315-336, Jul. 2007, Peer-reviwed
Scientific journal, English

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, Jan. 2007, Peer-reviwed
Scientific journal, English

囲碁における連数の最大値について
宮代隆平; 矢野洋平; 村松正和
情報処理学会論文誌, 48, 3463-3469, 2007, Peer-reviwed
Scientific journal, Japanese

A pivoting procedure for a class of second-order cone programming
M Muramatsu
OPTIMIZATION METHODS & SOFTWARE, TAYLOR & FRANCIS LTD, 21, 2, 295-314, Apr. 2006, Peer-reviwed, 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.
Scientific journal, English

On Pivot Selection Rules of the Pivoting Method for a Class of Second-Order Cone Programming
Keisuke Kurita; Masakazu Muramatsu
統計数理, 53, 349-360, 2006
Scientific journal, Japanese

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, Peer-reviwed, 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.
Scientific journal, English

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, Dec. 2005, Peer-reviwed, 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.
Scientific journal, English

A unified class of directly solvable semidefinite programming problems
M Muramatsu
ANNALS OF OPERATIONS RESEARCH, SPRINGER, 133, 1-4, 85-97, Jan. 2005, Peer-reviwed, 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.
Scientific journal, English

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, Peer-reviwed, 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.
International conference proceedings, English

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, Peer-reviwed, 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.
International conference proceedings, English

Generalization of Kernel PCA and Automatic Parameter Tuning
Takahide Nogayama; Masakazu Muramatsu; Haruhisa Takahashi
Proccedings of The ANZIIS 2003 Conference, 173-178, Dec. 2003, Peer-reviwed
International conference proceedings, English

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, Jun. 2003, Peer-reviwed, 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.
Scientific journal, English

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, Mar. 2002, Peer-reviwed, 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.
Scientific journal, English

直列型生産ラインシステムにおける最適加工容量配分問題と その二次錐計画法による解法
石塚陽; 村松正和; 鷺森崇
日本経営工学会論文誌, Japan Industrial Management Association, 52, 6, 363-372, 2002, Peer-reviwed, We formulate an optimal service capacity allocation problem in tandem production systems, and propose a solution method via second order cone programming. Given total amount of service capacities (service rates), the problem is to find an optimal allocation of the capacities to the production stages so as to maximize the throughput in the steady state. Since it is difficult to know the exact value of the throughput, our approach is based on the so-called "sample-path optimization." It finds an approximate optimal allocation by maximizing an approximate value of the throughput obtained through a simulation run under a fixed series of random numbers. We show that the maximization problem can be converted into a second order cone programming problem with many linear constraints and a low number of second order cone constraints, and an effective algorithm developed. Numerical experiments show that our method can be applied to large size systems with more than 100 stages.
Scientific journal, Japanese

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, Peer-reviwed, 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.
Scientific journal, English

Commutative class and power class of search directions for symmetric cone linear programming
M.Muramatsu
The first Sino-Japan Optimization Meeting，香港，中国, 0, Oct. 2000
International conference proceedings, English

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, Mar. 2000, Peer-reviwed, 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.
Scientific journal, English

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, Feb. 1999, Peer-reviwed, 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.
Scientific journal, English

Affine scaling algorithm fails for semidefinite programming
M Muramatsu
MATHEMATICAL PROGRAMMING, ELSEVIER SCIENCE BV, 83, 3, 393-406, Nov. 1998, Peer-reviwed, 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.
Scientific journal, English

Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm
M Muramatsu; T Tsuchiya
MATHEMATICAL PROGRAMMING, ELSEVIER SCIENCE BV, 72, 3, 291-305, Mar. 1996, Peer-reviwed, 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.
Scientific journal, English

An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption
M Muramatsu; T Tsuchiya
ANNALS OF OPERATIONS RESEARCH, BALTZER SCI PUBL BV, 62, 325-355, 1996, Peer-reviwed, 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.
Scientific journal, English

Affine scaling algorithm fails for semidefinite programming
MURAMATSU M.
上智大学理工学部機械工学科学術報告書, 16, 1996
English

GLOBAL CONVERGENCE OF A LONG-STEP AFFINE SCALING ALGORITHM FOR DEGENERATE LINEAR-PROGRAMMING PROBLEMS
T TSUCHIYA; M MURAMATSU
SIAM JOURNAL ON OPTIMIZATION, SIAM PUBLICATIONS, 5, 3, 525-551, Aug. 1995, Peer-reviwed, 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.
Scientific journal, English

Infeasibility Detection in an Affine Scaling Infeasible Interior Doint Algorithm
Research Memorandum The Institute of Statistical Mathematics, 553, 1995
Research institution, English

A Convergence analysis of a long-step variant of the projective scaling algorithm (共著)
Research Memorandum, (]G0061[)454 The Institute of Statistical Mathematics, 1993
Research institution, English

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
Research institution, English

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

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

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

ジョルダン代数
脇隼人; 村松正和
公益社団法人日本オペレーションズ・リサーチ学会, Nov. 2010, オペレーションズ・リサーチ, 55, 11, 718-719, Japanese, Introduction other, 0030-3674, 110007880839, AN00364999

コンピュータ囲碁の飛躍の背景
Kazuki Yoshizoe; Masakazu Muramatsu
日本評論社, Oct. 2010, 数学セミナー, 49, 10, 52-27, Japanese, Introduction other, 0386-4960, 40017291503, AN10333470

二次錐計画
脇隼人; 村松正和
Oct. 2010, オペレーションズ・リサーチ, 55, 10, 655-656, Japanese, Introduction other

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, English, Peer-reviwed, 0926-6003, 10025482257

プロ棋士対コンピュータ：FIT2008 における囲碁対局報告
村松正和
Jan. 2009, 情報処理, 50, 1, 70-73, Japanese, Introduction other

連続最適化における未解決問題
村松正和
連続最適化の理論的研究における未解決問題を,特に,線形計画,錐線形計画,多項式計画,2次計画の各テーマに絞って紹介する., 公益社団法人日本オペレーションズ・リサーチ学会, Jan. 2008, オペレーションズ・リサーチ, 53, 1, 10-14, Japanese, Introduction other, 0030-3674, 110006532513, AN00364999

半正定値計画と内点法
村松正和
2007, オペレーションズ・リサーチ, 52, 513-518, Japanese, Introduction other, 10020194073

多項式計画と錐線形計画ーー非線形計画への線形計画からのアプローチ
村松正和
2006, システム／制御／情報, 50, 8-13, Japanese, Introduction other

多項式計画と錐線形計画–非線形計画への線形計画からのアプローチ
村松正和
2006, システム／制御／情報, 50, 8-13, Japanese, Introduction other

錐線形計画への招待
村松正和
2003, システム／制御／情報, 47, 5, 223-228, Japanese, Peer-reviwed, Introduction other

「アイスクリーム・コーンの中には何がある?」
村松正和
2000, (Introduction to the second-order cone programming problems)アイ・サイ問答教室，システム/制御/情報, 44, 9, 541-542, Japanese, Peer-reviwed, Introduction other

あたらしい数理最適化
久保幹雄; J.P.ペドロソ、A. レイス; 村松正和
Japanese, Joint work, 近代科学社, 2012

最適化法
田村明久; 村松正和
Japanese, Joint work, 共立出版株式会社, Apr. 2002

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

経営科学OR用語大辞典(共著)朝倉書店
Japanese, 1999

居酒屋チェーン店における従業員の勤務表作成問題
中村克; 村松正和
Oral presentation, 日本OR学会2023年度春季研究発表会
07 Mar. 2023

A Variant of Knapsack Problem Efficient for Benders Decomposition
Kosuke Aratani; Masakazu Muramatsu
Oral presentation, 13th International Congress on Advanced Applied Informatics Winter, Peer-reviewed
Dec. 2022

居酒屋スタッフのスケジューリング問題
中村克; 村松正和
Oral presentation, 日本OR学会2022年度春季研究発表会
18 Mar. 2022

木の最小シュタイナー支配集合
古舘周平; 村松正和
Oral presentation, 日本OR学会2022年春季研究発表会
17 Mar. 2022

小型電動固定翼の交通網の設計
和田和馬; 村松正和
Oral presentation, Japanese, 日本OR学会 2022年春季研究発表会
17 Mar. 2022

非線形計画って何だろう？
村松正和
Invited oral presentation, Japanese, モデリングを通して見えた世界, Invited, Domestic conference
12 Mar. 2022

Solving SDP completely with an interior point oracle
Masakazu Muramatsu
Invited oral presentation, English, International Conference on Nonlinear Analysis and Convex Analysis (NACA) and International Conference on Optimization: Techniques and Applications (ICOTA), Invited, NACA and ICOTA Organizing Committee, Hakodate, Japan, International conference
31 Aug. 2019

A 2-approximation algorithm for minimum knapsack problem with single continuous variable
Yuki Kimura; Masakazu Muramatsu
Oral presentation, English, International Conference on Nonlinear Analysis and Convex Analysis and International Conference on Optimization Techniques and Applications, NACA-ICOTA Organizing Committee, Hakodate, Japan, International conference
30 Aug. 2019

Solving SDP by projection and rescaling algorithms
Natsuki Okamura; Bruno F. Lourenco; Masakazu Muramatsu
Oral presentation, English, International Conference on Continuous Optimization 2019, Mathematical Optimization Society, Berlin, International conference
07 Aug. 2019

Extensions of Chubanov’s Projection and Rescaling Algorithms
Masakazu Muramatsu
Oral presentation, English, Numerical Verification (NIVEA) 2019, International conference
27 Feb. 2019

Extensions of Projection and Rescaling Algorithms
Masakazu Muramatsu
Invited oral presentation, English, International Workshop on Control and Optimization, Invited, 豊田理化学研究所・特定課題研究 「制御工学研究者と応用数学研究者の連携による革新的な制御理論構築」, 京都大学, International conference
07 Aug. 2018

Extensions of Projection and Rescaling Algorithms
Masakazu Muramatsu
Invited oral presentation, English, International Symposium on Control and Optimization, Invited, 豊田理化学研究所・特定課題研究 「制御工学研究者と応用数学研究者の連携による革新的な制御理論構築」, 京都大学, International conference
07 Aug. 2018

An extension of Chubanov’s algorithm to symmetric cone programming
Masakazu Muramatsu
Invited oral presentation, English, ISMP 2018, Invited, Mathematical Optimization Society, Bordeaux, France., International conference
03 Jul. 2018

Comparative Performance of Green Pipe, Green Hose, and Green Hose-Rectangle Models in Power Efficient Network
Masakazu Muramatsu
Oral presentation, English, IEEE-CQR 2018, International conference
15 May 2018

錐線形計画と Facial Reduction への招待
村松正和
Invited oral presentation, Japanese, 第60回自動制御連合講演会, 自動制御連合講演会, Domestic conference
10 Nov. 2017

錐線形計画と Facial Reduction への招待
村松正和
Invited oral presentation, Japanese, 第60回自動制御連合講演会, 自動制御連合講演会, 電気通信大学, Domestic conference
10 Nov. 2017

Chubanov による同次線形計画問題の内点許容解を求めるアルゴリズムとその拡張に関する最近の展開
村松正和
Invited oral presentation, Japanese, RAMPシンポジウム2017, Invited, 日本オペレーションズ・リサーチ学会数理計画研究部会, 筑波大学, http://infoshako.sk.tsukuba.ac.jp/~ramp/index.html, Domestic conference
13 Oct. 2017

Chubanov による同次線形計画問題の内点許容解を求めるアルゴリズムとその拡張に関する最近の展開
村松正和
Invited oral presentation, Japanese, RAMPシンポジウム2017, Invited, 日本オペレーションズ・リサーチ学会数理計画研究部会, 筑波大学, http://infoshako.sk.tsukuba.ac.jp/~ramp/index.html, Domestic conference
13 Oct. 2017

同次対称錐計画問題の内点実行可能解を求める新しいアルゴリズム
村松正和
Oral presentation, Japanese, 数理最適化の発展：モデル化とアルゴリズム, 数理解析研究所, 数理解析研究所, https://sites.google.com/site/narushimalab/krims2017, Domestic conference
25 Aug. 2017

Partial Polyhedrality and Facial Reduction
Masakazu Muramatsu; Bruno Lourenco; Takashi Tsuchiya
Oral presentation, English, SIAM Conference on Optimization 17, Invited, Society for Industrial and Applied Mathematics, Vancouver, Canada., https://www.siam.org/meetings/op17/, International conference
24 May 2017

Network Congestion Minimization Models Based on Robust Optimization
Bimal Chandra Das
Oral presentation, English, 研究集会「最適化：モデリングとアルゴリズム」, 統計数理研究所, 東京都立川市, Domestic conference
23 Mar. 2017

An extension of Chubanov's algorithm to symmetric cone feasibility problems
Bruno F. Lourenco
Oral presentation, Japanese, 研究集会「最適化：モデリングとアルゴリズム」, 統計数理研究所, 東京都立川市, Domestic conference
23 Mar. 2017

対称錐に対する Chubanov のアルゴリズムの拡張
Bruno F. Lourenco
Oral presentation, Japanese, 日本オペレーションズ・リサーチ学会2017年春季研究発表会, 日本オペレーションズ・リサーチ学会, 沖縄県那覇市, Domestic conference
17 Mar. 2017

三角形総面積最大化問題に関する研究
市橋志朗
Oral presentation, Japanese, 日本オペレーションズ・リサーチ学会2017年春季研究発表会, 日本オペレーションズ・リサーチ学会, 沖縄県那覇市, Domestic conference
16 Mar. 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
Invited oral presentation, English, 2nd ISM-ZIB-IMI MODAL Workshop on Mathematical Optimization and Data Analysis, Invited, The Institute of Statistical Mathematics, Zuse Institute of Berlin, Institute of Math for Industry., Berlin, Germany, http://www.zib.de/node/3105, International conference
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
Invited oral presentation, English, 2nd ISM-ZIB-IMI MODAL Workshop on Mathematical Optimization and Data Analysis, Invited, The Institute of Statistical Mathematics, Zuse Institute of Berlin, Institute of Math for Industry., Berlin, Germany, International conference
2017

内点オラクルによる錐線形計画問題の完全な求解
Bruno F. Lourenco
Oral presentation, Japanese, 日本オペレーションズ・リサーチ学会秋季研究発表会, 日本オペレーションズ・リサーチ学会, Domestic conference
16 Sep. 2016

Weak Infeasibility, Facial Reduction, and Geometry in Conic Programming
Masakazu Muramatsu
Oral presentation, English, International Conference on Continous Optimization 2016, Mathematical Optimization Society, Tokyo, Japan, http://www.iccopt2016.tokyo, International conference
09 Aug. 2016

Solving SDP completely with an Interior-Point Oracle
Takashi Tsuchiya
Oral presentation, English, International Conference on Continous Optimization 2016, Mathematical Optimization Society, Tokyo, Japan, http://www.iccopt2016.tokyo, International conference
09 Aug. 2016

A Mixed-Integer SOCP Model for Robust and Power Efficient Networks
Bimal Chandra Das
Poster presentation, English, International Conference on Continous Optimization 2016, Mathematical Optimization Society, Tokyo, Japan, International conference
09 Aug. 2016

FRA-Poly, Partial Polyhedrality and Facial Reduction
Bruno F. Lourenco
Oral presentation, English, International Conference on Continuous Optimization 2016, Mathematical Optimization Society, Tokyo, Japan, http://www.iccopt2016.tokyo, International conference
08 Aug. 2016

さまざまなグラフにおける情報拡散ゲームの ナッシュ均衡に関する考察
櫻井亮佑; 村松正和; 高橋里司; 保木邦仁
Oral presentation, Japanese, 日本OR学会春季研究発表会, 日本OR学会, Domestic conference
26 Mar. 2015

Weak Status of Conic Programming
Masakazu Muramatsu
Invited oral presentation, English, First Pacific Optimization Conference, Invited, 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., International conference
31 Oct. 2014

Monte-Carlo Simulation Adjusting
Nobuo Araki; Masakazu Muramatsu; Kunihito Hoki; Satoshi Takahashi
Poster presentation, English, AAAI 2014, THE ASSOCIATION FOR THE ADVANCEMENT OF ARTIFICIAL INTELLIGENCE (AAAI), Quebec city, Canada, International conference
Jul. 2014

面の話 PartII
村松正和
Public discourse, Japanese, 最適化の理論と応用 -- 未来を担う若手研究者の集い 2014, Invited, 日本OR学会「最適化の理論と応用」研究部会, 筑波大学, http://www.misojiro.t.u-tokyo.ac.jp/~y-koba/SOTA/mirai14.html, Domestic conference
01 Jun. 2014

A Geometrical Analysis of Weak Infeasibility in Semidefinite Programming and Related Issues
Bruno Lourenco; Masakazu Muramatsu; Takashi Tsuchiya
Oral presentation, English, SIAM Conference on Optimization, SIAM, San Diego, USA, International conference
22 May 2014

モンテカルロ木探索における予測読みに関する研究
モンテカルロ木探索における予測読みに関する研究; 荒井 光; 村松正和
Oral presentation, Japanese, エンターテイメントと認知科学シンポジウム, 電気通信大学 エンターテイメントと認知科学研究ステーション, 電気通信大学, http://entcog.c.ooco.jp/entcog/contents/symposium/date/20150319.html, Domestic conference
20 Mar. 2014

低ランク整数完全正値行列 の判定について
川瀬 弘樹; 村松 正和; 高橋 里司
Oral presentation, Japanese, 日本オペレーションズ・リサーチ学会春季研究発表会, 日本オペレーションズ・リサーチ学会, 大阪大学, Domestic conference
07 Mar. 2014

2次元トーラスグラフ上での情報拡 散ゲームにおけるナッシュ均衡
祐成友樹; 村松正和
Oral presentation, Japanese, 日本オペレーションズ・リサーチ学会秋季研究発表会, 日本オペレーションズ・リサーチ学会, 徳島大学, Domestic conference
12 Sep. 2013

Adaptive SDP relaxation for Polynomial Optimization
Masakazu Muramatsu
Oral presentation, English, ICCOPT 2013, Mathematical Optimization Society, International conference
31 Jul. 2013

多項式計画に対する半正定値緩和
村松正和
Invited oral presentation, Japanese, 組合せ最適化セミナー, Invited, Domestic conference
Jul. 2012

情報拡散ゲームにおけるナッシュ均衡 についての一考察
伊藤彰宏; 村松正和
Oral presentation, Japanese, 日本OR学会,日本OR学会2011年度春季研究発表会
Mar. 2012

東京23区踏破問題の解法
祐成友樹; 村松正和
Oral presentation, Japanese, 日本OR学会,日本OR学会2011年度春季研究発表会
Mar. 2012

多項式計画に対する半正定値緩和の不思議な性質
村松正和
Invited oral presentation, Japanese, ワークショップ「最適化理論の産業・諸科学への応用」, 九州大学マスフォアインダストリ研究所
Oct. 2011

多項式計画に対する半正定値緩和の不思議な性質
村松正和
Invited oral presentation, Japanese, ワークショップ「最適化理論の産業・諸科学への応用」, 九州大学マスフォアインダストリ研究所, 福岡県, International conference
Oct. 2011

Strange Behaviors of Interior-point Methods for Solving Semidefinite Programming Problems in Polynomial Optimization and their Reason
村松正和
Public symposium, Japanese, 最適化手法の深化と広がり, 京都大学数理解析研究所, 京都
Jul. 2011

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

Facial Reduction Algorithm and Conic Expansion Algorithm
Masakazu Muramatsu; Hayato Waki
Oral presentation, English, International Symposium on Mathematical Programming 2009
Aug. 2009

A Facial Reduction Algorithm for Semidefinite Programming Problems in Polynomial Optimization
Hayato Waki; Masakazu Muramatsu
Oral presentation, English, International Symposium on Mathematical Programming, 2009
Aug. 2009

計算と最適化の新展開に向けて
久野誉人; 村松正和; 藤澤克樹
Oral presentation, Japanese, 日本オペレーションズリサーチ学会,春期研究発表会
Mar. 2009

錐線形計画における錐の面的縮小と正則拡大およびその応用
村松正和; 脇隼人
Oral presentation, Japanese, 日本オペレーションズリサーチ学会,春期研究発表会
Mar. 2009

A Facial Reduction Approach in Conic Programming
村松正和; 脇隼人
Oral presentation, Japanese, SCOPE,日本オペレーションズリサーチ学会研究部会
Mar. 2009

Strange behaviors of interior-point mehtods for solving semidefinite programming problems in polynomial optimization
Hayato Waki; Masakazu Muramatsu
Oral presentation, English, HPOPT2008
Jun. 2008

Semidefinite programming relaxation for polynomial optimization problems
Masakazu Muramatsu
Invited oral presentation, English, International Conference on Modeling, Computation and Optimization, Indian Statistical Institute, Delhi, India, International conference
Jan. 2008

Semidefinite programming relaxation for polynomial optimization problems
Masakazu Muramatsu
Invited oral presentation, English, International Conference on Modeling, Computation and Optimization, Indian Statistical Institute, Delhi, India, International conference
Jan. 2008

コンピュータ囲碁における局所的なヨミを用いた群分割について
山崎大輔; 橋本千裕; 村松正和
Oral presentation, Japanese, エンターテイメントと認知科学研究ステーション,第一回エンターテイメントと認知科学シンポジウム
Mar. 2007

Aspects of SDP Relaxation for Polynomial Optimization
Masakazu Muramatsu
Invited oral presentation, English, Global Optimization -- Integrating Convexity, Optimization, Logic Programming, and Computational Algebraic Geometry, Erwin Schlodinger Institute for Mathematical Physics, Wien, Austria, International conference
Dec. 2006

A Sparse SDP Relaxation for Polynomial Optimization Problems over Symmetric Cones
Masakazu Muramatsu; Masakazu Kojima
Oral presentation, English, ISMP2006
Aug. 2006

A Sparse SDP Relaxation for Polynomial Optimization Problems over Symmetric Cones
Masakazu Muramatsu; Masakazu Kojima
Oral presentation, English, INFORMS2006 Hong Kong
Jun. 2006

Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity
Masakazu Muramatsu; Masakazu Kojima; Sunyoung Kim; Hayato Waki
Oral presentation, English, IFORS
Jul. 2005

On a Simplex Method for a Class of Second-Order Cone Programming
Masakazu Muramatsu; Keisuke Kurita
Oral presentation, English, Society for Industrial and Applied Mathematics (SIAM)
May 2005

SparsePOP: A Sparse SDP relaxation of Polynomial Optimization Problems
Hayato Waki; Sunyoung Kim; Masakazu Kojima; Masakazu Muramatsu
Oral presentation, English, Positive Polynomials
Mar. 2005

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones
Masakazu Kojima; Masakazu Muramatsu
Public symposium, English, HPOPT2004, HPOPT2004, Amsterdam
Jun. 2004

２次錐計画とその応用
村松正和
Invited oral presentation, Japanese, 第１５回RAMPシンポジウム, RAMP
2003

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

On Commutative Class of Search Directions for Symmetric Cone Programming
M.Muramatsu
Oral presentation, English, International Symposium on Mathematical Programming, International conference
Aug. 2000

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

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

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

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

連続最適化基礎論
The University of Electro-Communications

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

数理計画法
The University of Electro-Communications

数理計画法
電気通信大学

大学院技術英語
The University of Electro-Communications

Graduate Technical English
The University of Electro-Communications

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

Apr. 2022 - Present
電子情報通信学会

2007 - Present
情報処理学会

Apr. 2000 - Present
The Japan Society for Industrial and Applied Mathematics

1999 - Present
SIAM(Society for Industrial and Applied Mathematics)

Apr. 1994 - Present
The Operations Research Society of Japan

1994 - Present
Mathematical Optimization Society

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

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

面削減法を用いた錐線形計画の双対理論と誤差解析
村松正和
Principal investigator
01 Apr. 2017 - 31 Mar. 2020

Applying heuristics to complex games close to real-world competition
Hoki Kunihito
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), Aiming to develop competitive artificial intelligence by achieving the scale-up of existing heuristics in games that are close to competition in the real world, where there are many options for actions, and situations and state transitions can only be partially observed. This research was carried out by using Go, Mahjong, a card game, chess, digital curling, etc., provided a new algorithm to realize the aim, and was published in several papers., 16K00503
01 Apr. 2016 - 31 Mar. 2020

錐線形計画における退化とモデリング
村松正和
Principal investigator
01 Apr. 2014 - 31 Mar. 2017

潜在情報事前分布に基づくベイズ統計理論の構築と応用
駒木文保
01 Apr. 2014

Information Geometry of Convex Optimization : Extension and Applications
TSUCHIYA Takashi; OHARA Atsumi; MURAMATSU Masakazu; FUKUDA Mituhiro
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (B), Interior-point algorithms for semidefinite programs and symmetric cone programs are analyzed in view of information geometry to show that the iteration complexity of primal-dual interior-point algorithms is approximately represented as a infomration geometric integral over central trajectory. Through extensive numerical experiments we demonstrated that the integral very accurately predict iteration-complexity of interior-point algorithms. One of the largest Gaussian graphical models in the world are successfully solved with super computer. Primal-dual interior-pont algorithms for large-scale Gaussian graphical models are developed. Regularization and facial reduction approaches for ill-conditioned semidefinite programs are developed., 20340024
2008 - 2010

Development of numerically stable primal-dual interior point algorithms for solving nonlinear semidefinite programming problems
YOSHISE Akiko; FUJISAWA Katsuki; YAMAMOTO Yoshitsugu; KUNO Takahito; SHIGENO Maiko; MURAMATSU Masakazu
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, University of Tsukuba, Grant-in-Aid for Scientific Research (C), The aim of this research is to develop numerically stable primal-dual interior point methods foe solving nonlinear semidefinite programming problems. The semidefinite programming problem is an optimization problem over a closed convex cone that is not polyhedral unlike the linear programming problem. By this reason, we often observe a problem which has an asymptotic optimal solution but no optimal solution, I.e., any sequence on which the object value converges to the optimal value diverges. This brings us a numerical difficulty in determining the optimality when we apply interior point algorithms to solve the problem. A high accuracy of an optimal solution of the problem is critical if we adopt the problem as an approximation model of a combinatorial optimization problem or a robust optimization problem. To overcome the difficulty, many techniques have been proposed for obtaining a numerical stability of the algorithms. Such techniques are more highly expected when we solve nonlinear semidefinite programming problems. In order to provide one of such techniques, we introduced a homogeneous model for the nonlinear semidefinite programming problem, and showed that for the homogeneous model, (a) a bounded path having a trivial starting point exists, (b) any accumulation point of the path is a solution of the homogeneous model, c if the original problem is solvable then it gives us a finite solution, (d) if the original problem is strongly infeasible, then it gives us a finite certificate proving infeasibility, and (e) a class of algorithms for numerically tracing the path in (a) solves the problem in a polynomial number of iterations under a moderate assumption, 18560052
2006 - 2007

The second order mean field approximation of graphical models and its application to Bayesian inference
TAKAHASHI Haruhisa; MURAMATSU Masakazu
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), Markov random field (MRF) and its discriminative version have been shown useful for both biological analysis and practical applications. In biological analysis, the debate on neuronal correlations is now continuing in which the analysis of the probability P( r| s) of the neuronal response r conditional on a stimulus s is required, which could be modeled with MRF. In this context the importance of a parametric model for analyzing correlations by modeling joint probability P(r, s) is shown using Gibbs distribution. Several approximation techniques have been proposed for computing state probabilities of MRFs, CRFs, including belief propagation, which is not applicable for MRFs in a general situation. Mean field approximation (MRF) is known as only the generally applicable approximation technique at present. To improve the accuracy of the mean-field approximation several advanced techniques have been proposed. Since the better accuracy we attain, the more intricate equations we get into, it becomes hard to know the efficient training procedure. In fact the training procedure is known only for the naive mean-field approximation (NMF), which is not so sufficient for the approximation accuracy. The achievement of this research is to have refined the mean field approximation to alleviate both the testing and learning time, and to have shown the efficient learning scheme for object recognition with the variational phasor mean field model (VPMF). The striking result is that our learning scheme shows comparable testing performance with SVM, despite using much smaller size of training data, and in addition the detection time and the training time are much smaller than SVM based face detection. Performance evaluation of VPMF is given for approximation accuracy, the local minima, and a face recognition problems. We have also attained the conclusion that the correlation of population coding in neural networks is more powerful than just using only the mean firing rate. Performance evaluation of VPMF is given for approximation accuracy, the local minima, and a face recognition problems., 17500088
2005 - 2007

Developments of Advanced Optimization Systems Unitying Discrete and Continuous Approaches Associate
IMAI Hiroshi; MURAMATSU Masakazu; TSUCHIYA Takashi; IMAI Keiko; MUROTA Kazuo; ASANO Takao
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Tokyo, Grant-in-Aid for Scientific Research (B), Optimization methods by computers have a great impact upon various fields in science and technology due to its wide scope of applications. In this research project, was have aimed at unifying existing results for system analysis obtained by each of project members on interiorpoint methods for linear programming, computational-geometric algorithms, matroid theory, Boolean function theory, etc., and produce new theoretical results and devrlop prototype optimization systems via this unifying work. Through this project, from the viewpoint of continuous optimization, we have extended the framework of linear programming to that of semidefinite programming, and, from the viewpoint of discrete optimization, theory of discrete convex analysis has been developed. By this theory of discrete convex analysis, connection with continuous methods and discrete methods can be established, with extending matroids and submodular systems on which the discrete convexity theory is based. Randomization is also applied through this connection between continuous and discrete approaches, and, by applying the randomized rounsing technique using the semidefinite programming to the satisfiability problem, approximate algorithms with better porformance ratio have been obtained. Furthermore, based on polyhedral structures having both continuous and combinatorial properties, the branch-and-cut technique is applied to the famous minimum-length triagulation problem in computational geometry. Finally, we developed a prototype system handling a family of sets by using the so-called binary decision diagram (or, BDD) as a promising approach from discrete Boolean function theory, and applied it to various problems, including network reliability computation which have continuous aspect, and other invariants in graphs, knots, and statistical physics. The system is made public for wide use., 07555615
1995 - 1996