Research projects

The purpose of this study is as follow. (1) Evaluation of complexity of primal-dual interior point algorithms for linear programs. (2) Applications of interior point algorithms to nonconvex quadratic programs and combinatorial optimization problems. (3) Development of software for linear programs with the use of interior point algorithms. (4) Extension of interior point algorithms to general convex programs. For the purpose (1), we proposed a method for controlling step lengths and a method for choosing an initial point from which an interior point for a linear program starts. We confirmed for the purpose (3) the effectiveness and efficiency of these new methods in computational experiments. We made investigation into nonconvex quadratic programs and combinatorial optimization problems, but we have not succeeded in incorporating interior point algorithms into the problems. We also extended the methods mentioned above in the purpose (1) to general convex programs.

連続体および連続体近似できる自然現象の数理モデル方程式を数学解析し, 次のような研究成果が得られた(主要なもののみ記す). (1) Navier-Stokes方程式, Stokes 方程式に対して, 区分的に連続な境界を持つ領域, 角領域での強解の一意存在 ; (2) Navier-Stokes方程式に対して, 滑り境界条件(Navier型, 閾値型) 下での強解の一意存在 ; (3) 水の波(渦なし非圧縮Euler方程式の自由境界問題) の長波近似, 浅水波近似の正当化 ; (4) 自己重力作用下での流体星(化学的に活性な圧縮性粘性流体) の1次元問題および3次元球対称問題の滑らかな時間大域解の一意存在 ; (5) 弾性体に対するいくつかの亀裂問題の可解性.

1.研究代表者を中心として得られた知見 (1)正定値自己共役作用素を近似する有界自己共役作用素列の分数巾の収束率と一様有界性 近似作用素の列の収束率が近似作用素の分数巾の列の収束率に適切に反映されることを示し、この結果から分数巾の列のある意味での一様有界性がしたがうことを示した。(2)水の波線形非定常問題の有限要素離散化問題の収束性と誤差評価の方法の抽象的展開 (1)の結果を手がかりにして、研究を展開した。支配作用素が一階の擬微分作用素であることから生ずる興味ある知見を得た。(3)スチェクロフ作用素を用いた透過境界条件の設定とその数値的取り扱い 外部領域におけるポアッソン問題などの有限要素近似問題に適用しその方法を正当化した。(4)軸対称容器内の水の波固有値問題の有限要素計算 理論解析結果の正しさを確認するとともに、理論の適用出来ない場合の問題点を整理した。 2.分担者が著しい成果を収めた研究課題(分担者名) (1)凸汎関数に対する劣微分作用素の固有値問題の列における解の列の収束性(渡辺二郎、海津總)。(2)積分半群の理論の追究とその線形関数微分方程式の解半群への応用(内藤敏機)。(3)3次精度上流型有限要素近似による自動搬送車廻りの気流解析(田端正久)。(4)高レイノルズ数円柱回り流れにおける流脈線のシミュレーションと近似流脈線の誤差評価(田端正久)。(5)抵抗性磁気流体作用素のスペクトル的性質の解明とその近似解法(加古孝)。(6)ある種の凸最小最大問題に対する再帰的アルゴリズム(田村明久)。 3.電気通信大学数値解析研究会の継続開催と研究資料「電気通信大学数値解析研究会講演題目集」の作成 本年度21回に亘っておおむね金曜午前に実施し、3月4日には一日研究会「恩故知新の集い」を開催した。研究資料には1977年から現在にいたるこの研究会とその前身の会での講演題目を収録した。

