村松 正和

学長・理事等(役員)理事
  • プロフィール:

    博士課程では線形計画に対する内点法を研究。その後,半正定値計画へと興味の対象が移る。 さらに2000年ごろから,対称錐上の線形計画へと行き着き,現在は広く錐線形計画をテーマとしている。他のさまざまな分野の研究者と共同研究もしている。

学位

  • 工学修士, 東京大学, 1991年03月
  • 博士(学術), 総合研究大学院大学, 1994年03月

研究キーワード

  • 多項式最適化
  • 線形最適化
  • 非線形最適化
  • 2次錐計画
  • 半正定値計画
  • 錐計画
  • オペレーションズ・リサーチ

研究分野

  • 情報通信, 数理情報学

経歴

  • 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学会文献賞

論文

  • Shift Quality Classifier Using Deep Neural Networks on Small Data with Dropout and Semi-Supervised Learning
    Takefumi KAWAKAMI; Takanori IDE; Kunihito HOKI; Masakazu MURAMATSU
    IEICE Transactions on Information and Systems, Institute of Electronics, Information and Communications Engineers (IEICE), E106.D巻, 12号, 掲載ページ 2078-2084, 出版日 2023年12月01日
    研究論文(学術雑誌)
  • 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.
    研究論文(学術雑誌), 英語
  • 2次錐計画のサブクラスに対する単体法的アルゴリズムにおけるピボット選択規則について
    栗田圭介; 村松正和
    統計数理, 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年
    研究論文(大学,研究機関等紀要), 英語

MISC

  • 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年度秋季研究発表会
    発表日 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月
  • 2次錐計画とその応用
    村松正和
    口頭発表(招待・特別), 日本語, 第15回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年