【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】一般研究(C)

【研究期間】1995

【研究代表者】水野 眞治 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 数理計算法 / 線形計画問題 / 内点法 / 線形方程式

【概要】最適化問題を解く内点法についての基礎的な研究を行った。とくに、アルゴリズムの理論的な収束性について研究した。 線形計画問題を解く内点法には、多項式オーダーで収束するアルゴリズムが数多く提案されているが、その中でも係数行列のみに依存した数で反復回数がおさえられる新しいタイプのアルゴリズムが、VavasisとYeにより最近発表された。このアルゴリズムは、優れた収束性を備えているが、理論的に定義されてい...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2015-04-01 - 2018-03-31

【研究代表者】北原 知就 東京工業大学, 工学院, 助教 (10551260)

【キーワード】単体法 / 線形計画問題 / 多項式アルゴリズム / 線形計画法 / 強多項式アルゴリズム

【概要】研究期間全体を通じた主な研究成果は次の通りである。（a)単体法に対する実用的なピボット規則である、最急辺降下規則について研究し、反復回数の理論的上界を初めて得ることができた。（b) 線形計画問題に対するLP-Newton法に二分探索法を組み込んだ新しい方法を提案した。提案手法を解析し、反復回数についての理論的示唆を得ることができた。（c) 線形計画問題に対する新しい解法であるChuvanovのアル...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2017-04-01 - 2023-03-31

【研究代表者】澄田 範奈 東京工業大学, 情報理工学院, 講師 (10761356)

【キーワード】オンラインマッチング / 線形相補性問題 / 公平割当 / 線形計画問題 / アルゴリズム (他8件)

【概要】本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2017-04-01 - 2023-03-31

【研究代表者】澄田 範奈 東京工業大学, 情報理工学院, 講師 (10761356)

【キーワード】オンラインマッチング / 線形相補性問題 / 公平割当 / 線形計画問題 / アルゴリズム (他8件)

【概要】本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】1996 - 1998

【研究代表者】水野 眞治 (水野 真治) 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 社会システム / 内点法 / 線形計画問題 / 半正定値計画問題 (他6件)

【概要】社会システムにおける最適化問題を解く内点法についての基礎的な研究を平成8年度より引き続き行った。今年度は、社会システムによく現れる線形計画問題と半正定値計画問題を解く内点法の開発とその大域的収束性と局所的収束性について重点的に研究した。 社会システムにおける最適化問題の多くは、数理計画問題としてモデル化することができる。最も基本的な数理計画問題は、線形計画問題である。線形計画問題を解く内点法につい...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2015-04-01 - 2018-03-31

【研究代表者】北原 知就 東京工業大学, 工学院, 助教 (10551260)

【キーワード】単体法 / 線形計画問題 / 多項式アルゴリズム / 線形計画法 / 強多項式アルゴリズム

【概要】研究期間全体を通じた主な研究成果は次の通りである。（a)単体法に対する実用的なピボット規則である、最急辺降下規則について研究し、反復回数の理論的上界を初めて得ることができた。（b) 線形計画問題に対するLP-Newton法に二分探索法を組み込んだ新しい方法を提案した。提案手法を解析し、反復回数についての理論的示唆を得ることができた。（c) 線形計画問題に対する新しい解法であるChuvanovのアル...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2017-04-01 - 2023-03-31

【研究代表者】澄田 範奈 東京工業大学, 情報理工学院, 講師 (10761356)

【キーワード】オンラインマッチング / 線形相補性問題 / 公平割当 / 線形計画問題 / アルゴリズム (他8件)

【概要】本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2015-04-01 - 2018-03-31

【研究代表者】北原 知就 東京工業大学, 工学院, 助教 (10551260)

【キーワード】単体法 / 線形計画問題 / 多項式アルゴリズム / 線形計画法 / 強多項式アルゴリズム

【概要】研究期間全体を通じた主な研究成果は次の通りである。（a)単体法に対する実用的なピボット規則である、最急辺降下規則について研究し、反復回数の理論的上界を初めて得ることができた。（b) 線形計画問題に対するLP-Newton法に二分探索法を組み込んだ新しい方法を提案した。提案手法を解析し、反復回数についての理論的示唆を得ることができた。（c) 線形計画問題に対する新しい解法であるChuvanovのアル...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】2000 - 2002

【研究代表者】水野 眞治 (水野 真治) 東京工業大学, 大学院・社会理工学研究科, 教授 (90174036)

【キーワード】最適化 / アルゴリズム / 内点法 / 線形計画問題 / 最適化問題