「非線形最適化手法による組合せ最適化問題の効率的解法の開発」という目的で本年度は研究を進めて来た。組合せ最適化問題の中でも安定集合問題を双向グラフ上に一般化した問題に(一般化安定集合問題と呼ぶ)対しては、本研究の目的を完全に達成した。具体的には、双向グラフのパ-フェクト性を導入し、無向グラフのパ-フェクト性との関係を明らかにし、さらにパ-フェクト双向グラフに対する一般化安定集合問題を半正定値計画問題として定式化する方法を示した。この半正定値計画問題に対する多項式時間解法である楕円体法や内点法を用いることでパ-フェクト双向グラフに対する一般化安定集合問題に対する多項式時間解法を構築した。これらの結果は3編の論文としてまとめ、1編はJ.of the Operations Resarch Society of Japanに掲載予定であり、他の2編はMathematical Programming誌と国際会議の査読付きProceedingsに投稿中である。 その他の組合せ的な問題点に対しては、グラフのバンド幅を求める問題について、木グラフのバンド幅の上界値を与える方法を提案した。この上界は既知の結果であるChavatalovaの上界より良く、頂点数が10^9以下の木グラフについてはChunnの上界よりもよいものであった。この結果Discrete Mathematics誌に掲載された。また、グラフのある種の変換についての同型性の研究や符号理論や暗号理論に関する研究を進めた。 非線形を専門とする分担者は、人工ニューラルネットワークの逆問題解析への応用についての研究を進め、核融合プラズマの位置決定問題に適用し良好な結果を得た。これをFusion Technology誌に発表した。

We studied some properties of algorithms, mostly appeared in number theoretic algorithms, as measurable dynamical systems. In particular, we focused problems related to the projects in below and got a number of new results. The projects we focused are the

The problems in extremal graph theory is to find the minimum number of edges or a sharp minimum degree condition for a graph G to contain a prescribed subgraph H. In this research, by considering the problems from the unified point of view of factor problems, graph minor problems, and subgraph finding problems, we shall go into a new area of extremal graph theory. In particular, we focus on extremal problems of forests, vertex-disjoint chorded cycles and theta subgraphs, matching extendability, etc. Also, related to Hadwiger's conjecture, one of the most famous conjectures in graph theory, we propose the notion of rho-coloring, and give an alternative and much simpler proof of Hadwiger's conjecture for degree sequences.

In computational geometry, we proposed an idea of a geometric representation of an image by using contour line which enables approaches completely different from conventional ones based on matrix representation of an image. We also gave an algorithm to approximate rectilinear contour lines by smooth curves while keeping several basic properties inherent in contour lines. These applications are closely related to digital geometry in which vertices have integer coordinates. We investigated a new approach for Digital halftoning which is a technique to convert a grey image into a binary (black and white) image. We introduced an notion of bidirected graph as an extension of directed graph and we gave a linear time algorithm for the generalized stable set problem on triangulated bidirected graphs. We proposed a polynomial time algorithm for the M-convex function minimization problem. We proved that the edge wide-diameter of a k-edge connected graph does not exceed a plynomial of the diameter of it of degree k. We proved that the number of vertices of degree 5 of every 5-contraction critical graph is at least 1/5 of its order and the number of vertices of degree 6 of every 6-contraction critical graph is at least 1/7 of its order. We developed a new pseudo-probablistic method and we proved Bollbas-Kohayakawa conjecture on Erdos-Stone theorem.

1.研究代表者を中心として得られた知見 (1)スチェクロフ作用素を用いた透過境界条件の設定とその数値的取り扱い ラプラス方程式とポアッソン方程式の数値解法におけるスチェクロフ作用素の取扱いについて考察を深めた。スチェクロフ作用素を用いることによって、無限領域問題および角のある有界領域等の特異性のある領域での有限要素近似計算法を確立して、その数学解析と数値計算を実施した。完全流体における一様流の中の物体まわり流れの精密計算法を考察した。本研究は研究分担者小山大介と共同して実施した。(2)移流拡散非定常問題の差分近似問題の安定性と誤差評価 数値流体力学における基本問題である移流拡散問題の差分近似問題の安定性と誤差評価を研究した。空間一次元問題における等間隔五点差分公式を対象とした。 2.分担者が著しい成果を収めた研究課題(分担者名) (1)遅れをもつ線形微分方程式の線形作用素の半群の理論による取り扱い(内藤敏機)。(2)構造と音場の連成系の振動スペクトルとその有限要素法による近似理論(加古孝)。(3)狭い間隔をもつ同軸円筒管流のテイラー・クエット渦の数理解析と有限要素数値計算(海津聡)。(4)均質化理論による多孔質媒質における非線形固有値問題の取り扱い(海津聡)。(5)遅延微分方程式のルンゲ・クッタ法による数値解法とその代数的安定性の有効性の確立(小藤俊幸)。(6)グラフの全域木を列挙する効率的方法の開発(田村明久)。(7)組み合わせ最適化問題における実行可能多面体のフェイス構造(田村明久)。(8)交互境界条件法による領域分割計算法(竹田辰興、福原誠)。 3.電気通信大学数値解析研究会の継続開催 本年度15回にわたっておおむね金曜午前に実施し、2月9日には、応隆安北京大教授を囲む特別研究会、3月1日には一日研究会「陽春謳歌の会社」をそれぞれ開催した。

研究実績内容は各分担について以下の通りである: (1)山口耕平:最近話題となっている(ラベル付き)Configuration-空間のトポロジーを調べることを第1の目標とした。とくにArnold達によって研究されてきた,(ラベル付きConfiguration-空間の典型例のひとつである)次数d重複度がn未満の複素係数多項式の空間SP^d_n(C)のトポロジーの研究によりそれまでの結果を含む一般的な結果を得た。(これに関しては論文準備中であり,今春の日本数学会の特別講演で講演予定である。)またこれに関連して,F.Cohen,R.CohenやVassiliev達のこれらの空間に関する安定ホモトピー型に関する結果の別証明も得られた。(それについても論文準備中である。)さらにそれに類似した結果として複素係数有利関数の空間に関する結果も類似の方法で得られた。(これについては論文投稿中である。)またそのために必要となる向き付きConfiguration-空間のトポロジーに関する結果も得られた。(これについての論文が今年中に発行される予定である。)最後に,これらに関連して特異点論の研究および数式処理の研究も行った。 (2)内藤敏機:バナッハ空間上で無限の送れを持つ場合の線形関数微分方程式の研究を行った。とくに,その解半群のスペクトル分解が成立することを一般的の場合で証明した。またその具体例を一般に調べそれらの解の安定性を調べた。 (3)大久保謙二郎:常微分方程式の研究とそれに関する数式処理の研究を行った。とくに数式処理の工学的応用および教育的応用の研究も行った。

1.前年度に開発した無交差ラーマングラフをすべて列挙するアルゴリズムにおいて、実用的な観点から、出力されるグラフのクラスに制限を課した列挙アルゴリズムを開発した。一つは最大次数の上限が与えられている場合で、もう一つはあらかじめ辺集合を指定し、それらを含まないグラフに限定するものである。これらは、いずれも計算困難であることが予想されるが、実用的なアルゴリズムを開発した。 2.逆探索法によって列挙された静定構造物(ラーマングラフ)に対して,節点座標と部材断面積を連続変数として,指定された性能(大変形挙動)を満たすコンプライアントメカニズムを求めた。また,節点数と計算量の関係を検討し,最適な解を求める際の計算量限界を明らかにした。 3.無交差全域木の高速列挙アルゴリズムを開発した。その計算時間の理論的性能評価とともに、計算機実験をおこない、その実用的な性能を評価した。 4.火災等の発生時における建物内部から安全な外部への最適避難経路(最大移動時間最小化問題)や、津波や大地震発生時に安全な建物・地域への最適避難経路を求める問題を考察した。実用的な観点から、格子状ネットワーク、木構造ネットワークに限定し、通路幅一定、途中での枝分かれを許さない、経路が交差しない等の制約下での最適経路群を求めた。またGISや実データを利用し、通行可能経路が確率的に定まるような実際的な問題への導入も検討した。 5.LRTなどを模した線的施設配置問題について研究した。駅と線路からなる平面上の全域木において、利用者の総移動時間を最小化するような、ネットワークのトポロジーを求めるヒューリスティクスを開発した。