【概要】本研究は、大規模な数理計画問題を効率よく解くアルゴリズムを開発し、その理論的な性質と実用性を明らかにすることを目的としている。平成12年度には、そのための基礎的な研究を行った。大規模な数理計画問題では、問題に含まれる変数に自由変数、非負変数、上下限制約付きの変数の3種類がある。これらの変数を同時に、そのまま処理することが、問題を効率よく解く上で重要である。そこで、このような問題を直接解く内点法によ...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】1996 - 1998

【研究代表者】水野 眞治 (水野 真治) 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 社会システム / 内点法 / 線形計画問題 / 半正定値計画問題 (他6件)

【概要】社会システムにおける最適化問題を解く内点法についての基礎的な研究を平成8年度より引き続き行った。今年度は、社会システムによく現れる線形計画問題と半正定値計画問題を解く内点法の開発とその大域的収束性と局所的収束性について重点的に研究した。 社会システムにおける最適化問題の多くは、数理計画問題としてモデル化することができる。最も基本的な数理計画問題は、線形計画問題である。線形計画問題を解く内点法につい...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】一般研究(C)

【研究期間】1995

【研究代表者】水野 眞治 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 数理計算法 / 線形計画問題 / 内点法 / 線形方程式

【概要】最適化問題を解く内点法についての基礎的な研究を行った。とくに、アルゴリズムの理論的な収束性について研究した。 線形計画問題を解く内点法には、多項式オーダーで収束するアルゴリズムが数多く提案されているが、その中でも係数行列のみに依存した数で反復回数がおさえられる新しいタイプのアルゴリズムが、VavasisとYeにより最近発表された。このアルゴリズムは、優れた収束性を備えているが、理論的に定義されてい...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2017-04-01 - 2023-03-31

【研究代表者】澄田 範奈 東京工業大学, 情報理工学院, 講師 (10761356)

【キーワード】オンラインマッチング / 線形相補性問題 / 公平割当 / 線形計画問題 / アルゴリズム (他8件)

【概要】本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】2000 - 2002

【研究代表者】水野 眞治 (水野 真治) 東京工業大学, 大学院・社会理工学研究科, 教授 (90174036)

【キーワード】最適化 / アルゴリズム / 内点法 / 線形計画問題 / 最適化問題

【概要】本研究は、大規模な数理計画問題を効率よく解くアルゴリズムを開発し、その理論的な性質と実用性を明らかにすることを目的としている。平成12年度には、そのための基礎的な研究を行った。大規模な数理計画問題では、問題に含まれる変数に自由変数、非負変数、上下限制約付きの変数の3種類がある。これらの変数を同時に、そのまま処理することが、問題を効率よく解く上で重要である。そこで、このような問題を直接解く内点法によ...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2017-04-01 - 2023-03-31

【研究代表者】澄田 範奈 東京工業大学, 情報理工学院, 講師 (10761356)

【キーワード】オンラインマッチング / 線形相補性問題 / 公平割当 / 線形計画問題 / アルゴリズム (他8件)

【概要】本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1994

【研究代表者】小島 政和 東京工業大学, 大学院・情報処理工学研究科, 教授 (90092551)

【キーワード】線形計画問題 / 内点法 / カ-マーカー法 / 数理計画問題 / 組み合せ最適化 (他6件)

【概要】本研究の目的「より一般的で広範な数理計画問題を解く計算手法を開発する」に沿って、以下の研究を行った。 1.研究代表者の小島等のグループが開発した大規模な線形計画問題の高速解法である主双対内点法を半正定値計画問題(Semidefinite Program)に拡張し、その理論的基礎を築いた。半正定値計画問題はシステムと制御、組み合わせ最適化、統計等に広い応用がある。 2.線形計画問題、半正定値計画問題...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1992

【研究代表者】小島 政和 東京工業大学, 理学部, 教授 (90092551)

【キーワード】線形計画問題 / 内点法 / カーマーカー法 / 数理計画問題 / 組み合せ最適化 (他6件)

【概要】平成3年度および4年度に計画した研究目標は以下通りであった。 1.主双対内点法の計算効率の向上および評価に関する基礎研究。 2.非凸型2次計画問題および組合せ最適化問題への内点法の適用に関する基礎研究。 3.内点法を中心とする線形計画法のソフトウェアに関する基礎研究。 4.内点法の一般化に関する基礎研究。 研究目標1に関しては, (1)内点法の各反復でのステップ長をコントロールする新手法の提案, ...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1994

【研究代表者】小島 政和 東京工業大学, 大学院・情報処理工学研究科, 教授 (90092551)

【キーワード】線形計画問題 / 内点法 / カ-マーカー法 / 数理計画問題 / 組み合せ最適化 (他6件)