(1) Interior point algorithms for linoar programs and linear complementarity problems. Interior point algorithms first proposed in 1984 by N. Karmarkar turned out to be the most efficient algorithms for solving large scale linear programs and linear complementarity problems. We tried to improve and polish this algorithm and obtained several new results. Some of the more important ones are ; development of the algorithm whose number of iteration is a cubic function of the number of variables ; development of primal-dual interior point algorithm ; construction of the unified theoretical framework of the interior point algorithms and the extension of the interior point algorithms to nonlinear complementarity problems. (2) Global minimization of a class of nonconvex functions over a polytope. The starting point of this research was our discovery of parametric linear programming algorithm for linear multiplicative programming problem which took place in 1989. Since then we tried to extend it to diverse classes of nonconvex minimization problems such as (a) (generalized) convex multiplicative programming problems, (b) minimization of a sum (and a product) of two linear fractional functions (c) convex minimization under linear multiplicative constraints (d) minimization of a product of p convex functions (e) minimization of rank two and rank three bilinear programming problems (f) minimum cost lot-sizing problem with rho-concave cost functions. All of these problems can now be solved effectively by our algorithms. (3) Financial optimization problems. We proposed two new models in the field of portfolio optimization. One is the MAD model in which the absolute deviation is used as a measure of risk instead of the standard deviation. Second is the MADS model which enables the quantitative treatment of the third moment. In addition, we developed a unified framework for the multi-period portfolio-dividend optimization problems. We can now solve a large scale problem of this class which could not have been solved by existing methods.

The research on ergodic theory has had a strong relation to the theory of numbers even from the beginning until now. In particular, there are a number of open questions in the theory of binary, decimal, and continued fraction expansions. On the other hand, there are also new open questions concerning the theory of cryptography and the communication theory. In the present research, we mainly study the approximation theory of continued fractions with its speed of the convergence and also study the probabilistic estimate of the calculation costs of the Euclidean algorithms. We have some new results concerning these problems as well as other related subjects as the theory of uniform distributions.

From a given graph G, a graph obtained from a subgraph of G by contracting several edges is called a minor of G. Some important classes of graphs, such as planar graphs are closed under the operation taking a minor, and are characterized by forbidden minors. In this research, we extend some results of planar graphs concerning cycles, spanning trees and factors, from the point of view of forbidden minors. In particular, we obtained some results on the toughness and the spanning trees in graphs without complete bipartite minors. We also considered similar problems on the forbidden induced subgraphs.

We developed a theoretical framework for auctions in two-sided markets, where both buyers and sellers act strategically under realistic constraints such as budget constraints and indivisible goods. Specifically, we extended the polyhedral clinching auction to handle indivisible goods and provided efficiency guarantees based on various measures. Furthermore, we established a theoretical foundation for budget-constrained auctions in social networks. Our work has resulted in publications in TEAC and AAMAS, leading venues for algorithmic game theory.

In this project, four research groups, i.e., two-sided matching, auction, AI/optimization, behavioral/experimental economics, conducted research in a close collaboration. Within the project period, we have published 40 papers, performed 45 presentations (including 13 invited talks). In particular, we conducted research on following topics: constrained two-sided matching, auctions on social networks, distributed constraint optimization, max satisfiablity problems against adversary, new group decision making procedure called majority judgment. For these topics, we have obtained various research results, which are published in top international conferences and international journals.

The aims of this research are to deeply study discrete allocation problems with hard constraints by using discrete convex analysis, and to apply theoretical results to problems in the real world. We established five research themes and obtain theoretical results for each theme. On feedback to problems in the real world, we developed software of our two proposed algorithms which have been used to solve the allocation problem of students to departments in our affiliation.

In this project, we conducted theoretical researches on general market design. We published 32 articles in international journals and 33 papers from proceedings of international conferences, and 18 invited talks. We also conducted 14 international joint researches in total. During the project, PI and Co-PIs have received several community/conference awards, including the Commendation for Science and Technology by MEXT.

Major research results we obtained are the following : 1. We proposed efficient algorithms for source location, problems with flow requirement, which was based on the submodularity of cut functions of the underlying flow network. 2. We presented new algorithms for maximum matchings in regular bipartite graphs and for maximum flows in directed networks by means of maximum-adjacency ordering. 3. We showed a new approach to submodular function minimization problem presenting an O(n^2) algorithm using the membership oracle for base polyhedra. 4. We revealed the equivalence between discrete convexity and the gross substitutes condition in economics, and using discrete concave utility functions, we extended the concept of stable marriage due to Gale and Shapley and showed the existence of stable solutions algorithmically. 5. We introduced the concept of polybasic polyhedron by generalizing that of base polyhedron, a fundamental submodularity structure, which lead us to a new general framework for polyhedral structure of submodularity. 6. We presented a sequential pseudo-polynomial algorithm for enumerating minimal integral solutions of monotone linear systems. 7. We showed the hardness of enumerating maximal frequent sets and the polynomial-time solvability of enumerating minimal non-frequent sets.