【概要】本研究の目的「より一般的で広範な数理計画問題を解く計算手法を開発する」に沿って、以下の研究を行った。 1.研究代表者の小島等のグループが開発した大規模な線形計画問題の高速解法である主双対内点法を半正定値計画問題(Semidefinite Program)に拡張し、その理論的基礎を築いた。半正定値計画問題はシステムと制御、組み合わせ最適化、統計等に広い応用がある。 2.線形計画問題、半正定値計画問題...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1992

【研究代表者】小島 政和 東京工業大学, 理学部, 教授 (90092551)

【キーワード】線形計画問題 / 内点法 / カーマーカー法 / 数理計画問題 / 組み合せ最適化 (他6件)

【概要】平成3年度および4年度に計画した研究目標は以下通りであった。 1.主双対内点法の計算効率の向上および評価に関する基礎研究。 2.非凸型2次計画問題および組合せ最適化問題への内点法の適用に関する基礎研究。 3.内点法を中心とする線形計画法のソフトウェアに関する基礎研究。 4.内点法の一般化に関する基礎研究。 研究目標1に関しては, (1)内点法の各反復でのステップ長をコントロールする新手法の提案, ...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】1996 - 1998

【研究代表者】水野 眞治 (水野 真治) 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 社会システム / 内点法 / 線形計画問題 / 半正定値計画問題 (他6件)

【概要】社会システムにおける最適化問題を解く内点法についての基礎的な研究を平成8年度より引き続き行った。今年度は、社会システムによく現れる線形計画問題と半正定値計画問題を解く内点法の開発とその大域的収束性と局所的収束性について重点的に研究した。 社会システムにおける最適化問題の多くは、数理計画問題としてモデル化することができる。最も基本的な数理計画問題は、線形計画問題である。線形計画問題を解く内点法につい...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1994

【研究代表者】小島 政和 東京工業大学, 大学院・情報処理工学研究科, 教授 (90092551)

【キーワード】線形計画問題 / 内点法 / カ-マーカー法 / 数理計画問題 / 組み合せ最適化 (他6件)

【概要】本研究の目的「より一般的で広範な数理計画問題を解く計算手法を開発する」に沿って、以下の研究を行った。 1.研究代表者の小島等のグループが開発した大規模な線形計画問題の高速解法である主双対内点法を半正定値計画問題(Semidefinite Program)に拡張し、その理論的基礎を築いた。半正定値計画問題はシステムと制御、組み合わせ最適化、統計等に広い応用がある。 2.線形計画問題、半正定値計画問題...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1994

【研究代表者】小島 政和 東京工業大学, 大学院・情報処理工学研究科, 教授 (90092551)

【キーワード】線形計画問題 / 内点法 / カ-マーカー法 / 数理計画問題 / 組み合せ最適化 (他6件)

【概要】本研究の目的「より一般的で広範な数理計画問題を解く計算手法を開発する」に沿って、以下の研究を行った。 1.研究代表者の小島等のグループが開発した大規模な線形計画問題の高速解法である主双対内点法を半正定値計画問題(Semidefinite Program)に拡張し、その理論的基礎を築いた。半正定値計画問題はシステムと制御、組み合わせ最適化、統計等に広い応用がある。 2.線形計画問題、半正定値計画問題...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1992

【研究代表者】小島 政和 東京工業大学, 理学部, 教授 (90092551)

【キーワード】線形計画問題 / 内点法 / カーマーカー法 / 数理計画問題 / 組み合せ最適化 (他6件)

【概要】平成3年度および4年度に計画した研究目標は以下通りであった。 1.主双対内点法の計算効率の向上および評価に関する基礎研究。 2.非凸型2次計画問題および組合せ最適化問題への内点法の適用に関する基礎研究。 3.内点法を中心とする線形計画法のソフトウェアに関する基礎研究。 4.内点法の一般化に関する基礎研究。 研究目標1に関しては, (1)内点法の各反復でのステップ長をコントロールする新手法の提案, ...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】1996 - 1998

【研究代表者】水野 眞治 (水野 真治) 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 社会システム / 内点法 / 線形計画問題 / 半正定値計画問題 (他6件)

【概要】社会システムにおける最適化問題を解く内点法についての基礎的な研究を平成8年度より引き続き行った。今年度は、社会システムによく現れる線形計画問題と半正定値計画問題を解く内点法の開発とその大域的収束性と局所的収束性について重点的に研究した。 社会システムにおける最適化問題の多くは、数理計画問題としてモデル化することができる。最も基本的な数理計画問題は、線形計画問題である。線形計画問題を解く内点法につい...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】2000 - 2002

【研究代表者】水野 眞治 (水野 真治) 東京工業大学, 大学院・社会理工学研究科, 教授 (90174036)

【キーワード】最適化 / アルゴリズム / 内点法 / 線形計画問題 / 最適化問題