Major results of our research are the following. 1. By utilizing discrete concave functions and considering possibly bounded side payments, we have established a common generalization of the marriage model due to Gale and Shapley and the assignment model due to Shapley and Shubik that are standard in the theory of two-sided matching markets, and have shown the existence of a pairwise stable outcome in our model. 2. We have presented a first polynomial-time algorithm for the monotone min-max connected partitioning problem and have shown that the min-max connected partitioning problem is NP-hard if the cost function is not monotone, and that the min-sum connected partitioning problem is NP-hard even if the cost function is monotone. We also considered an evacuation problem in dynamic networks as an application of the tree partitioning problem. 3. Bisubmodular functions are a natural "directed", or "signed", extension of submodular functions with several applications. We have investigated the difficulty of extending the strongly polynomial version of the ordinary submodular function minimization algorithms to bisubmodular function minimization (BSFM), and we have showen a way around the difficulty. This new method gives the first combinatorial strongly polynomial algorithm for BSFM. 4. We have considered minimum-cost source-location problems and their generalizations with three connectivity requirements (arc-connectivity requirements and two kinds of vertex-connectivity requirements), and have shown that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard. Moreover, we have shown that the source location problems with three connectivity requirements are inapproximable within a ratio of c In D for some constant c, unless every problem in NP has an O (N log^2 N) -time deterministic algorithm. Here D denotes the sum of given demands. We have also devised (1+ In D) -approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions. 5. We have investigated support vector machine (SVM) with a discrete kernel, named electric network kernel, mined on the vertex set of an undirected graph. Emphasis is laid on mathematical analysis of its theoretical properties with the aid of electric network theory and the theory of discrete metrics. SVM with this kernel admits physical interpretations in terms of resistive eletric networks; in particular, the SVM decision function corresponds to an electric potential. 6. We nave considered a problem of finding a minimum transversal that can be regarded as a natural generalization of source location problems and external network problems in (undirected) graphs and hypergraphs. We have found an interesting structural characterization of minimal deficient sets and have shown a necessary and sufficient condition for such sets to form a tree hypergraph. By using this characterization, we have obtained a polynomial-time algorithm, which provides first polynomial-time algorithms for source location problem in hypergraphs and external network problems in graphs and hypergraphs.

In the area of nonlinear programming, the theory of convex analysis provides a unified framework for well-solved problems. In the area of discrete optimization, on the other hand, we do not have such a unified framework. Matroidal structure, however, is known to be a well-behaved structure in discrete optimization. The theory of "discrete convex analysis" is proposed by the head investigator with a view to capturing the continuous optimization and the discrete optimization from a common viewpoint. Discrete convex analysis is a theoretical framework connecting the theory of convex analysis and the theory of matroids. It is often the case that discrete optimization problems appearing in the real world do not have nice combinatorial structure such as matroids. Therefore, we need to use enumeration-type algorithms such as the branch-and-bound method or approximation algorithms such as meta heuristics. In either approach, it is essential to extract tractable part from the discrete structure of the problems to be solved. For example, it is often effective to extract network-like structure as subproblems when we solve general discrete optimization problems. The fundamental idea of our research is to extract certain structure which can be dealt with discrete convex analysis as subproblems when we solve general discrete optimization problems. We summarize the main results as follows : ・The concepts of M-convex and L-convex functions play a central role in the framework of discrete convex analysis. We showed various properties of these functions. ・We proposed efficient algorithms for the minimization of M-convex functions. ・We extended the concepts of M-convex and L-convex functions defined over the integer lattice to functions over the real space. ・We generalized the concepts of M-convex and L-convex functions to quasi M-convex/L-convex functions. ・We obtained some results on the application of discrete convex analysis to economic equilibrium such as the equivalence of gross substitutes property and M-convexity.