【概要】本研究は、大規模な数理計画問題を効率よく解くアルゴリズムを開発し、その理論的な性質と実用性を明らかにすることを目的としている。平成12年度には、そのための基礎的な研究を行った。大規模な数理計画問題では、問題に含まれる変数に自由変数、非負変数、上下限制約付きの変数の3種類がある。これらの変数を同時に、そのまま処理することが、問題を効率よく解く上で重要である。そこで、このような問題を直接解く内点法によ...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】1996 - 1998

【研究代表者】水野 眞治 (水野 真治) 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 社会システム / 内点法 / 線形計画問題 / 半正定値計画問題 (他6件)

【概要】社会システムにおける最適化問題を解く内点法についての基礎的な研究を平成8年度より引き続き行った。今年度は、社会システムによく現れる線形計画問題と半正定値計画問題を解く内点法の開発とその大域的収束性と局所的収束性について重点的に研究した。 社会システムにおける最適化問題の多くは、数理計画問題としてモデル化することができる。最も基本的な数理計画問題は、線形計画問題である。線形計画問題を解く内点法につい...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】一般研究(C)

【研究期間】1995

【研究代表者】水野 眞治 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 数理計算法 / 線形計画問題 / 内点法 / 線形方程式

【概要】最適化問題を解く内点法についての基礎的な研究を行った。とくに、アルゴリズムの理論的な収束性について研究した。 線形計画問題を解く内点法には、多項式オーダーで収束するアルゴリズムが数多く提案されているが、その中でも係数行列のみに依存した数で反復回数がおさえられる新しいタイプのアルゴリズムが、VavasisとYeにより最近発表された。このアルゴリズムは、優れた収束性を備えているが、理論的に定義されてい...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2017-04-01 - 2023-03-31

【研究代表者】澄田 範奈 東京工業大学, 情報理工学院, 講師 (10761356)

【キーワード】オンラインマッチング / 線形相補性問題 / 公平割当 / 線形計画問題 / アルゴリズム (他8件)

【概要】本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】一般研究(C)

【研究期間】1995

【研究代表者】水野 眞治 統計数理研究所, 予測制御研究系, 助教授 (90174036)

【キーワード】最適化 / 数理計算法 / 線形計画問題 / 内点法 / 線形方程式

【概要】最適化問題を解く内点法についての基礎的な研究を行った。とくに、アルゴリズムの理論的な収束性について研究した。 線形計画問題を解く内点法には、多項式オーダーで収束するアルゴリズムが数多く提案されているが、その中でも係数行列のみに依存した数で反復回数がおさえられる新しいタイプのアルゴリズムが、VavasisとYeにより最近発表された。このアルゴリズムは、優れた収束性を備えているが、理論的に定義されてい...

【研究テーマ】社会システム工学

【研究種目】基盤研究(C)

【研究期間】2000 - 2002

【研究代表者】水野 眞治 (水野 真治) 東京工業大学, 大学院・社会理工学研究科, 教授 (90174036)

【キーワード】最適化 / アルゴリズム / 内点法 / 線形計画問題 / 最適化問題

【概要】本研究は、大規模な数理計画問題を効率よく解くアルゴリズムを開発し、その理論的な性質と実用性を明らかにすることを目的としている。平成12年度には、そのための基礎的な研究を行った。大規模な数理計画問題では、問題に含まれる変数に自由変数、非負変数、上下限制約付きの変数の3種類がある。これらの変数を同時に、そのまま処理することが、問題を効率よく解く上で重要である。そこで、このような問題を直接解く内点法によ...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2015-04-01 - 2018-03-31

【研究代表者】北原 知就 東京工業大学, 工学院, 助教 (10551260)

【キーワード】単体法 / 線形計画問題 / 多項式アルゴリズム / 線形計画法 / 強多項式アルゴリズム

【概要】研究期間全体を通じた主な研究成果は次の通りである。（a)単体法に対する実用的なピボット規則である、最急辺降下規則について研究し、反復回数の理論的上界を初めて得ることができた。（b) 線形計画問題に対するLP-Newton法に二分探索法を組み込んだ新しい方法を提案した。提案手法を解析し、反復回数についての理論的示唆を得ることができた。（c) 線形計画問題に対する新しい解法であるChuvanovのアル...

【研究テーマ】数理情報学

【研究種目】若手研究(B)

【研究期間】2017-04-01 - 2023-03-31

【研究代表者】澄田 範奈 東京工業大学, 情報理工学院, 講師 (10761356)

【キーワード】オンラインマッチング / 線形相補性問題 / 公平割当 / 線形計画問題 / アルゴリズム (他8件)

【概要】本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような...